Design And Analysis Of Computer Algorithms

по дисциплината: Проектиране и анализ на компютърни алгоритми

Образователно-квалификационна степен: бакалавър

по дисциплината: Проектиране и анализ на компютърни алгоритми

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

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

Преслав Наков

дем. Панайот Добриков

GSM 087 62 32 98

дем. Светлин Наков

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

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

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) Алгоритми. Основни понятия. Сложност: време и памет.

3) Теория на числата. Мерсенови и съвършени числа.

4) Теория на числата. Биномни коефициенти. Факторизация.

5) Структури от данни. Линейни списъци (едносвързан, двусвързан, цикличен, S-списък), стек, опашка, дек.

8) Сортиране. Елементарни методи за сортиране: вмъкване, селекция и мехурче.

9) Сортиране. Сортиране чрез броене, множество и пермутация.

10) Сортиране. Побитово сортиране и метод на бройните системи.

11) Сортиране. Бързо сортиране и намиране на k-ия елемент.

13) Сортиране. Приоритетна опашка и пирамида. Пирамидално сортиране.

15) Търсене. Последователно търсене, търсене в сортиран списък. Двоично търсене.

16) Търсене. Търсене със стъпка, квадратично търсене, Фибоначиево търсене, интерполационно търсене.

17) Теория на графите. Основни понятия, представяне на граф, обхождане на граф.

18) Теория на графите. Минимално обхващащо дърво.

19) Теория на графите. Екстремален път в граф.

25) Търсене с връщане. Задача за осемте царици

26) Търсене с връщане. Задача за раницата (оптимална селекция)

27) Търсене с връщане. Печеливши стратегии при игри

28) Разделяй и владей. Сортиране чрез сливане

29) Разделяй и владей. Организиране на първенства

30) Разделяй и владей. Алгоритъм на Щрасен за умножение на матрици

31) Разделяй и владей. Бързо умножение на дълги числа

36) Динамично оптимиране. Умножение на матрици

37) Динамично оптимиране. Триангулация на многоъгълник. Числа на Kаталан

38) Динамично оптимиране. Най-дълга обща подредица

39) Динамично оптимиране. Най-дълга ненамаляваща подредица

40) Динамично оптимиране. Задача за разделянето

41) Динамично оптимиране. Сравнение на символни низове

42) Динамично оптимиране. Разпознаване на контекстно свободен език

43) Динамично оптимиране. Представяне на сума с минимален брой монети

44) Динамично оптимиране. Максимална сума на подредица

45) Динамично оптимиране. Трионообразна редица

47) Алчни алгоритми. Максимално съчетание на дейности

48) Алчни алгоритми. Дробна задача за раницата

49) Алчни алгоритми. Задача за магнитна лента

51) Алчни алгоритми. Разходката на коня. Хиперкуб. Код на Грей

52) Алчни алгоритми. Монте Карло и Лас Вегас алгоритми

53) Алчни алгоритми. Числени алгоритми с приближение

54) Компресиране. Въведение и елементарни алгоритми.

55) Компресиране. Кодиране с линейно предсказване.

56) Компресиране. Алгоритми на Шенън-Фано и Хъфман.

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.

3) Lectures on CS http://campus.murraystate.edu/academic/faculty/bob.pilgrim/445/