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

Доказывать эту теорему будем методом индукции.

Для n=1 ( n - кол-во ходов в игре):

На рисунке 2 показано дерево игры из одного хода где К - максимальное количество предметов, которое можно взять за один ход; символ * обозначает либо ‘-‘ или ‘+’, т.е. выигрыш А, или выигрыш В соответственно.

·

Рис.2. Дерево игры из одного хода

Тогда ходы, заканчивающиеся ‘+’ и образуют выигрышную стратегию для игрока А. Если среди * есть хотя бы один ‘+’, то А имеет выигрышную стратегию, если нет, то B выигрывает всегда, т.е. он имеет выигрышную стратегию.

2) По индукции: пусть утверждение теоремы верно для n=S, докажем, что оно верно и для S+1. На рисунке 3 показано дерево игры S+1 ходов, где g - поддеревья, для игры не более, чем из S ходов .

Поскольку g: - дерево игры из не более, чем S ходов, то для него утверждение теоремы верно. Поэтому, если среди * в gесть хотя бы один ‘+’ , то существует выигрышное поддерево (g) (по предположению индукции) и, следовательно, А выиграл. В противном случае выиграл В. Итак, мы доказали существование решения для рассматриваемой проблемы.

Оказывается, что эта теорема верна и для игр, где возможна ничья. Следовательно, она верна и для шахмат! Но тогда, если есть выигрышная стратегия для шахмат, то почему мы говорим об искусстве шахмат? Зачем нужны чемпионаты мира?

Применительно к играм, подобным шахматам, эта теорема показывает, что рассматриваемая проблема лишь потенциально разрешима. Дело в том, что построение дерева игры, такой как шахматы, и его анализ потребует для современных вычислителей времени больше, чем время жизни одного человека или время от поломки до поломки исполнителя.

Таким образом, мы приходим к понятиям о потенциально разрешимых проблемах и практически разрешимых. У потенциально разрешимой проблемы вычислительный процесс даже у самого эффективного алгоритма может оказаться сколь угодно длинным. Конечным, но сколь угодно длинным. Больше, чем, например, жизнь заказчика, которого интересует решение проблемы. У практически разрешимых, вычислительный процесс всегда реализуем за приемлемое для заказчика время. Иными словами, сложность алгоритма у практически разрешимой проблемы имеет разумную с точки зрения заказчика величину.

·

*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.