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

Презентация: Элементы теоретического программирования
1 из 22
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
2.0
1 оценка

Комментарии

Нет комментариев для данной презентации

Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.


Добавить свой комментарий

Аннотация к презентации

Презентация для студентов на тему "Элементы теоретического программирования" по информатике. Состоит из 22 слайдов. Размер файла 0.09 Мб. Каталог презентаций в формате powerpoint. Можно бесплатно скачать материал к себе на компьютер или смотреть его онлайн.

Содержание

  • Презентация: Элементы теоретического программирования
    Слайд 1

    Элементы теоретического программирования

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

  • Слайд 2

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

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

  • Слайд 3

    Множество всех пар вида (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

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

Посмотреть все слайды

Сообщить об ошибке