Алгоритмы и исполнители. Линейные алгоритмы в визуальной среде
Понятие алгоритма, свойства алгоритмов, система команд исполнителя (СКИ), блок-схемы, среда Scratch и линейные скрипты.
Слово «алгоритм» происходит от имени великого среднеазиатского ученого Аль-Хорезми (Abu Ja'far Muhammad ibn Musa al-Khwarizmi), сформулировавшего правила выполнения четырех арифметических действий над числами в IX веке.
Алгоритм — это точное и понятное предписание исполнителю выполнить строгую последовательность действий, направленных на достижение поставленной цели или решение конкретной задачи за конечное число шагов.
Любой алгоритм должен удовлетворять пяти фундаментальным свойствам:
1. Дискретность — алгоритм разбит на отдельные последовательные шаги (команды);
2. Понятность — каждая команда алгоритма входит в систему команд, известную данному исполнителю;
3. Определенность (детерминированность) — команды однозначны, исключают двоякое толкование;
4. Результативность (конечность) — за конечное число шагов алгоритм обязательно завершается и дает искомый результат;
5. Массовость — алгоритм применим для целого класса однотипных задач с разными входными данными (например, алгоритм сложения в столбик верен для любых двух чисел).
Алгоритм
Детерминированность
Пример из жизни
Кулинарный рецепт, инструкция по сборке конструктора LEGO или алгоритм перехода улицы по светофору — это алгоритмы, которые человек выполняет каждый день.
Исполнитель — это человек, животное, робот или электронное устройство (компьютер), способное понимать и безошибочно выполнять предписанные команды алгоритма.
Характеристики любого исполнителя:
• Среда обитания (обстановка) — условия и рабочее пространство, в котором действует исполнитель (например, экран в Scratch, шахматная доска для робота);
• Система команд исполнителя (СКИ) — исчерпывающий перечень команд, которые исполнитель понимает и умеет исполнять без ошибок;
• Отказ исполнителя — ситуация, когда исполнителю поступает команда, не входящая в его СКИ, либо команда, которую невозможно выполнить в текущей обстановке (например, «шаг вперед», если перед исполнителем кирпичная стена).
Исполнитель
СКИ (Система команд)
Существуют три главных способа записи алгоритмов:
1. Словесный (на естественном языке) — пошаговый текст с нумерацией («1. Взять чайник. 2. Налить воду»);
2. Графический (блок-схемы) — наглядное представление с помощью стандартизированных геометрических фигур, соединенных стрелками перехода;
3. Программный (на языке программирования) — запись на формальном компьютерном языке (Python, C++, Scratch).
Основные блоки графических блок-схем (ГОСТ 19.701-90):
• Овал (скругленный прямоугольник) — Начало или Конец алгоритма;
• Параллелограмм — Ввод данных (с клавиатуры) или Вывод результата (на экран);
• Прямоугольник — Операция процесса (вычисления, математические действия, присваивание);
• Ромб — Проверка логического условия (ветвление «Да / Нет»);
• Стрелки — Линии потока управления, указывающие порядок выполнения шагов.
Овал
Прямоугольник
Линейным называют алгоритм, в котором все команды выполняются строго последовательно одна за другой, в порядке их записи, без ветвлений и повторений.
Визуальная среда Scratch (разработанная лабораторией MIT Media Lab) позволяет создавать программы из разноцветных графических блоков-кирпичиков, соединяющихся между собой подобно деталям конструктора LEGO. Это исключает синтаксические ошибки в коде.
Основные элементы среды Scratch:
• Сцена (Stage) — координатная плоскость размером 480 × 360 точек, где разворачивается действие программы;
• Спрайт (Sprite) — исполнитель программы (по умолчанию Рыжий кот);
• Палитра блоков — разделы команд: «Движение» (синие блоки: идти 10 шагов, повернуть на 90 градусов), «Внешность» (фиолетовые: сказать «Привет!», сменить костюм), «События» (желтые шапки: когда флажок нажат);
• Область скриптов — рабочее поле для сборки программы.
Простейший линейный скрипт всегда начинается с блока-шапки «когда зеленый флаг нажат» и выполняет команды сверху вниз.