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

Первоначально термин «алгоритм» использовался для обозначения операций над числами. В XII в. европейцы, ознакомились с трудом арабского ученого Абу Джафара ибн Мусы аль-Хорезми, посвященного правилам счета в десятичной системе счисления. Термин «алгоритм» произошел от латинской редакции имени средневекового математика. В XV-XVI в. данный термин стали применять по отношению к единственному широко известному алгоритму - алгоритму Евклида, предназначенному для нахождения наибольшего - общего делителя пары натуральных чисел.

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

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

Алгоритмический процесс - процесс последовательного преобразования конструктивных объектов (слов, чисел, пар слов, пар чисел, предложений и т.п.), происходящий дискретными «шагами». Каждый шаг состоит в смене одного конструктивного объекта другим.

Алгоритмом считается такое предписание, которое обладает следующими свойствами (свойства алгоритма):

• дискретностью – разбиением процесса обработки информации на более простые этапы (шаги выполнения);

• однозначностью – единственность толкования правил выполнения действий и порядка их выполнения;

• результативностью – получение желаемого результата при допустимых значениях исходных данных за конечное число шагов;

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

Как правило, для любого заданного алгоритма можно выделить семь характеризующих его независимых параметров:

1. совокупность возможных исходных данных;

2. совокупность возможных промежуточных результатов;

3. совокупность результатов;

4. правило начала;

5. правило непосредственной переработки;

6. правило окончания;

7. правило извлечения результата.

Пример. Алгоритм вычисления корней квадратного уравнения .

Исходные данные – коэффициенты уравнения: а – при второй степени неизвестного; b – при первой степени неизвестного; с – при нулевой степени неизвестного.

Искомый результат – значения корней уравнения х₁ и х₂.

Предписание:

1. Вычислить значение дискриминанта по формуле .

2. Если , то вычислить значения корней уравнения по формулам:

3. Если , то уравнение не имеет корней.

Приведенное предписание обладает всеми свойствами алгоритма:

• дискретностью – предписание разбито на этапы (шаги выполнения);

• однозначностью – однозначно указано как обозначаются коэффициенты, дискриминант, корни, приведены формулы для вычисления дискриминанта и корней уравнения;

• результативностью – при выполнении предписания получается результат – значения корней уравнения или заключение, что уравнение не имеет решения;

• массовостью – в предписании составлено для общего случая (указаны не конкретные значения коэффициентов).

На практике в программировании очень часто используется задание алгоритмов в виде блок-схем. В блок-схемах для обозначения логически различных фрагментов программы используются стандартные символы. Основные элементы блок-схемы (рис.4): Начало/Конец, Ввод/Вывод, Обработка, Выбор, Узел.

Блок схема позволяет наглядно представить последовательность действий, необходимых для решения поставленной задачи.

Блок-схема – это ориентированный граф, вершины которого могут быть одного из трех типов, представленных на рис. 5

Функциональная вершина используется для представления функции .

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

Объединяющая вершина представляет передачу управления от одной из двух входящих ветвей к одной выходящей ветви.

Структурная блок-схема - это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем (см. рис. 5).

Рис.5. Структуры управления программы

Любая программа для машины может быть представлена структурной блок-схемой.

Важной особенностью приведенных структур является то, что они имеют один вход и один выход.

Структурное программирование - процесс разработки алгоритмов с помощью структурных блок-схем.

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

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