"Мой помощник - компьютер" 2010
Второй этап. 26 января - 24 февраля
Задания второго этапа будут сформулированы в виде задач. Решения задач нужно отправлять вложением в электронное письмо в виде файла в формате Word2003. Пример оформления решения в виде таблицы можно посмотреть на этой странице в рубрике Справка. Дополнительно, если установлено рекомендованное приложение с сайта www.loonies.narod.ru, можно добавлять вложение с решением в формате этого приложения (.alg).
Ответы отсылать по адресу scpinerPVV@yandex.ru по мере решения, желательно в срок до обнародования очередной задачи. Обязательно указывайте тему письма МПК_Фамилия_задача*, где * - номер задачи.
По любым вопросам можно писать в форум Этап второй. Активность в форуме оценивается.
Тексты задач можно скачать:
Сроки решения задач являются условными. Можно решать не все задачи
Справка
Английским математиком А.Тьюрингом (1912-1954) для построения формального определения алгоритма в 1936 году была предложена абстрактная вычислительная конструкция, которая позже была названа «машиной». Описание машины Тьюринга Машина Тьюринга — это строгое математическое построение, математический аппарат, созданный для решения определенных задач. Он был назван "машиной" потому, что по описанию его составляющих частей и функционированию он похож на вычислительную машину или автоматическое устройство. В машине Тьюринга есть две части: 1) неограниченная в обе стороны лента, разделенная на ячейки; в каждой ячейке может быть записан ровно один символ; 2) автомат, головка для считывания/записи, управляемая программой. Автомат имеет одну ячейку памяти, в которой хранится символ состояния. Принципиальное отличие машины Тьюринга от реальных вычислительных машин состоит в том, что ее запоминающее устройство – лента – бесконечно, а значит, имеет бесконечную емкость: у реальных компьютеров запоминающее устройство может быть очень большим, но обязательно конечным. По этой причине реализовать машину Тьюринга на реальных компьютерах в полной мере невозможно, и в этом смысле она мощнее любой реальной вычислительной машины. У каждой машины Тьюринга есть два конечных алфавита: алфавит входных символов (символов ленты) А = {а0, ..., аm} и алфавит состояний Q = {q0, q1,..., qn}. Для разных машин Тьюринга (т.е. задач) могут использоваться разные алфавиты A и Q. Во множестве состояний обязательно есть два специальных элемента — состояния q0 и q1. Состояние q0 называется пассивным, или состоянием останова. Если машина попала в состояние q0, то она завершает свою работу. Состояние q1 называется начальным. Когда машина Тьюринга начинает свою работу, она находится в состоянии q1 Алфавит входных символов А обязательно содержит один специальный символ а0 — так называемая пустая буква (часто обозначается _), который используется как признак того, что "ячейка пуста". Входное слово размещается на ленте, по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (заполненные пустыми буквами а0). Ячейки ленты не имеют номеров или каких-либо пометок. В каждый момент времени автомат просматривает только одну ячейку ленты. Он может: прочитать букву из текущей ячейки, записать букву в текущую ячейку, переместиться на одну ячейку влево (Л) или вправо (П), либо остаться на месте (H). Ячейка памяти хранит так называемое "состояние машины Тьюринга". Машина Тьюринга может записывать в нее только символы из алфавита состояний. Состояния нужны для того, чтобы обозначать различные шаги программы. Программа машины Тьюринга Программа машины Тьюринга состоит из набора правил вида: "если текущее состояние равно qi и из текущей ячейки считан символ аi, то в текущую ячейку следует записать символ аj, перевести машину в состояние qj и передвинуть автомат в направлении dj. При этом для каждой команды исходное состояние qi может быть любым из множества Q, кроме состояния останова q0, конечное состояние команды qj — любым из Q, символы а — любые из алфавита ленты А, а направление перехода d — элемент из множества {Л, П, H} (Л — влево, П — вправо, Н — неподвижен). Для записи программы машины Тьюринга обычно используют одну из двух форм:
либо список команд, записанных в формате {ai, qi} → {аj, d, qj},
либо таблица, у которой столбцы проиндексированы символами алфавита ленты а, строки — символами алфавита состояний q, а в каждой ячейке таблицы записана тройка {a, d, q} — символ, который надо записать в текущую ячейку, направление перехода и новое состояние машины Тьюринга. Состояния qi и qj, а также символы аi и аj могут совпадать.
Пример задачи
На ленте записано входное слово - последовательность символов +. Автомат находится где-то справа от входного слова. Необходимо найти слово и поставить символ * справа и слева от него. Конечное положение автомата роли не играет.
Запись программы машины Тьюринга в виде таблицы
Q\A |
_ |
+ |
* |
1 |
_ Л 1 |
0 Н 2 |
|
2 |
|
0 П 3 |
|
3 |
* Л 4 |
|
|
4 |
_ Н 5 |
0 Л 4 |
|
5 |
* Н 0 |
|
|
На каждом шаге машина Тьюринга находит строку, соответствующую текущему состоянию, и столбец, соответствующий символу в текущей ячейке. Из соответствующей ячейки таблицы выбирается тройка "выходных" параметров команды — какой символ записать на ленту, в какое состояние перейти и куда переместить считывающую головку. Перед запуском программы лента машины Тьюринга пуста — во всех ее ячейках записана пустая буква _). На ленту записывается входное слово для машины Тьюринга, автомат устанавливается в (заданную по условию) исходную позицию относительно входного слова, и состояние машины Тьюринга изменяется на начальное состояние q1 после чего машина Тьюринга начинает работать. В процессе работы автомат будет выполнять команды до тех пор, пока не выполнит команду, которая переведет его в состояние q0. В табличном представлении программы соответствующая клетка называется клеткой останова. Дойдя до любой такой клетки, машина Тьюринга останавливается. Если клеток останова в программе нет или машина в процессе работы на них не попадает, то считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она рано или поздно дойдет до одной из клеток останова.
|