Реферат: Интуитивное понятие алгоритма и его свойств

baaba ® abababa ® baabab ® abababa ® bababab ® babababa ®

® ...не останавливается.

abaab ® baabb ® abbaba ® bbabab …нет правила на этот случай.

Случаи 2, 3 демонстрируют примеры исходных данных, к которым алгоритм не применим. Эти примеры показывают важность проблемы строгого определения и проверки исходных данных.

Рассматриваемые примеры - это частные случаи более общей проблемы, которую называют проблемой применимости и формулируют так:

Построить алгоритм, который по алгоритму и исходным данным определяет, применим ли алгоритм к этим данным.

(Как мы увидим позднее, эта проблема имеет решение не всегда.)

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

построить алгоритм решения диофантовых уравнений.

Пример диофантова уравнения: X² + Y² - Z² = 0 , где

X, Y и Z - целые числа.

Одно из решений: X=3, Y=4, Z=5.

В 1969г. отечественный математик Ю.В. Матеясевич показал, что не существует алгоритма для решения произвольного диофантова уравнения.

Итак, подведем итоги:

Не для всякой массовой проблемы существует алгоритм;

Для одной и той же проблемы могут существовать разные алгоритмы с разной сложностью;

Алгоритм определяет последовательность действий;

Данные, алгоритм и вычислительный процесс - конструктивные объекты;

Исходные данные образуют класс, описываемый некоторым языком;

Алгоритм и исходные данные определяют вычислительный процесс полностью;

При одних и тех же исходных данных алгоритм всегда дает один и тот же результат;

Алгоритм одинаково понимается всеми исполнителями.

Алгоритм - точное предписание, которое задает потенциально осуществимый вычислительный процесс, начинающийся с произвольного исходного данного, из класса исходных данных, к которым данный алгоритм применим, и направленный на получение результата, полностью определенного этими исходными данными.

Основные свойства алгоритма:

Массовость;

Потенциальная осуществимость (конечность, сложность);

Детерминированность;

Однозначность понимания всеми исполнителями.

Вопросы :