Просмотр исходного текста страницы Сложность алгоритмов

Обязательный курс для студентов 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.==
Лектор: В.Б. Алексеев, осень 2017 года.
[[Media: Вопросы_сложность_алгоритмов_2017.doc| вопросы к экзамену]]

'''В билете 2 вопроса – один из части А и один из части В.'''

'''Часть  А – ответ без подготовки, но по любым материалам (конспекты, книжки и т.д.).''' 
Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки утверждений – без конспектов.

<ol>
<li>	Метод «разделяй и властвуй». Теорема о скорости роста функции, заданной рекуррентным неравенством.
<li>	Алгоритм Тоома для умножения чисел.
<li>	Алгоритм Штрассена для умножения матриц.
<li>	Алгоритмы обычного и булевского умножения матриц с битовыми операциями.
<li>	Сложность распознавания принадлежности функции, заданной векторно, классам, определяемым двухместными предикатами.
<li>	Сложность распознавания принадлежности булевой функции, заданной векторно, классу FmU(Rm).
<li>	Вычислимые функции, их нумерация. Теоремы о существовании трудно вычислимой общерекурсивной функции.
<li>	Теорема Барздиня о распознавании симметрии.
<li>	Теорема о совпадении классов регулярных языков и языков, распознаваемых автоматами.
<li>	Теорема о регулярности языка, распознаваемого со следом константной длины.
<li>	Теорема о регулярности языка, распознаваемого со слаборастущими длиной следа или временем.
<li>	Теорема Кука.
<li>    Теорема об NP-полноте языка 3 – ВЫПОЛНИМОСТЬ. 
<li>	Теорема об NP-полноте языка ГАМИЛЬТОНОВ ЦИКЛ.
<li>	Жадный алгоритм для задачи о кратчайшем остовном дереве.
<li>	Задача коммивояжера, ее NP-трудность, теоремы о приближенных алгоритмах для нее.
<li>	Теорема о PSPACE-полноте задачи о квантифицированных булевских формулах.
<li>	Теорема об иерархии по памяти. Несовпадение классов  DLOG  и  PSPACE.
</ol>

'''Часть В – ответ без конспектов и почти без подготовки (с доказательствами).'''

<ol start="19">
<li>	Сложность алгоритма бинарного поиска в упорядоченном массиве.
<li>	Нижние оценки сложности поиска в упорядоченном массиве.
<li>	Нижняя оценка сложности сортировки. Сложность алгоритма сортировки вставкой.
<li>	Сложность алгоритма сортировки слиянием.
<li>	Алгоритм динамического программирования для задачи об оптимальном порядке умножения матриц.
<li>	Алгоритм динамического программирования для поиска кратчайших путей между всеми парами вершин в графе.
<li>	Алгоритм Карацубы для умножения чисел.
<li>	Алгоритм транзитивного замыкания графа.
<li>	Верхние оценки сложности распознавания принадлежности булевой функции, заданной векторно, предполным классам Поста T0, T1, S, L, M.
<li>	Леммы о максимальной длине и сумме длин различных слов.
<li>	Классы P и NP. Примеры языков из NP. Замкнутость класса P относительно полиномиального сведения.
<li>	Теоремы об NP-полноте языков КЛИКА, Независимое Множество Вершин, Вершинное Покрытие.
<li>	Полиномиальный алгоритм для построения эйлерова цикла.
<li>	Задача о минимальном вершинном покрытии, ее NP-трудность, жадный и 1-приближенный алгоритмы для нее.
<li>	Класс PSPACE. Соотношение между классами NP и PSPACE. Верхняя оценка времени работы для задач из PSPACE.
<li>	Теорема о принадлежности задачи о квантифицированных булевских формулах классу PSPACE.
<li>	Класс DLOG. Соотношение между классами DLOG и P.
</ol>

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

[[Категория:Лекционные_курсы_кафедры_МК]]