1.3. Понятие алгоритма
Уже с давних времен ученые задумывались над проблемой формализации умственной деятельности человека, в частности формализации вычислений. Основная проблема при этом заключалась в разложении процесса вычисления на элементарные операции таким образом, чтобы каждая операция была определена абсолютно формально и выбор следующей операции был бы однозначно предопределен предыдущими шагами. Такая последовательность операций и правил их выбора в совокупности составляет алгоритм решения задачи. Построение алгоритма называется алгоритмизацией задачи.
В теории алгоритмов каждое элементарное действие определено строго формально, т.е. полностью заданы состояния исполнителя до и после этого действия. Исполнителя алгоритма можно назвать вычислительной машиной. То, над чем производятся действия исполнителя, в теории обычно является числами или символами некоторого алфавита. Алгоритм должен быть составлен предварительно до начала работы машины. В такой ситуации его принято называть программой.
Пользователи, начинающие работать на компьютере, как правило, не задумываются над тем, каким образом компьютер функционирует. Для них естественно одушевлять компьютер, приписывая ему некоторую долю разумности и самостоятельности. Между тем компьютер ничего не делает самостоятельно. Все его действия обусловлены теми программами, которые в него заложены. Эти инструкции однозначно определяют действия, которые он должен выполнить в текущей ситуации. Ситуация определяется поставленной целью и конкретными данными, предоставленными к этому моменту для достижения этой цели. Для того чтобы компьютер правильно функционировал, соответствующие программы должны быть кем-то составлены.
Весь процесс программирования подразумевает прежде всего формулировку цели программы, затем анализ содержания задачи и, наконец, создание программы для компьютера. Для этого программист должен уметь учитывать все ситуации, которые могут встретиться в процессе работы программы, и предусмотреть для них правильное действие.
Проблемами алгоритмизации при решении вычислительных задач занимались Паскаль, Декарт, Лейбниц, Лаплас и многие другие ученые. В XX в. бурно развивалась формальная теория алгоритмов. Среди ученых, внесших в эту теорию наиболее значительный вклад, можно назвать Геделя, Клини, Черча, Тьюринга, Поста, Маркова, Петера.
На практике составление алгоритмов невозможно без таких средств их изображения, которые отличались бы наглядностью и понятностью. Необходимо иметь адекватные средства как для описания элементарных шагов алгоритма, так и для отображения структуры алгоритма в целом. Наиболее естественно изображение алгоритмов в форме блок-схем, которые являются визуальным представлением действий и их последовательности. Один блок блок-схемы изображается контуром на плоскости с текстом внутри. Элементарное действие алгоритма описывается текстом в одном блоке схемы, а линии, соединяющие блоки, указывают последовательность их выполнения. Поскольку реально выбор того или иного продолжения работы зачастую зависит от данных, поступивших на обработку, очередной блок может иметь не одно, а несколько продолжений и для него необходимо указывать, каким условиям соответствует то или иное продолжение. Проверки такого рода принято выделять в отдельный блок специального типа (условный блок). Обычный блок имеет одно продолжение, условный блок — несколько продолжений, соответствующих различным вариантам результата проверки условия. Достаточно распространено соглашение, согласно которому обычные блоки заключаются в прямоугольник, а условные — в ромб. Иногда другие типы блоков обрамляются овалами или параллелограммами.
Описание на языке блок-схем очень хорошо читаемо, его легко модифицировать, и главное, оно естественно отражает сущность процесса алгоритмизации задачи. Критерии выделения блока носят отчасти объективный, отчасти субъективный характер. Общая схема может содержать небольшое число крупных блоков. Крупные блоки, описывающие сложные действия, можно развернуть в более подробные блок-схемы, блоки которых, в свою очередь, также изображаются блок-схемами, и т.д. То есть, алгоритм решения задачи может быть представлен сложной структурой блок-схем.