10 класс Тема урока: Машина Тьюринга. Выполнила учитель информатики МАОУ «Гимназия 37» г.Казани Хуснутдинова Р.Р. - презентация

1 10 класс Тема урока: Машина Тьюринга. Выполнила учитель информатики МАОУ «Гимназия 37» г.Казани Хуснутдинова Р.Р.

2 1. Историческая справка Историческая справка 2. Разминка Разминка 3. Машина Тьюринга Машина Тьюринга 4. Решение задач Решение задач 5. Применение машины Тьюринга Применение машины Тьюринга 6. Домашнее задание Домашнее задание

3 Алан Матисон Тьюринг ( – ) английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики.. В 1936 году Тьюринг предложил проект простого устройства, имеющего все основные свойства современной информационной системы: программное управление, память, и пошаговый способ действий. Эта воображаемая машина, получившая название «машины Тьюринга», используемая в теории автоматов или компьютеров позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

4 Машина Тьюринга является расширением модели конечного автомата и способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому Память об Алане Тьюринге Одна из ежегодных наград Ассоциации вычислительной техники называется Премия Тьюринга, в народе ее называют нобелевская для программистов.

5 У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 3 2. умножь на 4 Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд. +3 * 4 ОТВЕТ: ОТВЕТ:

6 для всякой ли задачи обработки информации может быть построен алгоритм решения В 30-х годах XX века возникает новая наука теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

7 1) неограниченная в обе стороны лента, разделенная на ячейки; 2) автомат (головка для считывания/записи, управляемая программой). 3) Алфавит (состояний и внешний)

8 Бескон. лента Алфавит состояний запускALGO2000

9 Что умеет воображаемая машина? За один такт работы она может: изменить содержимое обозреваемой ячейки памяти, т.е. заменить содержащуюся в ней букву алфавита другой; совершить сдвиг влево или вправо на одну ячейку или остаться на месте и изменить свое внутреннее состояние.

10 Дискретность Понятность Детерминированность Результативность. Массовость.

11 Задача 1 На ленте МТ находится десятичное число. Прибавить к этому числу 1. Автомат обозревает некую цифру входного числа 125 Q0 – поиск последней цифры числа Q1 – изменение значения последней цифры на 1 6

12

13 Задача 2 На ленте МТ находится натуральное число N>1. Разработать алгоритм МТ, которая уменьшала бы заданное число N на 1. Автомат обозревает правую цифру числа

14

15 Для лучшего понимания термина «алгоритм» Для понимания принципов работы ЭВМ, в связи с наличием общих свойств: наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.

16 1. Задача На ленте МТ находится натуральное число N. Разработать алгоритм машины Тьюринга, который бы умножил заданное число на 2 2. Творческое задание. Выяснить, что такое «Тест Тьюринга»

17 Оцените свою работу на уроке: На уроке было скучно и ничего не понятно Все получилось, урок удался

18

19 1. Шаблон презентации dlya-oformleniya-prezentatsiy-ms-powerpoint-po Портреты Тьюринга: a) Turing.jpghttp:// Turing.jpg b) ru.yandex.net/i?id=885138e8d9dc781a85e426c1e8b829dd &n=21http://im0-tub- ru.yandex.net/i?id=885138e8d9dc781a85e426c1e8b829dd &n=21 3. Машина Тьюринга: 4. Биография Тьюринга: 5. Изображение Калькулятор: tbn1.gstatic.com/images?q=tbn:ANd9GcS0169cTfiZCK_rtf6N8p 0KWvykp9gyYcor0ksSUctVJ9C8JL00Cg

20 6. Изображение на слайде 15: 7. Изображение компьютера а) tbn3.gstatic.com/images?q=tbn:ANd9GcRYN3sVlt5OlGzmrN x2ZSycg5lV4tCqzZPM1IOORKD9LerZBBZEJghttps://encrypted- tbn3.gstatic.com/images?q=tbn:ANd9GcRYN3sVlt5OlGzmrN x2ZSycg5lV4tCqzZPM1IOORKD9LerZBBZEJg б) tbn3.gstatic.com/images?q=tbn:ANd9GcSu8kUcHo_zaLwn6d arXiFMbAH5MfDf-7jxiW8UR0_DfOaxir1t2Ahttps://encrypted- tbn3.gstatic.com/images?q=tbn:ANd9GcSu8kUcHo_zaLwn6d arXiFMbAH5MfDf-7jxiW8UR0_DfOaxir1t2A 8. ALGO Чепкунова Е.Г. 9. Чепкунова Е.Г.«Основы теории кодирования информации и теории алгоритмов» Казань – 2009, 60 с.