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

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

Такими свойствами являются:

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

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

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

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

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

Само выражение «свойства алгоритма» не совсем корректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм - искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить все же не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.

Правила построения алгоритмов

Первое правило - при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.

Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

Третье правило - дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

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

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

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

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

2. Понятность - алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т.е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на выполнение “не размышляющего” исполнителя . Алгоритм составляется из команд, входящих в СКИ.

Рассмотрим известный пример “бытового” алгоритма - алгоритм перехода улицы: “Посмотри налево. Если машин нет, дойди до середины улицы. Если есть, подожди, пока они проедут, и т.д.”. Представьте себе ситуацию: машина слева есть, но она не едет - у нее меняют колесо. Если вы думаете, что исполнитель алгоритма должен ждать, то вы поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.

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

4. Результативность - исполнение алгоритма должно закончиться за конечное число шагов, и при этом должен быть получен результат решения задачи. В качестве одного из возможных результатов может быть и установление того факта, что задача решений не имеет.

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

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

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

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

Обобщив вышесказанное, сформулируем следующее понятие алгоритма.

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

Приведенное определение не является определением в математическом смысле слова, т.е. это не формальное определение (формальное определение алгоритма см. в статье “Теория алгоритмов ”).

Отметим, что для каждого исполнителя набор допустимых действий (СКИ) всегда ограничен - не может существовать исполнителя, для которого любое действие является допустимым. Перефразированное рассуждение И.Канта обосновывает сформулированное утверждение следующим образом: “Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднять. Но это противоречит допустимости действия «Поднять любой камень»”.

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

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

Графический способ описания алгоритма

3.Как называется блочный символ, представленный на рисунке ?

4.Как называется блочный символ, представленный на рисунке ?

5.Как называется блочный символ, представленный на рисунке ?

Сопоставьте условные обозначения применяемые в блок-схемах и их назначение

а) б) в) г) д)

Укажите соответствие для всех 5 вариантов ответа:

1) блок принятия решения (проверка условия)

2) Блок начала и конца алгоритма

3) блок описания данных

4) блок обработки данных (выполнения действий)

5) блок модификации

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

9. Величины, значения которых меняются в процессе исполнения алгоритма, называются:

10. К какому виду алгоритмов можно отнести алгоритм, для записи которого на алгоритмическом языке используется конструкция:

ЕСЛИ - ТО - ИНАЧЕ - ВСЕ

11.К какому виду алгоритмов можно отнести алгоритм, для записи которого на алгоритмическом языке используется конструкция:

НЦ ПОКА условие

Тело цикла

12. К какому виду алгоритмов можно отнести алгоритм, для записи которого на алгоритмическом языке используется конструкция:

НЦ ДЛЯ i ОТ i1 ДО i2

Тело цикла

13. Дан фрагмент линейного алгоритма:

b:=5+2*a

a:=b/5*a

Чему равно значение переменнойапосле его исполнения?

Выявление ошибок и их устранение называется...

Отдельное указание исполнителю - это...

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

Блок-схема - это...

Какое действие определяет блок комментарии?

20. В блок-схеме начало и конец алгоритма обозначается фи­гурой:

а) б) в) г) д)

21. В блок-схеме действие в алгоритме обозначается фи­гурой:

а) б) в) г) д)

22. В блок-схеме условие обозначается фи­гурой:

а) б) в) г) д)

23. В блок-схеме вывод и ввод данных обозначается фи­гурой:

а) б) в) г) д)

24. Определенность алгоритма означает:

25. Результативность алгоритма означает:

26. Массовость алгоритма означает:

27. Дискретность алгоритма означает:

28. Свойство алгоритма «конечность» означает:

29. Свойство алгоритма «дискретность» означает:

64. Свойство алгоритма «результативность» означает:

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

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

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

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

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

Слово «алгоритм» появилось в Средние века, когда ев­ропейцы познакомились со способами выполнения ариф­метических действий в десятичной системе счисления, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской об­ласти Узбекистана). Слово «алгоритм» есть результат ев­ропейского произношения слов «аль-Хорезми».

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результа­тивностью.

Дискретность - это свойство, означающее следую­щее: каждый алгоритм состоит из отдельных законченных действий, т. е. «делится на шаги».

Массовость - применимость алгоритма ко всем зада­чам рассматриваемого типа при любых исходных данных.

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

Результативность - свойство, состоящее в том, что любой алгоритм должен находить решение за конечное число шагов.

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

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

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

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

Блоки, характеризующие нача­ло и конец алгоритма:

Блок, отображающий процесс {оператор), предназначенный для описания отдельных действий:

Блок, описывающий цикл с пара­метром:

Блок ввода/вывода с произвольного носителя информации:

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

Алгоритмический язык, именуемый как псевдокод, - это запись алгоритмов, во многом напоминающая запись алгоритма на естественном языке и языке программиро­вания. При описании алгоритма на псевдокоде использу­ются следующие конструкции:

нп - начало цикла; кп_ - конец цикла; для - цикл с параметром; если - условие; то - результат выполнения условия; иначе - результат невыполнения условия; всё - конец условия; пока - условие цикла.

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

Блок-схема линейного алгоритма нахождения перимет­ра прямоугольного треугольника Р при известных длинах его катетов a, b изображена на рис. 5.1.

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

Различают неполное (если-то) и полное (если-то-иначе) виды ветвления.

Неполное ветвление предполагает нали­чие оператора только на одной ветви (то; Да; Истина), на другой ветви оператор отсутст­вует и управление сразу переходит к точке слияния

Полное ветвление позволяет организовывать две вет­ви в алгоритме (то или иначе; Да илиНет; Истина или Ложь), каждая из которых ведет к общей точке их слия­ния (рис. 5.26).

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

Широкое применение получили три типа циклов: цикл с параметром, цикл с предусловием и цикл с постуслови­ем.

Цикл с параметром используется в тех случаях, когда известна величина k, т. е. количество элементов или ша­гов цикла.

Количество шагов цикла с предусловием заранее не определено. В нем сначала проверяется выпол­нение условия. Если оно Истинно (Да), то исполняется тело цикла, после чего вновь проверяется условие. Ука­занные действия проверяются до тех пор, пока условие не примет значение Ложно (Нет).

Цикл с постусловием отличается от цик­ла с предусловием расположением условия и тем, что тело цикла всегда будет выполнено хотя бы один раз. Тело это­го цикла будет выполняться, пока условие Ложно (Нет).

Для повышения производительности и качества рабо­ты каждый язык программирования имеет структуриро­ванный тип данных - массив.

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