Какие бывают свойства алгоритма как
Виды алгоритмов и способы их описания.
Различают следующие виды алгоритмов:
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными.Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
Например:
Алгоритм «Погода».
Начало
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Конец.
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.
Например:
Программа — описание структуры алгоритма на языке алгоритмического программирования.
Например:
program E3;
uses crt;
var t: real;
begin
clrscr;
writeln(‘введите температуру воздуха t=‘);
readln(t);
if t < 0 then writeln(‘одеть шубу’) else writeln(‘одеть куртку’);
end.
I. Дискретность
Одним из таких свойств является дискретность. Под дискретностью понимается то, что алгоритм состоит из описания последовательности шагов обработки, организованный таким образом, что в начальный момент задаётся исходная ситуация, а после каждого следующего шага ситуация преобразуется на основе данных, полученные в предшествующие шаги обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
II. Определённость
Другое свойство принято называть определённостью. Оно означает, что на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма.
К примеру, в одном из кулинарных рецептов сказано:
Слегка потрясите, чтобы смесь стала комковатой. Подогрейте коньяк в маленькой кастрюльке и влейте её в смесь.
Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.
III. Результативность
Третье свойство — результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким — либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.
К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм — когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .
IV. Понятность
Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.
V. Массовость
Наконец, еще одно свойство алгоритма — массовость. Оно означает, что имеется некоторое множество данных, которые могут обрабатываться алгоритмом, или данный алгоритм может быть применен для решения любой задачи одного типа. Массовость алгоритма тесно связанна с понятностью, в качестве примера можно разобрать пример с тортом, и сказать, что чем подробнее будет описан алгоритм приготовления, тем больше вероятности, что торт будет испечен. Также в качестве примера можно взять руководство по эксплуатации электрических приборов, инструкции и т. д. , чем полнее изложен алгоритм работы с приборами, тем легче нам с вами будет в нем разобраться. С точки зрения практической ценность алгоритмов важно, что бы множество допустимых исходных данных было достаточно большим, как правило, практическая ценность алгоритма не велика, если его можно использовать только один раз.
Алгоритм — это система точных и
понятных предписаний о содержании и последовательности выполнения конечного
числа действий, необходимых для решения любой задачи данного типа.
Примеры: правила сложения, умножения,
решения алгебраических уравнений и т.п.
Свойства алгоритма:
1.Универсальность (массовость) —
применимость алгоритма к различным наборам исходных данных.
2.Дискретность — процесс решения задачи
по алгоритму разбит на отдельные действия.
3.Конечность — каждое из действий и весь
алгоритм в целом обязательно завершаются.
4.Результативность — по завершении
выполнения алгоритма обязательно получается конечный результат.
5.Выполнимость (эффективность) —
результата алгоритма достигается за конечное число шагов.
6.Детерминированность (определенность) —
алгоритм не должен содержать предписаний, смысл которых может восприниматься
неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один
и тот же результат.
7.Последовательность – порядок исполнения
команд должен быть понятен исполнителю и не должен допускать
неоднозначности.
Классы алгоритмов.
1.вычислительные алгоритмы,
работающие со сравнительно простыми видами данных, такими как числа и матрицы,
хотя сам процесс вычисления может быть долгим и сложным;
2.информационные алгоритмы,
представляющие собой набор сравнительно простых процедур, работающих с большими
объемами информации (алгоритмы баз данных);
3.управляющие алгоритмы,
генерирующие различные управляющие воздействия на основе данных, полученных от
внешних процессов, которыми алгоритмы управляют.
По типу передачи управления алгоритмы
бывают: основные (главные выполняемые программы) и вспомогательные
(подпрограммы).
Для задания алгоритма необходимо описать
следующие его элементы:
1.набор объектов, составляющих
совокупность возможных исходных данных, промежуточных и конечных результатов;
2.правило начала;
3.правило непосредственной переработки
информации (описание последовательности действий);
4.правило окончания;
5.правило извлечения результатов.
Способы описания алгоритмов.
Символьный, когда алгоритм описывается с
помощью специального набора символов (специального языка).
Словесная форма записи алгоритмов обычно
используется для алгоритмов, ориентированных на исполнителя-человека. Команды
такого алгоритма выполняются в естественной последовательности, если не
оговорено противного.
Графическая запись с помощью блок-схем
осуществляется рисованием последовательности геометрических фигур, каждая из
которых подразумевает выполнение определенного действия алгоритма. Порядок
выполнения действий указывается стрелками. Графическая запись алгоритма имеет
ряд преимуществ: каждая операция вычислительного процесса изображается отдельной
геометрической фигурой и графическое изображение алгоритма наглядно показывает
разветвления путей решения задачи в зависимости от различных условий, повторение
отдельных этапов вычислительного процесса и другие детали.
Виды блоков.
Правила создания блок – схем:
1.Линии, соединяющие блоки и указывающие
последовательность связей между ними, должны проводится параллельно линиям
рамки.
2.Стрелка в конце линии может не
ставиться, если линия направлена слева направо или сверху вниз.
3.В блок может входить несколько линий,
то есть блок может являться преемником любого числа блоков.
4.Из блока (кроме логического) может
выходить только одна линия.
5.Логический блок может иметь в качестве
продолжения один из двух блоков, и из него выходят две линии.
6.Если на схеме имеет место слияние
линий, то место пересечения выделяется точкой. В случае, когда одна линия
подходит к другой и слияние их явно выражено, точку можно не ставить.
7.Схему алгоритма следует выполнять как
единое целое, однако в случае необходимости допускается обрывать линии,
соединяющие блоки.
Виды алгоритмов.
В линейном алгоритме операции выполняются
последовательно, в порядке их записи. Каждая операция является самостоятельной,
независимой от каких-либо условий. На схеме блоки, отображающие эти операции,
располагаются в линейной последовательности.
В алгоритме с ветвлением предусмотрено
несколько направлений (ветвей). Каждое отдельное направление алгоритма обработки
данных является отдельной ветвью вычислений. Направление ветвления выбирается
логической проверкой, в результате которой возможны два ответа:
1.«да» — условие выполнено.
2.«нет» — условие не выполнено.
Циклические алгоритмы содержат цикл – это
многократно повторяемый участок алгоритма.Различают циклы с предусловием и
постусловием.Также циклы бывают детерминированные и итерационные.Цикл называется
детерминированным, если число повторений тела цикла заранее известно или
определено. Цикл называется итерационным, если число повторений тела цикла
заранее неизвестно, а зависит от значений параметров (некоторых переменных),
участвующих в вычислениях.
Решение задач с использованием компьютера основано на понятии алгоритма, который является точным описанием вычислительного процесса, ведущего от варьируемых начальных данных к конечному результату.
Алгоритмы заложены в основе каждой программы, а также они встречаются во многих сферах деятельности человека (например, рецепты, схема вязания или танца).
Понятие алгоритма
Определение 2
Алгоритм представляет собой точное описание определенного процесса, инструкцию по его выполнению.
Процесс разработки алгоритма — достаточно сложный и трудоемкий.
Можно также сказать, что алгоритм представляет собой конечную последовательность команд для исполнителя, направленную на достижение конкретной цели.
Цель же, в свою очередь, является достижением желаемого результата.
В качестве исполнителя могут выступать люди, живые существа, автоматические устройства, способные к исполнению и восприятию команд.
Готовые работы на аналогичную тему
Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость
Определение 3
Перечень команд, воспринимаемых и выполняемых (по возможности) исполнителем, называют системой команд.
Каждый алгоритм предназначен для конкретного исполнителя. Исполнение алгоритма начинается с первой команды. После того, как ее исполнили, переходят к следующей команде и так до конца алгоритма.
В качестве примера алгоритма можно вспомнить известный всем со школы арифметический способ сложения двух положительных чисел «столбиком». Алгоритм данной задачи представим в виде системы следующих действий:
- выделим в слагаемых разряды единиц и сложим единицы;
- при получении суммы меньшей 10 запишем ее в разряде единиц под нижним числом;
- при получении суммы большей или равной 10 запишем в разряде единиц только количество единиц, затем выделим в слагаемых разряд десятков и запишем полученный при сложении единиц десяток над разрядом десятков первого (верхнего) слагаемого;
- сложим десятки и т. д.
Аналогичные указания дают для сложения единиц других разрядов числа. Системой-исполнителем этого алгоритма может стать как ЭВМ, так и человек.
Понятие алгоритма в теорию и практику обучения вошло в конце $50$-х годов прошлого столетия в связи с развитием программированного обучения и применением обучающимися машин.
Способы описания алгоритмов
Существуют различные способы описания алгоритмов. Приведем основные из них:
- словесный (пошаговое описание);
- табличный и в виде формул;
- графический (в виде схем);
- с использованием псевдокода (алгоритмического языка).
Алгоритмический язык является формальным языком, предназначенным для записи алгоритма. В его состав входят набор основных символов (алфавит), система точных правил построения текстов (синтаксис) и система соответствия синтаксически допустимых текстов языка описываемым действиям и объектам (семантика).
Множество языков программирования, используемых при ре¬шении задач на ЭВМ, являются алгоритмическими.
Псевдокод представляет собой способ описания логики программы до начала ее программирования и занимает промежуточное положение между машинным языками и естественными.
Под схемой алгоритма понимают графическое пред¬ставление последовательности шагов алгоритма, наглядно показывающее взаимосвязь опера¬ций, которые осуществляются в алгоритме на каждом шаге, и их очередность. Другими словами, для графического изображения структуры алгоритма используется блок-схема.
В соответствии с блок-схемой последовательность действий указывается с по¬мощью стрелок, которые соединяют отдельные блоки и показывают, какой блок и за каким должен быть выполнен.
Свойства алгоритмов
Существует ряд определенных требований к алгоритмам. Перечислим семь важных свойств, которыми должен обладать каждый алгоритм:
- Наличие ввода исходных данных.
- Наличие вывода результата выполнения.
- Однозначность, так как компьютеру понятны лишь однозначные инструкции.
- Общность, в соответствии с которой алгоритм может использоваться не только для решения одной задачи, но и целого класса задач.
- Корректность, согласно которой при выполнении алгоритма должно быть всегда правильное решение задачи.
- Конечность означает, что решение задачи необходимо получить за конечное число шагов.
- Эффективность означает, что для решения задачи необходимо использовать ограниченные ресурсы компьютера (объем оперативной памяти, процессорное время и т. д.).
Эффективность алгоритма определяют с учетом потребляемых ресурсов компьютера, к которым относят быстродействие (количество выполняемых операций и затраты трудоемкости на каждую из них) и общий объем оперативной памяти, которая выделяется под данные. Приведенные показатели могут иногда быть противоречивыми: так в результате повышения быстродействия могут потребоваться дополнительные расходы памяти и наоборот. При возможности улучшения одного показателя без ущерба для другого необходимо этого добиваться. В случаях, когда возникает дилемма, рекомендуется предпочесть экономию памяти в ущерб производительности, поскольку тактовая частота процессоров растет опережающими темпами по сравнению с объемами оперативной памяти.
Специалистами предлагается ряд мер для повышения эффективности.
Блок-схемы
Основные алгоритмические структуры изображаются с помощью специальных графических символов. Все составляющие блок-схемы соединяются между собой в той последовательности, в какой они должны быть исполнены.
Кроме того, в алгоритмах используются разветвляющие и циклические блоки.
Обязательными блоками являются блоки начала и конца алгоритма. Между ними размещаются остальные блоки алгоритма.
Операторный блок (блок действия) содержит команды обработки данных.
Блок проверки условия предполагает 2 варианта дальнейшего развития решения задачи, в зависимости от того или иного выполнения поставленного условия.
Блоки ввода или вывода данных. Для выполнения алгоритма необходимы не только команды, но и данные, поступающие из вне. Для получения этих данных используется блок ввода. Для того, чтобы можно было вывести результат выполнения программы, либо какое-нибудь сообщение используют блок вывода.
Ниже на рисунке представлены графические изображения основных блоков алгоритма.