Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Интуитивное понятие алгоритма и его свойств.
Алгоритм отностится к основным понятиям математики, а поэтому не имеет определения. Часто это понятие формулируют так:"точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного класса".
Рассмотрим подробнее ключевые слова в этой формулировке:
"точное предписание” означает, что предписание однозначно и одинаково понимается всеми исполнителями алгоритма и при одних и тех же исходных данных любой исполнитель всегда получает один и тот же результат;
“из заданного фиксированного множества” означает, что множество действий, используемых в предписании, оговорено заранее и не может меняться в ходе исполнения алгоритма.
“решения всех задач, заданного класса” означает, что это предписание предназначено для решения класса задач, а не одной отдельной задачи. Позднее мы подробнее рассмотрим смысл выражения “класс задач”.
Эта формулировка требует знания таких понятий, как исходные данные, результат, действие, исполнитель, класс задач. Познакомимся с ними на примере алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел:
Исходные данные: n, m - натуральные числа
Результат: НОД (n, m) - натуральное число d, такое, что
Алгоритм:
. Положи a =n, b = m ; (следующий шаг)
. Сравни a и b ; (следующий шаг)
. Если a=b, то a - результат; (стоп)
иначе; (следующий шаг)
. Если a<b, то поменяй их местами; (следующий шаг)
. Вычти b из a ; (следующий шаг)
. Положи a = разность; (перейти к шагу 2)
В этом алгоритме действия обозначены словами: положи, сравни, если_то_иначе, вычти, поменяй_местами, следующий шаг. Все исполнители, реализующие этот алгоритм, должны одинаково понимать смысл этих действий.
Например:
Сравни a и b ;(следующий шаг)
Все исполнители должны “понимать”, что надо сравнить значения, представленные символами а и b, а не сами символы, и перейти к действию 3.
Положи a = разность; (перейти к шагу 2)
Означает, что в качестве текущего значения переменной а надо взять разность между значениями, представленными переменными а и b, вычисленную на предыдущем этапе, и перейти к действию 2.
Последовательность действий, выполняемых исполнителем, образуют процесс. Назовем этот процесс вычислительным процессом. Например, для случая исходных данных n=3, m=2 и алгоритма НОД этот процесс можно описать так:
|
значение а |
значение b |
№ действия |
|
|
1 |
|||
|
2 |
|||
|
3 |
|||
|
4 |
|||
|
5 |
|||
|
6 |
|||
|
7 |
|||
|
8 |
|||
|
9 |
|||
|
10 |
|||
|
11 |
|||
|
12 |
|||
|
13 |
Стоп
Нетрудно видеть разницу между алгоритмом и вычислительным процессом, им порождаемым. Так, например, действие, которое встречается в алгоритме один раз, может быть выполнено несколько раз, а следовательно встретиться неоднократно в описании вычислительного процесса. Примерами такого действия может быть действие 3, либо действие 5, либо 6. В нашем алгоритме, как правило, экземпляры одного и того же действия будут различаться данными (операндами), над которыми совершается это действие. Однако, эти данные могут быть представлены одними и теми же именами.
По алгоритму не всегда можно предсказать вычислительный процесс. Например, не всегда можно предвидеть точно, как много действий будет в вычислительном процессе. Примером тому может служить алгоритм вычисления НОД.
Алгоритм всегда определяет однозначно, какое действие должно быть выполнено следующим, равно как и то, какое действие должно быть выполнено первым. Очередное действие всегда определено однозначно. Именно этой цели служат слова “(cледующий шаг).” Они явно указывают какое действие должно быть выполнено следующим. В силу этого свойства алгоритма, которое называется детерминированность, вычислительный процесс всегда для заданных исходных данных определен однозначно. Таким образом, при одних и тех же исходных данных вычислительный процес будет одним и тем же.
Обычно по умолчанию предполагают “естественный” порядок выполнения действий в алгоритме. Это означает, что если нет явного изменения порядка выполнения действий, то они выполняются последовательно одно за другим, а выполнение алгоритма начинают с первого по порядку действия. Поэтому, в дальнейшем слова “(следующий шаг)” мы будем опускать.
Рассмотрим подробнее понятие действия. В нашем примере присутствуют как минимум два вида действий:
действия над данными (например, сравни, вычти, положи);
действия, изменяющие “естественный” порядок вычислений (например, если - то - иначе; перейди к шагу #).
Если присмотреться внимательней, то мы увидим, что действия вида “сравни”, “вычти” и действия вида “положи ” - это разные действия. Разница между ними в том, что действия первого вида указывают что делать с его операндами, но не указывают где “сохранить” полученный результат. Действия второго вида, наоборот “умалчивают” каким образом получено значение, которое надо “сохранить” в качестве нового значения переменной.
Теперь пристальнее рассмотрим правило окончания алгоритма и выбора результата. В алгоритме могут быть использованы десятки переменных, но результат будет храниться лишь в нескольких. Эти “результирующие” переменные должны быть явно указаны в алгоритме, т.к. в противном случае нет никакой возможности их выявить. Момент, когда в этих переменных сформированы нужные значения, определяет правило окончания алгоритма. Правило окончания всегда формулируется как некоторое условие на множестве текущих значений переменных. Достижение этого условия и означает, что в определенных переменных получен результат. В нашем примере таким условием является равенство текущего значения переменной а текущему значению переменной b.
Итак, сформулируем наши наблюдения в общей форме. Исходные данные - это значения, с которых начинается исполнение алгоритма. Множество исходных данных всегда точно определено. Оно может быть определено явно, перечислением его элементов, либо не явно, в виде системы правил, определяющих конструкцию его элементов. (Этот способ мы рассмотрим позднее).
Данные в алгоритме могут быть представлены переменными (в нашем примере именуемые a и b), либо явно, в виде постоянной величины - константы (в нашем примере n и m), которая не меняет своего значения в конце выполнения алгоритма.
Переменная - это имя, с которым связано конкрентное множество значений. В каждый конкретный момент времени исполнения алгоритма каждая переменная принимает одно конкретное значение, из связанного с ней множества.
Определение 1.1
Типом переменной называется множество возможных ее значений.
Пусть у нас есть множество переменных {vi|i=1,k}. (Примеры!)
Определение 1.2
Состоянием на множестве переменных {vi|i=1,k} называется набор значений этих переменных.
Пусть А - алгоритм, {vi|i=1,k} - набор всех переменных, используемых в этом алгоритме. Добавим к этому набору еще одну переменную , тип которой есть множество индексов действий в алгоритме. Каждый шаг исполнения алгоритма можно однозначно охарактеризовать сосотоянием на множестве переменных ({vi|i=1,k},).
Определение 1.3
Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.
Определение 1.4
Состоянием вычислительного процесса, порожденного алгоритмом А, называется состояние на множестве переменных ({vi|i=1,k},), где{vi|i=1,k} - набор всех переменных, используемых в алгоритме А.
Нетрудно видеть, что вычислительный процесс можно описать в виде последовательности его состояний.
Определение 1.5
Терминальным состоянием называется состояние вычислительного процесса, на множестве значений которого выполняется определенное условие - правило окончания алгоритма.
Определение 1.6
Результат - это определенная совокупность значений из терминального состояния вычислительного процесса алгоритма.
Определение 1.7
Действие - переход из одного состояния в другое.
Действительно, если действие связано с преобразованием каких-либо данных, то правильность этого утверждения очевидна. Если же действие связано с изменением “естественного” порядка выполнения действий в алгоритме, то состояние вычислительного процесса меняется все равно, т.к. изменяется значение специальной переменной - индекс действия.
Рассмотрим еще один пример. Пусть нам надо построить алгоритм для решения следующего класса задач:
вычислить значение выражения , в точке x=b, где
aiR, bR, где R - множество вещественных чисел.
Множество исходных данных: , где aiR, bR.
вектор из n+1 вещественных числа;
b - вещественное число.
Результат b r: , где
Переменные: i - типа целый; х, r - типа вещественный.
Константы:{ai|i=1, n+1}, п.
Нетрудно видеть, что мы имеем дело с классом задач. Ниже приведен алгоритм для этого класса задач.
Алгоритм:
Положи i равным п, x равным b;
Положи r равным ;
Умножь r на x;
Положи r равным произведению;
Положи 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.
A
A
A
A
B
B