СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
АЛГОРИТМ. АЛГОРИТМ И ЕГО СВОЙСТВА
Алгоритм - это точная инструкция исполнителю в понятной для него форме, определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов. При этом предполагается выполнение следующих свойств:
1. Дискретность – команды алгоритма, представляющие разделимую последовательность действий.
2. Конечность – число шагов алгоритма должно быть конечно.
3. Определенность (однозначность, детерминированность) – каждая команда алгоритма должна быть однозначно воспринята исполнителем.
4. Массовость – алгоритм предназначен для решения множества задач заданного вида.
5. Эффективности – интерес представляют в первую очередь такие алгоритмы, которые решают поставленную задачу в пределах допустимого времени с желательно меньшим расходом ресурсов исполнителя. В учебном варианте эффективность можно понимать как требование "ничего лишнего". То есть не производить повторных вычислений одинаковых выражений и т.д.
Существует большое количество известных примеров алгоритмов из математики. Например, алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел, алгоритм решения квадратного уравнения и др. Немало алгоритмов действий используется в быту.
Любой алгоритм по существу перерабатывает информацию. Поэтому для каждого алгоритма предполагается наличие множества входных и выходных данных. Такие множества и их обозначения будем называть параметрами или аргументами алгоритма. Множества входных и выходных данных могут быть либо пустыми, либо пересекаться, либо совпадать, либо не иметь пересечений. Выходные параметры иногда называют также аргументами-результатами.
Множества входных и выходных данных могут рассматриваться также как некоторые абстрактные каналы (линии связи), по которым передается информация.
Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Выделяют три крупных класса алгоритмов:
- вычислительныеалгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
- информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
- управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
Существует три основных способа представления алгоритмов:
1) Графический;
2) неформальная языковая нотация (алгоритмическая запись);
3) запись на алгоритмическом языке.
Любая форма записи (представления) алгоритма должна обеспечивать свойства алгоритма:
· дискретности
· конечности
· определенности
· массовости.
В графической форме алгоритм представлен в виде геометрических фигур. Обычно они связываются линиями, которые показывают направление передачи информации при исполнении алгоритма. Существует несколько вариантов графического представления алгоритмов, но широкую известность получило представление в виде блок-схем. Метод блок-схем был предложен самим Фон Нейманом – одним из первых разработчиков вычислительной техники.
Алгоритм может быть представлен в виде записей литературного языка, например, русского. В этом случае последовательностью предложений описывается последовательность действий исполнителя, которым может быть в большинстве случаев только человек. Никаких специальных правил и требований к таким записям алгоритмов не предъявляется. Главное, что бы выполнялись требования, предъявляемые к алгоритмам, о которых указывалось выше. В литературе, посвященной алгоритмам, иногда используется такой способ записи алгоритмов. В качестве примера можно привести трехтомную монографию известного специалиста по информатике Д. Кнута "Искусство программирования для ЭВМ". Такие записи на естественном языке называют иногда неформальной алгоритмической нотацией.
В неформальной алгоритмической нотации может использоваться так называемый псевдокод. Псевдокод – это запись алгоритма с использованием языковых конструкций известных алгоритмических языков, либо языков программирования. Например, Паскаль, Алгол, Си, Бейсик и др. При этом нет никаких специальных требований к оформлению таких записей, за исключением требования однозначности при реализации записанных действий.
Способ записи алгоритмов с использованием алгоритмических языков, либо языков программирования. Алгоритмический язык – это система правил и обозначений для точной и однозначной записи алгоритмов. Такая запись является формализованной. Это означает, что запись подчиняется строгим требованиям синтаксиса языка. Язык программирования – это система обозначений и правил для записи алгоритмов, предназначенная для использования на ЭВМ. На практике языки программирования привязаны к конкретным классам ЭВМ, операционным системам и т.д. В языках программирования существенными являются технические и технологические аспекты, что не характерно для алгоритмических языков, которые обычно машинно-независимы.
Существует большое количество языков программирования. Одни из них широко распространены: Basic,Pascal,C/C++,Modula,Fortran. Другие же имеют специальное назначение: Prolog,Forth, Lisp.
Некоторые языки сыграли заметную роль в программирования, но сейчас не используются. Примером является язык Algol. Именно этот язык послужил основой для разработки более совершенных языков, таких как Pascal, C/C++и других. Algol использовался также как алгоритмический язык для записи алгоритмов, в том числе в качестве автокода. Можно также отметить такой важный язык программирования для научно-технических расчетов: Fortran.
Существуют языки декларативного (логического) программирования, например Prolog. Здесь нет алгоритмических инструкций, а есть описания данных и связей между ними. Исполняющая система производит поиск наилучшего способа решения поставленной задачи. На других принципах построены функциональные языки, например, Lisp. Основные управляющие структуры таких языков есть последовательность вызовов, так называемых рекурсивных функций. Это означает, что нет необходимости выполнять проверку логических условий, а выполнять только вычисления. Чтобы понять суть таких подходов, необходимо получить специальные знания по теории алгоритмов и математической логике. Это касается глубинного понимания сути алгоритма, связанного с рекурсивными функциями и различными моделями машины Тьюринга.
В 1985 году основатель школьной информатики академик А.П.Ершов предложил для записи алгоритмов новый алгоритмический язык, который назвали школьным алгоритмическим языком. Иногда этот язык называют Е-языком, в честь его создателя. Но это называние является неформальным.
Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и циклической структуры.
В алгоритмах линейной структуры действия выполняются последовательно одно за другим:
В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.
В алгоритмах циклической структуры в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла. Вложенным называется цикл, находящийся внутри тела другого цикла. Различают циклы с предусловием и постусловием:
Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. В этом случае одно повторение цикла называется итерацией.