Задача за намиране максимум на подниз решения. Анализ

Изтегляне 127.78 Kb.

Pdf просмотр

Дата	21.12.2022
Размер	127.78 Kb.
	#116010
Тип	Задача

saap conspect
Свързани:
CAA.doc

Синтез и Анализ на алгоритми и програми

1. Основни понятия. Варианти на алгоритми. Влияние върху производителността.
Въведение в анализа
2. Примерна задача – свързаност на обекти. Дефиниране на абстрактни операции в
задачата. Начален алгоритъм. Алгоритъм за бързо намиране. Програмна
реализация. Представяне в дърво.
3. Свързаност на обекти – алгоритъм с бързо обединение. Програмна реализация.
Анализ и сравнение с алгоритъма за бързо намиране. Представяне в дърво.
4. Свързаност на обекти – алгоритъм с претеглено бързо обединение. Представяне.
5. Математически основи в анализа на алгоритми. Използвани формули с експоненти,
логаритми, редици. Доказателства.
6. Въведение в рекурсията. Основни свойства на рекурсията. Типове рекурсии, анализ
на производителността и доказателства. Формални техники за преобразуване на
рекурсивни в нерекурсивни алгоритми:опашна рекурсия; множествена рекурсия;
7. Оптимизации при взаимна рекурсия;
8. Анализ на алгоритми. Математически обозначения, дефиниции и правила в анализа.
правила за анализ на алгоритми в цикли,последователни блокове, оператор if.
9. задача за намиране максимум на подниз. решения. Анализ.
10. логаритми в анализа. бинарно търсене, Евклидов алгоритъм за НОД, повдигане на
степен. Анализ.

11. Рекурсия и дървета. Рекурсивни алгоритми.
12. Подходът: разделяй и владей. Свойства, известни алгоритми, реализация и
оценъчна формула.
13. Дървета. Основни понятия и класификации. Дефиниции и свойства.
14. Математически свойства на двоичните дървета.
15. Обхождане на дърво и граф.
16. Рекурсивни алгоритми в двоични дървета.

17. сортировки. Селективна сортировка. Сортиране чрез вмъкване. Примери.
18. Сортиране по метод на мехурчето. Подобрение на алгоритъма. Анализ.
19. Сортировка на Шел. Примери и свойства.
20. Бързо сортиране. Стратегии за разделяне. Избор на разделящ елемент. Анализ.
21. Сортиране чрез сливане. Анализ.
22. Сортиране на свързани списъци. Индексно и указателно сортиране. Примери.
23. Пирамидална сортировка. Базирани на пирамида алгоритми. Конвертиране в
пирамида. Сортиране на пирамида.

24. Списъци. Типове и реализация (реализация през шаблони и обекти). Приложни
аспекти.
25. Стек. Абстаркция и реализация. Приложни аспекти: постфиксен запис и
преобразувания, задачи от практиката,
26. Опашки. Абстракция и реализация. Използване на опашки.
27. Хеш таблици. Идея, функции, избор на оптимална функция.

28. Философия на алгоритмизирането (design techniques): постъпателни алгоритми
(greedy алгоритми).Проблемът –оптимална диспечеризация ( Simple scheduling )
29. Постъпателни алгоритми – синтез на кодове на Huffman ( компресия на файл.)
30. Постъпателни алгоритми -проблемът “пакетиране”
.
.

м
м
е
е
т
т
о
о
д
д
и
и
;
;

O
O
n
n
-
-
l
l
i
i
n
n
e
e

и
и

First Fit.

31. Постъпателни алгоритми -проблемът “пакетиране”. Методи:Best Fit, Next fit.

32. Off-line алгоритми. Помощни теореми и оценки на подхода.
33. Стратегия разделяй и владей .

Анализ на времето на изпълнение
34. Стратегия разделяй и владей – откриване “най-близкостоящи точки”. Анализ.
35. теоретични подобрения на аритметични операции. Анализ.
36. Динамично програмиране:

таблици вместо рекурсия
37. Ускоряване на сортировката с паралелизми чрез стратегия ‘разделяй и владей’.
38. Технологиии за паралелизация; OpenMP, ThreadPool. ускорена сортировка.
39. Динамично програмиране:

oптимално бинарно търсене в дърво
40. Алгоритми с backtracking: проблемът – реконструиране
41. алгоритми от теория на игрите. Оптимизационни техники.

42. Теория на графите. Общи понятия. Представяне на граф. Топологично сортиране.
43. Намиране най-къс път. Алгоритъм на Дейкстра.
44. Алгоритъм на Дейкстра при ациклични графи.
45. Пропускателна способност на мрежа.
46. Минимално обхващащо дърво. Алгоритъм на Прим. Алгоритъм на Крускал.

проф. д-р О. Наков

Изтегляне 127.78 Kb.

Сподели с приятели: