Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Занятия 3,4 - Детерминированная Машина Тьюринга

Читайте также:
  1. III. Ньютоновский мир-машина
  2. Ажет материалыңды табу, іздеу машиналарымен жұмыс істеу.
  3. Амфибийная машина
  4. Б) по теме занятия
  5. БОЕВАЯ МАШИНА БМ-21 С ПРИБОРОМ 9В370М И ТРАНСПОРТНОЙ МАШИНОЙ С КОМПЛЕКТОМ СТЕЛАЖЕЙ 9Ф37
  6. Внеклассные занятия
  7. Вопрос 20. Подведение итогов занятия.

Оглавление

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 занятий) практики.

Данный курс лекций в течение двух лет читался в Московском физико-техническом институте и четвертый год – в МГТУ им. Н.Э.Баумана.

Данный курс не является полностью автономным. Требуется знакомство с элементами математической логики, знание основных понятий и определений теории графов и математического программирования.

 


Рекомендованная литература

 

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.

4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984.

 


 

Задачи

 

Занятие 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 – включены в алфавит. (Докажите это в виде простого упражнения.).

 

3.4. Занятие 5 – Схемы из функциональных элементов

Задача 5.1 Для функции f построить схему в базисе B.

Задача 5.2. Для системы функций построить схему в базисе B.

Задача 5.2. Для функции f построить схему сложности не выше m в базисе B={Ù,Ú,ù}.

 

3.5. Занятие 6 – Полиномиальная сводимость

Задача 6.1. Доказать, что задача "гамильтонов цикл" сводится к задаче "коммивояжер".

Задача 6.2 Доказать, что задача "КНФ выполнимость" сводится к задаче "клика".

Задача 6.3 Доказать, что задача «3-выполнимости" сводится к задаче "ЦЛП".

Задача "ЦЛП" (целочисленного линейного программирования):

3.6. Занятие 7 – NP-полные задачи

Задача 7.1. Доказать полиномиальную разрешимость задачи «2-КНФ».

Задача 7.2. Доказать NP- полноту задачи «вершинное покрытие». (Вершины вершинного покрытия содержатся во всех ребрах графа).

 

3.7. Занятие 8 – Классы сложности

Задача 8.1 Для задач из класса NP, рассмотренных на предыдущих трех занятиях, сформулировать соответствующие задачи из класса co-NP.

Задача 8.2 Для алгоритмов, рассмотренных на Занятии 1 оценить используемую память.

Задача 8.3 Для задачи «k-е по порядку подмножество» оценить используемую память.


Дата добавления: 2015-11-16; просмотров: 37 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
The Migration Of Russian Scientists| Киевские Физические Бои 2012

mybiblioteka.su - 2015-2024 год. (0.008 сек.)