Интуитивное понятие алгоритма и его свойств (стр. 3 из 3)
Применительно к играм, подобным шахматам, эта теорема показывает, что рассматриваемая проблема лишь потенциально разрешима. Дело в том, что построение дерева игры, такой как шахматы, и его анализ потребует для современных вычислителей времени больше, чем время жизни одного человека или время от поломки до поломки исполнителя.
Таким образом, мы приходим к понятиям о потенциально разрешимых проблемах и практически разрешимых. У потенциально разрешимой проблемы вычислительный процесс даже у самого эффективного алгоритма может оказаться сколь угодно длинным. Конечным, но сколь угодно длинным. Больше, чем, например, жизнь заказчика, которого интересует решение проблемы. У практически разрешимых, вычислительный процесс всегда реализуем за приемлемое для заказчика время. Иными словами, сложность алгоритма у практически разрешимой проблемы имеет разумную с точки зрения заказчика величину.
· 
*1 · 
*2 .......... · *к 
Рис.3. Дерево для игры из S+1 ходов.
Теперь изучим вопрос: что будет, если на вход алгоритма попадут данные не из множества исходных данных. Такое действительно может произойти, если исполнитель не проверит поступившие данные на принадлежность к исходным данным, либо если в алгоритме не предусмотрено соответствующих проверок, либо если само множество исходных данных четко не определено.
Алгоритм:
Исходное данное умножь на 2;
Прибавь к произведению 1;
Раздели сумму на 3;
Раздели исходное данное на остаток.
Если остаток от последнего деления равен 0, то стоп.
Рассмотрим вычислительный процесс для исходных данных:
| 6 | 7 | |
| 1. | 12 | 14 |
| 2. | 13 | 15 |
| 3. | 4 (1 в остатке) | 5 (0 в остатке) |
| 4. | 6 | 7:0? |
В случае исходных данных 7 вычислительный процесс становится не определенным. Рассмотрим еще один пример.
Исходные данные: слова в алфавите {a,b};
Действия: aP ® Pb, baP ® Paba, где P - любое слово в алфавите {a,b};
Правило остановки: Р= aaW, где W - результат.
Рассмотрим вычислительный процесс этого алгоритма для слов babaa; baaba; abaab.
babaa ® baaaba ® aabaaba стоп.
baaba ® abababa ® baabab ® abababa ® bababab ® babababa ®
® ...не останавливается.
abaab ® baabb ® abbaba ® bbabab …нет правила на этот случай.
Случаи 2, 3 демонстрируют примеры исходных данных, к которым алгоритм не применим. Эти примеры показывают важность проблемы строгого определения и проверки исходных данных.
Рассматриваемые примеры - это частные случаи более общей проблемы, которую называют проблемой применимости и формулируют так:
Построить алгоритм, который по алгоритму и исходным данным определяет, применим ли алгоритм к этим данным.
(Как мы увидим позднее, эта проблема имеет решение не всегда.)
Теперь уместно задать вопрос: для всякой ли массовой проблемы существует алгоритм? Как мы уже отмечали, Гедель дал отрицательный ответ на этот вопрос. Существуют проблемы, для решения которых нет алгоритмов. Примером одной из таких проблем является 10-я проблема Гильберта:
построить алгоритм решения диофантовых уравнений.
Пример диофантова уравнения: X2 + Y2 - Z2 = 0 , где
X, Y и Z - целые числа.
Одно из решений: X=3, Y=4, Z=5.
В 1969г. отечественный математик Ю.В. Матеясевич показал, что не существует алгоритма для решения произвольного диофантова уравнения.
Итак, подведем итоги:
Не для всякой массовой проблемы существует алгоритм;
Для одной и той же проблемы могут существовать разные алгоритмы с разной сложностью;
Алгоритм определяет последовательность действий;
Данные, алгоритм и вычислительный процесс - конструктивные объекты;
Исходные данные образуют класс, описываемый некоторым языком;
Алгоритм и исходные данные определяют вычислительный процесс полностью;
При одних и тех же исходных данных алгоритм всегда дает один и тот же результат;
Алгоритм одинаково понимается всеми исполнителями.
Алгоритм - точное предписание, которое задает потенциально осуществимый вычислительный процесс, начинающийся с произвольного исходного данного, из класса исходных данных, к которым данный алгоритм применим, и направленный на получение результата, полностью определенного этими исходными данными.
Основные свойства алгоритма:
Массовость;
Потенциальная осуществимость (конечность, сложность);
Детерминированность;
Однозначность понимания всеми исполнителями.
Вопросы :
Что определяет алгоритм?
Что такое вычислительный процесс?
Всегда ли по алгоритму можно определить точное число действий в вычислительном процессе?
2х2 = 4 - это алгоритм ?
Что такое численный алгоритм?
Всегда ли алгоритм дает точное решение?
Что означает массовость алгоритма?
Что такое конструктивный объект?
Отметить какие из нижеперечисленных объектов являются конструктивными - число 2, множество натуральных чисел, множество текстов на русском языке.
Что означает потенциальная осуществимость алгоритма?
Всякий ли алгоритм должен быть потенциально осуществим?
Что такое сложность алгоритма?
В каких единицах измеряется сложность алгоритма?
Можно ли сказать, что понятие области определения функции есть аналог множества исходных данных для алгоритма?
Как отличить результат от исходных данных и промежуточных результатов?