Способы записи алгоритмов

Теоретический блок

Одновременно с эволюцией ЭВМ шла эволюция базовых программных средств для них. В первую очередь это относится к языкам программирования, с помощью которых люди кодируют задачи для решения их на ЭВМ. Языки программирования принято делить на пять поколений.

Первое поколение – вплоть до конца 50-х годов программирование сводилось к детальному кодированию длинных последовательностей команд двоичными, восьмеричными или шестнадцатеричными числами. Эта деятельность называлась кодированием в отличие от программирования, к которому относилась более трудная задача – конструирование алгоритмов.

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

С появлением более быстрых вычислительных машин с большим объемом памяти трудности кодирования настолько возросли, что стала очевидна неэффективность выполнения этой работы человеком.

Возникла необходимость учета аппаратной организации каждой конкретной машины, то есть необходимость перекодировки программ при переносе с одной машины на другую – зачастую наблюдалась непереносимость алгоритмов, разработанных для одних машин при переносе на другие. Практически не представлялась возможным понять принципы построения другой программы.

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

Эти трудности привели к созданию так называемых языков программирования «высокого уровня».

Третье поколение – самое «обширное» поколение языков. Это универсальные языки высокого уровня, с помощью которых удается решать задачи из любых областей. Начало оно ведет с 1955 года с появлением языка ФОРТРАН (FORmulaTRANslator – переводчик формул), первого компилируемого языка, созданного Джимом Бэкусом в 50-е годы. ФОРТРАН продолжает активно использоваться во многих организациях и в сегодняшние дни.

В 1960 году появился АЛГОЛ (ALGOritmicLanguage- алгоритмический язык). Он был призван заменить Фортран, но из-за более сложной структуры не получил широкого распространения.Однако он долгое время пользовался определенной популярностью в программистских кругах.

1965 году был создан один из наиболее популярных и поныне языков программирования – БЭЙСИК (BASIC – Beginner’sAllpurposeSymbolicInstructionCode – дословно: «многоцелевой код символической инструкции для начинающих»). Широкое распространение БЭЙСИК получил на персональных компьютерах. Он создавался в качестве учебного языка и очень прост в изучении. На нынешний день существует несколько достаточно мощных версий этого языка.

В 1970 году Никлаус Вирт создал язык Pascal (Паскаль), во многом напоминающий Алгол, но в нем ужесточен ряд требований к структуре программы и имеются возможности, позволяющие успешно применять его при создании крупных проектов. Этот язык обладает весьма развитыми средствами, особенно те его версии, которые используются в настоящее время.

В 1980 году появился язык ADA (Ада) – один из самых мощных языков программирования. Он принят в качестве основного языка на вычислительных центрах министерства обороны США. Структура самого языка похожа на Паскаль. В нем имеются средства разграничения доступа к различным уровням спецификаций, доведена до предела мощность управляющих конструкций. Назван по имени леди Огасты Ады Байрон, дочери английского поэта Байрона.

В настоящее время используется еще один мощный язык программирования – С (Си). Данный язык был создан в лаборатории Bellи первоначально не рассматривался как массовый. Он планировался для замены ассемблера, чтобы иметь возможность создавать столь же эффективные и компактные программы и в то же время не зависеть от конкретного типа процессора.

Четвертое поколение языков – это языки управления программным обеспечением, или, как их еще называют, «генераторы программ». Для примера можно привести такие языки, как Clipper, dBase, SuperCalc.

Все названные языки являются процедурными, в противоположность языкам «Пятого поколения», которые являются декларативными. Основные языки этого поколения – LISP – язык обработки списков /ЛИСП/ и PROLOG – программирование в терминах логики /ПРОЛОГ/.

ЛИСП появился в 1961 году. Он ориентирован на структуру данных в форме списка и позволяет организовывать эффективную обработку больших объемов текстовой информации. LISP является очень мощным и многообразным языком, но он может оказаться достаточно большим и громоздким. ПРОЛОГ создан в 1973 году Аланом Колмероэ. Программа на этом языке строится из последовательности фактов и правил, а затем формулируется утверждение, которое Пролог будет пытаться доказать с помощью введенных правил. При решении задач на этих языках от программиста требуется описать, ЧТО надо сделать, а не КАК это следует делать. Об этом позаботится сама система (ЛИСП или ПРОЛОГ).

Таким образом, все языки программирования можно разделить на три категории: языки НИЗКОГО уровня – машинные языки и языки Ассемблера, то есть языки первого и второго поколения; ВЫСОКОГО уровня – все процедурные языки, то есть языки третьего и четвертого поколений и СВЕРХВЫСОКОГО уровня – языки пятого поколения.

Говорят, что программирование – это искусство получения ответов от машины, и, если мы решили применить компьютер, нам предстоит пройти три основных этапа:

1. Ясно и точно установить, что же должно быть сделано.

2. Установить точно определенную последовательность действий, ведущую к желаемому результату, то есть, предложить алгоритм.

3. Выразить алгоритм в виде понятном для машины.

Первый этап носит название СИСТЕМНЫЙ АНАЛИЗ. Второй этап – КОНСТРУИРОВАНИЕ ПРОГРАММЫ. Третий этап – ПРОГРАММИРОВАНИЕ.

Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинской транскрипции имени Мухаммеда аль-Хорезми, выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством.

