Лекция 10. Алгоритм и его свойства. Базовые структуры алгоритмов.
Первые алгоритмы появились вместе с математикой, а теория алгоритмов возникла лишь в 30-х гг. нашего века.
Алгоритм – одно из фундаментальных понятий современной науки, которое используется в различных областях знания, но изучается оно в математике и информатике.
Под алгоритмом понимают последовательность четких и понятных исполнителю инструкций или предписаний, необходимых для решения поставленной задачи.
Каждое отдельное действие, выполняемое в рамках алгоритма называется шагом алгоритма. Последовательность шагов алгоритма строго фиксирована.
Всякий алгоритм составляется в расчете на конкретного исполнителя (управляемая информационная система, реализующая алгоритм). Поэтому важно учитывать возможности конкретного исполнителя, т.к. действия, предназначенные например, человеку, могут быть не понятны машине и наоборот.
Условно исполнителей алгоритма можно разделить на следующие типы: человек (группа людей), механический исполнитель (робот, станок), электронно – вычислительная машина (компьютер).
Независимо от решаемой задачи и сферы применения каждый алгоритм должен обладать следующими свойствами:
· дискретность, т.е. процесс решения задачи должен протекать в виде последовательности отдельных действий, следующих друг за другом;
· элементарность действий, т.е. каждое действие должно являться настолько простым, что не вызывать сомнений и возможности неоднозначного толкования;
· детерминированность (определенность), т.е. каждое действие должно быть определено однозначно и после его выполнения однозначно определено, какое действие надо выполнять следующим;
· конечность, т.е. алгоритм должен заканчиваться после конечного числа действий (шагов);
· результативность, т.е. в момент прекращения работы алгоритма должно быть известно, что считать его результатом;
· массовость, т.е. алгоритм должен описывать некоторое множество процессов, применимых при различных входных данных.
Классы алгоритмов
Можно выделить три крупных класса алгоритмов:
1. Вычислительные алгоритмы, как правило, работают со сравнительно простыми видами данных (числа, матрицы), но сам процесс вычисления может быть долгим и сложным.
2. Информационные алгоритмы представляют собой набор сравнительно простых процедур (например, поиск числа или слова, удовлетворяющего определенным признакам), но работающих с большими объемами информации. Таковы алгоритмы в различных базах данных. Для того, чтобы они работали эффективно, важно иметь хорошую организацию данных. Например, чтобы в картотеке можно было быстро найти нужные сведения, эти сведения нужно постоянно поддерживать в определенном порядке (по разделам, внутри разделов по алфавиту и т.д.).
3. Управляющие алгоритмы характеризуются тем, что данные к ним поступают от внешних процессов, которыми они управляют. Результаты работы этих алгоритмов представляют собой различные управляющие воздействия. Поэтому значения данных в ходе работы управляющих алгоритмов меняются (иногда очень быстро), и алгоритм должен вовремя правильно отреагировать, т.е. выдать нужный управляющий сигнал в нужный момент.
Способы записи алгоритмов
1. Вербальный способ – описание всех действий алгоритма на знакомом составителю языке (русском, английском и т.д.) с указанием порядка выполнения этих действий (первое, второе,…, перейти к первому и т.д.).
Например, алгоритм деления отрезка пополам описывается так:
· поставить ножку циркуля в точку А;
· установить раствор циркуля большим половины длины отрезка АВ;
· провести окружность;
· поставить ножку циркуля в точку В;
· провести окружность;
· провести прямую через точки пересечения окружностей.
2. Табличный способ – запись алгоритма, используемого для вычислений, в форме таблицы. Удобно использовать, когда требуется найти не одно, а несколько значений одного и того же выражения для различных значений переменных, входящих в данное выражение.
Например, рассмотрим решение следующей задачи: В одном кучке 72м ткани, а в другом в у раз больше. Сколько метров ткани во втором куске? Составьте выражение и найдите его значение, если у=2,4,8.
| Значение переменной | у | |||
| Значение выражения | 72*у |
3. Алгоритмы, используемые для вычислений, могут быть записаны с помощью формулы. Например, для нахождения корней квадратного уравнения ах2+вх+с=0 (а≠0) удобнее применять не словесную запись, а формулу:
______
-в + √в2 – 4ас
х1, 2 = _____________
2а
4. Графический способ – это блок –схема – ориентированный граф, указывающий порядок исполнения команд алгоритма. Основные компоненты блок – схемы:
 |
- начало (конец) алгоритма
 |
- ввод – вывод данных (блок ввода – вывода)
 |
- выполнение арифметических операций (обрабатывающий блок)
- 
выполнение логических операций (условный блок)
- 
вызов вспомогательного алгоритма
- 
порядок выполнения операций
 |
- цикл с параметром
 |
- цикл (повторяющиеся действия)
В блоке ввода информации перечисляются переменные, значения которых заранее известны. В блоке вывода, который имеет такое же графическое обозначение, как и блок ввода, перечисляются имена переменных, значения которых требовалось определить в задаче. Если последовательность действий зависит от тог, каков результат проверки некоторого условия, то используется условный блок (блок обработки условия).
5. Базовые структуры алгоритмов
1. Следование – самая важная из структур. Она означает последовательное выполнение действий.
 |
вход
Действие 1
 |
Действие 2
 |
выход
Например: в задаче вычисления площади круга, если радиус – заданное натуральное число, все действия в блок-схеме последовательны.
3. Ветвление (развилка) – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей. Различают структуры полного и неполного ветвления.
· Полное ветвление. Эта структура называется "ЕСЛИ – ТО – ИНАЧЕ". Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.
вход
нет 
да
условие
ложь истина
действие 2 действие 1
 |
выход
· Неполное ветвление. Может оказаться, что для одного из результатов проверки ничего предпринимать не надо. В этом случае можно применять только один обрабатывающий блок. (ЕСЛИ – ТО)
вход
нет да
условие
ложь истина
действие 1
 |
выход
Например: пусть в задаче требуется вычислить площадь круга, причем, радиус вводится с клавиатуры. Тогда, с учетом того, что задача решается только для положительных значений введенного числа.
3. Цикл (повторение) предусматривает многократное повторение некоторого набора команд программы. Различают 3 вида циклов:
· Цикл с предусловием. Начинается с проверки логического выражения. Если оно истинно, то выполняется тело цикла (набор команд) и затем снова проверяется логическое выражение. Цикл заканчивается тогда, когда логическое выражение становится неверным.
 |
вход
 |
нет да
условие
действие
 |
выход
· Цикл с постусловием. Цикл начинается с выполнения тела цикла, а затем проверяется условие. Цикл повторяется в том случае, если условие оказывается неверным (ложь). Выход из цикла осуществляется тогда, когда условие становится истинным.
 |
вход
 |
действие
да нет
условие
выход
· Цикл с параметром. В его составе имеется переменная цикла и автоматический счетчик, который изменяет переменную цикла на единицу (по умолчанию) или на величину указанного шага от начального значения до конечного. Выход из цикла происходит тогда, когда переменной цикла присваивается значение большее указанного конечного.
вход
I=L,R,H
|
действие
 |
выход