Элементы теории алгоритмов Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Проверка домашнего задания Приложение2.doc Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Уточнение понятия алгоритма Машина Тьюринга Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Проблема разрешимости в теории алгоритмов Если задача имеет решение, то известен ходя бы один алгоритм её решения. Если же задачу решить нельзя, то её следует отнести к разряду алгоритмически неразрешимых. А что такое АЛГОРИТМ??? Формальное (математически строгое) определение алгоритма ввели независимо друг от друга в 1936 году Алан Тьюринг и Эмиль Пост. Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Существует ли алгоритм, позволяющий сконструировать машину, предназначенную для перевода чисел из унарной системы счисления в десятичную? Цель создания Тьюрингом абстрактной воображаемой машины – получение возможности доказательства существования или несуществования алгоритмов решения различных задач. Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Машина Тьюринга Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Объекты, с которыми работают алгоритмы Алфавит – конечный набор различных символов, используемых в алгоритме. Буквы – символы алфавита. Слово в алфавите – любая конечная последовательность букв некоторого алфавита. Длина слова – количество букв в слове. Пустое слово – слово, в котором нет букв (а 0 ). Входное слово – слово, к которому применяется алгоритм. Выходное слово – слово, получаемое в результате работы алгоритма. Область применимости алгоритма – совокупность слов, к которым применим алгоритм. Кодирование – замена одного алфавита другим. Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Описание машины Тьюринга Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач. Машина Тьюринга Бесконечная лента, разделённая на ячейки (запоминающее устройство) Автомат (головка считывания/записи, управляемая программой) Два конечных алфавита (для разных МТ могут быть разными): 1.Алфавит входных символов (внешний) А={а 0, а 1, …,а m } 2.Алфавит состояний (внутренний) Q={q 0, q 1, …,q p } Состояние q 0 – пассивное (машина закончила работу) Состояние q 1 – начальное (машина начинает работу) Ячейка a 0 – пустая буква (признак того, что ячейка пуста) Клетка останова – клетка, в которой записано, что автомат должен перейти в состояние q 0 (дойдя до неё, машина останавливается). Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Виды команд машины Тьюринга 1.Написать новую букву в обозреваемую ячейку 2.Выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н) 3.Перейти в новое состояние. а0а0 а1а1 …аiаi …аjаj q0q0 q1q1 …a k {ЛПН} q m qiqi … qjqj 111*11 q0q0 ^ Указание о смене символа Указание о сдвиге каретки Указание о смене внутреннего состояния Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а0а0 01 q1q1 1Пq 1 0Пq 1 1Пq 1 а0а0 01 q1q1 1Нq 0 0Пq 1 1Пq 1 Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Пример машин Тьюринга Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б». а0а0 абв…я q1q1 а 0 Н !б Л q 1 в Л q 1 … я Л q 1 у у б а а б р р у бараб а б б а абба Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а0а …789 q1q1 1Нq 0 2Нq 0 3Нq 0 4Нq 0 5Нq 0 … 8Нq 0 9Нq 0 0Лq 1 а0а …789 q1q1 1Н! 2Н!3Н!4Н!5Н! … 8Н!9Н!0Лq 1 Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. а0а0 +– q1q1 а 0 Л q 2 + П q 1 q2q2 а 0 Н !+ Л q 3 q3q3 а 0 Н ! – Л q 2 q 1 – машина ищет правый конец числа; q 2 – пропускает знак «+», при достижении конца последовательности – останов; q 3 – знак «+» заменяет на «–». Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

1. Опишите, какой алгоритм выполняет данная машина Тьюринга. Известно, что в начальном состоянии автомат обозревает самый левый символ входного слова. а0а0 01 q1q1 а0Н!а0Н!1Пq 1 0Пq 1 2. Дана десятичная запись натурального числа n > 1. Разработайте машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q 1 обозревает правую цифру числа. Кроме самой программы- таблицы опишите словами, что выполняется машиной в каждом состоянии. Задачи на построение машин Тьюринга Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Перевод чисел из унарной системы счисления в десятичную Построить машину Тьюринга для подсчёта штрихов, которые располагаются подряд и образуют входное слово, при этом требуется стереть все штрихи и записать на ленте их количество в десятичной системе. а0а0 0123…789/ q1q1 q2q2 q3q3 bkbk b k-1 …b1b1 b0b0 //…/ q 1 – q 2 – q 3 – Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

Итоги работы Номер группыКоличество баллов Результат Группа 1 Группа 2 Группа 3 Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010

1.Касаткин В.Н. Информация, алгоритмы, ЭВМ: Пособие для учителя. – М.: Просвещение, Андреева Е.В. Математические основы информатики. Элективный курс: Учебное пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина – 2-е изд., испр. – М.: БИНОМ. Лаборатория Знаний, Андреева Е.В. Математические основы информатики. Элективный курс: Методическое пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина –М.: БИНОМ. Лаборатория Знаний, Программная система моделирования работы машины Тьюринга Источники: Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010