PPt4Web Хостинг презентаций

Главная / Информатика / Элементы теоретического программирования
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Элементы теоретического программирования


Скачать эту презентацию

Презентация на тему: Элементы теоретического программирования


Скачать эту презентацию



№ слайда 1 Элементы теоретического программирования Машина Тьюринга – математическое поняти
Описание слайда:

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

№ слайда 2 Машина Тьюринга – математическое понятие алгоритма Каждой паре вида (si, qi), гд
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Каждой паре вида (si, qi), где si А и qi Q\{q0}, соответствует тройка (sj, t, qj), где sj A, t T и qj Q (q0 не участвует в парах (si, qi), так как паре (si, q0) уже ничего не соответствует, машина останавливается в заключительном состоянии q0).

№ слайда 3 Машина Тьюринга – математическое понятие алгоритма Множество всех пар вида (si,
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Множество всех пар вида (si, qi), где si A и qi Q\{q0}, называется произведением множеств А и Q\{q0) и обозначается А Q\{q0). Аналогично, множество всех троек вида (sj, t, qj), где sj A, t T и qj Q, называется произведением множеств А, Т и Q и обозначается А Т Q

№ слайда 4 Машина Тьюринга – математическое понятие алгоритма Таким образом, программа маши
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Таким образом, программа машины Тьюринга представляет собой функцию с областью определения А Q\{q0}, принимающую значения из множества А Т Q, или отображение первого множества во второе: А Q\{q0} A T Q

№ слайда 5 Машина Тьюринга – математическое понятие алгоритма Машиной Тьюринга (МТ) называе
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Машиной Тьюринга (МТ) называется система вида (A, s0, Q, q1, q0, T, ), где А конечное множество алфавит МТ, s0 A и называется пустой буквой алфавита, Q конечное множество, элементы которого называются состояниями МТ (Q множество состояний МТ), q1 Q, q1 начальное состояние МТ, q0 Q, q0 пассивное или заключительное состояние МТ, Т={Л, Н, П} множество сдвигов МТ, :А Q\{q0} A T Q, программа МТ.

№ слайда 6 Машина Тьюринга – математическое понятие алгоритма Машина Тьюринга перерабатывае
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Машина Тьюринга перерабатывает слова в алфавите машины согласно программе этой машины.

№ слайда 7 Машина Тьюринга – математическое понятие алгоритма Какую бы МТ, имеющую алфавит
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Какую бы МТ, имеющую алфавит A={s0, s1, ..., sk}, состояния q0, q1, ..., qp и программу , мы ни взяли, можем считать, что имеется алгоритм, исходными объектами, промежуточными и окончательными результатами которого являются слова в алфавите А. Предписанием, задающим этот алгоритм, является программа .

№ слайда 8 Машина Тьюринга – математическое понятие алгоритма Другими словами, с математиче
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Другими словами, с математической точки зрения МТ — это алгоритм для переработки слов в алфавите этой машины (ради удобства отождествляем МТ с ее программой).

№ слайда 9 Машина Тьюринга – математическое понятие алгоритма Массовость алгоритма. Множест
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Массовость алгоритма. Множество исходных данных для алгоритма — множество всевозможных слов в алфавите А машины. Это множество бесконечно, его элементы записываются на ленте машины.

№ слайда 10 Машина Тьюринга – математическое понятие алгоритма Результативность алгоритма. А
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Результативность алгоритма. Алгоритм по любому исходному данному позволяет в конечное число шагов получить результат. Программа МТ применяется единообразно ко всевозможным исходным данным и не меняется в процессе работы машины над исходным словом. Программа описывает переход от одного состояния к другому. Некоторое состояние опознается как заключительное. Появившееся при этом на ленте слово в алфавите А является результатом переработки слова, записанного на ленте в начальном состоянии машины.

№ слайда 11 Машина Тьюринга – математическое понятие алгоритма Конструктивность объектов. Ис
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Конструктивность объектов. Исходные объекты, промежуточные и окончательные результаты для МТ — слова в алфавите А машины. Такие объекты являются конструктивными.

№ слайда 12 Машина Тьюринга – математическое понятие алгоритма Детерминированность (определе
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Детерминированность (определенность) алгоритма. Программа составлена таким образом, что ее исполнение однозначно осуществимо. Действительно, программа — это совокупность команд вида siqj smTqp, причем любые две различные команды не содержат одинаковых левых частей. При этом условии система команд не может требовать двух или более различных действий в одно и то же время.

№ слайда 13 Машина Тьюринга – математическое понятие алгоритма Детерминированность (определе
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Детерминированность (определенность) алгоритма. Свойство детерминированности означает также, что применение программы к одному и тому же слову в алфавите А приводит к одному и тому же результату с одной и той же последовательностью состояний ленты.

№ слайда 14 Машина Тьюринга – математическое понятие алгоритма Конечность предписания, задаю
Описание слайда:

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

№ слайда 15 Машина Тьюринга – математическое понятие алгоритма Нельзя ли задавать посредство
Описание слайда:

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

№ слайда 16 Машина Тьюринга – математическое понятие алгоритма Тезис Тьюринга: Всякий алгори
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма Тезис Тьюринга: Всякий алгоритм может быть задан посредством МТ

№ слайда 17 Машина Тьюринга – математическое понятие алгоритма В тезисе Тьюринга речь идет,
Описание слайда:

Машина Тьюринга – математическое понятие алгоритма В тезисе Тьюринга речь идет, с одной стороны, о понятии алгоритма, которое не является точным математическим понятием; с другой стороны, о точном математическом понятии — МТ. Значение этого тезиса и заключается в том, что он уточняет понятие алгоритма через математическое понятие — машину Тьюринга

№ слайда 18 Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющ
Описание слайда:

Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющий по произвольному уравнению с целыми коэффициентами выяснить, имеет оно целочисленное решение или нет?

№ слайда 19 Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющ
Описание слайда:

Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющий по любому ассоциативному исчислению выяснить, разрешима в нем проблема эквивалентности слов или нет?

№ слайда 20 Машина Тьюринга ~ Нормальный алгоритм Маркова Класс алгоритмов в форме машин Тью
Описание слайда:

Машина Тьюринга ~ Нормальный алгоритм Маркова Класс алгоритмов в форме машин Тьюринга и класс нормальных алгоритмов совпадают, эти алгоритмы равносильны.

№ слайда 21 Машина Тьюринга ~ Нормальный алгоритм Маркова Иными словами, для каждого алгорит
Описание слайда:

Машина Тьюринга ~ Нормальный алгоритм Маркова Иными словами, для каждого алгоритма из класса машин Тьюринга существует равносильный ему алгоритм в классе нормальных алгоритмов, и наоборот.

№ слайда 22 Машина Тьюринга ~ Нормальный алгоритм Маркова В этом смысле две математические т
Описание слайда:

Машина Тьюринга ~ Нормальный алгоритм Маркова В этом смысле две математические теории алгоритмов: теория нормальных алгоритмов и теория машин Тьюринга, считаются эквивалентными (равносильными).

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru