Ученики на Учителя.com


Презентация "Машины Тьюринга" 10 класс

Скачать материал
Подписи к слайдам:
Тема урока: Машина Тьюринга.
  • 10 класс
  • Выполнила учитель информатики
  • МАОУ «Гимназия №37» г.Казани
  • Хуснутдинова Р.Р.
  • Историческая справка
  • Разминка
  • Машина Тьюринга
  • Решение задач
  • Применение машины Тьюринга
  • Домашнее задание
  • Содержание
  • Из истории
  • Алан Матисон Тьюринг
  • (23.06.1912 – 7.06.1954)
  • — английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики.
  • .
  • В 1936 году Тьюринг предложил проект простого
  • устройства, имеющего все основные свойства
  • современной информационной системы: программное управление, память, и пошаговый способ действий. Эта воображаемая машина, получившая название «машины Тьюринга», используемая в теории автоматов или компьютеров позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.
  • Из истории
  • Машина Тьюринга является расширением модели конечного автомата и способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому
  • Память об Алане Тьюринге Одна из ежегодных наград Ассоциации вычислительной техники называется
  • Премия Тьюринга,
  • в народе ее называют
  • нобелевская для программистов.
  • Разминка
  • У исполнителя Калькулятор две команды, которым присвоены номера:
  • 1. прибавь 3
  • 2. умножь на 4
  • Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.
  • +3
  • * 4
  • ОТВЕТ: 2 2 1 1 1
  • В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
  • Машина Тьюринга
1) неограниченная в обе стороны лента, разделенная на ячейки;
  • 1) неограниченная в обе стороны лента, разделенная на ячейки;
  • 2) автомат (головка для считывания/записи, управляемая программой).
  • 3) Алфавит (состояний и внешний)
  • Описание машины Тьюринга
  • Бескон. лента
  • Алфавит состояний
  • запуск
  • ALGO2000
Что умеет воображаемая машина?
  • Что умеет воображаемая машина?
  • За один такт работы она может:
  • изменить содержимое обозреваемой ячейки памяти, т.е. заменить содержащуюся в ней букву алфавита другой;
  • совершить сдвиг влево или вправо на одну ячейку или остаться на месте и
  • изменить свое внутреннее состояние.
Дискретность
  • Дискретность
  • Понятность
  • Детерминированность
  • Результативность.
  • Массовость.
  • Свойства машины Тьюринга
  • как алгоритма
Задача 1
  • Задача 1
  • На ленте МТ находится десятичное число. Прибавить к этому числу 1. Автомат обозревает некую цифру входного числа
  • 1
  • 2
  • 5
  • Q0 – поиск последней цифры числа
  • Q1 – изменение значения последней цифры на 1
  • 6
  • Решение задач
Задача 2
  • Задача 2
  • На ленте МТ находится натуральное число N>1. Разработать алгоритм МТ, которая уменьшала бы заданное число N на 1. Автомат обозревает правую цифру числа.
  • 1
  • 0
  • 0
  • 9
  • 9
  • Решение задач
Для лучшего понимания термина «алгоритм»
  • Для лучшего понимания термина «алгоритм»
  • Для понимания принципов работы ЭВМ, в связи с наличием общих свойств: наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.
  • Применение машины Тьюринга
  • Домашнее задание
  • Задача
  • На ленте МТ находится натуральное число N. Разработать алгоритм машины Тьюринга, который бы умножил заданное число на 2
  • Творческое задание.
  • Выяснить, что такое «Тест Тьюринга»
Оцените свою работу на уроке:
  • Оцените свою работу на уроке:
  • Рефлексия
  • На уроке было скучно и ничего не понятно
  • Все получилось, урок удался
  • Спасибо
  • за работу на уроке!
Источники
  • Шаблон презентации
  • http://nsportal.ru/shkola/informatika-i-ikt/library/2011/07/12/shablon-dlya-oformleniya-prezentatsiy-ms-powerpoint-po
  • Портреты Тьюринга:
  • http://www.pcworld.al/wp-content/uploads/2012/06/Alan-Turing.jpg
  • http://im0-tub-ru.yandex.net/i?id=885138e8d9dc781a85e426c1e8b829dd-04-144&n=21
  • 3. Машина Тьюринга:
  • http://aturingmachine.com
  • 4. Биография Тьюринга:
  • http://www.personbio.com/view_post.php?id_info=278
  • 5. Изображение Калькулятор:
  • https://encrypted-tbn1.gstatic.com/images?q=tbn:ANd9GcS0169cTfiZCK_rtf6N8p0KWvykp9gyYcor0ksSUctVJ9C8JL00Cg
Источники
  • 6. Изображение на слайде 15:
  • http://education.simcat.ru/school63/info/241
  • 7. Изображение компьютера
  • а) https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcRYN3sVlt5OlGzmrNx2ZSycg5lV4tCqzZPM1IOORKD9LerZBBZEJg
  • б) https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcSu8kUcHo_zaLwn6darXiFMbAH5MfDf-7jxiW8UR0_DfOaxir1t2A
  • 8. ALGO2000
  • http://www.fayloobmennik.net/1492236 Чепкунова Е.Г.
  • 9. Чепкунова Е.Г.«Основы теории кодирования информации и теории алгоритмов» Казань – 2009, 60с.

Информатика - еще материалы к урокам: