Информатика и вычислительная техника
Лабораторная
  • формат doc
  • размер 21.06 КБ
  • добавлен 27 мая 2011 г.
Лабораторные работы - Конструирование МТ
Архив содержит файлы решенных задач на МТ следующих вариантов:
Вариант 1
На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на -. Каретка в начальном состоянии находится где-то над указанным массивом.
Вариант 2
Дано число п в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число n на 1.
Вариант 3
Дана десятичная запись натурального числа п
1. Разработайте машину Тьюринга, которая уменьшала бы заданное число n на
1. При этом запись числа п - 1 не должна содержать левый нуль, например,
100-1 = 99, а не
099. Начальное положение головки - правое.
Вариант 4
Дан массив из открывающихся и закрывающихся скобок. Постройте машину Тьюринга, которая удаляла бы пары взаимных скобок. Например, дано: « ) ( ( ) ( ( ) », надо получить: «)…( ( ».
Вариант 5
Дана строка из букв а и b. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.
Вариант 6
Даны два целых положительных числа в десятичной системе счисления. Сконструируйте машину Тьюринга, которая будет находить разность этих чисел, если известно, что первое число больше второго, а между ними стоит знак «минус». Каретка находится над левой крайней цифрой левого числа.
Вариант 7
Даны два целых положительных числа в различных системах счисления, одно — в троичной системе, другое — в десятичной. Разработайте машину Тьюринга, которая будет находить сумму этих чисел в десятичной системе счисления.
Вариант 8
Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора.
Вариант 9
Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток.
Вариант 10
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три различные буквы: А, B и С. Каретка в начальном состоянии обозревает букву, расположенную справа. Необходимо составить функциональную схему машины Тьюринга, которая сумеет поменять местами крайние буквы.
Вариант 11
Даны два натуральных числа m и n представленных в унарной системе счисления. Соответствующие наборы символов « | » разделены « - », вслед за последним символом набора п стоит знак «=». Разработайте машину Тьюринга, которая будет находить разность чисел т и п. При этом результат должен быть записан следующим образом: если т п, то справа от «=» должны стоять знак «+» и набор символов « | » в количестве т- п; если т = п, то справа от знака «=» должна стоять пустая клетка; если т п, то справа от «=» должны стоять знак « - » и набор символов « | » в количестве п - т.
Вариант 12
Даны два натуральных числа п и т, заданных в унарной системе счисления. Числа п и т представлены наборами символов « | », разделенных « \ ». В конце набора стоит «=». Разработайте машину Тьюринга, которая будет производить деление нацело двух натуральных чисел п и т и находить остаток от деления. При этом результат должен быть записан следующим образом: после «=» должен находиться набор символов « | » частного (он может быть и пустым), после чего ставится знак «(», за которым следует набор символов « | » остатка от деления п на т.
Вариант 13
На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.
Вариант 14
На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число
11. Каретка обозревает крайнюю правую цифру числа.
Вариант 15
На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {а, b, с, d}. Подсчитайте число букв «а» в данном слове и полученное значение запишите на ленту левее исходного слова через пробел. Каретка обозревает крайнюю левую букву.
Вариант 16
На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», если нет — «нет». Каретка находится где-то над числом.
Вариант 17
На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.
Вариант 18
На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.
Вариант 19
На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и B. Сожмите массив, удалив из него все элементы B.
Вариант 20
Число п задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение п по формуле:
Каретка обозревает крайнюю левую метку.
Вариант 21
Число п задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение п по формуле:
Каретка обозревает крайнюю левую метку.
Вариант 22
Налейте машины Тьюринга находится массив 2N меток. Уменьшите этот массив в 2 раза.
Вариант 23
Даны два натуральных числа п и т, представленные в унарной системе счисления. Между этими числами стоит знак «? ». Выясните отношение т и п, т. е. знак «? » замените на один из подходящих знаков « », « », «=».
Вариант 24
Найдите произведение двух натуральных чисел т и п, заданных в унарной системе счисления. Соответствующие наборы символов « | » разделены знаком « * », а справа от последнего символа правого члена стоит знак «=». Поместите результат умножения этих чисел вслед за знаком «=».
Вариант 25
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2,
3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.
Похожие разделы
Смотрите также

Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Таль А.А. Логика, автоматы, алгоритмы

  • формат djvu
  • размер 5.45 МБ
  • добавлен 13 марта 2009 г.
Категория: Математическая логика. Автор: Таль А. А. , Айзерман М. А. , Гусев Л. А. , Розоноер Л. И. , Смирнова И. М. Название: Логика, автоматы, алгоритмы. Количество страниц: 556. Год издания: 1963. Издательство: Наука. ОГЛАВЛЕНИЕ. Элементы математической логики. Вводные замечания. Основные понятия. Исчисление высказываний. Об исчислении предикатов (двузначных). Технические приложения исчисления высказываний. Однотактные релейно-контактные схемы...

Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов

  • формат pdf
  • размер 528.46 КБ
  • добавлен 15 октября 2009 г.
Учебное пособие. - Улан-Удэ: Изд-во ВСГТУ, 2000 г. - 51 с. В учебном пособии рассмотрены основные понятия теории; формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы. Сод...

Кнут Д.Э. Устойчивость супружеских пар и другие комбинаторные задачи: Введение в математический анализ алгоритмов

  • формат djvu
  • размер 546.15 КБ
  • добавлен 25 сентября 2011 г.
М.: МЦНМО, 2001 г., 78 с. "Цель данной работы состоит в том, чтобы ознакомить читателя с основами анализа алгоритмов, причём сделать это с помощью примеров, а не систематического изложения теории. Надеюсь, что такой подход позволит читателю быстро войти в курс дела, познакомиться с идеями, используемыми в этой области, а также понять взаимосвязь анализа алгоритмов с другими математическими дисциплинами. Задача об устойчивых супружеских парах наи...

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы

  • формат doc
  • размер 7.54 МБ
  • добавлен 06 апреля 2010 г.
В книге подробно разобрано много конкретных алгоритмов; мы старались рассказать о них понятно, но не опуская деталей и не жертвуя строгостью изложения. Алгоритмы записаны с виде «псевдокода» и прокомментированы в тексте; мы старались сделать описание алгоритма понятным людям с минимальным программистским опытом. Книга содержит более 260 рисунков, поясняющих работу различных алгоритмов. Мы обращаем особое внимание на эффективность рассматриваемых...

Курсовая работа - Теория алгоритмов. Разработка эффективных алгоритмов

Курсовая работа
  • формат doc
  • размер 1.16 МБ
  • добавлен 09 сентября 2011 г.
Содержание Введение: Актуальность темы Понятие алгоритма Признаки алгоритмов Структуры данных и их представление в памяти ЭВМ Эффективность алгоритмов и методы её достижения Форма алгоритмов Эффективность алгоритмов Машина Тьюринга Краткое содержание курсовой работы Разработка эффективных алгоритмов: Типы алгоритмов Линейный алгоритм Задание 1 Алгоритмы разветвляющейся структуры Задание 2 Циклические вычислительные процессы Задание 3 Словесн...

Реферат - Принципы развития теории алгоритмов

Реферат
  • формат doc
  • размер 137 КБ
  • добавлен 04 января 2012 г.
Автор Лифшиц Ю.М. РАН СПб. Отделение Математического Института им. В.А. Стеклова, Лаборатория математической логики Содержание Введение Хронология теории алгоритмов Современное состояние теории алгоритмов Использование других наук в алгоритмах Наиболее значимые применения алгоритмов Идеи и техники в теории алгоритмов Формирование популярных направлений исследований Стили проведения научных исследований Заключение и выводы Список источников В эт...

Скиена С. Алгоритмы. Руководство по разработке

  • формат djvu
  • размер 10.81 МБ
  • добавлен 16 января 2012 г.
2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил. Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбин...

Шпоры

Шпаргалка
  • формат htm
  • размер 150.58 КБ
  • добавлен 27 июня 2011 г.
Ответы на вопросы: Машина Тьюринга. Конструирование МТ. Вычислимые по Тьюрингу функции: ПРФ, ЧРФ. Правильная вычислимость. Уточнение понятия алгоритма через машину с неограниченными регистрами. нормальные алгоритмы Маркова. Вычислимые функции и разрешимые множества: вычислимость, разрешимость, перечислимость, множество n-ок нат чисел, диагональная конструкция, главные универсальные функции, универсальная ОРФ, перечислимое неразрешимое множество.r...