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

Для того, чтобы сравнивать сложность разных алгоритмов, надо чтобы она подсчитывалась для них в терминах одинаковых действий. Например, умножь, сложи, положи. Выразим сложность действия возведения в степень  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. В любой игре, из рассматриваемого класса, всегда существует выигрышная стратегия для одного из игроков.

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



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

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