Вопросы к экзамену по теории алгоритмов. 2012.

Часть I

1. 
   Понятие алгоритма. Вычислимые функции и породимые множества.
   

Определение функции. Вычислимость. Экстраалгоритм. Теорема об экстраалгоритме. Теорема о функции экстраалгоритма. Пример функции с числом π. Алгоритм. Частичные и тотальные функции. Примеры: кодирование из N в N² и кодирование кортежей. Исчисление. Свойства исчислений и алгоритмов. Конечный, конструктивный объект.

2. 
   Основные представительные модели.
   

Нормальный алгоритм Маркова. Каноническая система Поста. Пример про палиндромы. Машина Тьюринга. Машина Поста. Машина с неограниченными регистрами. МНР-вычислимые функции и класс C^МНР. Функция f_P, вычисляемая программой P. Примеры МНР-вычислимых функций: , , .

3. 
   Тезис Чёрча.
   

Основной результат: класс C. Тезис Чёрча. Свидетельства в пользу тезиса Чёрча. Способы доказательства МНР-вычислимости.

4. 
   Порождение вычислимых функций.
   

Предикат и его характеристическая функция. Разрешимость предиката. Примеры: «x кратно y» и «M_э(x) не разрешим». Лемма о вычислимости основных функций. Соединение программ. Теорема о замкнутости C относительно подстановки. Примитивная рекурсия. Примеры: , . Теорема о замкнутости C относительно примитивной рекурсии. Класс PR.

5. 
   Порождение вычислимых функций.
   

Класс PR. Теорема о вычислимости функций: , , , y, , , y, и , , . Следствие о вычислимости кусочно-заданной функции. Следствие об алгебре разрешимости.

6. 
   Порождение вычислимых функций.
   

μ-оператор. Теорема о замкнутости C относительно μ-оператора. Два примера. Пример с порождения нетотальной функции μ-оператором. Следствие о μ-операторе от разрешимого предиката (оператор поиска). Класс частично-рекурсивных функций R. Функция Аккермана. Теорема о существовании тотальной вычислимой не примитивно-рекурсивной функции (Th 5.2). Теорема о равенстве R и C. Класс R₀. Рекурсивный предикат. Соотношение между классами PR, R₀, Total, R, C.

7. 
   Нумерация вычислимых функций.
   

Счетность, (Геделева) нумерация, перечисление множества. Эффективная счетность множества всех конечных последовательностей натуральных чисел, J множества всех команд МНР, P множества всех программ МНР. - n-местная функция, вычисляемая по программе P_a. Теорема о счетности C. Теорема Фридберга (б/д). Теорема о существовании невычислимой всюду определенной функции. s-m-n-теорема (б/д).

8. 
   Универсальные программы.
   

Универсальная функция . Теорема о вычислимости . Следствие о разрешимости предиката «P_e(x)↓y за t или меньше шагов».

9. 
   Неразрешимые задачи.
   

Теоремы о неразрешимости проблем: «Ф_x всюду определена» (6.1), «или функция Ф_x(x) определена» (6.2), «или функция Ф_x(y) определена или P_x(y)↓» (6.4, проблема остановки), «Ф_x ≡ 0» (6.5), «Ф_x ≡ Ф_y» (следствие), «P_x(c)↓ и P_x(y)↓с» (6.6) (б/д). Теорема Райса (б/д, доказательство – бонус при спорной оценке).

10. 
    Частично разрешимые задачи.
    

Частично разрешимый предикат и его частичная характеристическая функция. Любой разрешимый предикат частично разрешим. Примеры частично разрешимых проблем: «», «или P_x(y)↓» (проблема остановки), «», «». Критерий разрешимости предиката (6.11). Следствие: предикат P_x(y)↑ не частично разрешим.

11. 
    Рекурсивные и рекурсивно-перечислимые множества.
    

Множество истинности. Рекурсивные множества. Характеристическая функция . Примеры рекурсивных и нерекурсивных множеств. Теорема о рекурсивности , , , . Рекурсивно перечислимые множества и их частичные характеристические функции. Критерий рекурсивного множества. Три эквивалентных утверждения (б/д). Теорема о рекурсивной перечислимости множеств и . Теорема о бесконечном рекурсивном множестве и тотальной возрастающей вычислимой функции (б/д). Вторая теорема о рекурсии (б/д – только формулировка). Мера вычислительной сложности . Теоремы Блюма о псевдоускорениях и ускорениях (б/д).

