АНОТАЦИЯ НА КУРСА:

    Курсът подготовя студенти по Информатика, КСТ и КТТ за решаване на задачи, за които се изисква съставяне на по-сложни алгоритми. Изучава се целия път от поставяне на задачата до анализ на решенията - анализ на данните, преглед на съществуващи алгоритми за решаванети й, избиране на подходящ алгоритъм, модифициране на съществуващ или построяване на нов алгоритъм, избор на структури от данни, програмиране, тестване на програмата, анализ на ефективността на алгоритъма и програмата. Занятията са в компютърна зала и студентите имат възможност както сами да решават поставените задачи така и да проверяват веднага разглежданите алгоритми. Всички алгоритми се изучават заедно с най-ефективните им реализации като програми на С и С++.
    Студентите трябва да знаят да програмират на С и/или С++.
 

СЪДЪРЖАНИЕ НА УЧЕБНАТА ПРОГРАМА

1. Въведение и задача за свързаност: доц. Николай Киров - БСУ и ИМИ, БАН
1.1. Технология на провеждане на студентски състезания по програмиране
1.2. Техника на програмирането на състезания по програмиране
1.3. Задача за свързаност - различни решения и оценка на ефективността на всяко решение
###3

2. Принципи на анализа на алгоритми: гл. ас. Веселина Стоянова - БСУ
2.1. Принципи
2.2. Нарастване на функция
2.3. Основни рекурсии
2.4. Примери
###3

3. Структури от данни: доц. Николай Киров
3.1 Масиви - задачи за симулации с подхвърляне на монета и изчисляване на най-близки точки
3.2. Свързани списъци - задача на Йосиф, обръщане на свързан списък, намиране на n-ти най-малък елемент
3.3. Съставни структури от данни - двумерен масив. Сортиране на масив от низове
3.4. Представяне на граф с матрица на съседство и чрез списъци на съседство
###3

4. Крайни автомати: доц. Стоян Капралов, ТУГ
###6

5. Графи: доц. Красимир Манев - СУ, ФМИ.
5.1. Представяне и елементарни методи - търсене в дълбочина и ширина, ойлерови и хамилтонови цикли и др.)
5.2. Свързаност
5.3. Графи с тегла - най-къс път, минимално покриващо дърво и др.
5.4. Ориентирани графи - топологическо сортиране и др.
###6

6. Два метода за съставяне на алгоритми: доц. Николай Киров
6.1. Пълно изчерпване
6.2. Търсене с връщане
###3

7. Нестандартни задачи и подходи за решаването им: Кристиян Хараламбиев - ФМИ, СУ.
###6

8. Рекурсивни алгоритми, разделяй и владей: доц. Николай Киров
8.1. Рекурсия - задача за изчисляване на префиксни изрази
8.2. Задачи за ханойските кули и изчертаване на линийка
8.3. Оценка на метода разделяй и владей
###3

9. Алгоритми за комбинаторни игри: н.с. Емил Келеведжиев - ИМИ, БАН
9.1. Елементи от комбинаторната теория на игрите.
9.2. Метод на разклоняване и граници и алфа-бета отсичане. Метод за търсене с връщане
(backtracking) за програмиране решаването на комбинаторни задачи.
9.3. Матрични игри.
9.4. Други примери и разглеждане на задачи от български и международни конкурси.
###6

Литература:
[1] Преслав Наков, Основи на компютърните алгоритми, TopTeam Co., 2000.
[2] Никлаус Уирт, Алгоритми + структури от данни = програми, Техника, София, 1980. (Оригинал: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, Inc., Englewood Cliffs, 1975.)
[3] Лендерт Амерал, Алгоритми и структури от данни в С++, ИК "Софтех", София, 2001.
[4] Емил Келеведжиев, Динамично опримиране, Мусала Софт и Анубис, София 2001.
[5] Джон Монтаг, Ноа Суджанен, Интервюта за програмисти, ИК "Софтех", София, 2002.
[6] Робърт Седжуик, Алгоритми на С. Том 1 и 2, ИК "Софтех", София, 2002.
[7] Ellis Horowitz, Sartaj Sahni, Fundamentals of computer algorithms, Computre Science Press.