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

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

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

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

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

Каждый алгоритм создается конкретным автором и рассчитан на конкретного исполнителя.

При подготовке алгоритмов, исполнителем которых является компьютер (уровень предварительной подготовки равен 0),процесс подготовки задания делится на два этапа:

1. создание укрепленного алгоритма (требования к исходным данным и результатам, постановка задачи, описание точной схемы решения с указанием всех особых ситуаций);

2. изложение укрепленного алгоритма на языке, понятном машине (программа)

Форма представления укрупненного алгоритма м.б.: словесное описание, совокупность математических формул, сочетание - блок-схема.

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

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

Дискретность:

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

Только выполнив одну команду, исполнитель может приступить к выполнению следующей.

Пример. Переход улицы

Понятность:

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

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

Пример.

Определенность (точность, детерминированность):

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

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

Пример. «Взять две-три ложки сахарного песка», «умножить X на одно из двух данных числе A и B»

Массовость(необязательное свойство):

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

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

Выполнение алгоритма д. приводить к конкретному результату – решению задачи – за конечное число шагов.

!Под решением задачи подразумевается и сообщение о том, что при заданных исходный данных задача решения не имеет или алгоритм неприменим.

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

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

Решение задач:

Задача 1Можно ли известное вам явление «круговорот воды в природе» считать алгоритмом?

Задача 2 В одной из русских сказок герою дается поручение: «Пойди туда, не знаю куда, принеси то, не знаю что». Можно ли набор действий считать алгоритмом?

Задача 3 Являются ли алгоритмом следующие наборы команд:

Умножить а на 2;

Сложить а с 5;

Полученный результат разделить на 3.

Сложить 5 и 2;

Полученный результат умножить на 3.

Положить s равным 0;

Положить x равным 1;

К s прибавить x;

К x прибавить 1;

Если x>0, то перейти к п.3

Достать ключ;

Вставить его в замочную скважину;

Повернуть ключ по часовой стрелке;

Вынуть ключ;

Открыть дверь.

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

Пример 1 Составить алгоритм решения уравнения вида ax=b, где a и b – произвольные числа.

Дано: a, b – произвольные числа

Найти: x – корень уравнения ax=b.

Алгоритм решения задачи можно представить схематично:

Математическая модель:

x=b/a при ;

x – любое число при a=0 и b=0;

решений нет при a=0 и

Решение:

1. Задать числовые значения a, b

2. Если , то x=b/a. Перейти к п.5

3. Если b=0, то x – любое число. Перейти к п.6

4. Если , то решений нет. Перейти к п.6

5. Записать в качестве ответа значение x

6. Конец.

Т.е. правила записи алгоритма:

- Выделить величины, являющиеся исходными для задачи.

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

- Указать порядок выполнения команд.

- Указать признак окончания процесса решения задачи.

- Указать, что является результатом (в каждом из возможных случаев) решения задачи.

Домашнее задание:

1) Имеются три урны: белая, черная, полосатая. В полосатой урне находятся белые и черные шары. Переложить все черные шары в черную урну, а белые шары – в белую урну. Составить алгоритм сортировки шаров.

2) Составить алгоритмы выполнения 4-х арифметических действий с двумя обыкновенными дробями – a/b и c/d

Тема 3 Способы представления алгоритмов:

Рассмотрим на примере все способы записи алгоритма.

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

Пример 2 Составить алгоритм поиска меньшего из значений двух величин – А и В.

Дано: А, В – произвольные числа

Найти:Y – меньшее из значений двух величин А и В

1 способ: Словесный способ записи алгоритмов: (Словесный способ используется на начальном этапе изучения алгоритмов и предназначен для исполнения алгоритма человеком. Форма записи команд – произвольная, главное, чтобы она была понятной и точной)

Решение 1Пример 2:

1. задать числовые значения А и В;

2. если А<В, то Y присвоить значение величины А, иначе Y присвоить значение величины В;

3. записать в качестве ответа значение Y;

конец.

2 способ: Блок-схема алгоритма:

Обозначение блока	Пояснение
	Вычислительное действие (операция присваивания)
	Проверка условия (условный переход)
	Начало, конец
	Ввод исходных данных, вывод результатов

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

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

команды ввода	присваиванием
ввод <список переменных>	:=

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

Команда вывода в алгоритмах записывается: вывод <список вывода>

Решение 2 Пример 2:

Домашнее задание:

3) Составить блок-схему алгоритма
перемножения двух
обыкновенных дробей – a/b и c/d

Дано: a, b, c, d – произвольные числа

Найти: произведение a/b и c/d

Команда присваивания:

<переменная>:=<выражение>
(значение переменной, записаннойслева от знака :=, становится равным значению выражения, записанного справа от знака :=)

Например:Y:=A – переменной Y присвоить значение A

Пример 3

Команда	a	b	Свойства команды присваивания: пока переменной не присвоено новое значение, она остается неопределенной; значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующего присваивания этой переменной нового значения; новое значение, присвоенное переменной, заменяет ее предыдущее значение
a:=1		-
b:=2*a
a:=b
b:=a + b

Домашнее задание:

4) Составить блок-схему алгоритма
перемножения двух
обыкновенных дробей – a/b и c/d

Дано: a, b, c, d – произвольные числа

Найти: произведение a/b и c/d

3 способ: Учебный алгоритмический язык

Программа – это алгоритм, записанный на языке исполнителя.

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

Алгоритм записывается на русском языке при помощи некоторого ограниченного числа слов, смысл и способ употребления которых строго определен (служебные слова)

алг название алгоритма

Заголовок алг

арг список исходных данных

рез список результатов

Тело алг

нач

последовательность команд алгоритма

кон

Решение 3 Пример 2

Дано: А, В – произвольные числа

Найти:Y – меньшее из значений двух величин А и В

алг Меньшее из 2-х

арг А, В

рез Y

нач

если A<B

то Y:=A

иначе Y:=B

все

кон

Домашнее задание:

5) Составьте на алгоритмическом языке алгоритм вычисления значения y по формуле:

Задача 4 Алгоритм, определяющий, что надо надеть на прогулку, если на улице: -15⁰С, +20⁰С, -10⁰С

алг Одеться по погоде

нач

если на улице температура меньше -10⁰С

то надеть шубу

иначе

если на улице температура меньше +20⁰С

то надеть шубу

все

кон

Задача 5 В схематичном виде отразите изменение значений переменных А и В, в ходе последовательного выполнения команд присваивания.

Вариант 1:	Вариант 2:	Вариант 3:	Вариант 4:	Вариант 5:	Вариант 6:
А:=1 В:=2 А:=А+1 В:=2*А А:=В+А	А:=1 В:=2 А:=А+В В:= А-В А:= А-В	А:=1 В:=2 А:=В+4 А:=3*А В:=В-А	А:=1 В:=2 В:=А*3 В:=А+В А:= А-В	А:=1 В:=2 В:=В+4 А:=А*3 В:=В/А	А:=1 В:=2 В:=2*А А:=В-А В:=В+3