Сложность алгоритмов — различия между версиями

Версия 12:24, 21 декабря 2022

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор Алексеев Валерий Борисович.

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

Примеры задач с оценкой временной сложности по порядку.

Сложность распознавания симметрии на машине Тьюринга. Сложность распознавания полноты системы булевых функций на машине Тьюринга.

Некоторые общие результаты о сложности алгоритмов.

Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду. Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

Метод динамического пpогpаммиpования.

Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

Метод "pазделяй и властвуй" для построения быстрых алгоритмов.

Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

Метод pасшиpения модели для построения быстрых алгоритмов.

Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

Некоторые классы сложности.

Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.

Вопросы к экзамену на январь 2023 года

Литература

1. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отдел ф-та ВМиК МГУ, 2002.
2. Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
3. Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
4. Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
6. Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.