СУ ”Св. Климент Охридски”

У Ч Е Б Н А   П Р О Г Р А М А

по дисциплината: 	Проектиране и анализ на компютърни алгоритми
Образователно-квалификационна степен:	бакалавър
Факултет: 	ФМИ
Катедра:	Информационни технологии
Форма на обучение : 	редовно

София, 2001 година

УЧЕБНА ПРОГРАМА
по дисциплината: Проектиране и анализ на компютърни алгоритми

УЧЕБЕН ПЛАН

Вид на занятията	Хорариум, часа	
	седмичен	Общо	
А. Лекции	4	60	
Б. Лабораторни занятия	2	30	
В. Курсова работа		1	
   Изпит		1	
   Текуща оценка		90	

Преподавателски екип 2001/2002

Преслав Наков
РИЛА Солюшънс
е-mail  preslav.nakov {-at} rila.bg, preslav {-at} rocketmail.com
сл. тел. 97 97 319

дем. Панайот Добриков
In-Q-My labs.
е-mail 	panayot.dobrikov {-at} sap.com, panayot.dobrikov {-at} inqmy.com
GSM 087 62 32 98

дем. Светлин Наков
Мусала Софт
е-mail  svetlin.pranka2001 {-at} nakov.com

Внимание!
Курсът НЕ е увод в алгоритмите и предполага предварителни познания по анализ, проектиране и реализация на компютърни алгоритми, както и владеене на основни техники за оценка на алгоритмична сложност. Предполага се и познаване на класическите алгоритми и структури от данни. Предвижда се входен тест за проверка подготовката на кандидатите.

Анотация:
Курсът "Проектиране и анализ на компютърни алгоритми" има за цел да запознае студентите с някои от най-използваните в практиката техники за програмиране. Наред с представянето на широко известни методи за решаване на алгоритмични задачи (и анализ на техните свойства, приложения, предимства и недостатъци), се разглеждат и множество конкретни алгоритмични проблеми, обръща се внимание на анализа на алгоритмичната сложност на предложените решения, прави се сравнение между различни подходи за решение. В курса се засяга широк спектър от теми, както в теоретичен, така и в чисто приложен аспект: Алгоритми от теорията на числата, структури от данни, търсене и сортиране, алгоритми от теорията на графите, динамично оптимиране, разделяй и владей, алчни и вероятностни алгоритми, компресиране. Курсът е ориентиран към приложната страна и реализацията на разглежданите алгоритми, за сметка на чисто теоретични изследвания и доказателства за коректност. 

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.
СЪДЪРЖАНИЕ НА УЧЕБНАТА ПРОГРАМА 
по Проектиране и анализ на компютърни алгоритми
Лекции

