Ответы к экзамену: МЛиТА решенные билеты к сессии

1)

1. Понятие «задача». Форма задачи. Индивидуальная и массовая задача. Примеры.
2. Построить сведение задачи «Гамильтонов цикл» к задаче «Коммивояжер».
3. Приближенные алгоритмы с оценкой точности. Теорема об ԑ-приближенном алгоритме для задачи коммивояжера.

2)

1. Определение Машины Тьюринга (МТ). Различие детерминированной и недетерминированной МТ. Определение понятия «сложность» (трудоемкость) вычисления для обоих случаев. Привести примеры вычисления для обоих случаев.
2. Построить сведение задачи «КНФ-выполнимость» к задаче «Клика».
3. Дать определение СФЭ в общем случае. Привести пример.

3)

1. Определение Оракульной Машины Тьюринга (ОМТ). Различие оракульной и недетерминированной МТ.
2. Доказать нижнюю оценку функции Шеннона для СФЭ в базисе «¬, ˄, ˅».
3. Построить сведение задачи «КНФ-выполнимость» к задаче «Клика».

4)

1. Определение Недерминированной Машины Тьюринга (НМТ). Различие оракульной и недетерминированной МТ.
2. Доказать оценку функции Шеннона для СФЭ, реализующей все конъюнкции от n переменных.
3. Построить сведение задачи «Гамильтонов цикл» к задаче «Коммивояжер».

5)

1. Задание «входа» для индивидуальной задачи. Примеры кодировок графов. Понятие полиномиальной эквивалентности для различных кодировок объекта.
2. Построить алгорифм Маркова сложения двух чисел в алфавите «*,1».
3. Дать определение классов EXPTIME и PSPACE. Доказать утверждение о соотношении между ними.

6)

1. Классы PSPASE, NPSPASE. Соотношение между ними.
2. Построить СФЭ минимальной сложности для функции (00110101) в базисе «¬, ˄, ˅».
3. Теорема о PSPACE-полной задаче.

7)

1. Классы PSPASE, NPSPASE. Соотношение между ними.
2. Построить СФЭ минимальной сложности для функции (00110101) в базисе «¬, ˄, ˅».
3. Теорема о PSPACE-полной задаче.

8)

1. Классы PSPASE, EXPTIME. Соотношение между ними.
2. Построить минимальную СФЭ для функции (01110100).
3. Доказать оценку функции Шеннона для СФЭ, реализующей все конъюнкции от n переменных.

9)

1. Определение СФЭ в базисе «¬, ˄, ˅». Привести пример СФЭ.
2. Построить МТ для обращения слов в заданном алфавите.
3. Теорема Кука. Идея и схема доказательства.

10)

1. Классы P/Poly и P. Теорема о соотношении между ними.
2. Построить НАМ для обращения слов в заданном алфавите.
3. Доказать оценку сверху для функции Шеннона L(n)≤(n +1) 2n.

11)

1. Класс PSPASE и игра двух лиц. Теорема о соотношении между ними.
2. По заданной формуле в исчислении предикатов построить формулу в приведенной нормальной форме. Сформулировать теорему о длине формулы в исчислении предикатов.
3. Понятие РАМ (Равнодоступная Адресная Машина). Привести пример.

12)

1. Двуместные отношения и сводимость по Тьюрингу. NP-трудные задачи. Привести пример.
2. Привести примеры полиномиально разрешимых частных случаев NP –полных задач.
3. Доказать оценку сверху для функции Шеннона L(n) <12•2ⁿ / n.

13)

1. Дать определения и привести примеры следующих понятий в исчислении предикатов: Предикат. Формула в исчислении предикатов. Выполнимые и общезначимые формулы. Приведенная нормальная форма.
2. Определить классы сложности для задач «К-е по порядку множество», «Задача о камнях».
3. Доказать оценку L(n)> 2ⁿ / n.

14)

1. Теорема Кука. Идея и схема доказательства.
2. Построить СФЭ для функции (11100101).
3. Понятие «коммуникационная сложность». Коммуникационная сложность задачи о равенстве числа единиц в двух булевских векторах.

15)

1. Понятие алгоритма. Понятие эквивалентность алгоритмов. Тезис Черча.
2. Алгоритм нахождения кратчайшего пути между вершинами графа.
3. Доказать оценку сверху для функции Шеннона L(n) <12•2ⁿ / n.

16)

1. Примеры подходов к решению NP-полных задач: полиномиально разрешимые частные случаи, псевдополиномиальные алгоритиы, алгоритмы с оценкой точности.
2. Определение полиномиальной сводимости и сводимости по Тьюрингу. Привести пример полиномиальной сводимости и сводимости по Тьюрингу.
3. Построить МТ для вычисления x-y.

17)

1. Теорема о PSPACE-полной задаче.
2. Построить минимальную СФЭ для функции (11100101). (Базис задает преподаватель.)
3. Построить НАМ для вычисления x-y.

18)

1. Классы NP и co-NP. Соотношение между ними. Теорема об NP–полной задаче и классе Co-NP.
2. Построить МТ для сложения чисел.
3. Доказать оценку L(n)> 2ⁿ / n.

19)

1. Приближенные алгоритмы с оценкой точности. Теорема о существовании такого алгоритма для «Задачи коммивояжера».
2. Игра двух лиц. Определение. Игра двух лиц и классы NP и co-NP.
3. Определить классы сложности для задач «К-е по порядку множество», «Задача о камнях».

20)

1. Коммуникационная сложность. Коммуникационная сложность задачи о равенстве числа единиц в двух булевских векторах.
2. По заданной формуле в исчислении предикатов построить формулу в приведенной нормальной форме.
3. Теорема Кука. Идея и схема доказательства.