Методические указания и задания к лабораторным работам по курсам “




Скачать 321.54 Kb.
НазваниеМетодические указания и задания к лабораторным работам по курсам “
страница3/5
Дата публикации03.10.2013
Размер321.54 Kb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5


Описание МТ в виде диаграммы переходов


Вычисление на МТ словарной функции будем понимать следующим образом. Пусть в начальной конфигурации на ленте записано слово . Если значение определено, то конечного числа шагов (тактов) машина должна перейти в заключительную конфигурацию, в которой на ленте записано слово . В противном случае МТ должна работать бесконечно.

Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда =y , или работает бесконечно, когда не определена.
^ Задание на лабораторную работу
1.Описать системой команд, функциональной таблицей и диаграммой переходов работу машины Тьюринга, реализующую заданный вариантом алгоритм. Начальная и конечная конфигурации стандартны.

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

1. Реализовать функцию арифметическое вычитание в унарном коде.

2. Реализовать функцию выбор максимального из двух чисел над числами в унарном коде.

3. Реализовать функцию над числами в унарном коде.

4. Реализовать функцию над числами в унарном коде.

5. Реализовать функцию над числами в унарном коде.

6. Реализовать функцию над числами в унарном коде.

7. Реализовать функцию выбор аргумента над числами в унарном коде.

8. Реализовать вычисление предиката X>Y в унарном коде с сохранением (восстановлением) исходных данных.

9. Реализовать вычисление предиката X=Y в унарном коде с сохранением (восстановлением) исходных данных.

10. Реализовать вычисление предиката “x - четное число” в двоичном коде.

11. Реализовать алгоритм в алфавите , меняющий местами первую и последнюю буквы слова.

12. Реализовать алгоритм над алфавитом , меняющий местами первый ноль и последнюю единицу.

13. Реализовать операцию копирование в алфавите , то есть получить из слова слово .

14. Реализовать алгоритм над алфавитом , который выдает единицу, если в исходном слове только парные нули и ноль в противном случае.

15. Реализовать алгоритм в алфавите , который переставляет буквы в слове так, чтобы сначала шли все нули, потом – единицы.

16. Реализовать алгоритм, конструирующий в алфавите слова вида , где - произвольное натуральное число.

17. Реализовать алгоритм, реализующий функцию циклический сдвиг двоичного числа на одну ячейку.

18. Реализовать алгоритм в алфавите , анализирующий последовательность цифр в слове и выдающий «+», если цифры образуют неубывающую последовательность, и «–» в противном случае.

19. Реализовать выделение подстроки, заключенной между двумя символами (первая пара) в алфавите . Если последовательность отсутствует на ленте, стереть все.

20. В слове в алфавите стереть все, кроме . Если такой последовательности нет, все стереть.

21. Реализовать алгоритм над алфавитом , переставляющий буквы в обратном порядке.

22. Реализовать предиката «в слове  в алфавите есть пара букв ‘yy’ » .

23. Реализовать алгоритм в алфавите , производящий в слове  алфавита замену всех вхождений буквы а на букву б.

24. Реализовать алгоритм в алфавите для вычисления логической функции , где x,y,z принимают значение 0 или 1.

25. Реализовать алгоритм в алфавите для вычисления логической функции , где x,y,z принимают значение 0 или 1.
Контрольные вопросы


  1. Дать определение машины Тьюринга и ее составляющим.

  2. Перечислить и определить способы описания МТ.

  3. Какие операции выполняются в каждом такте работы МТ?

  4. Дать определение конфигурации МТ.

  5. Какие начальные и конечные конфигурации называют стандартными и как они обозначаются?

  6. Что такое функция, правильно вычислимая по Тьюрингу?

  7. Какие способы композиции МТ существуют, как они применяются и обозначаются?

  8. Формулировка тезиса Тьюринга; можно ли его доказать строго?

Лабораторная работа № 3
^ КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА
Цель работы: получить практические навыки в записи алгоритмов с использованием композиции машин Тьюринга.
Теоретическая справка

Вышеперечисленные способы описания МТ практически можно использовать только для несложных алгоритмов, в противном случае описание становится слишком громоздким. Машины Тьюринга для сложных алгоритмов могут строиться с использованием уже имеющихся элементарных МТ и такое построение называется композицией МТ.

Опишем 4 основных способа композиции МТ:

- последовательная композиция ( суперпозиция );

- параллельная композиция;

- разветвление

- цикл

^ 1. Последовательная композиция машин Тьюринга

Последовательной композицией или суперпозицией машин Тьюринга и , вычисляющих словарные функции и в алфавите А, называется машина M, вычисляющая функцию .

Последовательная композиция изображается следующим образом:



и обозначается или .

^ 2. Параллельная композиция машин Тьюринга

Параллельной композицией машин и , вычисляющих словарные функции и в алфавитах А и В, соответственно, называется машина M, вычисляющая словарную функцию . Здесь знак используется для разделения слов при параллельной композиции МТ.

Параллельная композиция МТ и изображается следующим образом:



и обозначается: .

Фактически параллельная композиция двух МТ получает на вход слово, состоящее из 2-х слов в разных алфавитах, и на выходе выдает слово, также состоящее из 2-х слов, т.е. представляет собой две одновременно и независимо работающие машины. Для реализации параллельной композиции используется машина с двухэтажной лентой.

Машина с двухэтажной лентой работает следующим образом:

1) слово переписывается на второй этаж ленты и стирается на первом,

2) вычисляется на первом этаже,

3) вычисляется на втором этаже

4) переписывается на первый этаж, возможно, со сдвигом.

Команда МТ с двухэтажной лентой записывается следующим образом:

,

где – буквы, записанные соответственно на первом и втором этажах. Обозначим длины слов , соответственно, .

Продемонстрируем работу машины Тьюринга с двухэтажной лентой. В общем случае длины слов и не совпадают между собой, но для простоты изображения принимаем, что они равны. Тогда реализация пунктов 1)-4) на МТ с двухэтажной лентой выполняется таким образом:








































































































Для реализации параллельной композиции n машин Тьюринга используется nэтажная лента.
1   2   3   4   5

Похожие:

Методические указания и задания к лабораторным работам по курсам “ iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по выбору рациональных структур...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсам “ iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по учебным дисциплинам...
«Электродинамика и распространение радиоволн», «Техническая электродинамика» (для студентов направлений подготовки 050901 «Радиотехника»,...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и задания к контрольной работе Ростов-на-Дону
Арженовский С. В. Анализ временных рядов и прогнозирование: Методические указания и задания к контрольной работе/Рост гос экон ун-т....

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница