Понятие алгоритма. Свойства алгоритмов. Уровни описания алгоритмов. Базовые структуры алгоритмов.
Понятие алгоритма относится к фундаментальным понятиям математики и информатики. Слово алгоритм происходит от algorithmi – латинской формы написания имени великого математика IX в. Аль Хорезми, который первым сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению поставленной задачи.
Строгого формального определения алгоритма не существует.
Алгоритм – это предписание, однозначно задающее процесс преобразования исходной информации в виде последовательности элементарных дискретных шагов, приводящих за конечное число их применений к результату.
Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающаяся детерминированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов.
Свойства алгоритма:
- Детерминированность(от лат. determinare – определять): если метод вычисления сообщить другому лицу в виде указаний о действиях на отдельных этапах вычислений, то это лицо обязательно алгоритм выполнит. Когда мы говорим о каких-то машинных действиях, то имеем в виду именно определенность тех правил, по которым выполняем эти действия.
- Массовостьвыражается в том, что алгоритм как единое предписание, определяющее вычислительный процесс, может быть начат с множества различных исходных данных, но всегда приведет вычислителя к конечному результату, т.е. с помощью алгоритма можно решать не одну задачу, а серию однотипных задач, что называется разрешимостью таких задач.
- Утверждение о том, что алгоритм всегда ведет к получению результата, определяет его результативность.
- Выполнение алгоритма разбивается на последовательность законченных действий – шагов. Переход к следующему шагу возможен лишь после завершения предыдущего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой. Это свойство алгоритма называется дискретностью.
- Запись алгоритма должна быть такова, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнить следующей. Это свойство алгоритма называется точностью.
- Каждый алгоритм строится в расчете на конкретного исполнителя, который должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением. Это свойство алгоритма называется понятностью(для данного исполнителя).
- Можно еще выделить такое свойство алгоритма, как правильность. Алгоритм правильный, если выполнение дает правильные результаты решения поставленных задач. Алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершиться вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся не правильными.
Уровни описания алгоритмов:
- неформальное описание (описание алгоритма на естественном языке без использования жестких конструкций);
- полуформальное описание (описание алгоритма с использованием условных обозначений);
- формальное описание (описание алгоритма с использованием жестких конструкций, понятных исполнителю – язык программирования, язык машинных кодов и т.д.).
Способы записи алгоритмов:
- Словесныйспособ предназначен для исполнения алгоритма человеком.
- Графический способ (блок-схемы) является вспомогательным способом описания алгоритмов, облегчающим процесс создания алгоритмов сложных задач.
- Алгоритмический язык. Исполнителем алгоритмов, записанных на алгоритмическом языке, может быть как человек (при этом разрешается использовать любые согласованные команды – школьный алгоритмический язык), так и компьютер, если используется только некоторая разрешенная система команд (язык исполнителя Кукарача).
- Языки программированияслужат для окончательной записи алгоритма в таком виде, в котором он может быть исполнен ЭВМ.
Исполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В таком случае говорят, что исполнитель действует формально, т.е. не отвлекаясь от содержания поставленной задачи и только строго выполняя некоторые правила, инструкции.
Базовые структуры алгоритмов:
- Структура следования
- Разветвляющиеся структуры:
- ветвление полное (если – то — иначе);
- ветвление не полное(если – то);
- Циклические структуры:
- с предусловием;
- с пост условием;
- с параметром.
При использовании структуры следования операции записываются последовательно одна за другой, что представляет собой определенную последовательность.
Разветвляющиеся структуры – это такая форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий.
Полное ветвление. Эта структура называется также «ЕСЛИ – ТО — ИНАЧЕ». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран.
Неполное ветвление. Если в алгоритме для одного из результатов проверки ничего предпринимать не надо, то в этом случае можно применять только один обрабатывающий блок. Эту структуру иначе называют «ЕСЛИ–ТО».
В качестве условия в команде ветвления может быть использовано любое понятное исполнителю утверждение, которое может быть истинным или ложным. Условия могут быть простыми, то есть состоящими из одного отношения между величинами, или составными – содержащими два и более отношений. При записи составных условий используются служебные слова и (AND), или (OR), не (NOT) и скобки для указания порядка проверки условий.
Цикл (или повторение) предусматривает возможность многократного повторения некоторых действий в алгоритме. Различают три вида циклов: с предусловием, с постусловием и с параметром.
Цикл с предусловием: цикл начинается с проверки логического выражения. Если оно истинно, то выполняется тело цикла (набор команд) и затем снова проверяется логическое выражение. Цикл заканчивается тогда, когда логическое выражение становится неверным.
Цикл с постусловием. Цикл начинается с выполнения тела цикла, а затем проверяется условие. Цикл повторяется в том случае, если условие оказывается неверным (ложь). Выход из цикла осуществляется тогда, когда условие становится истинным.
Цикл с параметром. Цикл с параметром отличается от рассмотренных циклов тем, что в его составе имеется переменная цикла и автоматический счетчик, который изменяет переменную цикла на единицу (по умолчанию) или на величину указанного шага от начального значения до конечного. Выход из цикла происходит тогда, когда переменной цикла присваивается значение большее указанного конечного.
Оставить комментарий