Форум Поща Карта на сайта Търсене Връзки Контакти
Начало Обучение Дисциплини в учебните планове на специалностите Информатика (бакалавър) Учебен план Алгоритми и структури от данни    English
Факултет по математика и информатика - Алгоритми и структури от данни
Специалност
Форма на оценяване
Дисциплината
се води
Информатика (бакалавър) редовно обучение
изпит
 
Анотация
Курсът има за цел да запознае учащите се с основните понятия свързани с динамичните структури от данни и тяхното приложение. Особено внимание се отделя на методите за спецификация на съответните динамични АТД, на тяхното приложение и подходи при програмна реализация (логическо, приложно и реализационно ниво на описание). Изучават се АТД файл, линейните свързани динамични АТД списък, стек, опашка и др., както и нелинейните свързани динамични АТД дърво, двоично дърво, граф. Разглеждат се основните алгоритми за обработка на изучаваните АТД: добавяне, изключване, търсене на елемент, начини на обхождане, реструктуриране с цел ефективност на обработката и сортиране. Втори основен акцент в курса е представяне на някои основни алгоритми с широко приложение (к омбинаторни алгоритми и алгоритми при транслация ) и на общи подходи при съставяне на алгоритми ( динамично програмиране и търсене с връщане назад). Упражненията илюстрират лекционния материал и са предназначени за практическо усвояване на изучаваните понятия чрез програмиране на MS Visual C++.
 
Съдържание
  1. АТД файл в ЕП (последователности) – основни понятия, достъп и конструиране, приложение. Реализация в ЕП – синтаксис за деклариране, множество от стойности, операции, примери.
  2. Основни алгоритми за обработка на файлове – търсене, добавяне, актуализация и изключване на елементи, сортиране на файлове.
  3. Комбинаторни алгоритми – променлив брой вложени цикли, пермутации, комбинации, вариации.
  4. Динамични свързани структури от данни – определение, видове (линейни и нелинейни), приложение, примери. Нива на описание на съответните АТД (логическо, приложно и реализационно).
  5. Спецификации на АТД за динамични свързани структури от данни (логическо ниво на описание). Категории операции за обработка на динамични АТД (конструктори, трансформатори, наблюдатели, итератори). Задаване на синтаксиса на АТД (и на неговите операции) чрез сигнатурите на операциите. Начини за определянето на семантиката на АТД.
  6. АТД списък, основни понятия, основни операции (обхождане, добавяне и изключване на елемент, търсене и сортиране), приложение, примери. Логическо, приложно и реализационно описание. Основни алгоритми за обработка на списъци.
  7. АТД стек, основни понятия, основни операции (обхождане, добавяне и изключване на елемент, търсене и сортиране), приложение, примери. Логическо, приложно и реализационно описание. Основни алгоритми за обработка на стекове
  8. АТД опашка, основни понятия, основни операции (обхождане, добавяне и изключване на елемент, търсене и сортиране), приложение, примери. Логическо, приложно и реализационно описание. Основни алгоритми за обработка на опашки.
  9. Основни алгоритми при транслация – синтактичен анализ и изчисляване на аритметичен израз в произволна алгебрична система. Преобразуване от инфиксен в постфиксен запис (обратен полски запис).
  10. АТД дърво, основни понятия, основни операции, приложение, примери. Двоични дървета, балансирани двоични дървета – AVL дървета. N-арни дървета – 2-3 дървета, B-дървета. Основни операции (обхождане, добавяне и изключване на елемент, търсене). Логическо, приложно и реализационно описание. Основни алгоритми за обработка на дървета.
  11. АТД граф, основни понятия, представяния на графи, основни операции (обхождане, добавяне и изключване на елемент, търсене), приложение, примери. Ориентирани и неориентирани графи. Логическо, приложно и реализационно описание. Основни алгоритми за обработка на графи – топологично сортиране, откриване на цикли, метод на критичния път.
  12. Други общи подходи при съставяне на алгоритми: динамично програмиране и търсене с връщане назад (backtracking).
Актуално
Още новини
Архив на новините
© 2009 ФМИ