Алгоритм и его формальное исполнение 7 февраля 2014 г.

Алгоритм – это строго определенная последовательность действий при решении задачи. Алгоритм содержит несколько шагов. Шаг алгоритма – это каждое отдельное действие алгоритма.

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в гг.

Алгоpитм заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.

Исполнитель алгоритма Исполнитель алгоритма это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя хаpактеpизуют: сpеда; элементаpные действия; cистема команд; отказы.

Классификация алгоритмов по структуре: Линейный (следование) Разветвленный (ветвление, выбор, альтернатива) Циклический (повтор) Вспомогательный Комбинированный

Исполнитель – это объект, умеющий выполнять определенный набор действий. Исполнителем может быть человек, робот, животное, компьютер. Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Среда исполнителя – обстановка, в которой функционирует исполнитель.

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

Словесный способ Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

ТАБЛИЦА

Линейный алгоритм Линейный алгоритм – это алгоритм, шаги которого выполняются последовательно друг за другом. (Пример: алгоритм сбора портфеля).

Задача Вычислить периметр произвольного треугольника по его трем сторонам. Решение: 1 этап: Постановка задачи. Исходные данные: А, B, C – стороны произвольного треугольника Выходные данные: P – периметр треугольника. 2 этап: Математическая модель. P=A+B+С

Блок - схемы ГРАФИЧЕСКИЙ СПОСОБ

Таблица основных условных обозначений в блок-схемах Условное обозначение Назначение блока Начало или конец алгоритма Ввод или вывод данных. Внутри блока перечисляются данные через запятую. действие Внутри блока записываются матем. формулы и операции для обработки данных. Проверка условия. Внутри блока записываются логические условия. Имеет два выхода Да(+) и Нет(-). Направление.

3 этап: Алгоритм. Начало Ввод A, B, C P=A+B+C Вывод P Конец 3 этап: Составление алгоритма

Базовая структура линейного алгоритма: Начало Серия команд 1 Серия команд N Серия команд 2 Конец

Задание: Составить алгоритм форматирования текста (словесно).

Разветвляющийся алгоритм

ЕСЛИ пошел дождь, ТО надо открыть зонт. ЕСЛИ назвался груздем, ТО полезай в кузов. ЕСЛИ ласточки летают низко, ТО будет дождь, ИНАЧЕ дождя не будет.

ЕСЛИ условие, ТО инструкция. ЕСЛИ условие, ТО инструкция1, ИНАЧЕ инструкция2. Неполная форма Полная форма Да Нет

Задание: Прочитайте отрывок из стихотворения Джани Родари «Чем пахнут ремесла?». Перефразируйте информацию о профессиях с помощью ключевых слов ЕСЛИ – ТО У каждого дела запах особый: В булочной пахнет тестом и сдобой. Мимо столярной идешь мастерской – Стружкою пахнет и свежей доской. Пахнет маляр скипидаром и краской. Пахнет стекольщик оконной замазкой. Куртка шофера пахнет бензином. Блуза рабочего – маслом машинным…

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

Базовая структура ветвления Условие Инструкция 1Инструкция 2 Да Нет Условие Инструкция Да Нет Неполная форма Полная форма

Задание: Выполнить вычисления по алгоритму, заданному блок-схемой Начало Ввод A A>9 X=A+8X=A-8 Вывод X Конец ДаНет

A X Начало Ввод A A>9 X=A-8X=A+8 Вывод X Конец ДаНет

Циклический алгоритм 7 февраля 2014 г. ПОВТОР

Циклический алгоритм – Циклический алгоритм – это алгоритм некоторые шаги которого повторяются N- количество раз. Тело цикла – Тело цикла – шаги алгоритма, которые повторяются. Параметр цикла – Параметр цикла – величина, от которой зависит число повторений в цикле.

Условие Инструкция Условие Инструкция ДА НЕТ ДА НЕТ Цикл «Пока»Цикл «До»

Деньги есть? Съел Понравилось? Купил ДА НЕТ ДА НЕТ Цикл «Пока»Цикл «До» Транжира Обжора

Составьте алгоритм сортировки 10 веществ на проводники и изоляторы. Обведи карандашом тело цикла. Начало 10 веществ Взять вещество Подвести ток Проводит ток? ДаНет Проводник Изолятор Все вещества проверили? ДаНет Конец