Что такое алгоритм какими свойствами он обладает

I. Дискретность

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

II. Определённость

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

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

Формальному исполнителю здесь неясно, требуется ли трясти смесь, пока она вся не станет комом, и какой всё-таки величины кастрюля. Большая или маленькая? И до какой температуры надо подогреть коньяк. Так что такой алгоритм любому исполнителю выполнить довольно трудно, практически невозможно. Можно сказать, что в алгоритме не должны присутствовать не определённые слова: немного, чуть-чуть, слегка и т. д.

III. Результативность

Третье свойство — результативность алгоритма. Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. Если это по каким — либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует.

К примеру, в инструкции по применению лекарства от кашля сказано:
Если врач не прописал, то принимать 3-4 раза в день по 15-20 капель, лучше всего в горячей сладкой воде.
Здесь не определено, например, когда должен заканчиваться алгоритм — когда кашель пройдет или когда лекарство закончиться. Свойство результативности обычно подразумевает конечность алгоритма, т. е. завершение его работы за конечное число шагов (при этом количество шагов может быть заранее не известным и различным для разных исходных данных) .

IV. Понятность

Надо сказать, что алгоритм должен быть понятен не только автору, но и исполнителю. Если мы предложим исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т. к. такой программы в нём не заложено. Или, например, если мы предложим какому-нибудь мальчику испечь торт то у него, как правило, ни чего не получится, потому что этого они делать не умеют. Но если мы составим подробный алгоритм работы, разобьем его на элементарные шаги, такие, что он без труда поймёт и сможет выполнить каждый шаг, то он сможет успешно испечь любой торт. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Это свойство алгоритма называют понятностью.

V. Массовость

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

Источник

Виды алгоритмов и способы их описания.

Различают следующие виды алгоритмов:

линейный – список команд (указаний), выполняемых последовательно друг за другом;

Что такое алгоритм какими свойствами он обладает

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

Что такое алгоритм какими свойствами он обладает

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

Что такое алгоритм какими свойствами он обладает

Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными.Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

Например:

Алгоритм «Погода».

Начало

1. определить температуру воздуха

2. если температура ниже 0, то надеть шубу, иначе надеть куртку

Конец.

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

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

Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.

Например:

Программа — описание структуры алгоритма на языке алгоритмического программирования.

Например:

program E3;

uses crt;

var t: real;

begin

clrscr;

writeln(‘введите температуру воздуха t=‘);

readln(t);

if t < 0 then writeln(‘одеть шубу’) else writeln(‘одеть куртку’);

end.

Источник

Valera

Высший разум

(218913)

8 лет назад

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

Алгоритм обладает следующими свойствами:

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

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

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

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

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

SerGo

Высший разум

(101320)

8 лет назад

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

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

• Понятность алгоритма — алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд.

• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

Евгенний Парфенюк

Ученик

(153)

4 недели назад

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

• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

Источник

Содержание

Алгоритм. Понятие алгоритма. 2

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

Система команд исполнителя 3

Формальное исполнение алгоритма 3

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

1. Естественный язык (словесная запись алгоритма) 3

2. Язык блок-схем (графическая запись алгоритмов). 4

3. Алгоритмический язык (псевдокоды). 5

4. Формальный язык (язык программирования). 5

Структуры алгоритмов. 5

Структура следование 6

Структура ветвление (развилка). 6

Структура повторение (цикл) 7

Контрольные вопросы. 10

Алгоритм. Понятие алгоритма.

Алгоритм — понятное и точное предписание (указание) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи.

Алгоритм — список команд, набор инструкций, выполнив которые можно получить определенный результат.

Сборником алгоритмов можно назвать книгу кулинарных рецептов. Рассмотрим простейший алгоритм.

Пр. 1. Алгоритм заварки чая.

1. Подготовить исходные величины — заварку, воду, чайник, заварник

2. Налить в чайник воду.

3. Насыпать в заварник заварку.

4. Довести воду до кипения.

5. Налить в заварник кипяток и подождать 3 минуты.

6. Заварка готова.

Не каждый набор команд можно назвать алгоритмом. Алгоритм обладает определенными свойствами:

1. Конечность. Суть свойства: алгоритм не может быть бесконечным, он должен закончиться за конечное число шагов.

2. Результативность. Суть свойства: выполнив алгоритм, должны получить результат. Установление факта, что задача решения не имеет, является тоже результатом исполнения алгоритма.

3. Дискретность (прерывистость). Суть свойства: алгоритм разбивается на отдельные шаги (команды), которые выполняются одна за другой.

4. Понятность. Суть свойства: команды алгоритма должны быть понятны исполнителю. В алгоритме используются только команды из системы команд исполнителя.

5. Определенность. Суть свойства: каждая команда однозначно определяет действия исполнителя.

6. Массовость. Суть свойства: алгоритм должен обеспечивать решение не одной конкретной задачи, а класса задач данного типа.

7. Эффективность. Суть свойства: каждый шаг алгоритма должен быть выполнен точно и за конечное время, а, значит, весь алгоритм должен быть выполнен за разумно конечное (эффективное) время.

Исполнитель – это тот, кто будет исполнять алгоритм.

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

Исполнитель может не иметь представления о цели выполнения алгоритма. Он должен строго и точно выполнять действия, предписанные алгоритмом, не понимая, зачем и почему это надо делать. Такое исполнение называется формальным исполнением алгоритма, что позволяет передать исполнение алгоритма автомату.

