Поддержи сайт!

  • Расскажи друзьям
  • Добавь материал
  • Настрой переадресацию с ящика группы на for@bsuir-helper.ru
  • Добавь ссылку на этот сайт на своём сайте, в подписи на форуме, ЖЖ, Вконтакте

АиАС

Лабы

Шпоры

Методы

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

Дата: пт, 02/06/2009 - 22:40; Автор: Viking
Голосовать
15

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

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

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

Дата: пт, 02/06/2009 - 22:17; Автор: Denis
Голосовать
23

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

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

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

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

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

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

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

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

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

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

RSS-материал