Анотация

---

Дисциплината е ориентирана към фундаменталната подготовка на студентите от специалност “КСТ” в ТУ – Варна. Целта е да се формират у студентите знания и умения, позволяващи да създават коректни и ефективни алгоритми и програми. Разглеждат се такива основни теми, като:

• Свойства и оценка на сложност на алгоритми, анализ на ефективност и оптималност.
• Алгоритмични стратегии: “разделяй и владей”, backtracking, “частните цели” и т н.
• Теоретични аспекти на структурното програмиране. Доказателство за коректност на алгоритми.
• Рекурсивни функции. Рекурсия и итерации. Ефективност. Реализация
• Алгоритми за сортиране и търсене.
• Систематизация на основните структури от данни. Дефиниране на абстрактен тип данни (АТД). Статични АТД
• Линейни динамични структури данни: стек, опашка, дек, списък. Алгоритми за работа с тях.
• Нелинейни динамични структури данни: дърво, граф. Алгоритми за работа с тях.
• Алгоритми за сортиране и търсене.
• Хеширане. Методи за отстраняване на колизии.
• Други класове алгоритми: комбинаторни, вероятностни, геометрични, паралелни, генетични и др.

Дисциплината осигурява всички специални дисциплини от учебния план на специалността, използващи програмиране на алгоритмични езици от високо ниво и работа със структури от данни: “Обектно-ориентирано програмиране”, “Дискретни структури”, “Програмни системи”, “Компютърна графика и визуализация”, “Компютърни архитектури”, “Бази от данни” и др., както и дипломното проектиране.

Съдържание

---

Тема 1. Алгоритми
1.1. Свойства на алгоритмите.
1.2. Формални модели – машина на Тюринг, нормални алгоритми на Марков.
1.3. Теза на Чърч.
1.4. Сложност на алгоритмите. Оценка.
1.5. Анализ на алгоритмите. Ефективност. Оптималност.
1.6. Коректност на алгоритми.
Тема 2. Алгоритмични стратегии и методи в програмирането
2.1. Рекурсия. Механизъм, рекурсивни функции, рекурсия и итерации,
2.2. Структурно програмиране
2.3. Стратегии: “разделяй и владей”, backtracking, метод на “частните цели”, “клоновете и границите”, използване на евристики, алгоритми тип “greedy” и др.
2.4. Обектно-ориентирано и процедурно програмиране.
Тема 3. Структури от данни
3.1. Систематизация на основните структури от данни. Дефиниране на абстрактен тип данни (АТД). Статични АТД.
3.2. Линейни динамични АТД: стек, опашка, дек, списък. Основни алгоритми за работа.
3.3. Нелинейни АТД. Дървовидни структури. Двоични дървета. Подредени дървета. Балансирани (AVL) дървета. B-дървета. RB-дървета, 2-3 дървета, 2-3-4 дървета. Основни алгоритми.
3.4. Мрежови структури. АТД-граф. Основни дефиниции и алгоритми за работа. Алгоритми DSF и BSF. Алгоритми на Dijkstra, Ford-Belman, Floyd за търсене на минимални пътища. Суперпозиция. Транзитивно затваряне на ориентиран граф. Топологично сортиране в ацикличен граф.
Тема 4. Класове алгоритми
4.1. Алгоритми за сортиране: сортиране чрез включване (пряко включване, алгоритъм на Shell), чрез размяна (BUBBLESORT, QUICKSORT, алгоритъм на Betcher), чрез извличане (прост избор, избор от дърво, HEAPSORT и др.).
4.2. Алгоритми за търсене (линейно търсене, двоично търсене и др.)
4.3. Алгоритми за хеширане. Хеш-функции. Обработка на колизии.
4.4. Паралелни алгоритми.
4.5. Комбинаторни алгоритми.
4.6. Вероятности алгоритми.
4.7. Евристични алгоритми.
4.8. Генетични алгоритми.