12. 
    Диофантовы множества.
    

Диофантово уравнение. Сводимость системы уравнений к одному. Приведение к уравнению 4-й степени. Теорема Лагранжа. Эквивалентность разрешимости в целых и натуральных числах. Диофантовы множества. Теорема о диофантовости и . Критерий диофантовости множества натуральных чисел.

13. 
    Диофантовы множества.
    

Диофантовые свойства, отношения, функции. Примеры: , , , , , , , , a – (не) степень двойки. Диофантовость конечных множеств и их представление. Универсальное уравнение. Теорема о существовании недиофантового дополнения. Универсальное ДУ без параметров и его диофантово множество. 10-я проблема Гильберта. Теорема Матиясевича (б/д). Критерий р.п. множества натуральных чисел (следствие) (б/д). Два следствия о существовании универсального многочлена (б/д). Разрешимость в рациональных числах. Следствие из теоремы Штурма (б/д). Теорема Тарского (б/д).

Часть II

1. 
   РАМ. Описание. Типы операндов. c(i), v(a). Команды. Интерпретация программы, как отображение лент, как функции, как языка. Пример с алфавитом {1, 2}.
   
2. 
   Вычислительная сложность РАМ-программ. Весовые критерии сложности. Логарифмический критерий для разных операндов и команд. Пример с программой, считающей nⁿ.
   
3. 
   Инварианты циклов. Пример программы, вычисляющей x^y, её инвариант, доказательство корректности, сложность.
   
4. 
   Неветвящиеся программы. Пример: схема Горнера. Равномерный весовой критерий . Битовые вычисления и логарифмический весовой критерий . Ветвления и пример: сортировка чисел попарным сравнением.
   
5. 
   «Разделяй и властвуй». Примеры: MinMax, умножение n-разрядных двоичных чисел, сортировка слиянием.
   
6. 
   Теорема о рекуррентных соотношениях.
   
7. 
   «Динамическое программирование». Пример с умножением матриц.
   
8. 
   Порядковые статистики.
   
9. 
   Редактирующее расстояние. ρ – метрика. Алгоритм Вагнера-Фишера. Поиск образца (Функция отказов, пример, теорема о распознавании вхождения сразу k цепочек).
   

Часть III

1. 
   Введение в теорию сложности.
   

Массовая и индивидуальная задачи. Алгоритм. Дескриптивная и метрическая т.а. Схема кодирования, временная сложность. O(f). Полиномиальные и экспоненциальные алгоритмы. Сложность в среднем и худшем случае. Труднорешаемая задача.

2. 
   Аспекты труднорешаемости.
   

Инвариантность относительно схем кодирования и вычислительных моделей (полиномиально эквивалентные функции, «разумные» схемы кодирования и вычислительные модели, связь МТ и РАМ), различные аспекты труднорешаемости. Задача распознавания. Примеры – изоморфизм подграфу, коммивояжер, связь с задачей оптимизации. Схема кодирования и язык. Функция Length.

3. 
   Детерминированные Машины Тьюринга и класс P.
   

ДМТ. Язык, распознаваемый ДМТ-программой. Решение задачи распознавания. Временная сложность ДМТ-программы. Полиномиальная ДМТ-программа. Класс языков P.

4. 
   Недетерминированное вычисление и класс NP.
   

НДМТ. Решение задачи распознавания. Принимающее вычисление. Язык, распознаваемый НДМТ-программой. Временная сложность НДМТ-программы. Полиномиальная НДМТ-программа. Класс языков NP.

5. 
   Взаимоотношения между классами P и NP.
   

P Н NP. Теорема: связь НДМТ-программы с полиномиальной временной сложностью и ДМТ.

6. 
   Полиномиальная сводимость и NP-полные задачи.
   

Сводимость языков (полиномиальная). Лемма о принадлежности P. Сводимость задач. Пример сводимости ГЦ КЖ. Лемма о транзитивности сводимости. Определение NPC. Лемма о признаке NPC.

7. 
   Основные NPC задачи.
   

Теорема Кука (б/д. Знать схему док-ва). Основные NPC задачи. Теорема: 3-ВЫП – NPC.

8. 
   Основные NPC задачи.
   

Теорема: КЛИКА – NPC. Лемма об эквивалентности ВП, НМ, КЛИКИ. Теорема: ВП – NPC. Следствие. Основные методы док-ва NPC.