Алгоритм. Разновидности, структура, свойства. Способы записи алгоритмов.
Содержание
1. АЛГОРИТМ...............................................................................................
2.рАзновидности алгоритмов........................................................
3. Свойства алгоритмов....................................................................
4. способы записей алгоритмов...................................................
5. структуры алгоритмов..................................................................
Список литературы..............................................................................
1.
Алгоритм –
это понятное и точное представление исполнителю совершить последовательность действий, направленных на решение поставленной задачи или достижение указанной цели.
Термин имеет интересное историческое происхождение. В IX веке великий узбекский математик аль-Хорезми
разработал правила арифметических действий над десятичными числами. Совокупность этих правил в Европе стали называть «алгоритм». Впоследствии слово трансформировать до известного нам сейчас вида и, кроме того, расширило свое значение: алгоритмом стали называть любую последовательность действий (не только арифметических), которая приводит к решению той или иной задачи. Можно сказать, что понятие вышло за рамки математики и стало применяться в самых различных областях.
2.
Можно выделить три разновидности алгоритмов: вычислительные, информационные и управляющие.
Первые, как правило, работают с простыми видами данных (числа, вектора, матрицы), но зато процесс вычисления может быть длинным и сложным. Информационные алгоритмы, напротив, реализуют сравнительно небольшие процедуры обработки (например, поиск элементов, удовлетворяющих определенному признаку), но для больших объемов информации. Наконец, управляющие алгоритмы непрерывно анализируют информацию, поступающую от тех или иных источников, и выдают результирующие сигналы, управляющие работой тех или иных устройств. Для этого вида алгоритмов очень существенную роль играет их быстродействие, т.к. управляющие сигналы всегда должны появляться в нужный момент времени.
Каждый алгоритм – это правила, описывающие процесс преобразования исходных данных в необходимый результат. Заметим, что данное важное свойство в некоторых книгах приводят как определение алгоритма.
3.
Для того чтобы произвольное описание последовательности действий было алгоритмом, оно должно обладать следующими свойствами.
· Дискретность
Процесс решения задачи должен быть разбит на последовательность отдельных шагов, каждый из которых называется командной.
Примером команд могут служить пункты инструкции, нажатие на одну их кнопок пульта управления, рисование графического примитива (линии, дуги и т.п.), оператор языка программирования. Наиболее существенным здесь является тот факт, что алгоритм есть последовательность четко выделенных пунктов – такие «прерывные» объекты в науке принято называть дискретными.
· Понятность
Каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены. Данное требование можно сформулировать более просто и конкретно. Составим полный список команд, который умеет делать исполнитель алгоритма, и назовем его системой команд исполнителя
(СКИ).
Требования использовать при составлении алгоритмов только те команды, которые входят в СКИ, связано с тем, что исполнение алгоритма осуществляется формально, без возможности вникнуть в суть команд и проанализировать их.
Одним из таких (вернее, основных из них) «бездушных» исполнителей является ЭВМ. Вообще ЭВМ является универсальным исполнителем алгоритмов. Это связано с тем, что любой алгоритм, составленный для ЭВМ, в конечном итоге транслируется в ее СКИ и, таким образом, становится доступным для исполнения.
· Определенность
(Детерминированность)
Команды, образующие алгоритм (или, можно сказать, входящие в СКИ), должны быть предельно четкими и однозначными. Их результат не может зависеть от какой-либо дополнительной информации извне алгоритма. Сколько бы раз вы не запускали программу, для одних и тех же исходных данных всегда будет получаться один и тот же результат.
Определенность также предполагает, что данные, необходимые для выполнения очередной команды алгоритма, получены на одном из предыдущих шагов алгоритма.
· Корректность
Любой алгоритм создан для решения той или иной задачи, поэтому нам необходима уверенность, что это решение будет правильным для любых допустимых исходных данных. Указанное свойство алгоритма принято называть его корректностью. В связи с обсуждаемым свойством большое значение имеет тщательное тестирование алгоритма перед его использованием. Как показывает опыт, грамотная и всесторонняя отладка для сложных алгоритмов часто требует значительно больших усилий, чем собственно разработка алгоритмов. При этом важно не столько количество проверенных сочетаний входных данных, сколько количество их типов.
Например, можно сделать сколько угодно проверок для положительных значений аргумента алгоритма, но это никак не будет гарантировать корректную его работу в случае отрицательной величины аргумента.
· Массовость
Алгоритм имеет смысл разрабатывать только в том случае, когда он будет применяться многократно для различных наборов исходных данных. Например, если составляется алгоритм обработки текстов, то вряд ли целесообразно ограничить его возможности только русскими буквами – стоит предусмотреть также латинский алфавит, цифры, знаки препинания и т.д. Тем более что обобщение особых трудностей не вызывает.
Таковы основные свойства алгоритмов. Если их внимательно проанализировать, то становиться очевидным, что исполнитель алгоритма не нуждается в какой либо фантазии и сообразительности. Боле того, для выполнения алгоритма совсем не требуется его понимание, а правильный результат может быть получен путем формального и чисто механического следования содержанию алгоритма.
Из возможности формального исполнения алгоритма следует очень важное следствие: поскольку осознавать содержание алгоритма не требуется, его исполнение вполне можно доверить автомату или ЭВМ. Таким образом, составление алгоритма является обязательным этапом автоматизации любого процесса.
Как только разработан алгоритм, машина может исполнять его лучше человека – быстрее и, что очень важно, не ошибаясь.
4.
Основными способами записи алгоритмов являются:
· словесный;
· словесно-формальный;
· на алгоритмическом языке;
· графический (блок-схема);
· на языке программирования высокого уровня.
5.
Основными алгоритмическими структурами (ОАС) является следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.
На схемах СЕРИЯ обозначает один или несколько любых операторов; ЛВ – логическое выражение (если его значение ИСТИНА, переход происходит по ветви Да, иначе НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ – параметр цикла, НЗ – начальное значение параметра цикла, КЗ – конечное значение параметра цикла, Ш – шаг изменения параметра цикла.
Простейшие задачи имеют линейный алгоритм
решения. Это означает, что такой алгоритм не содержит проверок условий и повторений, действия в нем выполняются последовательно, одно за другим, т.е. при его реализации используется структура «следование».
Чаще всего алгоритмы предполагают обработку некоторых величин. Величина
- это элемент данных с точки зрения их смыслового (семантического) содержания или обработки. При разработке алгоритма данные можно разбить по смыслу на входные – аргументы, выходные – результаты, и промежуточные. Исходные (входные) – это данные, известные перед выполнением задачи, из условия. Выходные данные – результат решения задачи. Переменные, которые не являются ни аргументом, ни результатом алгоритма, а используются только для обозначения вычисляемого промежуточного значения, называются промежуточными.
Чаще всего требуется указать имена и типы данных – целый, вещественный, логический и символьный, либо структурированный, базирующийся на одном из названных.
Ветвления играют в алгоритмах очень большую роль, поскольку предусматривают корректную реакцию на самые разнообразные ситуации, возникающие в процессе обработки информации. Благодаря этой структуре алгоритм приобретает способность выбирать один из существующих вариантов работы, наиболее подходящих к сложнейших в данный момент ситуации. В частном случае речь может идти о выполнении или игнорировании при определенных условиях того или иного участка алгоритма.
Значение ветвления в современном программном обеспечении трудно переоценить. Достаточно вспомнить элементы управления, такие, как меню, радиокнопки, флажки проверки или списки. Именно
Приведем также полную форму ветвления в различных алгоритмических языках.
QBasic
IF
<ЛВ> THEN
операторы ELSE
операторы ENDIF
Pascal
IF
<ЛВ> THEN
оператор ELSE
оператор
C
if
(<ЛВ>) оператор; else
оператор;
Очевидно, что запись отличается лишь незначительными второстепенными деталями. Для получения неполного ветвления ветвь «иначе» разрешается опускать.
Достаточно часто при организации алгоритма решение задачи необходимо одну и ту же определенную последовательность команд выполнить несколько раз подряд. Конечно, самый простой способ – записать эти команды несколько раз друг за другом, и необходимое повторение действий будит организовано. Но как быть в тех случаях, когда количество команд, которые исполняются несколько раз, слишком велико? Или само количество повторений команд огромно? Или вообще неизвестно, а сколько же раз нужно повторить последовательность этих команд? Решить эти проблемы можно, если использовать алгоритмическую структуру «цикл».
Командой повторения
, или циклом
, называется такая форма организации действий в алгоритме, при которой выполнение одной и той же последовательности команд повторяется до тех пор, пока истинно некоторое логическое выражение.
Для организации цикла необходимо выполнить следующие действия:
· перед началом цикла задать начальное значение параметров (переменных, используемых в логическом выражении, отвечающем за продолжение или завершение цикла);
· внутри цикла изменять переменную (или переменные), которая сменит значение логического выражения, за счет которого продолжается цикл, на противоположное (для того чтобы цикл в определенный момент завершился);
· вычислять логическое выражение – проверять условие продолжения или окончания цикла;
· выполнять операторы внутри цикла;
управлять циклом, т.е. переходить к его началу, если он не закончен, или выходить из цикла в противоположном случае.
Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред- и пост- условием).
Опишем схематично, как выполняется каждый из циклов.
Цикл с предусловием:
а) вычисляет значение логического выражения;
б) если значение логического выражения «истина», переход к следующему пункту, иначе к п. д)
в) выполняется тело цикла;
г) переход к п.а);
д) конец цикла.
Цикл с постусловием:
а) выполняется тело цикла;
б) вычисляется значение логического выражения;
в) если значение логического выражения «лож», переход к п. а), иначе к следующему пункту;
г) конец цикла.
Замечание.
Таким образом, цикл с послесловием организован, в организован, в частности, в алгоритмических языках Pascal и QBasic. В языке С переход к повторению вычислений, как и в цикле с предусловием, осуществляется в случае истинности логического выражения.
Цикл с параметром:
а) вычисляются значения выражений, определяющие начальное значение параметра цикла;
б) параметру цикла присваивается начальное значение;
в) параметр цикла сравнивается с конечным значением;
г) если параметр цикла превосходит (при положительном шаге) конечное значение параметра цикла (или, наоборот, меньше конечного значение параметра цикла при отрицательном шаге), переход к п. з), иначе к следующему пункту;
д) выполняется тело цикла;
е) параметр цикла автоматически увеличивается на значение шага;
ж) переход к п. в.
з) конец цикла
Запись цикла на языках программирования
| QBasic
|
Pascal
|
C
|
|
| С предусловием |
WHILE ЛВ операторы WEND |
WHILE ЛВ DO оператор |
while (ЛВ) оператор; |
| С постусловием |
LООР операторы UNTIL ЛВ |
REPEAT операторы UNTIL ЛВ; |
do оператор while (ЛВ); |
| С параметром |
FOR ПЦ= НЗ ТО КЗ STEР Ш операторы NEXT ПЦ |
FOR ПЦ := НЗ TO (DOWNTO) КЗ DO оператор; |
For (ПЦ = НЗ; НЗ<=КЗ; ПЦ = ПЦ+Ш) оператор; |
Циклы с предусловием и постусловием в большинстве случаев (за исключением отдельных реализаций алгоритмических языков) являются более универсальными по сравнению с циклом с параметром, поскольку в последнем требуется заранее указать число повторений, в то время как в первых двух это не требуется. Цикл с параметром в любом случае может быть преобразован к циклу с пред- или постусловием. Обратное верно не всегда.
Замечание.
В языке С
цикл for
на самом деле является универсальным циклом с предусловием. В частности, из него можно сделать и описанную форму цикла с параметром.
Примеры использования основных алгоритмических структур и их суперпозиций для составления алгоритмов, а по ним – программ приводятся в многочисленной литературе по программированию, по этому не будим здесь останавливаться.
Наконец, рассмотрим вопрос анализа алгоритмов.
Одну и ту же задачу могут решать много алгоритмов. Эффективность работы каждого из них описывается разнообразными характеристиками. Прежде чем анализировать эффективность алгоритма, нужно доказать, что данный алгоритм правильно решает задачу, то можно посмотреть, насколько это решение эффективно.
При анализе алгоритма определяется количество «времени», необходимое для его выполнения. Это не реальное число секунд или других промежутков времени, а приблизительное число операций, выполняемых алгоритмом. Число операций и измеряет относительное время выполнения алгоритма. Таким образом, иногда «временем» называют вычислительную сложность алгоритма. Фактическое количество секунд, требуемое для выполнения алгоритма на компьютере, непригодно для анализа, т.к. обычно интересует только относительная эффективность алгоритма, решающего конкретную задачу. Действительно, время, требуемое на решение задачи,- не очень хороший способ измерять эффективность алгоритма , потому что алгоритм не становится лучше, если его исполнять на более медленном.
На самом деле фактическое количество операций алгоритма на тех или иных входных данных не представляет большого интереса и не очень много сообщает об алгоритме. Реально определяется зависимость числа операций конкретного алгоритма на тех или иных входных данных. Можно сравнить два алгоритма по скорости роста числа операций. Именно скорость роста играет ключевую роль, поскольку при небольшом размере входных данных алгоритм А может требовать меньшего количества операций, чем алгоритм В, но при росте объема входных данных ситуация может поменяться на противоположную.
Два самых больших класса алгоритмов – это алгоритмы с повторением и рекурсивные алгоритмы. В основе алгоритмов с повторением лежат циклы и условные выражения; для анализа алгоритмов требуется оценить число операций, выполняемых внутри цикла, и число итераций цикла. Рекурсивные алгоритмы разбивают большую задачу на фрагменты и применяются к каждому фрагменту по отдельности. Такие алгоритмы называются иногда «разделяй и властвуй», и их использование может оказаться очень эффективным. В процесс решения большой задачи путем деления ее на меньшие создаются небольшие, простые т понятные алгоритмы. Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей и их размере, можно вывести рекуррентное соотношение для сложности алгоритма. Полученному рекуррентному соотношению можно придать замкнутый вид, затем сравнивать результат с другими выражениями.
Список литературы
1. Ахо, Альфред Структура данных и алгоритмы [Текст]. - М.: Издательский дом «Вильямс», 2000. - 384 с.
2. Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. - М:. Мир, 1978. - 356 с.
3. Вирт, Н. Алгоритмы и структуры данных [Текст].- М:. Мир, 1989. - 360 с.
4. Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. - М.: Наука, 1987. - 288 с.
5. Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.