1)	Алгоритми. Основни понятия. Сложност: време и памет.
2)	Теория на числата. Прости числа.
3)	Теория на числата. Мерсенови и съвършени числа.
4)	Теория на числата. Биномни коефициенти. Факторизация.
5)	Структури от данни. Линейни списъци (едносвързан, двусвързан, цикличен, S-списък), стек, опашка, дек.
6)	Структури от данни. Двоични дървета.
7)	Структури от данни. Хеш-таблици.
8)	Сортиране. Елементарни методи за сортиране: вмъкване, селекция и мехурче.
9)	Сортиране. Сортиране чрез броене, множество и пермутация.
10)	Сортиране. Побитово сортиране и метод на бройните системи.
11)	Сортиране. Бързо сортиране и намиране на k-ия елемент.
12)	Сортиране. Сортиране чрез дърво. 
13)	Сортиране. Приоритетна опашка и пирамида. Пирамидално сортиране.
14)	Сортиране. Паралелно сортиране.
15)	Търсене. Последователно търсене, търсене в сортиран списък. Двоично търсене.
16)	Търсене. Търсене със стъпка, квадратично търсене, Фибоначиево търсене, интерполационно търсене.
17)	Теория на графите. Основни понятия, представяне на граф, обхождане на граф.
18)	Теория на графите. Минимално обхващащо дърво.
19)	Теория на графите. Екстремален път в граф.
20)	Теория на графите. Цикли в граф.
21)	Теория на графите. Потоци в граф.
22)	NP. Класификация на задачите	
23)	NP. Задачата за удовлетворимост
24)	Търсене с връщане. Разходката на коня	
25)	Търсене с връщане. Задача за осемте царици	
26)	Търсене с връщане. Задача за раницата (оптимална селекция)
27)	Търсене с връщане. Печеливши стратегии при игри	
28)	Разделяй и владей. Сортиране чрез сливане
29)	Разделяй и владей. Организиране на първенства
30)	Разделяй и владей. Алгоритъм на Щрасен за умножение на матрици
31)	Разделяй и владей. Бързо умножение на дълги числа
32)	Разделяй и владей. Мажорант
33)	Динамично оптимиране. Числа на Фибоначи
34)	Динамично оптимиране. Задача за раницата
35)	Динамично оптимиране. Спортни срещи
36)	Динамично оптимиране. Умножение на матрици
37)	Динамично оптимиране. Триангулация на многоъгълник. Числа на Kаталан
38)	Динамично оптимиране. Най-дълга обща подредица
39)	Динамично оптимиране. Най-дълга ненамаляваща подредица
40)	Динамично оптимиране. Задача за разделянето	
41)	Динамично оптимиране. Сравнение на символни низове
42)	Динамично оптимиране. Разпознаване на контекстно свободен език	
43)	Динамично оптимиране. Представяне на сума с минимален брой монети
44)	Динамично оптимиране. Максимална сума на подредица
45)	Динамично оптимиране. Трионообразна редица
46)	Алчни алгоритми - общи задачи
47)	Алчни алгоритми. Максимално съчетание на дейности
48)	Алчни алгоритми. Дробна задача за раницата	
49)	Алчни алгоритми. Задача за магнитна лента	
50)	Алчни алгоритми. Процесорно разписание	
51)	Алчни алгоритми. Разходката на коня. Хиперкуб. Код на Грей
52)	Алчни алгоритми. Монте Карло и Лас Вегас алгоритми	
53)	Алчни алгоритми. Числени алгоритми с приближение
54)	Компресиране. Въведение и елементарни алгоритми.
55)	Компресиране. Кодиране с линейно предсказване.
56)	Компресиране. Алгоритми на Шенън-Фано и Хъфман.
57)	Компресиране. Аритметично кодиране.
58)	Компресиране. Речниково кодиране: LZ-77 и LZW.

ЛИТЕРАТУРА

А. Основна

1)	Наков Пр., Добриков П., "Алгоритми и реализации на Си" - (под печат)
2)	Наков Пр., “Основи на компютърните алгоритми”, изд. TopTeam Co., София, 1998.

Б. Допълнителна

1)	Кнут Д., “Искусство программирования для ЭВМ” том 1, “Мир”, Москва, 1976.
2)	Манев Кр., “Увод в дискретната математика”, “Издателство на Нов български университет”, София, 1996.
3)	Рейнгольд Э., Ю. Нивергельт, Н. Део, “Комбинаторные алгоритмы теория и практика”, “Мир”, Москва, 1980.
4)	Уирт Н., “Алгоритми + структури от данни = програми”, “Техника”, София, 1980.
5)	Шишков Д. и др., “Структури от данни”, “Интеграл”, Добрич, 1995.
6)	Aho A., J. Hopcroft, J.Ullman. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley. 1974.
7)	Aho A., J. Hopcoft, J. Ullman (1987) Data Structures and Algorithms. Addison-Wesley. 1987.
8)	Brassard G., P. Bratley (1996) Fundamentals of Algorithmics. Prentice-Hall. 1996.
9)	Cormen T., C. Leiserson and R.Rivest (1998). Introduction to Algorithms. MIT Press. Cambridge, MA. 1998.
10)	Sedgewick R. (1990). Algorithms in C. Addison-Wesley Publishing Company. New York. 1990.
11)	Sedgewick R. (2000) Algorithms in C++. Parts 1-4, Addison Wesley Longman, Reading, MA. 2000.
12)	Skiena S. (1997) The Algorithm Design Manual. Springer-Telos. 1997.

В. WEB сайтове

1)	Rila Solutions		  	http://books.rila.bg
2)	ИНФОМАН			http://infoman.musala.com
3)	Lectures on CS		http://campus.murraystate.edu/academic/faculty/bob.pilgrim/445/
4)	Lectures on CS 		http://jeff.cs.mcgill.ca/~luc/1997notes.html
5)	Lectures on CS 		http://www.cs.berkeley.edu/~edith/cs270/

20.09.2001					Съставили 
Пр. Наков, П. Добриков, Св. Наков