Тепловая машина
<<  Электрофорная машина Эксплуатация машин в строительстве  >>
Машина тьюринга
Машина тьюринга
Зачем нам нужно определение алгоритма
Зачем нам нужно определение алгоритма
Алгоритм – это автомат
Алгоритм – это автомат
Граф автомата
Граф автомата
Может ли автомат перемножать числа произвольной длины
Может ли автомат перемножать числа произвольной длины
Добавим к автомату бесконечную ленту
Добавим к автомату бесконечную ленту
Формальное определение машины Тьюринга
Формальное определение машины Тьюринга
Пример машины Тьюринга
Пример машины Тьюринга
Многоленточные и многоголовочные машины Тьюринга
Многоленточные и многоголовочные машины Тьюринга
Зачем придумали машину Тьюринга
Зачем придумали машину Тьюринга
Что должны знать все программисты
Что должны знать все программисты
Недетерминированная машина Тьюринга
Недетерминированная машина Тьюринга
Как определяется сложность алгоритмов
Как определяется сложность алгоритмов
Проблема на миллион долларов
Проблема на миллион долларов
Задача о занятом бобре
Задача о занятом бобре
Неоптимальное решение
Неоптимальное решение
Для тех, кто хочет попробовать себя в исследовании алгоритмов
Для тех, кто хочет попробовать себя в исследовании алгоритмов
Тьюрмиты и Тримувьи – плоские и пространственные машины Тьюринга
Тьюрмиты и Тримувьи – плоские и пространственные машины Тьюринга
Галерея изображений, построенных трехмерной машиной Тьюринга
Галерея изображений, построенных трехмерной машиной Тьюринга
Журнал «Компьютерные инструменты в школе»
Журнал «Компьютерные инструменты в школе»
Сайт журнала: www
Сайт журнала: www

Презентация на тему: «Машина тьюринга». Автор: Segey Pozdnyakov. Файл: «Машина тьюринга.ppt». Размер zip-архива: 1704 КБ.

Машина тьюринга

содержание презентации «Машина тьюринга.ppt»
СлайдТекст
1 Машина тьюринга

Машина тьюринга

Поздняков Сергей Николаевич pozdnkov@mail.ru

2 Зачем нам нужно определение алгоритма

Зачем нам нужно определение алгоритма

Можно ли написать программу для любой задачи? Например, существует ли программа, которая по тексту другой программы определяет, зациклится она или нет? Без строгого определения алгоритма ответ на этот вопрос невозможен.

3 Алгоритм – это автомат

Алгоритм – это автомат

У автомата есть строгое определение: Входные и выходные символы Состояния автомата Начальное состояние Функция перехода между состояниями Функция выхода

4 Граф автомата

Граф автомата

Автомат обычно изображается графом:

Это автомат для сложения двоичных чисел произвольной длины

5 Может ли автомат перемножать числа произвольной длины

Может ли автомат перемножать числа произвольной длины

Пусть такой автомат существует и имеет N состояний Умножим с его помощью число 10N+1+1 на себя: результат будет 10…010…01, где число нулей между соседними единичками равно N После того, как на выходе появятся первые N+2 цифры (исходное число), следующие N+1 цифр должны появится при пустом входе Сначала должны появится N нулей, но после этого атомат перейдёт в одно из пройденных состояний и последняя единичка никогда на выходе не появится

6 Добавим к автомату бесконечную ленту

Добавим к автомату бесконечную ленту

Автомат с присоединенной лентой и есть машина Тьюринга. Вот как изображают результат в «википедиях» на различных языках.

7 Формальное определение машины Тьюринга

Формальное определение машины Тьюринга

Алфавит (входной и выходной языки) Состояния. Начальное и конечное состояния. Функции перехода, вывода и сдвига вдоль ленты (R - вправо, L - влево, E - на месте). Их можно описать в форме таблицы, графа, набора «команд»

8 Пример машины Тьюринга

Пример машины Тьюринга

Проверка на чётность числа символов (единичек), записанных на ленте q1 1 –> q2 R * q2 1 –> q1 R * q1 * –> q0 E чётное q2 * –> q0 E нечётное

9 Многоленточные и многоголовочные машины Тьюринга

Многоленточные и многоголовочные машины Тьюринга

Реализовать содержательный алгоритм на машине Тьюринга очень трудоёмко, поэтому рассматривают более удобные вариации машины Тьюринга, сводящиеся к ней. Решим задачу проверки делимости натурального числа на меньшее: делимое будет записано на верхней ленте, а делитель – на нижней:

Q1(1,1) –> q1(r,r)(1,1) q1(1,*) –> q2(e,l)(1,*) q2(1,1) –> q2(e,l)(1,1) q2(1,*) –> q1(e,r)(1,*) q1(*,*) –> q0(e,e)(делится,*) q1(*,1) –> q0(e,e)(не делится,1)

10 Зачем придумали машину Тьюринга

Зачем придумали машину Тьюринга

Проблема останова Проблема самоприменимости

