Презентация Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма абсолютно бесплатно. Урок-презентация на эту тему содержит всего 22 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:22 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:89.50 kB
- Просмотров:72
- Скачиваний:3
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Элементы теоретического программирования
Машина Тьюринга – математическое понятие алгоритма
№2 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Каждой паре вида (si, qi), где siА и qiQ\{q0}, соответствует тройка (sj, t, qj), где sjA, tT и qjQ (q0 не участвует в парах (si, qi), так как паре (si, q0) уже ничего не соответствует, машина останавливается в заключительном состоянии q0).
№3 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Множество всех пар вида (si, qi), где siA и qiQ\{q0}, называется произведением множеств А и Q\{q0) и обозначается АQ\{q0). Аналогично, множество всех троек вида (sj, t, qj), где sjA, tT и qjQ, называется произведением множеств А, Т и Q и обозначается АТQ
№4 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Таким образом, программа машины Тьюринга представляет собой функцию с областью определения АQ\{q0}, принимающую значения из множества АТQ, или отображение первого множества во второе: АQ\{q0}ATQ
№5 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Машиной Тьюринга (МТ) называется система вида (A, s0, Q, q1, q0, T, ), где
А конечное множество алфавит МТ,
s0A и называется пустой буквой алфавита,
Q конечное множество, элементы которого называются состояниями МТ (Q множество состояний МТ),
q1Q, q1 начальное состояние МТ,
q0Q, q0 пассивное или заключительное состояние МТ,
Т={Л, Н, П} множество сдвигов МТ,
:АQ\{q0}ATQ, программа МТ.
№6 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Машина Тьюринга перерабатывает слова в алфавите машины согласно программе этой машины.
№7 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Какую бы МТ, имеющую алфавит
A={s0, s1, ..., sk}, состояния q0, q1, ..., qp и программу , мы ни взяли, можем считать, что имеется алгоритм, исходными объектами, промежуточными и окончательными результатами которого являются слова в алфавите А. Предписанием, задающим этот алгоритм, является программа .
№8 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Другими словами, с математической точки зрения МТ — это алгоритм для переработки слов в алфавите этой машины (ради удобства отождествляем МТ с ее программой).
№9 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Массовость алгоритма.
Множество исходных данных для алгоритма — множество всевозможных слов в алфавите А машины. Это множество бесконечно, его элементы записываются на ленте машины.
№10 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Результативность алгоритма.
Алгоритм по любому исходному данному позволяет в конечное число шагов получить результат. Программа МТ применяется единообразно ко всевозможным исходным данным и не меняется в процессе работы машины над исходным словом. Программа описывает переход от одного состояния к другому. Некоторое состояние опознается как заключительное. Появившееся при этом на ленте слово в алфавите А является результатом переработки слова, записанного на ленте в начальном состоянии машины.
№11 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Конструктивность объектов.
Исходные объекты, промежуточные и окончательные результаты для МТ — слова в алфавите А машины. Такие объекты являются конструктивными.
№12 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Детерминированность (определенность) алгоритма.
Программа составлена таким образом, что ее исполнение однозначно осуществимо. Действительно, программа — это совокупность команд вида siqjsmTqp, причем любые две различные команды не содержат одинаковых левых частей. При этом условии система команд не может требовать двух или более различных действий в одно и то же время.
№13 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Детерминированность (определенность) алгоритма.
Свойство детерминированности означает также, что применение программы к одному и тому же слову в алфавите А приводит к одному и тому же результату с одной и той же последовательностью состояний ленты.
№14 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Конечность предписания, задающего алгоритм.
Программа представляет собой конечное предписание, причем процесс вычислений протекает только согласно программе и исходным данным, ничего более не используется.
№15 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Нельзя ли задавать посредством МТ и другие известные нам алгоритмы, задаваемые обычно с помощью предписаний. Другими словами, насколько «богат» класс МТ? Быть может он включает все алгоритмы?
№16 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
Тезис Тьюринга:
Всякий алгоритм может быть задан посредством МТ
№17 слайд
Содержание слайда: Машина Тьюринга – математическое понятие алгоритма
В тезисе Тьюринга речь идет, с одной стороны, о понятии алгоритма, которое не является точным математическим понятием; с другой стороны, о точном математическом понятии — МТ. Значение этого тезиса и заключается в том, что он уточняет понятие алгоритма через математическое понятие — машину Тьюринга
№18 слайд
Содержание слайда: Классы задач не имеющих разрешающего алгоритма
Существует ли алгоритм, позволяющий по произвольному уравнению с целыми коэффициентами выяснить, имеет оно целочисленное решение или нет?
№19 слайд
Содержание слайда: Классы задач не имеющих разрешающего алгоритма
Существует ли алгоритм, позволяющий по любому ассоциативному исчислению выяснить, разрешима в нем проблема эквивалентности слов или нет?
№20 слайд
Содержание слайда: Машина Тьюринга ~
Нормальный алгоритм Маркова
Класс алгоритмов в форме машин Тьюринга и класс нормальных алгоритмов совпадают, эти алгоритмы равносильны.
№21 слайд
Содержание слайда: Машина Тьюринга ~
Нормальный алгоритм Маркова
Иными словами, для каждого алгоритма из класса машин Тьюринга существует равносильный ему алгоритм в классе нормальных алгоритмов, и наоборот.
№22 слайд
Содержание слайда: Машина Тьюринга ~
Нормальный алгоритм Маркова
В этом смысле две математические теории алгоритмов: теория нормальных алгоритмов и теория машин Тьюринга, считаются эквивалентными (равносильными).
Скачать все slide презентации Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма одним архивом:
