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