Лектор: профессор кафедры алгоритмических языков Абрамов С. А.

В курсе рассматриваются основные элементарные подходы к исследованию двух характеристик алгоритма – временной и пространственной сложности. Эти виды сложности рассматриваются в худшем случае и в среднем. Уделяется внимание вопросам корректного использования понятий и методов математического анализа при формулировании и доказательстве утверждений о сложности.

Результаты контрольной №1 в 2003 г.
Результаты контрольной №2 в 2003 г.
Результаты контрольной №3 в 2003 г.
Результаты семестра в 2003 г.

Программа курса:

1. Вход (входные данные) алгоритма и размер входа. Затраты алгоритма для данного входа; понятие сложности в худшем случае.
   
2. Однородная и битовая сложность.
   
3. Оценивание сложности; асимптотики. Сравнение сложностей разных алгоритмов на основе асимптотик.
   
4. Различие оценок при разных выборах размера как функции входа. Возможность «плохого» выбора.
   
5. «Полиномиальные» алгоритмы. Гипотеза P <> NP. Сводимость. NP-полнота.
   
6. Сложность фрагментов алгоритма; управляющие структуры.
   
7. Оценивание числа шагов циклического алгоритма (функции, убывающие по ходу выполнения алгоритма); завершимость алгоритма.
   
8. Различие в характере временных и пространственных затрат (сложностей).
   
9. Рекуррентные соотношения для пошаговых затрат. Временная и пространственная cложность рекурсивных алгоритмов.
   
10. Рекуррентные соотношения, сопутствующие стратегии «разделяй и властвуй».
    
11. Понятие сложности в среднем.
    
12. Производящие функции.
    
13. Анализ рандомизированных алгоритмов. Завершимость в среднем.
    
14. Нижние границы сложности алгоритмов некоторого класса (в худшем случае и в среднем). Привлечение ограниченных вычислительных моделей.
    
15. Оптимальные алгоритмы. Алгоритмы, оптимальные по порядку сложности.
    
16. Неветвящиеся программы и индукция. Вычислительные модели, ориентированные на конкретные задачи.