 |
Занятие 8 – Классы сложности
|
|
|
|
Оглавление
1. Предисловие. 4
2. Рекомендованная литература. 5
3. Задачи. 6
3.1. Занятие 1 - Понятие задачи и алгоритма. 6
3.2. Занятие 2 - Нормальные алгорифмы Маркова. 6
3.3. Занятия 3,4 - Детерминированная Машина Тьюринга. 6
3.4. Занятие 5 – Схемы из функциональных элементов. 6
3.5. Занятие 6 – Полиномиальная сводимость. 7
3.6. Занятие 7 – NP-полные задачи. 7
3.7. Занятие 8 – Классы сложности. 7
Предисловие
Данное учебное пособие – сборник задач для первого семестра годового курса лекций по теории сложности алгоритмов. В этом курсе проведено изложение и сравнение основных базовых формальных схем алгоритмов: алгорифм Маркова, детерминированная и недетерминированная машина Тьюринга, оракульная машина Тьюринга и др. На основе этих формализмов и понятия сводимости построена иерархия сложности наиболее значимых в прикладном отношении классов задач.
Учебная программа семестра: 32 часа лекций и 16 часов (8 занятий) практики.
Данный курс лекций в течение двух лет читался в Московском физико-техническом институте и с 1998 года – в МГТУ им. Н.Э.Баумана.
Курс не является полностью автономным. Требуется знакомство с элементами математической логики, знание основных понятий и определений теории графов и математического программирования.
2. Рекомендованная литература
1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
3. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.
4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984.
5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике, М., Наука, 1995 г.
|
|
|
Задачи
Занятие 1 - Понятие задачи и алгоритма
Задача 1.1 Написать на любом языке алгоритм находящий минимальное из n чисел и оценить его трудоемкость.
Задача 1.2 Написать на любом языке алгоритм сортирующий n чисел и оценить его трудоемкость.
Задача 1.3 Для заданного графа с 8 вершинами построить примеры: цикла, контура, гамильтонова цикла, клики, вершинного покрытия.
Задача 1.4 Написать на любом языке алгоритм распознавания простоты натурального n и оценить его трудоемкость.
Задача 1.5 Для 6 камней с заданными весами написать алгоритм решения задачи о камнях и оценить его трудоемкость.
Занятие 2 - Нормальные алгорифмы Маркова
Задача 2.1 Построить НАМ f(x)= 3.
Задача 2.2 Построить НАМ f(x,y)=x+êx-yú.
Задача 2.3 Построить НАМ f(x,y,z)=z+êx-yú.
Задача 2.4 Построить НАМ, преобразующую слово P в слово PP.
Занятия 3,4 - Детерминированная Машина Тьюринга
Задача 3.1. Построить МТ, вычисляющую функцию f(x,y,z)=z.
Задача 3.2. Построить МТ, вычисляющую функцию f(x)=x+1.
Задача 3.3. Построить МТ, вычисляющую функцию f(x,y)=x+y.
Задача 3.4. Построить МТ, вычисляющую функцию f(x,y,z)=z+êx-yú.
Задача 4.1. Построить МТ, записывающую буквы любого слова некоторого конечного алфавита в обратном порядке.
Задача 4.2. Построить МТ, преобразующую слово P в слово PP.
Задача 4.3. Для входного алфавита {b, c} построить МТ, "различающую" слова, содержащие b от остальных.
Задача 4.4 Определена машина Тьюринга (см. лекции) T = {S, A, F, q0, d}, d - упорядоченная последовательность команд. Доказать, что определение МТ эквивалентно определению, в котором команды перехода - L, R, St – включены в алфавит. (Докажите это в виде простого упражнения.).
Занятие 5 – Схемы из функциональных элементов
Задача 5.1 Для функции f построить схему в базисе B.
- f= xÚy, B={Ù,»}.
- F=xÅyz, B={®,ù}.
Задача 5.2. Для системы функций построить схему в базисе B.
|
|
|
- F=xyÚxzÚzy, g=xÅzÅy; B={Å,Ù}.
- F=ùx, g=ùxùy, h=1, T=ùxùzùy; B={ù,¯}.
Задача 5.2. Для функции f построить схему сложности не выше m в базисе B={Ù,Ú,ù}.
- f=x»y, m=4.
- F=ùxùy, m=2.
Занятие 6 – Полиномиальная сводимость
Задача 6.1. Доказать, что задача "гамильтонов цикл" сводится к задаче "коммивояжер".
Задача 6.2 Доказать, что задача "КНФ выполнимость" сводится к задаче "клика".
Задача 6.3 Доказать, что задача «3-выполнимости" сводится к задаче "ЦЛП".
Задача "ЦЛП" (целочисленного линейного программирования):
Занятие 7 – NP-полные задачи
Задача 7.1. Доказать полиномиальную разрешимость задачи «2-КНФ».
Задача 7.2. Доказать NP- полноту задачи «вершинное покрытие». (Вершины вершинного покрытия содержатся во всех ребрах графа).
Занятие 8 – Классы сложности
Задача 8.1 Для задач из класса NP, рассмотренных на предыдущих трех занятиях, сформулировать соответствующие задачи из класса co-NP.
Задача 8.2 Для алгоритмов, рассмотренных на Занятии 1 оценить используемую память.
Задача 8.3 Для задачи «k-е по порядку подмножество» оценить используемую память.
|
|
|
