Вопросы к экзамену
Описание файла
Документ из архива "Вопросы к экзамену", который расположен в категории "". Всё это находится в предмете "сложность алгоритмов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Вопросы к экзамену"
Текст из документа "Вопросы к экзамену"
Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.
Лектор: В.Б. Алексеев, осень 2016 года.
В билете 2 вопроса – один из части А и один из части В.
Часть А – ответ без подготовки, но по любым материалам (конспекты, книжки и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки утверждений – без конспектов.
-
Метод «разделяй и властвуй». Теорема о скорости роста функции, заданной рекуррентным неравенством.
-
Алгоритм Тоома для умножения чисел.
-
Алгоритм Штрассена для умножения матриц.
-
Алгоритмы обычного и булевского умножения матриц с битовыми операциями.
-
Сложность распознавания принадлежности функции, заданной векторно, классам, определяемым двухместными предикатами.
-
Сложность распознавания принадлежности булевой функции, заданной векторно, классу FmU(Rm).
-
Вычислимые функции, их нумерация. Теоремы о существовании трудно вычислимой общерекурсивной функции.
-
Теорема Барздиня о распознавании симметрии.
-
Теорема о совпадении классов регулярных языков и языков, распознаваемых автоматами.
-
Теорема о регулярности языка, распознаваемого со следом константной длины.
-
Теорема о регулярности языка, распознаваемого со слаборастущими длиной следа или временем.
-
Теорема Кука.
-
Теорема об NP-полноте языка 3 – ВЫПОЛНИМОСТЬ.
-
Теорема об NP-полноте языка ГАМИЛЬТОНОВ ЦИКЛ.
-
Жадный алгоритм для задачи о кратчайшем остовном дереве.
-
Задача коммивояжера, ее NP-трудность, теоремы о приближенных алгоритмах для нее.
-
Теорема о PSPACE-полноте задачи о квантифицированных булевских формулах.
-
Теорема об иерархии по памяти. Несовпадение классов DLOG и PSPACE.
Часть В – ответ без конспектов и почти без подготовки (с доказательствами).
-
Сложность алгоритма бинарного поиска в упорядоченном массиве.
-
Нижние оценки сложности поиска в упорядоченном массиве.
-
Нижняя оценка сложности сортировки. Сложность алгоритма сортировки вставкой.
-
Сложность алгоритма сортировки слиянием.
-
Алгоритм динамического программирования для задачи об оптимальном порядке умножения матриц.
-
Алгоритм динамического программирования для поиска кратчайших путей между всеми парами вершин в графе.
-
Алгоритм Карацубы для умножения чисел.
-
Алгоритм транзитивного замыкания графа.
-
Верхние оценки сложности распознавания принадлежности булевой функции, заданной векторно, предполным классам Поста T0, T1, S, L, M.
-
Леммы о максимальной длине и сумме длин различных слов.
-
Классы P и NP. Примеры языков из NP. Замкнутость класса P относительно полиномиального сведения.
-
Теоремы об NP-полноте языков КЛИКА, Независимое Множество Вершин, Вершинное Покрытие.
-
Полиномиальный алгоритм для построения эйлерова цикла.
-
Задача о минимальном вершинном покрытии, ее NP-трудность, жадный и 1-приближенный алгоритмы для нее.
-
Класс PSPACE. Соотношение между классами NP и PSPACE. Верхняя оценка времени работы для задач из PSPACE.
-
Теорема о принадлежности задачи о квантифицированных булевских формулах классу PSPACE.
-
Класс DLOG. Соотношение между классами DLOG и P.
https://studizba.com