Какие свойства относятся к основным свойствам алгоритма
I. Дискретность
Одним из таких свойств является дискретность. Под дискретностью понимается то, что алгоритм состоит из описания последовательности шагов обработки, организованный таким образом, что в начальный момент задаётся исходная ситуация, а после каждого следующего шага ситуация преобразуется на основе данных, полученные в предшествующие шаги обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
II. Определённость
Другое свойство принято называть определённостью. Оно означает, что на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма.
К примеру, в одном из кулинарных рецептов сказано:
Слегка потрясите, чтобы смесь стала комковатой. Подогрейте коньяк в маленькой кастрюльке и влейте её в смесь.
Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.
III. Результативность
Третье свойство — результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким — либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.
К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм — когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .
IV. Понятность
Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.
V. Массовость
Наконец, еще одно свойство алгоритма — массовость. Оно означает, что имеется некоторое множество данных, которые могут обрабатываться алгоритмом, или данный алгоритм может быть применен для решения любой задачи одного типа. Массовость алгоритма тесно связанна с понятностью, в качестве примера можно разобрать пример с тортом, и сказать, что чем подробнее будет описан алгоритм приготовления, тем больше вероятности, что торт будет испечен. Также в качестве примера можно взять руководство по эксплуатации электрических приборов, инструкции и т. д. , чем полнее изложен алгоритм работы с приборами, тем легче нам с вами будет в нем разобраться. С точки зрения практической ценность алгоритмов важно, что бы множество допустимых исходных данных было достаточно большим, как правило, практическая ценность алгоритма не велика, если его можно использовать только один раз.
Тема: Алгоритм. свойства алгоритма
Алгоритм — это понятное и точное предписание исполнителю, выполнить конечную последовательность шагов, приводящей от исходных данных к искомому результату
Свойства алгоритма
q Дискретность (прерывность)- алгоритм должен быть разбит на
последовательность выполняемых шагов;
q Определенность (детерминированность, точность) — алгоритм
должен быть однозначно (точно) реализован исполнителем.
q Массовость —составленный алгоритм применим для решения
подобных задач с разными исходными данными.
q Конечность (результативность) — за конечное число шагов
должен быть получен результат;
q Формальность – свойство означающее, что любой исполнитель,
например, компьютер, действует формально, то есть строго
выполняет инструкции предусмотренные разработчиком
алгоритма.
q Понятность – алгоритм должен содержать только те команды,
которые понимает конкретный исполнитель.
Блок-схемой называется графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций.
При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:
· линейный;
· ветвящийся;
· циклический.
Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.
Ветвящимся называется такой вычислительный процесс, в котором выбор направления обработки информации зависит от исходных или промежуточных данных (от результатов проверки выполнения какого-либо логического условия).
Циклом называется многократно повторяемый участок вычислений. Вычислительный процесс, содержащий один или несколько циклов, называется циклическим.
Ответьте на вопросы теста
1.К основным свойствам алгоритма относятся…
а) краткость, определенность, верность, массовость, формальность
б) дискретность, важность, результативность, верность, формальность
в) достоверность, прерывистость, результативность, обобщенность, формальность
г) опеределенность, важность, результативность, массовость
2. Графическое описание алгоритма-это описание с помощью…
а) ….диаграмм
б)… блок-схем
в) …графиков
г) …всех перечисленных выше способов
3. К какому свойству алгоритма относится определение
Исполнитель, не понимая смысл алгоритма и постановку задачи, выполняя правильно каждую команду, может получить правильный результат.
а) массовость
б) результативность
в) формальность
г) достоверность
4. Описание алгоритма на алгоритмическом языке – это средство для записи алгоритма..
а) … в теоретическом виде
б) … в виде схем
в) … в аналитическом виде
г) … в специальном виде
5. Свойство алгоритма, определяющее пошаговый характер алгоритма называется…
а) результативностью
б) однозначностью
в) дискретностью
г) массовостью
д) все свойства определяют пошаговый характер алгоритма
6. Алгоритм, называется линейным, если…
а) он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
б) последовательность выполнения его команд зависит от истинности тех или иных условий;
в) его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
г) он включает в себя вспомогательный алгоритм;
д) его запись представлена в виде одной строки.
7.К основным свойствам алгоритма НЕ относится…
а) корректность;
б) определенность
в) массовость
г) результативность
д) непрерывность
Valera
Высший разум
(218913)
8 лет назад
Свойства алгоритма
Алгоритм обладает следующими свойствами:
1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т. е. преобразование исходных данных в результат осуществляется во времени дискретно.
2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.
3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.
4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т. е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.
SerGo
Высший разум
(101320)
8 лет назад
• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
• Понятность алгоритма — алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд.
• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.
• Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Свойства алгоритма
Евгенний Парфенюк
Ученик
(153)
1 месяц назад
Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
• Понятность алгоритма — алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд.
• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.
• Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Виды алгоритмов и способы их описания.
Различают следующие виды алгоритмов:
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными.Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
Например:
Алгоритм «Погода».
Начало
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Конец.
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.
Например:
Программа — описание структуры алгоритма на языке алгоритмического программирования.
Например:
program E3;
uses crt;
var t: real;
begin
clrscr;
writeln(‘введите температуру воздуха t=‘);
readln(t);
if t < 0 then writeln(‘одеть шубу’) else writeln(‘одеть куртку’);
end.
3. Алгоритм и его свойства .
Алгоpитм — заранее заданное понятное и точное предписание возможному исполнителю
совершить определенную последовательность действий для получения решения
задачи за конечное число шагов.
Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая,
биологическая или биотехническая) система, способная выполнить действия,
предписываемые алгоритмом.
Исполнителя хаpактеpизуют:
- среда;
- элементарные действия;
- система команд;
- отказы.
Среда (или обстановка) — это «место обитания» исполнителя.
Система команд . Каждый исполнитель может выполнять команды
только из некоторого строго заданного списка — системы команд исполнителя.
Для каждой команды должны быть заданы условия применимости (в
каких состояниях среды может быть выполнена команда) и описаны результаты
выполнения команды . После вызова команды исполнитель совершает
соответствующее элементарное действие .
Отказы исполнителя возникают, если команда вызывается
при недопустимом для нее состоянии среды.
Основные свойства алгоритмов :
1. Понятность для исполнителя — исполнитель алгоритма
должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный
вариант исходных данных, исполнитель должен знать, как надо действовать
для выполнения этого алгоритма.
2. Дискретность (прерывность, раздельность) —
алгоpитм должен представлять процесс решения задачи как последовательное
выполнение простых (или ранее определенных) шагов (этапов).
3. Определенность — каждое правило алгоритма
должно быть четким, однозначным и не оставлять места для произвола. Благодаря
этому свойству выполнение алгоритма носит механический хаpактеp и не требует
никаких дополнительных указаний или сведений о решаемой задаче.
4. Результативность (или конечность) состоит
в том, что за конечное число шагов алгоpитм либо должен приводить к решению
задачи, либо после конечного числа шагов останавливаться из-за невозможности
получить решение с выдачей соответствующего сообщения, либо неограниченно
продолжаться в течение времени, отведенного для исполнения алгоритма, с
выдачей промежуточных результатов.
5. Массовость означает, что алгоpитм решения
задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого
класса задач, различающихся лишь исходными данными. При этом исходные данные
могут выбираться из некоторой области, которая называется областью применимости
алгоритма.
Виды алгоритмов
Алгоритмы как логико-математические средства отражают указанные компоненты
человеческой деятельности и тенденции, а сами алгоритмы, в зависимости
от цели, начальных условий задачи, Петей ее решения, определения действий
исполнителя подразделяются следующим образом:
механические алгоритмы (детерминированные, жесткие, например,
алгоритм работы машины, двигателя). Механический алгоритм задает определенные
действия, обозначая их в единственной и достоверной последовательности,
обеспечивая тем самым однозначный требуемый или искомый результат, если
выполняются те условия процесса, задачи, для которых разработан алгоритм;
гибкие алгоритмы:
вероятностные (стохастические) алгоритмы дают программу решения
задачи несколькими путями или способами, приводящими к вероятному достижению
результата;
эвристические алгоритмы – это алгоритмы, в которых достижение
конечного результата программы действий однозначно не определено, так же
как не обозначена вся последовательность действий исполнителя. К эвристическим
алгоритмам относят, например, инструкции и предписания. В этих алгоритмах
используются универсальные логические процедуры и способы принятия решений,
основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
линейные алгоритмы – наборы команд (указаний), выполняемых
последовательно во времени друг за другом;
разветвляющиеся алгоритмы – алгоритмы, содержащие хотя бы
одно условие, в результате проверки которого компьютер обеспечивает переход
на один из двух возможных шагов;
циклические алгоритмы – алгоритмы, предусматривающие многократное
повторение одного и того же действия (одних и тех же операций) над новыми
исходными данными. К циклическим алгоритмам сводится большинство методов
вычислений, перебора вариантов;
вспомогательные (подчиненные) алгоритмы (процедуры) – алгоритмы,
ранее разработанные и целиком используемые при алгоритмизации конкретной
задачи. В некоторых случаях при наличии одинаковых последовательностей
указаний (команд) для различных данных с целью сокращения записи так же
выделяют вспомогательные алгоритмы.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е.
основных) элементов .
Логическая структура любого алгоритма может быть представлена комбинацией
трех базовых структур: следование, ветвление, цикл.
Характерной особенностью базовых структур является наличие в них одного
входа и одного выхода.
1. Базовая структура «следование». Образуется
последовательностью действий, следующих одно за другим:
Школьный алгоритмический язык | Язык блок-схем |
действие 1 |
2. Базовая структура «ветвление» .
Обеспечивает в зависимости от результата проверки условия ( да или нет )
выбор одного из альтернативных путей работы алгоритма. Каждый из путей
ведет к общему выходу , так что работа алгоритма будет
продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует
в четырех основных вариантах:
- если—то;
- если—то—иначе;
- выбор;
- выбор—иначе.
Школьный алгоритмический язык | Язык блок-схем |
1. если—то | |
| если условие то действия все | |
2. если—то—иначе | |
| если условие то действия 1 иначе действия 2 все | |
3. выбор | |
| выбор при условие 1: действия 1 при условие 2: действия 2 . . . . . . . . . . . . при условие N: действия N все | |
4. выбор—иначе | |
| выбор при условие 1: действия 1 при условие 2: действия 2 . . . . . . . . . . . . при условие N: действия N иначе действия N+1 все | |
Примеры структуры ветвление
Школьный алгоритмический язык | Язык блок-схем |
| если x > 0 то y := sin(x) все | |
| если a > b то a := 2*a; b := 1 иначе b := 2*b все | |
| выбор при n = 1: y := sin(x) при n = 2: y := cos(x) при n = 3: y := 0 все | |
| выбор при a > 5: i := i+1 при a = 0: j := j+1 иначе i := 10; j:=0 все |
3. Базовая структура «цикл». Обеспечивает многократное
выполнение некоторой совокупности действий, которая называется телом
цикла . Основные разновидности циклов представлены в таблице:
Школьный алгоритмический язык | Язык блок-схем |
Цикл типа пока . | |
| нц пока условие тело цикла (последовательность действий) кц | |
Цикл типа для . | |
| нц для i от i1 до i2 тело цикла (последовательность действий) кц | |
Примеры структуры цикл
Школьный алгоритмический | Язык блок-схем |
| нц пока i <= 5 S := S+A[i] i := i+1 кц | |
| нц для i от 1 до 5 X[i] := i*i*i Y[i] := X[i]/2 кц |
Особенностью итерационного цикла является то, что число
повторений операторов тела цикла заранее неизвестно. Для его организации
используется цикл типа пока . Выход из итерационного
цикла осуществляется в случае выполнения заданного условия.
На каждом шаге вычислений происходит последовательное приближение
к искомому результату и проверка условия достижения последнего.
Пример. Составить алгоритм вычисления бесконечной суммы
с заданной точностью (для
данной знакочередующейся бесконечной суммы требуемая точность будет достигнута,
когда очередное слагаемое станет по абсолютной величине меньше ).
Алгоритм на школьном АЯ | Блок-схема алгоритма |
| алг Сумма ( арг вещ x, Eps, рез вещ S) дано | 0 < x < 1 надо | S = x — x**2/2 + x**3/3 — … нач цел i, вещ m, p ввод x, Eps S := 0; i := 1 | начальные значения m := 1; p := -1 нц пока abs(m) > Eps p := -p*x | p — числитель | очередного слагаемого m := p/i | m — очередное слагаемое S := S + m | S — частичная сумма i := i + 1 | i — номер | очередного слагаемого кц вывод S кон |
Пример вложенных циклов для
Вычислить сумму элементов заданной матрицы А(5,3).
Матрица | S := 0; нц для i от 1 до 5 нц для j от 1 до 3 S:=S+A[i,j] кц кц |
Пример вложенных циклов пока
Вычислить произведение тех элементов заданной матрицы A(10,10), которые
расположены на пересечении четных строк и четных столбцов.
| i:=2; P:=1 нц пока i <= 10 j:=2 нц пока j <= 10 P:=P*A[i,j] j:=j+2 кц i:=i+2 кц |
Алгоритм, в состав которого входит итерационный цикл, называется итеpационным
алгоpитмом. Итерационные алгоритмы используются при реализации
итерационных численных методов.
В итерационных алгоритмах необходимо обеспечить обязательное достижение
условия выхода из цикла ( сходимость итерационного процесса ).
В противном случае произойдет «зацикливание» алгоритма,
т.е. не будет выполняться основное свойство алгоритма — результативность .