24 Сентябрь, 2018
Алгоритм и его формальное исполнение
Классификация алгоритмов по структуре:
- Линейный (следование)
- Разветвленный (ветвление, выбор, альтернатива)
- Циклический (повтор)
- Вспомогательный
- Комбинированный
Алгоритм – это строго определенная последовательность действий при решении задачи.
Алгоритм содержит несколько шагов.
Шаг алгоритма – это каждое отдельное действие алгоритма.
Исполнитель – это объект, умеющий выполнять определенный набор действий. Исполнителем может быть человек, робот, животное, компьютер.
Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять.
Среда исполнителя – обстановка, в которой функционирует исполнитель.
Задание: Назови исполнителей следующих видов работы:
- Уборка мусора во дворе
- Обучение детей в школе
- Вождение автомобиля
- Ответ у доски
- Приготовление пищи
- Печатание документа на принтере
Свойства алгоритма
Результативность – получение результата за конечное количество шагов
Результативность
Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги
Дискретность
АЛГОРИТМ
Детерминированность
Детерминированность (определенность, точность) – каждое действие должно строго и недвусмысленно определено
Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения
Конечность
Массовость – использование алгоритма для решения однотипных задач
Массовость
Классификация алгоритмов по форме представления:
- Словесные
- Графические (блок-схемы)
- На алгоязыке
- Программные
Задание: Составь алгоритм сбора портфеля. Продумай СКИ.
Возьми портфель
Открой дневник
Посмотри расписание
Сложи школьные принадлежности в портфель
Закрой портфель
Способ описания алгоритма _______________
Число шагов __________________
Исполнитель ________________
Среда исполнителя _______________
Словесный
5 (пять)
Человек
Квартира
Таблица основных условных обозначений в блок-схемах
Условное обозначение
Назначение блока
Начало или конец алгоритма
Ввод или вывод данных.
Внутри блока перечисляются данные через запятую.
Процесс.
Внутри блока записываются матем. формулы и операции для обработки данных.
Проверка условия.
Внутри блока записываются логические условия. Имеет два выхода Да(+) и Нет(-) .
Направление.
Таблица основных условных обозначений на алгоритмическом языке (псевдокоде)
алг - алгоритм
арг - аргумент
рез - результат
нач - начало
кон - конец
цел - целый
вещ - вещественный
сим - символьный
лог - логический
таб - таблица
нц – начало цикла
кц – конец цикла
длин
дано
надо
если
то
иначе
все
пока
для
от
до
знач
и
или
не
да
нет
при
выбор
ввод
вывод
утв
повторять
Линейный алгоритм
Линейный алгоритм – это алгоритм, шаги которого выполняются последовательно друг за другом. (Пример: алгоритм сбора портфеля).
Задача
Вычислить периметр произвольного треугольника по его трем сторонам.
Решение:
1 этап: Постановка задачи.
Исходные данные : А , B , C – стороны произвольного треугольника
Выходные данные : P – периметр треугольника .
2 этап: Математическая модель.
P=A+B+ С
3 этап: Составление алгоритма
3 этап: Алгоритм.
Начало
Ввод
A, B , C
P=A+B+C
Вывод
P
Конец
Базовая структура линейного алгоритма:
Начало
Серия команд 1
Серия команд 2
Серия команд N
Конец
Разветвляющийся алгоритм
Разветвляющийся алгоритм описывает последовательности действий в зависимости от выбора одного из нескольких условий (направлений).
если – то
нет
да
условие
если – то - иначе
действие
да
нет
Условие
Действие 1
Действие 2
выбор
Да
Условие 1
Действие 1
Нет
Да
Действие 2
Условие 2
Нет
выбор - иначе
Да
Условие N
Действие N
Да
Нет
Условие 1
Действие 1
Нет
Да
Действие 2
Условие 2
Нет
Да
Условие N
Действие N
Нет
Действие N+1
Циклический алгоритм
Циклический алгоритм – это алгоритм, который при каждом исполнении предписывает многократное выполнение одной и той же последовательности действий для различных значений данных
цикл «пока» с предусловием
цикл «пока» с постусловием
цикл «для»