Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Доказательство:

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

Для 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, то стоп.

Рассмотрим вычислительный процесс для исходных данных:

Рекомендуем скачать другие рефераты по теме: социально реферат, мцыри сочинение.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки