Т. А. Сливина математическая логика и теория алгоритмов

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

Детерминированность алгоритма. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени (или «После выполнения очередного этапа однозначно определено, что делать на следующем этапе»).

Элементарность шагов алгоритма. Закон получения последующей системы величин из предшествующей должен быть простым.

Массовость алгоритма. Массовость алгоритма заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных. Начальная система величин (исходные данные) может выбираться из некоторого потенциально бесконечного множества.

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

Определенность. Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств.

Интуитивное понятие алгоритма, хотя и не строго, но настолько ясно, что всегда можно определить, является ли данный процесс алгоритмом. Поэтому доказательством существования алгоритма можно считать описание процесса решения какой-либо задачи.
Способы описания алгоритмов. К основным способам описания алгоритмов относятся следующие:
а) словесно-формульный;
б) структурный или блок-схемный;
в) с помощью граф-схем;
г) с помощью сетей Петри.
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями со стрелками. Данный способ по сравнению с другими способами записи алгоритмов имеет ряд преимуществ. Он наиболее нагляден: каждая операция вычислительного процесса изображается геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Алгоритмы, в которых основную роль играют математические действия, называются численными алгоритмами (приведены примеры в начале лекции). От численных алгоритмов отделяют логические алгоритмы игр. В качестве примера, дающего логический алгоритм, рассмотрим следующую игру.
Имеется 15 предметов. В игре участвуют двое: начинающий и противник. Каждый игрок по очереди берет один, два или три предмета. Выигрывает тот, кто берет последний предмет. Какой стратегии в игре должен придерживаться начинающий, чтобы выиграть?
Выигрышная стратегия начинающего может быть описана в форме следующей таблицы:

Номер	Ход начинающего	Ход противника
1	3	n
2	4 – n	m
3	4 – m	p
4	4 – p	0

Действительно, в итоге такой стратегии начинающий возьмет 3 + (4 - п) + (4 - m) + (4 - р) = 15 - (п + m + р) предметов, а противник возьмет п + т + р предметов, т.е. в сумме они возьмут 15 предметов, и последний предмет будет взят начинающим.