CSCB039 Алгоритми и програмиране
Анотация:
Курсът е изключително важен за подготовката на всеки специалист в областта на Информатиката и Информационните технологии. В рамките на този курс се осъществява интегрирането на знанията и уменията от курсовете по Програмиране и Структури от данни. Курсът включва както фундаментални теоретични знания, така и знания, които имат пряко приложение в програмистката практика. От теоретична гледна точка студентите ще се запознаят с различни формализми за приближаване на неформалното понятие алгоритъм, с понятията за сложност по време и памет и техниките за оценяване на сложността на алгоритми, с оценка на асимптотичното поведение на функциите на сложност, с някои популярни алгоритмични схеми, както и с най-голямото предизвикателство на съвременната Теория на алгоритмите - съществуването на задачи (NP-пълни), за които все още няма качествени алгоритми. От практическа гледна точка студентите ще се запознаят с някои, неизучавани в курса по Структури от данни, абстрактни типове и тяхното ефективно имплементиране, както и с най-често използваните в практиката алгоритми и оценката на тяхната сложност.
Преподавател(и):
проф. Красимир Манев д-р
Описание на курса:
Компетенции:
Завършилите курса студенти ще знаят:
= различни формализми на неформалното понятие алгоритъм;
= дефинициите за понятията сложност на алгоритъм по време и памет;
= асимптотично поведение на целочислени функции;
= основни алгоритмични схеми - "Разделяй и владей", Обхождане на графи, Динамично програмиране, "Лакоми" алгоритми, Търсене с връщане;
= основни алгоритми и оценката на тяхната сложност;
= дефиниция на понятията свързани със съществуването на NP-пълни задачи.
Завършилите курса студенти ще могат:
= да създават свои алгоритми на базата на известна алгоритмична схема;
= да оценяват сложността на създавани от тях алгоритми;
= да сравняват сложностите на различни алгоритми, решаващи една и съща задача.
Предварителни изисквания:
За да могат успешно да се справят с курса студентите трябва:
= да имат добри познания в областта на Дискретната математика и някои елементи на Математическия анализ на функции на реална променлива;
= да владеят на много добро ниво език за програмиране (за предпочитане C/C++);
= да познават най-необходимите за работата на алгоритмите абстрактни типове и класическите им имплементации в структури данни, както и обичайните функции за работа със структурирани данни.
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Български
Теми, които се разглеждат в курса:
- Понятие за масова задача и алгоритъм
- Формални представяния на алгоритъм. МПД
- Формални представяния на алгоритъм. Език за програмиране
- Сложност на алгоритми по време и памет
- Сложност на рекурсивни алгоритми
- Асимптотично поведение на целочислени функции
- Сравняване на асимптотичното поведение на целочислени функции
- Първо контролно
- Сортиране. Класически алгоритми
- Сортиране със сложност O(N.log N) - Сортиране със сливане
- Сортиране със сложност O(N) - Сортиране с броене
- Алгоритмична схема "Разделяй и владей"
- Двоично търсене. Търсене с хеш таблица
- Крайни графи и мултиграфи
- Коренови дървета
- Абстрактен тип пирамида. Пирамидално сортиране
- Обхождане на графи в ширина
- Обхождане на графи в дълбочина
- Топологическо сортиране
- Алгоритми за най-къс път в граф
- Пълно изчерпване и търсене с връщане
- "Лакоми алгоритми"
- Динамично програмиране - едномерни таблици
- Динамично програмиране - двумерни таблици
- Динамично програмиране в даг
- Второ контролно
- Алгоритмична геометрия
- Сложност на задачи. NP-пълнота
- Теорема на Кук
- Приближени алгоритми за NP-пълни задачи
Литература по темите:
1. Th.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C.Stein, Introduction to
Algorithms, MIT Press, Third ed., 2009.
2. R. Sedgewick, Algorithms, Addison-Wesley Pub, 1988.
3. St. Skiena, The Algorithm Design Manual, Springer, 2010.
4. Кр. Манев, Алгоритми в графи. Основни алгоритми, КЛМН, 2013.
5. St. Halim, F. Halim, Competitive Programming 3, self edited