LOGO Необходимость уточнения понятия алгоритм. Длительное время интуитивного понятия алгоритма было достаточно. - презентация

1 LOGO Необходимость уточнения понятия алгоритм

2 Длительное время интуитивного понятия алгоритма было достаточно

3 Пусть имеется массовая задача Если найден алгоритм (в интуитивном смысле) для ее решения, то не требуется другого определения алгоритма

4 Если после длительных попыток нахождения алгоритма возникает гипотеза, что такого алгоритма не существует, то доказать эту гипотезу на основе интуитивного определения алгоритма нельзя

5 Для доказательства несуществования алгоритма необходимо располагать точным определением понятия алгоритм

6 В 1900 году Давид Гильберт на 2-м Международном математическом конгрессе в Париже огласил 23 трудных математических проблемы Пример Давид Гильберт ( ) – выдающийся немецкий математик-универсал. В е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков

7 Десятая проблема Гильберта Найти алгоритм, применение которого к алгебраическому уравнению с целыми коэффициентами (с произвольным числом неизвестных) приводило бы к результату «да», если уравнение имеет целые решения и к результату «нет» – в противном случае

8 Десятая проблема Гильберта Для частного случая (уравнения с одним неизвестным) такой алгоритм есть Если уравнение с целыми коэффициентами имеет целый корень, то он обязательно является делителем свободного члена a n

9 Десятая проблема Гильберта Можно предложить такой алгоритм: 1)Найти все делители a n : d 1, d 2, …, d k 2)Вычислить P n (x) для каждого d i, i = 1..k 3)Если P n (d i ) = 0, то d i – корень уравнения

10 В 1970 году ленинградский ученый Ю.В. Матиясевич успешно завершил работу ряда математиков над доказательством того, что требуемый алгоритм невозможен Юрий Владимирович Матиясевич (род ) – советский и российский математик, исследователь Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН, академик РАН, доктор физико-математических наук. Внес существенный вклад в теорию вычислимости, завершив решение десятой проблемы Гильберта Десятая проблема Гильберта

11 Направления формализации понятия алгоритм

12 Алонзо Чёрч ( ) – американский математик и логик. Разработал теорию лямбда- исчислений, которая позволила показать существование т.н. «неразрешимых задач» Вместе с Тьюрингом показал, что лямбда-исчисления и машина Тьюринга имеют одинаковые свойства – тезис Чёрча-Тьюринга 1. Рекурсивные функции Стивен Коул Клини ( ) – американский математик. Участвовал в разработке теории вычислимости, известен изобретением регулярных выражений, внес важный вклад в теорию конечных автоматов

13 Курт Фридрих Гёдель ( ) – австрийский логик, математик и философ математики. Наиболее известный по сформулированной и доказанной им теоремой о неполноте (1931 г.) Теорема о неполноте: Любая эффективно аксиоматизируемая теория, в достаточно богатом языке, достаточном для определения натуральных чисел и операций сложения и умножения является неполной либо противоречивой. Неполнота означает наличие высказываний, которые нельзя ни доказать, ни опровергнуть, исходя из аксиом этой теории. Противоречивость возможность доказать любое высказывание: как истинное так и ложное. 1. Рекурсивные функции

14 Курт Фридрих Гёдель ( ) – австрийский логик, математик и философ математики. Кроме того, Гёдель написал работу по общей теории относительности, в которой предложил вариант решения уравнений Эйнштейна, из которого следует, что строение вселенной может иметь такое устройство, в котором течение времени является закольцованным (метрика Гёделя), что теоретически допускает путешествия во времени. Большинство современных физиков считают это решение верным лишь математически и не имеющим физического смысла. 1. Рекурсивные функции

15 В алгоритмическом процессе вычисляется значение некоторой функции f(x 1, x 2, …, x n ), определенной на множестве натуральных чисел Понятие алгоритма отождествляется со строгим математическим понятием «частично рекурсивная функция»

16 Алан Тьюринг ( ) – английский математик, логик и криптограф. Предложенная им в 1936 году абстрактная вычислительная машина Тьюринга позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследованиях 2. Машина Тьюринга Теорема Гёделя о неполноте побудила Тьюринга доказать, что нет общего метода определения истинности и, таким образом, математика всегда будет содержать недоказуемые высказывания

17 Алан Тьюринг ( ) – английский математик, логик и криптограф. 2. Машина Тьюринга Во время Второй мировой войны Тьюринг работал криптографом для раскрытия кода немецкой военной шифровальной машины «Энигма». Немцы пребывали в уверенности, что их система неуязвима. Но опираясь на работы польских математиков, А.Тьюринг совместно с У.Уэлчманом раскрыл шифры, создав дешифровочную машину «Бомба».

18 Эмиль Леон Пост ( (Польша) ) – американский математик и логик. Предложил абстрактную машину Поста 2. Машина Тьюринга Машина Поста отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

19 2. Машина Тьюринга Алгоритмический процесс – работа некоторой «абстрактной вычислительной машины». Каждая отдельная машина Тьюринга выполняет только один алгоритм Лучше подходит термин «программа машины Тьюринга» – набор инструкций, упрощенных до однотипной схемы Все машины Тьюринга отличаются программами, а общим является описание исполнителя (человек- вычислитель, действующий бездумно и неукоснительно, как машина)

20 3. Нормальные алгорифмы Маркова Алгоритмический процесс – переработка слов некоторого алфавита с помощью точно описанных правил переработки Андрей Андреевич Марков (младший) ( ) – советский математик, сын известного русского математика А.А.Маркова, основоположник советской школы конструктивной математики, автор понятия нормального алгоритма (1947 г.)

21 В последствии оказалось, что эти три варианта определения понятия алгоритма равносильны

22 Литература 1.Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, с. 2.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с. 3.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, с. 4.ВикипедиЯ. Свободная энциклопедия.

23 Многие готовы скорее умереть, чем подумать. Часто, кстати, так и бывает. Бертран Рассел