Проектиране и анализ на компютърни алгоритми – 1 част
Едносеместриален изборен курс (0+0+5) за учебната 2003/2004 г. за студенти от ФМИ на СУ
Преподавателски екип:
е-mail:
е-mail:
е-mail:
Анотация:
Курсът "Проектиране и анализ на компютърни алгоритми" има за цел да запознае студентите с някои от най-използваните в практиката алгоритмични техники. Наред с представянето на широко известни методи за решаване на алгоритмични задачи (и анализ на техните свойства, приложения, предимства и недостатъци), се разглеждат и множество конкретни алгоритмични проблеми, обръща се внимание на анализа на сложността на предложените решения, прави се сравнение между различни подходи за решение. В курса се засяга широк спектър от теми, както в теоретичен, така и в чисто приложен аспект: Алгоритми от теорията на числата, структури от данни, търсене и сортиране, алгоритми от теорията на графите, динамично оптимиране, разделяй и владей, алчни и вероятностни алгоритми, компресиране. Курсът е ориентиран към приложната страна и реализацията на разглежданите алгоритми, за сметка на чисто теоретични изследвания и доказателства за коректност.
Course Description:
This course objective is to introduce the students to the design and analysis of algorithms for some of the most frequently encountered computational problems. The course aims to provide familiarity with general algorithmic techniques, performance measures, and problem areas – a knowledge that anyone conducting research in computer science should have. General topics to be covered include: simple numerical algorithms, fundamental data structures, sorting and searching, graph searching and graph algorithms, dynamic programming, divide and conquer, NP-completeness, greedy and approximation algorithms as well as compression techniques.
Изисквания към студентите:
Необходими са начални познания по структури от данни и програмиране на C/C++.
Изпити и оценки:
Учебни занятия:
вторник, 19-21 часа, зала 325 на ФМИ
четвъртък, 18-21 часа, зала 325 на ФМИ
Първа сбирка:
7 октомври (вторник) от 18 ч. в зала 325 на ФМИ
За повече информация:
Учебна програма:
1. Въведение в алгоритмите
1.1. Алгоритми от теорията на числата. Прости числа. Бройни системи и преобразуване
1.2. Рекурсия и итерация. Примери
1.3. Основни комбинаторни алгоритми. Пермутации. Вариации. Комбинации. Генериране и кодиране
1.4. Сложност на алгоритми. Асимптотична нотация. Определяне на сложност на алгоритъм
2. Въведение в структурите от данни
2.1. Списък, стек, опашка. Последователна и свързана реализация
2.2. Двоични дървета. Търсене по ключ, добавяне, изтриване, обхождане
2.3. Балансирани дървета. Ротация. Червено-черни дървета. B-дървета
2.4. Хеш-таблици. Хеш-функции. Колизии
3. Алгоритми за сортиране
3.1. Сортиране чрез сравнение. Сортиране чрез вмъкване. Алгоритъм на Шел. Метод на мехурчето. Сортиране чрез клатене. Бързо сортиране на Хоор. Метод на “зайците и костенурките”. Сортиране чрез пряк избор. Пирамидално сортиране на Уилямс
3.2. Сортиране чрез трансформация. Сортиране чрез множество. Сортиране чрез броене. Побитово сортиране. Метод на бройните системи. Сортиране чрез пермутация
3.3. Паралелно сортиране
4. Алгоритми за търсене
4.1. Последователно търсене. Търсене с преподреждане
4.2. Търсене със стъпка. Квадратично търсене
4.3. Двоично търсене
4.4. Интерполационно търсене
5. Алгоритми от теорията на графите
5.1. Основни понятия. Представяне и прости операции с граф
5.2. Обхождане на граф. Обхождане в ширина. Обхождане в дълбочина
5.3. Оптимални пътища, цикли и потоци в граф
5.3.1. Екстремален път в граф. Алгоритъм на Форд-Белман. Алгоритъм на Флойд. Алгоритъм на Дейкстра. Най-дълъг път в ацикличен граф.
5.3.2. Цикли. Намиране на фундаментално множество от цикли. Минимален цикъл през връх
5.3.3. Хамилтонови цикли. Задача за търговския пътник
5.3.4. Ойлерови цикли
5.3.5. Потоци. Максимален поток. Повече от един източник и консуматор. Капацитет на върховете
5.4. Транзитивност и построяване. Топологично сортиране. Транзитивно затваряне. Алгоритъм на Уоршал. Построяване на граф по дадени степени на върховете
5.5. Достижимост и свързаност. Компоненти на свързаност. Компоненти на силна свързаност в ориентиран граф. Разделящи точки в неориентиран граф. Двусвързаност. k-свързаност
5.6. Оптимални подмножества и центрове
5.6.1. Минимално покриващо дърво. Алгоритъм на Крускал. Алгоритъм на Прим
5.6.2. Независими множества. Доминиращи множества. База на граф
5.6.3. Център, радиус и диаметър. p-център и p-радиус
5.6.4. Двойкосъчетание. Максимално двойкосъчетание
5.7. Оцветявания и планарност. Оцветяване на граф. Хроматично число. Планарност на графи
6. Търсене с връщане. NP-пълни задачи
6.1. Класификация на задачите по време и по памет. Нерешими задачи. Примери
6.2. NP-пълни задачи. Удовлетворимост на булева функция
6.3. Търсене с връщане. Оцветяване на граф. Най-дълъг прост път в цикличен граф. Разходка на коня. Задача за осемте царици
6.4. Метод на разклоненията и границите. Задача за раницата (оптимална селекция)
6.5. Оптимални стратегии при игри. Мини-максна стратегия и алфа-бета отсичане
7. Разделяй и владей
7.1. Основни принципи
7.2. Намиране на k-ия по големина елемент. Мажорант. Сливане на сортирани масиви. Сортиране чрез сливане. Бързо повдигане в степен. Задача за Ханойските кули. Организиране на първенства. Циклично изместване на елементите на масив. Покриване с шаблон
8. Динамично оптимиране
8.1. Основни принципи
8.2. Класически оптимизационни задачи. Задача за раницата. Умножение на матрици. Триангулация на многоъгълник. Оптимално двоично дърво за претърсване. Най-дълга обща подредица. Най-дълга ненамаляваща подредица. Сравнение на символни низове. Задача за разделянето
8.3. Неоптимизационни задачи. Числа на Фибоначи. Биномни коефициенти. Спортни срещи. Представяне на сума с неограничен брой монети. Представяне на сума с ограничен брой монети. Разбиване на естествено число
8.4. Други интересни оптимизационни задачи. Такси компания. Билети за влак. Числов триъгълник. Представяне на сума с минимален брой монети. Опроводяване на платка. На опашка за билети. Разпределение на ресурси. Семинарна зала. Крайпътни дървета. Разрязване на материали. Зациклен израз. Домино-редица. Трионообразна редица
9. Евристични и вероятностни алгоритми
9.1. Алчни алгоритми. Египетски дроби. Максимално съчетание на дейности. Минимално оцветяване на граф и дърво. Алгоритми на Прим и Крускал. Дробна задача за раницата. Задача за магнитната лента. Разходката на коня. Хиперкуб. Код на Грей
9.2. Търсене с налучкване. Алгоритми Монте Карло и Лас Вегас. Проверка дали число е просто. Числени алгоритми с приближение. Генетични алгоритми
9.3. Достигане на фиксирано приближение. Върхово покритие на граф