1. Естественный язык (словесная запись алгоритма)

Обычно используется для алгоритмов, ориентированных на исполнителя – человека. Команды алгоритма нумеруют, чтобы иметь возможность на них ссылаться. Словесная запись алгоритма была использована выше для составления алгоритма заварки чая (см. Пр. 1, стр. 2)

2. Язык блок-схем (графическая запись алгоритмов).

Конец

Начало

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

Овал обозначает начало и конец алгоритма (блок начало и блок конец).
Команды обработки информации помещают в блоках имеющих вид прямоугольников (блок арифметических выражений, блок присваиваний).
Проверка условий — ромб. В результате проверки условия возникают два возможных пути для продолжения алгоритма. Эти пути изображаются стрелками со знаками «+» и «–» (иногда пишут «да» и «нет»). Переход по стрелке со знаком «+» происходит если условие соблюдено а переход по стрелке «–», если условие не выполняется.
Операции ввода и вывода помещают в блоки, имеющие вид параллелограммов (блок ввода/вывода).

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

Начало

Конец

Ввод

a, b

P:=2(a+b)

Вывод

Пр. 2.

Задача. Даны длина и ширина прямо-угольника. Определить периметр этого прямоугольника.

Решение. Выделяем исходные данные и результаты.

Исходные данные: а – длина, b – ширина прямоугольника.

Результат: P – периметр прямоугольника.

Составим алгоритм решения задачи и запишем его на языке блок-схем (см. рис.)

3. Алгоритмический язык (псевдокоды).

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

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

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

Запишем алгоритм нахождения периметра прямоу-гольника (см. Пр. 2), на алгоритмическом языке:

алг периметр прямоугольника

нач ввод a, b

P := 2∙(a + b)

вывод P

кон

4. Формальный язык (язык программирования).

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

Из простых команд и проверок условий образуются составные команды (структуры).

Действие

Любой алгоритм может быть построен из базовых структур: следование, ветвление, цикл.

Структура следование

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

Под действием понимается либо простая, либо составная команда.

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

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

Структура ветвление (развилка).

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

Ветвление может использоваться в двух видах: полное и неполное.

Условие

Действие

Блок-схема неполной развилки

Условие

Блок-схема полной развилки

Действие 1

Действие 2

Рассмотрим ветвление на конкретных примерах.

Пр. 3. Фрагмент алгоритма Пр. 4. Фрагмент алгоритма

«Поедание яблока» «Покупка билетов»

Билеты есть?

Купить

Подойти к кассе

Отойти от кассы

Съесть

Выбросить

Яблоко гнилое?

Взять яблоко

Структура повторение (цикл)

Цикл – алгоритмическая структура, организующая многократное повторение действий.

Действия, которые повторяются в цикле, называют телом цикла.

Циклы бывают двух видов: цикл «До» и цикл «Пока».

Условие

Действие

Блок-схема цикла «До»

Условие

Действие

Блок-схема цикла «Пока»

Цикл «Пока» — цикл с предусловием (сначала проверяется условие, потом выполняется тело цикла). В цикле «Пока» тело цикла выполняется, пока выполняется условие.

Цикл «До» — цикл с постусловием (сначала выполняется тело цикла, потом проверяется условие). В цикле «До» тело цикла выполняется до тех пор, пока не выполнится условие.

Рассмотрим циклы на конкретных примерах.

Пр. 5. Фрагмент алгоритма Пр. 6. Фрагмент алгоритма

«Перейти дорогу» «Помыть тарелки»

Горит красный?

Посмотреть на светофор

Стоять

Перейти дорогу

Взять тарелку

Помыть

Убрать

Тарелки кончились?

Рассмотрим пример алгоритма, в котором внутри цикла находится ветвление.

Пр. 7. Алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух натуральных чисел:

1. Если числа равны, то взять первое число в качестве ответа и закончить исполнение алгоритма, иначе перейти к п.2

2. Определить большее из двух чисел.

3. Заменить большее число на разность большего и меньшего чисел.

4. Перейти к п.1

Блок-схема алгоритма Евклида:

Начало

Ввод

a, b

a ≠ b

a > b

Заменить

a на a-b

Заменить

b на b-a

Вывод

Конец

Например, a = 32, b = 24

Трассировочная таблица:

шаг	Операция	a	b	Условие
	Ввод а	32
	Ввод b		24
	а ≠ b			32 ≠ 24, да
	а > b			32 > 24, да
	а на а-b	8
	а ≠ b			8 ≠ 24, да
	а > b			8 > 24, нет
	b на b-a		16
	а ≠ b			8 ≠ 16, да
	а > b			8 > 16, нет
	b на b-a		8
	а ≠ b			8 ≠ 8, нет
	Вывод а
	Конец

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

Что такое алгоритм?
Какие вы знаете свойства алгоритма? В чем суть каждого свойства?
Как вы понимаете термин «исполнитель»?
Что такое система команд исполнителя?
Что означает формальное исполнение алгоритма?
Какие способы записи алгоритмов вы знаете?
Расскажите подробно о языке блок-схем.
Какой формальный язык вы знаете?
Как называется алгоритм, записанный на языке программирования
Какие алгоритмические структуры вы знаете?
Какой алгоритм называется линейным? Привести пример.
Что такое ветвление? Виды ветвлений? Привести примеры.
Что такое цикл? Виды циклов? Привести примеры.
Что такое тело цикла?
Чем цикл «До» отличается от цикла «Пока»?

Источник