по дисциплине "Алгоритмизация"
1. Основные понятия теории алгоритмов (Алгоритм, свойства алгоритма. Формы представления алгоритмов. Основные алгоритмические конструкции)
2. Формализация понятия алгоритма (Массовая и индивидуальная задачи. Алгоритм. Направления основных формализмов теории алгоритмов. Способы описания алгоритма: машины Поста)
3. Основные этапы решения алгоритмической задачи (Понимание задачи. Выбор вычислительных средств, структуры данных, методик проектирования алгоритма. разработка алгоритма. Оценка корректности алгоритма. Анализ алгоритма. Реализация алгоритма)
4. Основы анализа эффективности алгоритмов (Определение входной длины индивидуальной задачи. Показатели эффективности алгоритма: временная, пространственная. Зависимость показателей эффективности алгоритма от входной длины задачи. Единицы измерения временной эффективности: элементарные, базовые операции. Функция трудоемкости алгоритма. Оценки функции: худший, лучший и средний случай)
5. Классы эффективности алгоритмов (Порядок роста функции трудоемкости. Асимптотические классы эффективности. Классификация алгоритмов по типу зависимости функции трудоемкости от характеристик входных данных. Сложностные классы задач. Общий план анализа нерекурсивных алгоритмов. Общий план анализа рекурсивных алгоритмов. Эмпирический анализ алгоритмов. Визуализация алгоритмов)
6. Методика «грубой силы» разработки алгоритмов (Определение. Алгоритмы и задачи: сортировка выбором, пузырьковая сортировка, последовательный поиск, поиск подстроки, задача о паре двух ближайших точек, задача о выпуклой оболочке, задача коммивояжера, задача о рюкзаке, задача о назначениях)
7. Методика декомпозиции (Определение. Алгоритмы и задачи: сортировка слиянием, бинарный поиск, быстрая сортировка, задача о паре двух ближайших точек, задача о выпуклой оболочке)
8. Методика уменьшения размерности (Определение. Алгоритмы и задачи: сортировка вставкой, задача поиска фальшивой монеты, задача Иосифа)
9. Методика преобразования (Определение. Алгоритмы и задачи: схема Горнера вычисления значения полинома в точке, бинарное возведение в степень, пирамидальная сортировка, приведение задач, задача линейного программирования, задача целочисленного линейного программирования)
10. Методика пространственно-временного компромисса (Определение. Алгоритмы и задачи: алгоритмы Бойера-Мура и Хорспула поиска подстроки)
11. Методика динамического программирования (Определение. Алгоритмы и задачи: вычисление биномиальных коэффициентов, алгоритм Флойда)
12. Методика «жадные алгоритмы» (Определение. Алгоритмы и задачи: з адача о размене денег)
13. Методика поиска с возвратом» (Определение. Алгоритмы и задачи: задача о n-ферзях)
14. Методика ветвей и границ (Определение. Алгоритмы и задачи: задача о рюкзаке)
15. Приближенные методы решения (Основные понятия: ошибки усечения, ошибки округления, значащие цифры в представлении числа, абсолютная и относительная точность, стабильные и нестабильные алгоритмы, плохо обусловленные алгоритмы. Алгоритмы и задачи: деления пополам, метод секущих, метод Ньютона, задача нахождения корня уравнения, интерполирование функций)
16. Генетические алгоритмы (Основные понятия: генотип, фенотип, особь и качество особи, популяция и размер популяции, поколение, родители и потомки. Операторы скрещивания, мутации, отбора, редукции, останова)
17. Эфективность применения генетических алгоритмов (Области применения. Основные характеристики ГА: скорость и устойчивость. Способы повышения скорости генетического алгоритма: распараллеливание, кластеризация. Способы повышения устойчивости генетического алгоритма: родительское воспроизводство с рекомбинацией и мутацией, одноточечный, двухточечный и равномерный операторы скрещивания, стратегия разнообразия оператора мутации, рангово-пропорциональный отбор родителей, удаление наихудших в операторе редукции. Адаптивные генетические алгоритмы)
18. Графы (Представление графов в виде: матрицы смежности, списочными структурами с двумя адресными полями, массива списков смежных вершин, матрицы смежности для взвешенных графов. Операции над графами. Алгоритмы обхода графа в глубину, в ширину. Подсчет путей в графе. Алгоритм Прима-Дейкстры построения минимального остовного дерева взвешенного графа. Алгоритм Крускала построения минимального остовного дерева взвешенного графа.)
19. Деревья общего вида (Основные понятия: определение, степень узла, степень дерева, лист, уровень узла, предок, потомок, высота дерева, полное дерево. Основные свойства деревьев. Представление дерева списочной структурой)
20. Алгоритм Штрассена для умножения матриц
21. Генерация перестановок
22. Генерация подмножеств
23. Топологическая сортировка
24. Пирамидальная сортировка
25. Алгоритм Хорспула поиска подстрок
26. Алгоритм Бойера-Мура поиска подстрок
27. Алгоритм открытого хеширования реализации словарей
28. Алгоритм закрытого хеширования реализации словарей
29. Алгоритм Воршалла вычисления транзитивного замыкания орграфа
30. Алгоритм Флойда поиска кратчайшего (их) пути (ей) в графе
31. Деревья Хаффмана кодирования текста
32. Симплекс-метод решения задач линейного программирования
33. Венгерский метод решения задачи о назначениях
34. Сортировка Шелла
35. Интерполяционный поиск
36. Приближенный алгоритм решения задачи коммивояжера
37. Приближенные алгоритмы решения задачи о рюкзаке
Доцент Чекал Е.Г.