Свойства алгоритмов. Способы записи алгоритмов

• АЛГОРИТМЫ

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

Способы записи алгоритмов

Происхождение и развитие понятия алгоритма

Алгоритм – происходит от Al Horithmi – латинского написания

арабского имени среднеазиатского математика IX века аль - Хорезми

?

IX век

XX век

Основатели теории алгоритмов

Возникает научное

н а п р а в л е н и е

ТЕОРИЯ АЛГОРИТМОВ

Направление исследований :

разработка универсальной

алгоритмической модели

1903 - 1979 г.

1912 - 1954 г.

787 – 850 г.

30 – е годы

С появлением ЭВМ (2-я половина XX века) понятие АЛГОРИТМА

связывается с ПРОГРАММИРОВАНИЕМ . Появляется большое

количество алгоритмических языков: Фортран, Паскаль, Бейсик . . .

Происхождение и развитие понятия алгоритма

Алгоритм – происходит от Al Horithmi – латинского написания

арабского имени среднеазиатского математика IX века аль - Хорезми

?

XX век

IX век

Основатели теории алгоритмов

Возникает научное

н а п р а в л е н и е

ТЕОРИЯ АЛГОРИТМОВ

Направление исследований:

разработка универсальной

алгоритмической модели

1903 - 1979 г.

1912 - 1954 г.

787 – 850 г.

30 – е годы

В X I I веке в Европе вышел латинский перевод математического трактата аль – Хорезми . Алгоритмами назвали описанные в трактате правила выполнения арифметических вычислений в позиционной десятичной системе счисления.

В наше время понятие алгоритма понимается шире,

не ограничиваясь только арифметическими вычислениями.

Происхождение и развитие понятия алгоритма

Алгоритм – происходит от Al Horithmi – латинского написания

арабского имени среднеазиатского математика IX века аль - Хорезми

?

XX век

IX век

Основатели теории алгоритмов

Возникает научное

н а п р а в л е н и е

ТЕОРИЯ АЛГОРИТМОВ

Направление исследований:

разработка универсальной

алгоритмической модели

1912 - 1954 г.

1903 - 1979 г.

30 – е годы

787 – 850 г.

Английский математик Алан Тьюринг в 1935 – 1936 годах создает теорию «логических вычисляющих машин». Разработанная им « Машина Тьюринга » стала обязательной частью обучения будущих математиков и компьютерщиков. На одной из лондонских гостиниц мемориальная доска гласит: «Здесь родился Алан Тьюринг (1912 – 1954), взломщик кодов и пионер информатики».

Происхождение и развитие понятия алгоритма

Алгоритм – происходит от Al Horithmi – латинского написания

арабского имени среднеазиатского математика IX века аль - Хорезми

?

XX век

IX век

Основатели теории алгоритмов

Возникает научное

н а п р а в л е н и е

ТЕОРИЯ АЛГОРИТМОВ

Направление исследований:

разработка универсальной

алгоритмической модели

1903 - 1979 г.

1912 - 1954 г.

30 – е годы

787 – 850 г.

Русский математик Андрей Марков в 1947 году ввел понятие « нормального алгоритма » и впервые систематически и строго построил общую теорию алгоритмов. Современные языки символьной обработки (Пролог) берут свое начало от нормальных алгоритмов Маркова.

• Что такое алгоритм?

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

• Налить в чайник воду.
• Зажечь газовую горелку.
• Поставить на нее чайник.
• Подождать пока вода в чайнике закипит.
• Отключить газ.
• В заварной чайник насыпать 2-3 чайные ложки заварки.
• Залить кипятком и дать настояться 5 минут.
• Налить чай в чашки.
• Добавить сахар/молоко/мёд по вкусу.

Задание . Вы захотели выпить чашечку чаю. Запишите порядок своих действий.

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

Понятность – каждый шаг алгоритма должен быть понятен исполнителю;

Дискретность (прерывность, раздельность) – алгоритм может быть разбит на шаги;

Конечность - выполняемый алгоритм должен приводить к результату за конечное число шагов;

Результативность - алгоритм должен быть направлен на получение результата за конечное число шагов;

Массовость –алгоритм может быть использован для решения однотипных задач разной направленности.

Формальность – возможность выполнять команды механически . Это свойство позволяет поручить исполнение алгоритмов роботам, компьютерам и другим устройствам, т.е. выполнение алгоритма без понимания цели .

• Способы записи алгоритмов:

Алгоритмы можно записывать разными способами, называемыми формой представления алгоритма .

На практике наиболее распространены следующие формы представления алгоритмов:

