Базовые структуры алгоритмов

Класс

Урок № 14

Тема.Алгоритм: понятие, свойства алгоритмов, способы записи. Этапы решения задач. Метод пошаговой детализации. Базовые структуры алгоритмов.

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.

Алгоритм– описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически.

Свойства алгоритмов:

1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);

2. Понятность (набор команд должен быть знаком исполнителю).

3. Определенность (исполнение алгоритма разными исполнителями должно приводить к одному и тому же результату);

4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);

5. Результативность (выполнение алгоритма должно приводить к конкретному результату – решению задачи за конечное число шагов).

6. Формальность (пользуясь системой команд, исполнитель может выполнять алгоритм не вникая в содержание поставленной задачи).

Способы записи:

ü с помощью обычного языка общения (словесный),

ü с использованием блок-схем (графический)

ü с помощью алгоритмического языка. (программный)

Объект, который будет выполнять алгоритм, обычно называют исполнителем.

Идеальными исполнителями являются машины, роботы, компьютеры...

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Для более наглядного представления алгоритма широко используется графическая форма - блок-схема, которая составляется из стандартных графических объектов.

Вид стандартного графического объекта	Назначение
	Начало алгоритма
	Конец алгоритма
	Выполняемое действие записывается внутри прямоугольника
	Условие выполнения действий записывается внутри ромба
	Счетчик кол-во повторов
	Последовательность выполнения действий

Базовые структуры алгоритмов

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

Выделяют три базовые алгоритмические конструкции:

ü Следование

ü Ветвление

ü Повторение

Линейный алгоритм (последовательное выполнение, структура следования) - это алгоритм, который обеспечивает получение результата путем однократного выполнения последовательности действий, независимо от входных данных и промежуточных результатов. Действия в таких алгоритмах выполняются последовательно, одна за одной, т. 1.

ü Базовая структура следование. Образуется из последовательности действий, следующих одно за другим:

ü
Разветвленный алгоритм (условие, структура выбора) - в классическом варианте эта структура рассматривается как выбор действий в случае выполнения или невыполнения заданного условия. Ветвления бывают полными и неполными.
Полное ветвление - это ветвление, в котором определенные действия определены и при выполнении, и в случае невыполнения условия. Неполное ветвление - это разветвление, в котором действия определены только при выполнении (или в случае невыполнения) условия.

ü 2. Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

ü

Циклический алгоритм (цикл, структура повторения) - это алгоритм, в котором предусмотрено повторения некоторой серии команд. С помощью этой структуры описываются однотипные повторяющиеся несколько раз. Такие алгоритмы обеспечивают выполнение длинной последовательности действий, записанных сравнительно короткой последовательностью команд. Именно использование циклов позволяет в полной мере реализовать быстродействие компьютеров.
Основная особенность базовых алгоритмических структур - это их полнота, то есть этих структур достаточно для создания сложного алгоритма.