Сложность алгоритмов — различия между версиями
Root (обсуждение | вклад) |
Root (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Обязательный курс для студентов 418 группы. Читается в осеннем семестре. | Обязательный курс для студентов 418 группы. Читается в осеннем семестре. | ||
| − | + | Лектор - профессор [[Алексеев Валерий Борисович]]. | |
| − | [[Алексеев Валерий Борисович]] | + | |
== Программа курса == | == Программа курса == | ||
Версия 12:37, 26 декабря 2013
Обязательный курс для студентов 418 группы. Читается в осеннем семестре.
Лектор - профессор Алексеев Валерий Борисович.
Содержание
- 1 Программа курса
- 1.1 Примеры задач с оценкой временной сложности по порядку.
- 1.2 Некоторые общие результаты о сложности алгоритмов.
- 1.3 Метод динамического пpогpаммиpования.
- 1.4 Метод "pазделяй и властвуй" для построения быстрых алгоритмов.
- 1.5 Метод pасшиpения модели для построения быстрых алгоритмов.
- 1.6 Некоторые классы сложности.
- 2 Литература
Программа курса
Примеры задач с оценкой временной сложности по порядку.
Сложность распознавания симметрии на машине Тьюринга. Сложность распознавания полноты системы булевых функций на машине Тьюринга.
Некоторые общие результаты о сложности алгоритмов.
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду. Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между 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, NLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач.
Литература
- Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
- Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
- Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
- Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.