Чтобы не было недоразумений, введем термины, которые будем применять в дальнейшем.

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

Действие – одно из важнейших понятий. Это нечто, что имеет конечную продолжительность и приводит к желаемому результату.

Объект– это то, над чем это действие совершается и по изменению состояния которого можно судить о результате этого действия.

Инструкция – описание действия с помощью некоторого языка или системы формул.

Процесс (вычисление) – действие, которое можно разложить на составные части. Если эти части во времени следуют строго друг за другом и никакие две части не выполняются одновременно, то процесс называется последовательным.

Программа – инструкция, описывающая процесс и состоящая из составных частей. Это запись алгоритма в виде последовательности инструкций для получения определенного результата, которая будет понята машиной.

Исполнитель (процессор)– то, что выполняет действия согласно заданным инструкциям. Это более или менее нейтральный термин, не определяющий конкретно, что является исполнителем – человек или автомат. В самом деле, программы, если они записаны на языке, который точно определен, имеет смысл безотносительно к специфике процессора.

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

Каждое такое предписание называется командой. Порядок команд в алгоритме очень важен.

При составлении алгоритма требуется знать систему команд исполнителя, а не его устройство, то есть множество предписаний, которые понимает и умеет выполнять исполнитель нашего алгоритма. Исполнители можно разделить на неформальные (человек) и формальные (робот, компьютер или язык программирования). В дальнейшем мы будем иметь дело только с формальными исполнителями.

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

Свойства алгоритма

К алгоритму решения задач предъявляются высокие требования. Он должен обладать дискретностью, массовостью, компактностью, детерминированностью и результативностью.

Дискретность алгоритма определяет то, что всякий алгоритм имеет прерывистый, дискретный характер, т.е. представляет собой последовательность выполненных один за другим отдельно законченных шагов.

Массовостью алгоритма называется его способность быть пригодным для решения широкого класса задач данного типа. Алгоритм должен составляться не для решения отдельно взятой проблемы (задачи), а для создания возможности решения всех типов подобных проблем.

Детерминированность (определенность) алгоритма – это строгая определенность (однозначность предписываемых действий в каждой инструкции алгоритма), конкретность, чтобы в его записи не оставалось место двусмысленности и произвольному толкованию.

Результативностьюалгоритма называется свойство обеспечения нужного результата за конечное число шагов, если данные принадлежат области исходных данных, которыми определена массовость алгоритма.

Конечность определяет, что каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.

Понятность алгоритма – это обязательность составления алгоритма учетом системы команд исполнителя, т.е. алгоритм должен быть зафиксирован в той форме, которая будет понятна исполнителю. Значения всех приведенных действий в алгоритме должны быть ясными, точными и определенными.

Компактностью алгоритма называется его краткость, свойство минимальности инструкций. Наиболее удачно составленным алгоритмом считается алгоритм, обладающий компактностью и минимальностью количества вычислений при обязательной массовости алгоритма.

Каждый исполнитель должен однозначно понимать правило выполнения каждого действия алгоритма. Это называется свойством однозначности алгоритма.

Способы записи алгоритмов

Существует несколько способов записи алгоритмов, отличающихся друг от друга наглядностью, компактностью, степенью формализации и другими показателями:

· Графический– в виде блок-схем. Графическая запись алгоритмов в виде блок схем характеризуется использованием графических символов, математических записей и записей на естественном языке, наглядностью, пониманием записи алгоритма любым человеком, знакомым с алгоритмами, использованием простых правил описания последовательности действий.

· Словесный – на естественном языке. Достоинством записи алгоритма на естественном языке является доступность для понимания его любым человеком, а недостатки его состоят в громоздкости записи, ненаглядности, неточности и многозначности.

· На алгоритмическом языке (псевдокод) – то есть на специальном языке.

Алгоритмический язык – это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения. Этот язык, с одной стороны, близок к естественному языку, он записывается в виде простого текста. В состав алгоритмического языка входят числа, наименования величин и функций, знаки арифметических операций, скобки операций, а также термины с определенной функцией и некоторые символы.

Вычисление значения любой величины задается через выражение. Во время выполнения алгоритма вычисление значения выражения и приравнивание его к переменной называется присваиванием. Процесс присваивания осуществляется через команду присваивания. Образец записи команды присваивания следующий:

<имя переменной>:=<выражение>;

Оператор присваивания выполняет изменение значения переменной. При операторе присваивания вычисляется <выражение> в правой части, результат записывается в <переменную>.Тип выражения должен быть совместим по присваиванию с переменной.

Команда присваивания в блок-схеме изображается в виде четырехугольника блока процесса.

· В виде программ для ЭВМ – значит на любом алгоритмическом языке, понятном для машины, когда исполнителем является компьютер. Широко известны такие языки программирования как Паскаль, Дельфи, Пролог, Си и т.д.

При графическом описании алгоритма принято использовать стандартные графические символы. Блок-схема - самый распространенный и понятный способ записи алгоритмов. Это последовательность блоков, соединенных линиями передачи.

Элементы блок-схем

Название процесса

Вид блок-схемы

Описание действия

Терминатор