CSCB029 Алгоритми и програмиране
Анотация:
Познаването на един език за програмиране, само по себе си, не е достатъчно за изграждането на един програмист – необходими са елементарни познания в поне още две дисциплини – Алгоритми и Структури от данни. Целта на този курс е да се запознаят студентите с основни алгоритми, с някои от техниките за разработка на алгоритми и най-вече да развият умения да имплeмeнтират свои алгоритмични идеи в програми.
Преподавател(и):
проф. Красимир Манев д-р
Описание на курса:
Компетенции:
Успешно завършилите курса студенти:
1) знаят:
• Основни алгоритми – сортиране, търсене, обхождане на графи, обработка на низове.
• Основни техники за разработване на алгоритми – „разделяй и владей“, динамично програмиране, лакоми алгоритми, backtracking.
• Основни структури данни подобряващи сложността на алгоритмите.
2) могат:
• Да подберат подходяща структура данни и да имплементират описан математически алгоритъм.
• Да разработят свой алгоритъм за решаване на не сложна алгоритмична задача и да го имплементират.
Предварителни изисквания:
Студентите да имат знания и/или умения:
• Успешно завършен курс Дискретни структури.
• Много добро познаване на език и съответна среда за програмиране (желателно е езикът да е C/C++).
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Български
Теми, които се разглеждат в курса:
№ Заглавие на темата Форма Часове
1 Задачи и алгоритми. Сложност на алгоритъм лекция 2 ч.
2 Сортиране с квадратична сложност упражн. 2 ч.
3 Разделяй и владей. Сортиране със сложност
O(n.log n) упражн. 2 ч.
4 Сортиране с линейна сложност. Хеширане упражн. 2 ч.
5 Търсене – двоично търсене, търсене на образец
в низ упражн. 2 ч.
6 Двоична пирамида – операции и приложения упражн. 2 ч.
7 Разбиване на множество с find и merge операции упражн. 2 ч.
8 Първо контролно 2 ч.
9 Графи лекция 2 ч.
10 Обхождане в ширина и дълбочина упражн. 2 ч.
11 Ойлерови обхождания упражн. 2 ч.
12 Пълно изчерпване. Търсене с връщане упражн. 2 ч.
13 Динамично програмиране упражн. 2 ч.
14 Лакоми алгоритми упражн. 2 ч.
15 Второ контролно 2 ч.
Литература по темите:
ПРЕПОРЪЧИТЕЛНА ЛИТЕРАТУРА
• Th.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C.Stein, Introduction to
Algorithms, MIT Press, Third ed., 2009.
• R. Sedgewick, Algorithms, Addison-Wesley Pub, 1988.
• St. Skiena, The Algorithm Design Manual, Springer, 2010.
• Кр. Манев, Алгоритми в графи, КЛМН, 2013.
Средства за оценяване:
ФОРМИ НА ОЦЕНЯВАНЕ ТЕКУЩ КОНТРОЛ КОМБ. ОЦЕНЯВАНЕ ФИН.ИЗПИТ
КОНТРОЛНА РАБОТА 50 % I контр.
КОНТРОЛНА РАБОТА 50 % II контр.
ПРАКТИЧЕСКА ЗАДАЧА 50 %
ПИСМЕНО ИЗЛОЖЕНИЕ 50 %
ДОПЪЛНИТЕЛНИ УСЛОВИЯ ПРИ ФОРМИРАНЕ НА КРАЙНАТА ОЦЕНКА:
При добър резултат (60% от максимума) от Текущ контрол, студентите се освобождават от решаване на Практическата задача на Финалния изпит.
При при много добър резултат (75 % от максимума) от Текущ контрол или Практическата задача на Финалния изпит, студентите се освобождават от Писмено изложение на Финалния изпит.
Скала за оценяване (процентите са от максималния брой точки): до 50% - Слаб 2; от 51 до 60% - Среден 3; от 61 до 74% - Добър 4; от 75 до 84% - Много добър 5; над 84% - Отличен 6.