• словесная (записи на естественном языке);
• графическая (стрелки, изображения, блок-схемы);
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• программная (тексты на языках программирования).

• Словесная форма

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

Примеры записи алгоритмов на естественном языке.

Алгоритм « Набери в лесу грибов »

Алгоритм « Съешь конфету»

1.Возьми конфету из вазы.

1.Возьми пустую корзину.

2.Разверни фантик.

2.Прийди в лес.

3.Съешь конфету.

3.Если нашел съедобный гриб, то положи в корзину.

4.Фантик выбрось в мусорное ведро.

4.Если корзина еще не полная, то повтори п.3, иначе перейди к п.5.

5.Приди домой.

6.Поставь корзину с грибами на место.

Алгоритм « Рисунок »

1.Возьми карандаш.

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

• Графическая форма

Шаги алгоритмов обозначаются геометрическими фигурами.

Пример алгоритма

представленного в форме блок-схемы

Начало или конец

Начало

Ввод или вывод

Подойти к переходу

Выполнение действия

Дождаться зеленого света

Принятие решения

Перейти улицу

Цикл со счетчиком

Конец

Переход

• Псевдокод

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

Примеры записи алгоритмов на алгоритмическом языке.

АЛГ

НАЧ

Ввод

Вывод

КОН

АЛГ Дождь

НАЧ

Подойди к окну

ЕСЛИ Идет дождь

ТО Останься дома

ИНАЧЕ Иди гулять

ВСЕ

КОН

АЛГ Вычислить Y=R+T-X

НАЧ

Ввод R,T,X

A1:= R+T

Y:= A1-X

Вывод Y

КОН

b then max:=a else max:=b; writeln (max); End. Алгоритм, записанный на понятном компьютеру языке программирования, называется программой. " width="640"

• Программа

Program ostatok;

Uses crt;

Var a, b, max: real;

Begin

ClrScr;

Readln (a, b);

If ab

then max:=a

else max:=b;

writeln (max);

End.

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

• Виды алгоритмов:

• Линейный алгоритм – это описание последовательности действий, которые выполняются однократно в заданном порядке.
• Разветвляющийся алгоритм - это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
• Циклический – это описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие (параметр цикла).

• Линейные алгоритмы

• Состоят из нескольких команд (операторов), которые должны быть выполнены последовательно одна за другой

Структура линейного алгоритма

Действие 1

Действие 2

. . .

Действие N

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

• Состоят из нескольких команд. В зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов.

Логику принятия решения можно описать так:

Да

Нет

ЕСЛИ

ТО

ИНАЧЕ

ВСЕ

Условие

Действие 1

Действие 2

П р и м е р ы :

ЕСЛИ хочешь быть здоров, ТО закаляйся, ИНАЧЕ валяйся весь день на диване;

ЕСЛИ низко ласточки летают, ТО будет дождь, ИНАЧЕ дождя не будет;

ЕСЛИ уроки выучены, ТО иди гулять, ИНАЧЕ учи уроки.

В некоторых случаях могут отсутствовать:

Нет

Условие

ЕСЛИ

ТО

ВСЕ

Да

Действие 1

Действие

АЛГ Пословица

НАЧ

ЕСЛИ Назвался груздем

ТО Полезай в кузов

ВСЕ

КОН

АЛГ Раскрасить листок

НАЧ

ЕСЛИ Ты любишь осень?

ТО Возьми желтый карандаш

ИНАЧЕ Возьми зеленый карандаш

ВСЕ

Раскрась листок

Убери карандаш

КОН

• Фальшивая монета

?

Задача: Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?

• Блок-схема

Начало

Положить по одной монете

на каждую чашу весов,

третью монету отложить

в сторону

Весы в

равновесии?

Да

Нет

Монета на поднявшейся

вверх чаше фальшивая

Отложенная монета –

фальшивая

Конец

• Циклические алгоритмы

• Состоят из нескольких команд. Команды повторяются несколько раз (или ни разу) до тех пор, пока выполняется некоторое условие.

Цикл с постусловием

Тело цикла

Нет

условие

Цикл со счетчиком

Да

счетчик

Цикл с предусловием

Нет

условие

Тело цикла

Да

Тело цикла

• Подготовка домашнего задания

Начало

Решить задачу

Все задачи по математике решены?

Нет

Да

Пойти гулять до ужина

Конец

Алгоритм поиска Золушки

Начало

Встретить девушку

Примерить ей туфельку

Распрощаться с девушкой

Подошла?

Нет

Да

Золушка найдена!

Конец

• Самостоятельная работа

Творческая работа:

• Приготовление моего любимого блюда.
• Мой обычный день.