Алгоритмизация и программирование

1. Понятие алгоритма и его свойства
Алгоритм (от algoritmi)- предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за конечное число их применений к результату.
Мухаммед ибн Муса
аль-Хорезми (783-850)

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

Свойства алгоритма
Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов. Преобразование исходных данных в результат осуществляется дискретно во времени.
Понятность – каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае, эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены.
Определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвольного толкования.
Результативность означает возможность получения результата после выполнения конечного количества операций.
Корректность - решение должно быть правильным для любых допустимых исходных данных.
Массовость заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных (разработка в общем виде).

Составление алгоритма является обязательным этапом автоматизации любого процесса.

2. Способы описания алгоритмов
словесный (на естественном языке);
формульно-словесный;
табличный (обычно носит вспомогательный характер);
графический (использует элементы блок-схем).

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

3. Основные алгоритмические конструкции
Линейным принято называть вычислительный процесс, в котором этапы вычислений выполняются в линейной последовательности и каждый этап выполняется только один раз.

Блок-схема вычисления гипотенузы по теореме Пифагора

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

полное ветвление
если-то-иначе
неполный вариант ветвления
если-то

Алгоритм вычисления функции:

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

Цикл называется детерминированным (цикл с параметром), если число повторений тела цикла заранее известно или определено.
Цикл называется итерационным (с пред- и постусловием), если число повторений тела цикла заранее неизвестно, а зависит от значений переменных, участвующих в вычислениях.

4. Базовые алгоритмы
Алгоритм поиска наибольшего (наименьшего) значения:
за max (min) принимаем значение любого из данных и поочередно их сравниваем. Если окажется, что очередное значение входного данного больше (меньше) max (min) , то max (min) присваиваем это значение. Алгоритм использует неполное ветвление.

Пример. Заданы три числа a, b, c. Найти значение наименьшего из них.
a=9 b=3 c=5
min=9
3<9
min=3
5<3

Правило произведения:
начальное значение произведения Р=1;
в теле некоторой циклической конструкции выполнить команду: Р = Р * <множитель>

Пример. Составим алгоритм вычисления суммы N первых натуральных чисел. Используется цикл с предусловием.
N=5
S=0 i=1
S=0+1=1 i=2
S=1+2=3 i=3
S=3+3=6 i=4
S=6+4=10 i=5
S=10+5=15 i=6
S=15

Правило суммирования:
начальное значение суммы S=0;
в теле некоторой циклической конструкции выполнить команду: S = S + <слагаемое>

Пример. Задано 20 чисел. Сколько среди них чисел, больших 10?

Правило счетчика:
начальное значение счетчика K=0;
в теле некоторой циклической конструкции выполнить команду: K = K + 1

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

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

Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным.
Массив - упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами).
Количество элементов массива называют размерностью.

Блок-схема алгоритма ввода элементов массива А(10)

Пример. В массиве А(10) найти наибольший элемент и его индекс.

6. Создание программ
Программа - это описание алгоритма и данных на некотором языке программирования, предназначенное для последующего автоматического выполнения.
Программирование - это
1) раздел информатики, изучающий методы и приемы составления программ для компьютеров;
2) теоретическая и практическая деятельность, связанная с созданием программ.