АиАС

Прочее

Лабы

Шпоры

Методы

Лаба №3. Машины Тьюринга

Дата: Пт, 02/06/2009 - 23:40; Автор: Viking

Целью данного занятия является закрепление знаний по теории распознавания языков. Требуется подробно ознакомиться с языком ВЫПОЛНИМОСТЬ, играющим ключевую роль в теории сложности алгоритмов.

Задание 1. Построить распознающую машину Тьюринга, распознающую слова, начинающиеся с двух и долее подряд идущих единиц.

Задание 2. Построить распознающую машину Тьюринга, распознающую слова, содержащие комбинацию 010 в любом месте входного слова.

Задание 3. Построить распознающую машину Тьюринга, распознающую слова, заканчивающиеся тремя подряд идущими единицами.

Лаба №1. Машины Тьюринга

Дата: Пт, 02/06/2009 - 23:17; Автор: Denis

Целью данного занятия является закрепление знаний по построению и работе машин Тьюринга, которые являются математическими (формальными) моделями алгоритмов.

Задание 1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.

Задание 2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.

Шпоры, 1ый семестр. [30/30 вопросов]

Дата: Пт, 02/06/2009 - 23:14; Автор: Denis
Название: 
Шпоры
Примечания: 

*.doc уменьшенные

Список вопросов: 

1.Введение в предмет
2.Понятие машины Тьюринга
3.Представление машины Тьюринга
4.Альтернативы машине Тьюринга
5.Нумерация машин Тьюринга
6.Невычислимые функции
7.Примеры алгоритмически неразрешимых проблем
8.Современное программирование с точки зрения машины Тьюринга
9.Рекурсивные функции и множества
10.Операция примитивной рекурсии
11.Графическое и схемное описание алгоритмов
12.Табличный способ представления алгоритмов
13.Уменьшение числа состояний
14.Алгоритмы и исчисления

Условия лаораторных работ (Лаб. практикум)

Дата: Пт, 02/06/2009 - 23:10; Автор: Denis
Название: 
Условия лаораторных работ
Тип: 
Лабораторный практикум
Содержание: 

Практическое занятие №1. Машины Тьюринга.
Практическое занятие №2. Рекурсивные функции и множества. Тезис Черча.
Практическое занятие №3. Распознавание языков. Язык ВЫПОЛНИМОСТЬ.
Практическое занятие №4. Метод резолюций Робинсона.
Практическое занятие №5. Примеры NP-полных задач.

RSS-материал