Интуитивное понятие алгоритма и его свойств (стр. 2 из 3)
Положи i равным i -1;
Положи r равным r+
; 
Если i = 0, то r - результат
иначе перейди к шагу 3;
Организацию вычислений по этому алгоритму можно пояснить вот таким выражением:
Этот метод вычисления значения полинома в точке называется схемой Горнера. Однако, есть и другой алгоритм для решения этих задач, который мы назовем прямым.
Исходные данные: те же, что и в предыдущем примере.
Результат: тот же.
Переменные: r, s, x - типа вещественный, i - типа целый.
Константы:
, п.Алгоритм:
Положи i равным п, s равным 0, х равным b;
Возведи х в степень i
Умножь
на степень;Положи s равной сумме s и произведения.
Если i = 0, то s - результат (стоп)
иначе положи i=i -1, перейди к шагу 2.
Организацию вычислений по этому алгоритму описывает выражение
Читателю предлагается построить вычислительные процессы для этих алгоритмов, например, для полинома
в точке 2, и убедиться, что это разные вычислительные процессы.Итак мы видим, что для решения одного и того же класса задач может существовать несколько алгоритмов, реализующих разные вычислительные процессы. Эти вычислительные процессы различаются набором действий и их количеством. Количество действий в вычислительном процессе - весьма важная характеристика алгоритма, т.к. оно определяет время и ресурсы исполнителя, необходимые для выполнения алгоритма.
Определение 1.8
Сложностью алгоритма называется количество действий в вычислительном процессе этого алгоритма.
Обратите внимание, именно в вычислительном процессе, а не в самом алгоритме.
Для того, чтобы сравнивать сложность разных алгоритмов, надо чтобы она подсчитывалась для них в терминах одинаковых действий. Например, умножь, сложи, положи. Выразим сложность действия возведения в степень i как (i - 1) операций умножения. Тогда, сложность первого алгоритма (по схеме Горнера) в виде числа операций сложения и умножения будет равна 2п. Для прямого алгоритма она будет равна:
Таким образом, первый алгоритм эффективнее второго.
Вывод: Для решения одного и того же класса задач существуют разные алгоритмы, разной сложности.
Теперь рассмотрим вопрос: всегда ли алгоритм дает точное решение? На примере алгоритмов деления в столбик и вычисления корня квадратного не трудно видеть, что, например, при вычислениях 20:3 и
, мы вынуждены довольствоваться лишь приблизительным решением.Теперь рассмотрим свойство массовости алгоритма, выражающееся в том, что алгоритм предназначен “для решения всех задач заданного класса”, т.е. множества задач. Здесь уместно вспомнить парадокс греческого философа Эвбулида "Что есть куча?" Один камень - это куча? Два - это куча? И т.д. В нашем случае наводящим соображением для решения возникшей проблемы является то, что все эти задачи различаются лишь исходными данными.
Массовость предполагает существование четко определенного класса объектов, которые могут быть исходными данными. Мощность этого класса - свойство класса объектов, а не алгоритма. Массовость означает существование языка данных, т.е. четких правил построения этих объектов, называемых данными, из некоторого, как правило, фиксированного множества базовых объектов, называемого алфавитом. Такие объекты в математике называются конструктивными объектами. Примерами конструктивных объектов могут служить слова в некотором фиксированном алфавите. Таким образом, данные - это слова в алфавите. В рассмотренных примерах исходными данными были числа. В данном случае мы можем рассматривать эти числа, как слова в алфавите {0,1,2,3,4,5,6,7,8,9,}. Позднее мы рассмотрим и другие нечисловые примеры, на которых покажем, что в нечисленных алгоритмах исходные данные - слова в определенном алфавите, т.е. конструктивные объекты. Итак, исходные данные - всегда конструктивные объекты.
До сих пор мы рассматривали лишь алгоритмы над числами, т.е. исходными данными были числа, а результатом - число. Рассмотрим проблему построения выигрышной стратегии для определенного класса игр. Выигрышная стратегия - это набор правил, следуя которым один из игроков обязательно выигрывает. Класс игр, который мы будем рассматривать, определим так:
Двое игроков ходят по очереди;
Обязательно выигрывает только один;
При выборе очередного хода случайность отсутствует;
Каждый играющий знает свои ходы и ходы противника.
Примером такой игры может служить игра “чет-нечет”. Есть шесть предметов и два игрока: А и В. Игрок может за один ход взять от 1 до 2 предметов. Проигрывает тот, кто берет последний предмет. Может ли А, который всегда начинает, “заставить” В взять последний предмет? Оказывается - да! Может! Его выигрышная стратегия очень проста: первым ходом он всегда берет два предмета; если число оставшихся предметов не 0 и В взял l предметов, то А должен взять 3-l предметов. (Читателю предлагается проверить этот факт пока экспериментально).
Первый вопрос, который здесь возникает, как представить игру? До сих пор мы имели дело лишь с числами. Нам же необходимо такое представление игры, которое бы позволило проанализировать все возможные комбинации ходов и найти характерные признаки только тех, которые ведут к победе А.
Воспользуемся для представления игры объектом, который в математике называется двоичное дерево. Двоичное дерево состоит из вершин и дуг, соединяющих вершины. У всех вершин, за исключением одной, есть только одна дуга, “заходящая” в эту вершину, и две дуги, “исходящие” из этой вершины. Единственная вершина, в которую “не заходит” ни одна дуга, называется корнем дерева; вершины, из которых “не исходит” ни одной дуги, называются листьями.
Замечание. Нетрудно видеть, что двоичные деревья - конструктивные объекты, т.к. есть набор базовых объектов: вершины и дуги; и одна операция: соединения двух вершин дугой.
Тогда игру “чет-нечет” в виде дерева можно представить так, как показано на рисунке 1.
Рис.1. Дерево игры “чет-нечет”.
Здесь каждая вершина представляет состояние в игре, после очередного хода. Каждый ход представлен дугой. Число на дуге показывает, сколько всего предметов было взято в игре с учетом этого хода. Конечные вершины, из которых не исходит ни одной дуги и которые называются листьями, помечаются “+”, если выигрывает А и “-” если - В.
Пометим все вершины в этом дереве “+” или “-” по следующему правилу:
Если ход А заканчивается хотя бы одним “+”, то помечаем вершину, с которой начинается ход А, так же “+”. В противном случае помечаем вершину, с которой начинается ход А ,“-“.
Если ход В заканчивается так, что обе вершины помечены “+”, то вершина, с которой начинается этот ход, так же метится “+”. В противном случае ставим “-”.
Ясно, что если в результате этой разметки корень будет помечен “+”, то есть такая последовательность ходов когда А обязательно выигрывает. Читателю предлагается доказать, что предложенная ранее стратегия игры для А в случае 6 предметов действительно является выигрышной и всегда обеспечивает ему победу. Мы же докажем более общую теорему:
Теорема1.1. В любой игре, из рассматриваемого класса, всегда существует выигрышная стратегия для одного из игроков.
Доказательство:
Доказывать эту теорему будем методом индукции.
Для n=1 ( n - кол-во ходов в игре):
На рисунке 2 показано дерево игры из одного хода где К - максимальное количество предметов, которое можно взять за один ход; символ * обозначает либо ‘-‘ или ‘+’, т.е. выигрыш А, или выигрыш В соответственно.
· 
Рис.2. Дерево игры из одного хода
Тогда ходы, заканчивающиеся ‘+’ и образуют выигрышную стратегию для игрока А. Если среди * есть хотя бы один ‘+’, то А имеет выигрышную стратегию, если нет, то B выигрывает всегда, т.е. он имеет выигрышную стратегию.
2) По индукции: пусть утверждение теоремы верно для n=S, докажем, что оно верно и для S+1. На рисунке 3 показано дерево игры S+1 ходов, где g
- поддеревья, для игры не более, чем из S ходов .Поскольку g
: - дерево игры из не более, чем S ходов, то для него утверждение теоремы верно. Поэтому, если среди * в g есть хотя бы один ‘+’ , то существует выигрышное поддерево (g ) (по предположению индукции) и, следовательно, А выиграл. В противном случае выиграл В. Итак, мы доказали существование решения для рассматриваемой проблемы.Оказывается, что эта теорема верна и для игр, где возможна ничья. Следовательно, она верна и для шахмат! Но тогда, если есть выигрышная стратегия для шахмат, то почему мы говорим об искусстве шахмат? Зачем нужны чемпионаты мира?