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

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

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

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

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

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

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

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

8 Описание машины Тьюринга Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач. Машина Тьюринга Бесконечная лента, разделённая на ячейки (запоминающее устройство) Автомат (головка считывания/записи, управляемая программой) Два конечных алфавита (для разных МТ могут быть разными): 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

9 Виды команд машины Тьюринга 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

10 Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а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

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

12 Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а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

13 Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии 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

14 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

15 Перевод чисел из унарной системы счисления в десятичную Построить машину Тьюринга для подсчёта штрихов, которые располагаются подряд и образуют входное слово, при этом требуется стереть все штрихи и записать на ленте их количество в десятичной системе. а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

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

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