Алгоритмы и исполнители. Основы алгоритмизации

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

Примеры алгоритмов
Рисование лошади

Примеры алгоритмов
Исходные данные
Алгоритм
Результат
Общая схема работы алгоритма
Задать два числа
Сложить заданные числа
Разделить сумму на 2
Вычислительный алгоритм
Среднее арифметическое двух чисел

Исполнитель алгоритма
Исполнитель - это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
Формальный
Неформальный
Исполнитель
Круг решаемых задач
Среда исполнителя
Режимы работы
Непосредственное управление
Программное управление
Область, обстановка, условия
Исполнители алгоритмов
СКИ

Исполнитель Робот

Исполнитель Кузнечик

Свойства алгоритма
Свойства алгоритма
Путь решения задачи
разделён на отдельные шаги
Алгоритм состоит из
команд, входящих в СКИ
Команды понимаются
однозначно
Обеспечивается получение
ожидаемого результата
Обеспечивается решение
задач с различными исходными
данными
Дискретность
Понятность
Определённость
(детерминированность)
Результативность
Массовость

Дискретность (от лат. discretus – разделенный, прерывистый) означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель сможет приступить к выполнению следующей.
да
нет
Начало
Конец
x, y
a
x > y
a = x
a = y

Понятность означает, что алгоритм состоит только из команд, входящих в систему команд исполнителя, т. е. из таких команд, которые исполнитель может воспринять и по которым может выполнить требуемые действия.
Окрошка «Мясная»
1-1.5 л кваса
500 г картофеля
300 г колбасы
3 яйца
200 г редиса
300 г огурцов
зелень по вкусу
сметана
соль
перец
Картофель отварить до готовности.
Остудить, почистить.
Нарезать кубиками.
Колбасу нарезать кубиками.
Яйца нарезать кубиками.
Редис тонко нарезать.
Огурцы нарезать кубиками.
Смешать картофель, колбасу, яйца, редис, огурцы.
Посолить, поперчить.
Выложить в тарелки.
Залить квасом, посыпать зеленью.
Подавать со сметаной.
Рецепт приготовления

Определённость означает, что в алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять на следующем шаге.
Доехать до стадиона
Идти прямо
Данная последовательность действий не обладает свойством определённости!
В какую сторону повернуть?
В какой автобус сесть?
Повернуть
Идти прямо
Сесть в автобус
Доехать до остановки «Стадион»
Какое расстояние нужно пройти прямо?

Результативность означает, что алгоритм должен обеспечивать возможность получения результата после конечного, возможно, очень большого, числа шагов. При этом результатом считается не только обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения по какой-либо причине решения данной задачи.
Данная последовательность команд не обладает свойством результативности. Что нужно изменить?
Взять книгу
Открыть первую страницу
Пока не конец книги выполнять следующие действия:
3.1 Прочитать текст
3.2 Перелистнуть страницу
Чтение книги
3.3 Прочитать текст
3.4 Открыть первую страницу

Массовость означает, что алгоритм должен обеспечивать возможность его применения для решения любой задачи из некоторого класса задач с различными исходными данными.
Алгоритм вычисления корней квадратного уравнения.
Конец
да
нет
Начало
Ввод
коэффициентов
Вычисление
дискриминанта
Дискриминант
меньше 0?
Вычисление
значений корней
«Корней нет»
Вывод корней

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

Основные способы записи алгоритма
Словесные
Графические
На алгоритмических языках
Словесное описание
Построчная запись
Последователь-ность рисунков
Структурограмма
Школьный алгоритмический
язык
Язык программирова-ния
Блок-схема

Словесное описание
Словесное описание - самая простая запись алгоритма в виде набора высказываний на обычном разговорном языке.
Пример. Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары целых чисел (алгоритм Евклида).
Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y. Запишите первое из заданных чисел в столбец Х, а второе - в столбец Y. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.
Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца Х считайте искомым результатом.

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

Построчная запись алгоритма Евклида
Построчная запись алгоритма Евклида
1. Начало.
2. Обозначить первое из заданных чисел Х, второе - Y.
3. Если Х = Y то перейти к п. 9.
4. Если X >Y , то перейти к п. 5, иначе перейти к п. 7.
5. Заменить X на X-Y.
6. Перейти к п. 3.
7. Заменить Y на Y-X
8. Перейти к п. 3.
9. Считать Х искомым результатом.
10. Конец.

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

Запись алгоритма Евклида с помощью блок-схемы

Опорный конспект
Дискретность
Свойства алгоритма
Понятность
Определённость
Результативность
Массовость
Алгоритм - это предназначенное для конкретного исполнителя описание последовательности действий, приводящих от исходных данных к требуемому результату, которое обладает свойствами дискретности, понятности, определённости, результативности и массовости.

Алгоритмический
язык
Словесный
Блок-схема
Способы записи алгоритмов
Обычный
разговорный
язык
Геометрические
фигуры
Слова имеют
заданный смысл и
способ записи

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

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

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

Полная форма ветвления
если <условие>
то <действие 1>
иначе <действие 2>
все
Да
Нет

Неполная форма ветвления
если <условие>
то <действие 1>
все
Да
Нет

Операции сравнения

Вычисление функции f(x)=|x|
Начало
Список данных
X, Y -вещ
Х
Х>0
Y:=X
Y:=-X
Y
Конец
да
нет

Простые и составные условия
Простые условия состоят из одной операции сравнения. Составные условия получаются из простых с помощью логических связок and (и), or (или), not (не).
Пример. Алгоритм определения принадлежности точки Х отрезку [A; B].
Ответ: Принадлежит
A=2
X=4
B=6
Ответ: Не принадлежит
B=4
X=6

Следование - алгоритмическая конструкция, отображающая естественный, последовательный порядок действий.
Алгоритмы, в которых используется только структура «следование», называются линейными.
Действие 1
Действие 2
Опорный конспект

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

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

Типы циклов
Заданы условия
продолжения работы
Могут быть
Заданы условия
окончания работы
Задано число
повторений
Пока есть кирпич
Ровно 100 кирпичей
Пока не наступит ночь

цикл-ПОКА, цикл с предусловием
цикл-ДО, цикл с постусловием
(цикл-ДЛЯ, цикл с параметром)

Вычисление значения переменной b

Таблица значений переменных
2 = 8 (Нет)
4 = 8 (Нет)
8 = 8 (Да)
1
1
2
2
4
4
8
8
1
1
3
7
7
15
3

Опорный конспект
С заданным
условием
продолжения
работы
С заданным
условием
окончания
работы
С заданным
числом
повторений
Повторение - алгоритмическая конструкция, представляющая собой последовательность действий, выполняемых многократно.
Алгоритмы, содержащие конструкцию «повторение», называют циклическими или циклами.
Последовательность действий, многократно повторяющаяся в процессе выполнения цикла, называется телом цикла.
Тип цикла
Цикл - ПОКА
Цикл - ДО
Цикл - ДЛЯ