Презентация на тему: В чем смысл эквивалентности машин Тьюринга и Поста и нормальных алгоритмов Маркова?
презентация к уроку

Слайд 1

В чем смысл эквивалентности машин Тьюринга и Поста и нормальных алгоритмов Маркова ? Государственное бюджетное общеобразовательное учреждение СОШ № 17 Василеостровского района Выполнила: Учитель информатики Мардарь Надежда Петровна г . Санкт – Петербург 2022г.

Слайд 2

То есть «конструктивно» машина Тьюринга, так же как и машина Поста, состоит из двух основных узлов: ленты с ячейками и каретки. Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной в предложенной им модели вычислений. Это предположение известно как тезис Черча—Тьюринга. Каждый компьютер может моделировать машину Тьюринга, для этого достаточно моделировать операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины. Значит , он может моделировать алгоритмы в машине Тьюринга, и из этого тезиса следует, что все компьютеры, независимо от мощности, архитектуры и других особенностей, с точки зрения принципиальной возможности решения алгоритмически разрешимых задач эк­вивалентны.

Слайд 3

Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930-х гг. Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс рекурсивно-вычислимых функций Черча были первыми формальными описаниями алгоритма, опирающимися на строго определенные модели вычислений. Сформулированные гипотезы Поста и Черча—Тьюринга постулировали эквивалентность предложен­ных ими моделей вычислений, как формальных систем, и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство существования алгоритмически неразрешимых проблем.

Слайд 4

В 1950-х гг. существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и основанный на теории формальных грамматик алгоритмический формализм Маркова — так называемые нормальные алгоритмы Маркова. Формаль­ные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой.

Слайд 5

Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели в 1960—1970-х гг. к практически значимым исследованиям алгоритмов и вычислительных задач. На этой основе впоследствии выделилось несколько разделов теории алгоритмов.

Слайд 6

Классическая теория алгоритмов : формулировка задач в терминах формальных языков; понятие задачи разрешения; описание сложностных классов задач; фор­мулировка в 1965 г. Эдмондсом проблемы P = NP; открытие класса TVP-полных задач и его исследование; введение новых моделей вычислений — алгебраического дерева вычислений (Бен- Op ), машины с произвольным доступом к памяти, схем алгоритмов Янова, стандартных схем программ Котова и др. Теория асимптотического анализа алгоритмов : понятие сложности и трудоем­кости алгоритма; критерии оценки алгоритмов; методы получения асимптотиче­ских оценок, в частности, для рекурсивных алгоритмов; асимптотический анализ трудоемкости или времени выполнения; получение теоретических нижних оценок сложности задач. В развитие этой теории внесли существенный вклад Кнут, Ахо , Хопкрофт , Ульман, Карп, Мошков, Кудрявцев и др . Теория практического анализа вычислительных алгоритмов: получение явных функций трудоемкости; интервальный анализ функций; практически значимые критерии качества алгоритмов; методики выбора рациональных алгоритмов. Ос­новополагающей работой в этом направлении, очевидно, следует считать фунда­ментальный труд Д. Кнута «Искусство программирования для ЭВМ». Методы создания эффективных алгоритмов включают в себя множество алго­ритмов, среди которых динамическое программирование, метод ветвей и границ, метод декомпозиции, «жадные» алгоритмы, специальные структуры данных и пр.

Слайд 7

Обобщая исследования в различных разделах теории алгоритмов, можно вы­делить следующие основные задачи и направления развития, характерные для современной теории алгоритмов: □ формализация понятия «алгоритм» и исследование формальных алгоритмиче­ских систем (моделей вычислений); □ доказательство алгоритмической неразрешимости задач; □ формальное доказательство правильности и эквивалентности алгоритмов; □ классификации задач, определение и исследование сложностных классов; □ доказательство теоретических нижних оценок сложности задач; □ получение методов разработки эффективных алгоритмов; □ асимптотический анализ сложности итерационных алгоритмов; □ исследование и анализ рекурсивных алгоритмов; □ получение явных функций трудоемкости алгоритмов; □ разработка классификаций алгоритмов; □ исследование емкостной (по ресурсу памяти) сложности задач и алгоритмов; □ разработка критериев сравнительной оценки ресурсной эффективности алго­ритмов и методов их сравнительного анализа.