Четверг, 28.03.2024, 21:45
Приветствую Вас Гость | RSS
Главная | "МПК"-2010-Второй этап | Регистрация | Вход
Меню сайта
Наш опрос
Проголосуй за наш сайт
Форма входа
Календарь новостей
«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031
Поиск
Друзья сайта
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Конкурсы и олимпиады

"Мой помощник - компьютер" 2010

Второй этап. 26 января - 24 февраля

 
Задания второго этапа будут сформулированы в виде задач. Решения задач нужно отправлять вложением в электронное письмо в виде файла в формате Word2003. Пример оформления решения в виде таблицы можно посмотреть на этой странице в рубрике Справка. Дополнительно, если установлено рекомендованное приложение с сайта www.loonies.narod.ru, можно добавлять вложение с решением в формате этого приложения (.alg).
Ответы отсылать по адресу scpinerPVV@yandex.ru по мере решения, желательно в срок до обнародования очередной задачи. Обязательно указывайте тему письма МПК_Фамилия_задача*, где * - номер задачи.
По любым вопросам можно писать в форум Этап второй. Активность в форуме оценивается.
 
Тексты задач можно скачать:
Задача1 (до 29 января)
Задача2 (до 2 февраля)
Задача3 (до 6 февраля)
Задача4 (до 11 февраля)
Задача5 (до 16 февраля)
Задача6 (до 24 февраля)
 

Сроки решения задач являются условными. Можно решать не все задачи

Справка
Английским математиком А.Тьюрингом (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. В табличном представлении программы соответствующая клетка называется клеткой останова. Дойдя до любой такой клетки, машина Тьюринга останавливается.
Если клеток останова в программе нет или машина в процессе работы на них не попадает, то считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она рано или поздно дойдет до одной из клеток останова.
Конструктор сайтов - uCozCopyright ШЦМИ и Точка роста © 2024