ВИМОГИ ДО ОФОРМЛЕННЯ  ЗВІТУ

I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.

II. В звіті мають бути відображені наступні пункти:

1. Мета роботи

2. Постановка задачі

2.1. Загальна частина

2.2. Індивідуальне завдання

3. Словесний опис алгоритму

3.1. Обгрунтування вибору додаткових символів, що не входять в алфавит А (за потребою)

4. Алгоритм у вигляді програми для МТ

4.1. Повна таблиця

4.2. Скорочена таблиця

4.3. Протокол роботи МТ

5. Ефективність алгоритму

5.1. Часова складність

5.1. Місткісна складність

5.1. Програмна складність

6. Результати виконання програми

Висновки

КОНТРОЛЬНІ ЗАВДАННЯ

Задана машина Тьюрінга з наступною функціональною схемою:

0
1

1. Записати зовнішній алфавіт та алфавіт внутрішніх станів цієї МТ.

2. Записати програму в скороченому табличному представленію.

3. Записати протокол роботи програми по переробці вхідного слова , якщо машина в початковому стані розпізнає третій починаючи зліва символ вхідного слова .

4. Визначити в яке слово переробляє МТ слово , якщо в початковому стані каретка вказує на перший зліва символ слова, що переробляється.

5. Визначити часову, місткісну та програмну складності МТ для попереднього завдання 4.

СПИСОК ЛІТЕРАТУРИ

1. Ершов, С.С. Элементы теории алгоритмов. – Челябинск: Издательский центр ЮУрГУ, 2009. – 64 с.

2. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы (учебное пособие для студентов 1 курса) – М., Издательский отдел факультета ВМК МГУ, 1997.

3. Марков А.А., Нагорный Н.М. Теория алгорифмов. – М., ФАЗИС, 1996.

4, Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. – М.: МГУ, 2006. – 47 с.

ЗМІСТ

1. Мета роботи……………………………………..………………………………………...…3

2. Теоретичні відомості..........….………………………………………………………….…. .3

2.1. Поняття алгоритму….………………………………………………………...….…. .3

2.2. Машина Тьюрінга….……………………………………………………….....….…. .3

2.3. Структура машини Тьюрінга…………………………………………………....…. .4

2.4. Такт роботи машини Тьюрін………………………………………………….....…. .5

2.5. Програма для машини Тьюрінга ……………………………………………......…. .5

2.6. Правила виконання програми ………………………………………………......…. .6

2.7. Приклади створення програм для МТ …………………………………….........…. .7

2.8. Емулятор машини Тьюрінга ………………………………………………..….…. .15

2.9. Дослідження ефективності машин Тьюрінга ………………………………....…. .17

3. Порядок виконання роботи..............………………………………………..……..…….....17

4. Завдання на лабораторну роботу ....………………………………………..……………...18

4.1. Вибір варіанта індивідуального завдання ……………………………..….....…...18

4.2. Варіанти завдань …………………………..……..……….….………..…………......18

5. Вимоги до оформлення звіту.......................……...……..………………………..……….  19

6. Контрольні завдання................………..……………………………………………...……. 19

Список літератури ………...……….....................…………………………………………..20

Навчальне видання

Методичні вказівки

до лабораторної роботи

" Програмування машин Тьюрінга"

з дисципліни

“ Алгоритми та методи обчислень "

для підготовки студентів напряму

6.050102 “Комп’ютерна інженерія”

Укладач                           Т.А.Матвейчук, ст. викладач каф.ЕОМ

Редактор

Комп’ютерне складання

Підписано до друку    2010 р.

Формат 70 х 100 ¹/₁₆. Папір офсетний.

Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......

Наклад ..... прим. Зам.   

Поліграфічний центр

Видавництва Національного університету “Львівська політехніка”

вул. Колесси, 2, 79000, Львів