Лектор: Котов Владимир Михайлович, доц., кандидат физ-мат. наук.

3-й курс, 6-й семестр 2000-2001 учебного года.
Лекции (~1.6Мб)
задания Волчковой
Книга Clifford Shaffer (~420Кб)
Книги Jianer Chen (~670Кб)
Книга "Сложность вычислений и криптография" (~570Кб)
Доп. см. здесь

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