Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
– дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно;
– детерминированность – определенность. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдает один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список исходных данных вероятностный алгоритм становится подвидом обычного;
– понятность – алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд;
– завершаемость (конечность) – при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0;
– массовость – алгоритм должен быть применим к разным наборам исходных данных;
– результативность – завершение алгоритма определенными результатами:
– алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе;
– алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи. Алгоритм – это формальное описание способа решения задачи путем разбиения ее на конечную по времени, последовательность действий (элементарных операций). Под словом «формальное» подразумевается, что описание должно быть абсолютно полным и учитывать все возможные ситуации, которые могут встретиться по ходу решения задачи. Под элементарной операцией понимается действие, которое по заранее определенным критериям (например, очевидности) не имеет смысла детализировать.
Алгоритм на выбранном языке программирования записывается с помощью команд описания данных, вычисления значений и управления последовательностью выполнения программы.
Алгоритмический язык – формальный язык, используемый для записи, реализации и изучения алгоритмов. Всякий язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования. В узком смысле слова алгоритмическим языком также называют семейство языков программирования Алгол.
При преподавании информатики в школах для изучения основ алгоритмизации применяется так называемый школьный алгоритмический язык (учебный алгоритмический язык), использующий понятные школьнику слова на русском языке. В отличие от большинства языков программирования, алгоритмический язык не привязан к архитектуре компьютера, не содержит деталей, связанных с устройством машины.
Использование таких алгоритмических конструкций, как ветвление и цикл, подразумевает использование логических выражений, построение которых невозможно без понятия высказывания, логического значения, логических операций и кванторов.
В математической логике наряду с логическими операциями используются и кванторы. Квантор (от лат. quantum – сколько) – логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате ее применения.
В обычном языке носителями таких характеристик служат такие слова, как «все», «каждый», «некоторый», «любой», «всякий», «бесконечно много», «существует», «имеется», «единственный», «несколько», «конечное число», а также все количественные числительные. В формализованных языках, составной частью которых является исчисление предикатов, для выражения всех подобных характеристик оказывается достаточным кванторов двух видов: квантора общности и квантора существования.
Кванторы позволяют из конкретной высказывательной формы получить высказывательную форму с меньшим числом параметров, в частности из одноместной высказывательной формы получить высказывание.
Алгоритм, представленный в форме, пригодной для восприятия и выполнения компьютером, называется программой. Для записи алгоритмов в такой форме существуют различные языки программирования. Алгоритмические конструкции в языке программирования записываются с помощью соответствующих операторов. Информация, подаваемая на вход программе, называется данными. Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) структурами данных. Примерами структур данных являются числа, логические значения, последовательности, таблицы, строки, списки, деревья, графы и т.п. Перечисленные структуры данных существуют независимо от их реализации в программировании. С этими структурами работали математики и в XVIII, и в XIX вв., когда еще не придумали вычислительные машины и никто не знал, что наступит эра информатизации. Удачный выбор структуры данных для представления информации может существенно повысить эффективность решения задачи. Реализация этих структур в языке программирования производится через соответствующие типы данных. Разработка программ в настоящее время – это достаточно сложный процесс, она требует и знания систем программирования, и владения технологией программирования, и сознательного использования одной из парадигм программирования, в частности объектно-ориентированного программирования.
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Само же слово «алгоритм» появилось в Средние века, когда европейцы познакомились со способами выполнения арифметических действий, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми. Слово «алгоритм» – европеизированное произношение слов «аль-Хорезми».
В своем нынешнем смысле слово «алгоритм» часто ассоциировалось с алгоритмом Евклида, который представляет собой
процесс нахождения наибольшего общего делителя (НОД) двух чисел.
Приведем современное описание алгоритма Евклида с использованием блок-схемы.
Стрелка, используемая при описании данного алгоритма, обозначает операцию замещения, или присваивания. Разумеется, в книге Евклида «Начала» этот алгоритм сформулирован не совсем так (а записан совсем не так). В данном случае мы продемонстрировали современную формулировку этого алгоритма и одну из распространенных наглядных форм записи алгоритмов.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя, а множество команд, которые исполнитель может выполнять, – систему команд исполнителя (СКИ).
Таким образом, алгоритм можно рассматривать как последовательность команд управления работой исполнителя (предписание исполнителю на выполнение последовательности действий).
Алгоритмы подразделяются на:
– линейные (действия выполняются одно за другим);
– разветвленные (есть условие и существует хотя бы два пути выполнения алгоритма);
– циклические (многократное повторение некоторой группы шагов).