76Понятие алгоритма. Виды алгоритмов. Свойства алгоритмов. Способы представления алгоритмов.

Точного определения алгоритма не существует, также, как не существует определения информации, множества и т.д. Однако можно дать достаточно полное представление о таком понятии как алгоритм. Под алгоритмом понимают совокупность точных и однозначных инструкций для некоторого исполнителя данного алгоритма, предназначенных для решения какой-либо задачи (достижения какой-либо цели). При этом предполагается выполнение следующих свойств: 1. Дискретность – команды, инструкции алгоритма представляют собой разделимую по-следовательность действий. 2. Конечность – число шагов алгоритма должно быть конечно. 3. Определенность (однозначность, детерминированность) – каждая команда алгоритма должна быть однозначно воспринята исполнителем. 4. Массовость – алгоритм предназначен для решения множества задач заданного вида. 5. Эффективности – интерес представляют в первую очередь такие алгоритмы, которые решают поставленную задачу в пределах допустимого времени с желательно меньшим расхо-дом ресурсов исполнителя. В учебном варианте эффективность можно понимать как требова-ние "ничего лишнего". То есть не производить повторных вычислений одинаковых выражений и т.д. Существует большое количество известных примеров алгоритмов из математики. Напри-мер, алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел, алго-ритм решения квадратного уравнения и др. Немало алгоритмов действий используется в быту. Любой алгоритм по существу перерабатывает информацию. Поэтому для каждого алго-ритма предполагается наличие множества входных и выходных данных. Такие множества и их обозначения будем называть параметрами или аргументами алгоритма. Множества входных и выходных данных могут быть либо пустыми, либо пересекаться, либо совпадать, либо не иметь пересечений. Выходные параметры иногда называют также аргументами-результатами. Множества входных и выходных данных могут рассматриваться также как некоторые аб-страктные каналы (линии связи), по которым передается информация.

СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ Отметим, что алгоритм может пониматься как некоторая функция со специальными свой-ствами, которые были описаны ранее. Эта функция существует как абстракция. Мы же всегда воспринимаем алгоритм в его некоторой записи, или, как говорят, в его представлении. Очевидно также, что любой исполнитель может воспринимать алгоритм, исполнять его, только в том случае, когда алгоритм представлен в том виде, в каком он понятен исполнителю. Это означает, что любое представление алгоритма является некоторым информационным бло-ком, то есть представление алгоритма является информацией, и она расположена на некотором носителе информации. Таким образом, сам алгоритм есть некоторая абстракция, но реальная его реализация воз-можна только в виде его представления. Очевидно также, что у любого алгоритма могут быть различные представления. Они могут быть похожими, однако могут и не иметь ничего общего, кроме как реализации одного алгоритма. Представление алгоритма можно понимать как отображение множества алгоритмов для фиксированного исполнителя во множество некоторых данных, например, символов или ри-сунков. Существует три основных способа представления алгоритмов: 1)графический; 2)неформальная языковая (алгоритмическая) нотация (запись); 3)запись на алгоритмическом языке.

Любая форма записи (представления) алгоритма должна обеспечивать свойства алгорит-ма: дискретности, конечности, определенности, массовости.

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