Предположим, что некто придумал алгоритм, который может определить, зацикливается ли любой представленный ему на анализ алгоритм или нормально заканчивает свою работу. Теперь, когда у нас есть строгое понятие алгоритма, мы можем переформулировать задачу так: некто придумал машину Тьюринга A, которая, читая команды любой другой машины Тьюринга X, может определить, придёт ли она когда-нибудь в конечное состояние. Тогда на основе этой машины Тьюринга мы сконструируем новую машину B, которая будет зацикливаться, при анализе машиной A останавливающейся машины X и останавливаться при анализе машиной A зацикливающейся машины X. Теперь машину B мы представим на анализ машине A. Каков будет ответ? Если X будет проанализирована как останавливающаяся, это будет означать, что B зацикливается, но X=B!!!

11 Что должны знать все программисты

Что должны знать все программисты

Из изложенного следует, что у теории алгоритмов есть границы. Не для каждой задачи можно построить решающий её алгоритм. Это должен знать каждый программист, который не хочет потратить свою жизнь на создание «вечного двигателя». Чем ещё полезна машина Тьюринга? На формализации идеи алгоритма построена теория сложности алгоритмов. Оказывается, что есть такие алгоритмы, которые работают так долго, что практически применять их невозможно. Для того, чтобы разделить «хорошие» алгоритмы от «плохих», рассмотрим понятие НЕДЕТЕРМИНИРОВАННОЙ машины Тьюринга.

12 Недетерминированная машина Тьюринга

Недетерминированная машина Тьюринга

Как построить машину Тьюринга для определения простоты числа на ленте? Можно воспользоваться предыдущей машиной Тьюринга для определения делимости Тогда для заданного числа N (N единичек на ленте) можно создать N-2 машины Тьюринга, на которых будет записано от 2 до N-1 единиц и запустить их всех сразу, если все машины дадут отрицательный результат, то число N-простое Такая конструкция называется недетерминированной машиной Тьюринга Понятно, что появление такого определения связано с решением задач «подбором» или более точно «перебором» всех вариантов

13 Как определяется сложность алгоритмов

Как определяется сложность алгоритмов

Предположим, что на ленте записано N символов и посчитаем, сколько шагов T сделает машина Тьюринга прежде, чем остановится. Зависимость T(N) и можно рассматривать как меру сложности алгоритма Для первого алгоритма (определение чётности числа) машина Тьюринга сделает N шагов, для второго (деление числа M на N) MN шагов Но во втором случае мы рассматривали многоленточную машину Тьюринга. Если заменить её машиной с одной лентой, то шагов будет существенно больше. Может ли тогда трудоемкость иметь порядок T2, T3 или больше? Может, но это всегда будет степенная функция! Поэтому все такие алгоритмы объединяют в один класс сложности P –алгоритмы ПОЛИНОМИАЛЬНОЙ сложности

14 Проблема на миллион долларов

Проблема на миллион долларов

В алгоритме для проверки простоты числа сразу работают N полиномиальных алгоритмов, класс сложности таких задач называют классом алгоритмов НЕДЕТЕРМИНИРОВАННОЙ ПОЛИНОМИАЛЬНОЙ сложности До сих пор неизвестно, можно ли их свести к обычным «непереборным» алгоритмам. Эта задача называется задачей P?NP и входит в число задач, поставленных для решения в XXI веке. Например, существует «задача коммивояжера», состоящая в том, что надо найти кратчаший маршрут между городами, соединенными транспортной сетью. Проверить, что предложенный маршрут меньше какого либо заданного числа просто, но найти маршрут, длина которого меньше заданного числа, трудно. Это и демонстрирует суть проблемы P?NP.

15 Задача о занятом бобре

Задача о занятом бобре

16 Неоптимальное решение

Неоптимальное решение

17 Для тех, кто хочет попробовать себя в исследовании алгоритмов

Для тех, кто хочет попробовать себя в исследовании алгоритмов

Сайт конкурса: www.kio.spb.ru/kio

18 Тьюрмиты и Тримувьи – плоские и пространственные машины Тьюринга

Тьюрмиты и Тримувьи – плоские и пространственные машины Тьюринга

19 Галерея изображений, построенных трехмерной машиной Тьюринга

Галерея изображений, построенных трехмерной машиной Тьюринга

20 Журнал «Компьютерные инструменты в школе»

Журнал «Компьютерные инструменты в школе»

Электронное приложение «Журнал в журнале»

21 Сайт журнала: www

Сайт журнала: www

kio.spb.ru/journal

Все, желающие найти статьи про машину Тьюринга, занятых бобров, тьюрмитов, тримувьев и прочее, могут получить БЕСПЛАТНЫЙ доступ к архивам журнала

Для этого надо зарегистрироваться на сайте журнала и отправить электронное письмо с просьбой открыть архивы Позднякову С.Н. pozdnkov@mail.ru

«Машина тьюринга»
http://900igr.net/prezentacija/fizika/mashina-tjuringa-112174.html
cсылка на страницу

Тепловая машина

11 презентаций о тепловой машине
Урок

Физика

134 темы
Слайды