Уроки 58 - 60
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Зачем нужно определение алгоритма?
Зачем нужно определение алгоритма?
Как вы знаете, алгоритмом называют точный набор инструкций для исполнителя, который приводит к решению задачи за конечное время.
Особый интерес проявляли к алгоритмам математики. Один из древнейших известных алгоритмов — алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух натуральных чисел. Само слово «алгоритм» (от имени математика IX века аль-Хорезми, которого считают основателем алгебры) ввёл в науку в XVII веке немецкий математик Г. В. Лейбниц.
Долгое время считалось, что для любой математической задачи можно найти метод (алгоритм) решения, просто для ряда задач такие алгоритмы ещё не найдены. Эту идею высказал аль-Хорезми, такой же точки зрения придерживались и другие математики вплоть до начала XX века.
Однако, несмотря на все усилия, решить некоторые задачи не удавалось в течение столетий. Например, безуспешно закончились многочисленные попытки найти алгоритм доказательства правильности любой теоремы на основе заданной системы аксиом.
В 1931 г. австрийский математик К. Гёдель доказал теорему о неполноте, смысл которой состоит в том, что в любой достаточно сложной формальной системе, основанной на аксиомах (например, в арифметике, где введены натуральные числа и операции сложения и умножения), есть утверждение, которое невозможно ни доказать, ни опровергнуть в рамках этой системы. Поэтому было высказано предположение о том, что некоторые задачи алгоритмически неразрешимы, т. е. для них в принципе не существует алгоритма решения, и поэтому искать его бессмысленно. Чтобы строго доказать или опровергнуть эту гипотезу, нужно было ввести математическое понятие алгоритма.
«Определение», которое мы привели в начале главы, часто называют интуитивным, потому что оно содержит такие «нематематические» понятия, как «точный набор», «инструкция», «исполнитель», «решение задачи». Эти термины невозможно записать строго, используя язык математики и логики, поэтому для математического доказательства такое определение не подходит.
Исследования в этой области, которые начали активно проводиться в 30-х годах XX века, привели к возникновению теории алгоритмов, которая занимается:
• доказательством алгоритмической неразрешимости задач;
• анализом сложности алгоритмов;
• сравнительной оценкой качества алгоритмов.
Значительный вклад в развитие теории алгоритмов внесли математики А. Тьюринг (Великобритания), Э. Пост (США), А. Чёрч (Великобритания), С. Клини (США) и А. А. Марков (СССР).
Следующая страница 
Что такое алгоритм?
Cкачать материалы урока
