Основные понятия теории алгоритмов

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

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

В теории программирования доказано [1, 2], что для записи любого сложного алгоритма достаточно трех базовых структур: следование – последовательное выполнение действий (рис. 1, а); ветвление – соответствует выбору одного из двух вариантов действий (рис. 1, б); цикл-пока – определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 2).

Рис. 1. Базовые алгоритмические структуры:

а) следование, б) ветвление

Рис. 2. Базовая структура: цикл-пока

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

Рис. 3. Дополнительная структура «выбор» и реализация ее через базовые структуры

Рис. 4. Дополнительная структура: цикл – до

Рис. 5. Дополнительная структура: цикл с заданным числом повторений (счетный цикл).

На основе алгоритмов создается программное обеспечение (ПО) для решения прикладных задач.