Конспект Синтез и анализ на алгоритми и програми



Дата18.11.2017
Размер24.06 Kb.
Размер24.06 Kb.

Конспект

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

  1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа.

  2. Примерна задача – свързаност на обекти. Дефиниране на абстрактни операции в задачата. Начален алгоритъм. Алгоритъм за бързо намиране. Програмна реализация. Представяне на дърво.

  3. Свързаност на обекти – алгоритъм с бързо обединение. Програмна реализация. Анализ и сравнение с алгоритъма за бързо намиране. Представяне в дърво.

  4. Свързаност на обекти – алгоритъм с претеглено бързо обединение. Реализация. Анализ. Представяне в дърво.

  5. Математически основи в анализа на алгоритми. Използвани формули с експоненти, логаритми, редици. Доказателства.

  6. Въведение в рекурсията. Основни свойства на рекурсията. Типове рекурсии, анализ на производителността и доказателства.

  7. Опасности при рекурсивни алгоритми. Формални техники за преобразуване на рекурсивни в нерекурсивни алгоритми:опашна рекурсия; множествена рекурсия; рекурсия в средата; алгоритмични решения с взаимна рекурсия.

  8. Анализ на алгоритми. Математически обозначения и дефиниции в анализа . Базови правила в анализа на алгоритми.

  9. Конкретизация на правилата за анализ на алгортми в : цикли for; вложени цикли; последователни блокове; оператор if.

  10. Конкретизация на анализа при рекурсия и множествена рекурсия. Математически извод.

  11. Четири варианта на решение на задачата за максимум на подниз. Алгоритмично и програмно решение. Математически извод, определящ производителността. Анализ на получените значими разлики.

  12. Логаритми в анализа на алгоритми. Основни алгоритми в тази група: двоично търсене, Евклидов алгоритъм за ХОД, повдигане на степен. Програмна реализация на алгоритмите. Анализ и изработване оценъчна формула.

  13. Рекурсия и дървета. Рекурсивни алгоритми.

  14. Подходът: разделяй и владей. Свойства, известни алгоритми, реализация и оценъчна формула.

  15. Техники за подобрения в рекурсията: Динамично програмиране. Известни алгоритми в тази реализация. Анализ.

  16. Дървета. Основни понятия и класификации. Дефиниции и свойства.

  17. Математически свойства на двоичните дървета.

  18. Обхождане на дърво и граф.

  19. Рекурсивни алгоритме в двоични дървета.

  20. Елементарни сортировки. Селективна сортировка. Сортиране чрез вмъкване.

  21. Сортиране по метод на мехурчето. Характеристики на елементарни те сортировки. Дефиниции Свойства.

  22. Сортировка на Шел. Примери и свойства.

  23. Сортиране на свързани списъци. Индексно и указателно сортиране.

  24. Философия на алгаритмизирането (design techniques): постъпателни алгоритми (greedy алгоритми). Проблемът:Simple scheduling.

  25. Кодове на Huffman ( компресия на файл ).

  26. Проблемът “пакетиране” Метод First Fit.

  27. Проблемът “пакетиране”. Методи: Best Fit и Off-line алгоритми. Оценки.

  28. Разделяй и владей – алгоритми. Анализ на времето на изпълнение.

  29. Проблемът: “най – близкостоящи точки”

  30. Теоретични подобрения с аритметични задачи.

  31. Динамично програмиране: таблици вместо рекурсия.

  32. Динамично програмиране: оптимално бинарно търсене в дърво.

  33. Алгоритми с backtracking: проблемът реконструиране.

  34. Алгоритми с backtracking: игри.

  35. Теория на графите. Общи понятия. Представяне на граф. Топологично сортиране.

  36. Намиране на най-къс път. Алгоритъм на Дейкстра.

  37. Алгоритъм на Дейкстра при ациклични графи.

  38. Пропускателна способност на мрежа.

  39. Минимално обхващащо дърво. Алгоритъм на Прим. Алгоритъм на Крускал.


2004 г. Съставил: доц. д-р О. Наков

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


©zdrasti.info 2017
отнасят до администрацията

    Начална страница