Урок по теме "Алгоритмы"

Тема:

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

ИЗУЧИТЬ:

Что такое алгоритм и его основные свойства

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

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

АЛГОРИТМ

Более 1000 лет назад (в 825 году) ученый математик и астроном из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло из названия латинского перевода книги «Algoritmi de numero Indoru», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов».

Понятие алгоритма является одним из основных понятий современной математики и является объектом исследования специального раздела математики - теории алгоритмов.

Сегодня, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации.

АЛГОРИТМ

• описание последовательности действий (план)

• строгое исполнение этих действий

• для исполнителя

• приводит к решению поставленной задачи за конечное число шагов

ОПРЕДЕЛЕНИЕ

АЛГОРИТМ - это понятное и точное предписание исполнителю совершить строгую последователь-ность действий, направленных на решение поставленной задачи

Универсальная схема оказания первой помощи на месте происшествия

Если нет сознания и нет пульса на сонной артерии-

ПРИСТУПИТЬ К РЕАНИМАЦИИ

I

Если нет сознания , но есть пульс на сонной артерии-

ПЕРЕВЕРНУТЬ НА ЖИВОТ и

ОЧИСТИТЬ РОТОВУЮ ПОЛОСТЬ

II

При артериальном кровотечении-

НАЛОЖИТЬ ЖГУТ

III

При наличии ран-

НАЛОЖИТЬ ПОВЯЗКИ

IV

Если есть признаки переломов костей конечностей-

НАЛОЖИТЬ ТРАНСПОРТНЫЕ ШИНЫ

V

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

ДИСКРЕТНОСТЬ

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

ПОНЯТНОСТЬ

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

ОПРЕДЕЛЕННОСТЬ

ДЕТЕРМИНИРОВАННОСТЬ

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

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

Отмеченное свойство называется свойством определенности ( детерминированности)

РЕЗУЛЬТАТИВНОСТЬ

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

МАССОВОСТЬ

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

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

ДИСКРЕТНОСТЬ

ПОНЯТНОСТЬ

ОПРЕДЕЛЕННОСТЬ

ДЕТЕРМИНИРОВАННОСТЬ

РЕЗУЛЬТАТИВНОСТЬ

МАССОВОСТЬ

Основные способы задания алгоритмов

• Словесный- формульный ( письменно или устно);
• Графический (стрелками, рисунками,

блок – схемами);

• Программный (алгоритмический язык)

Пример №1

Алгоритм Эратросфена

• Выписать все натуральные числа от 1 до N. Вычеркнуть 1.
• Подчеркнуть наименьшее из неотмеченных чисел.
• Вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге.
• Если в списке имеются еще не отмеченные числа, то перейти к шагу 2.
• Все подчеркнутые числа – простые.

Пример №2

Пример №3

НАЧАЛО

ВВОД a,b,c

p=(a+b+c)/2

s =SQR(p(p-a)(p-b)(p-c))

ВЫВОД S

КОНЕЦ

Пример №4

REM Вычисление площади треугольника по 3 сторонам

CLS

INPUT "Введите сторону а: ", a

INPUT "Введите сторону b: ", b

INPUT "Введите сторону c: ", c

p=(a+b+c)/2

s=SQR(p(p-a)(p-b)(p-c))

PRINT " Площадь треугольника равна: ", s

END

Элементы блок-схемы

Команда алгоритма

Начало или конец алгоритма

Проверка условия

Ввод или вывод данных

. . .

Повторение действий (цикл)

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

1. Линейные (простые)

Команда 1

Команда 2

. . .

Команда N

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

2.Разветвляющиеся

а) Полное ветвление

Условие

Да

Нет

Серия 1

Серия 2

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

2. Разветвляющиеся

б) Неполное ветвление

Условие

Да

Нет

Серия 1

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

3. Циклические

а) арифметический цикл

Счетчик цикла

Серия

команд

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

3. Циклические

б) Логический цикл с предусловием

Условие

Нет

Да

Серия

команд

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

3. Циклические

в) Логический цикл с послеусловием

Серия

команд

Нет

Условие

Да

Алгоритм – это …

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

Алгоритмы можно записать такими способами …

Основные структуры алгоритмов:

1. -

2. -

3. -

Алгоритм решения задач на ЭВМ

• Постановка задачи
• Разработка метода решения(Построение математической модели)
• Разработка алгоритма
• Составление программы на языке программирования
• Отладка и тестирование программы
• Анализ результатов

ПОСТАНОВКА ЗАДАЧИ.

Определить время встречи двух

траулеров РТМС «Лира» и СРТМ «Ольга», идущих навстречу

друг другу, если известно, что

расстояние между ними L миль,

скорость первого траулера V1 узлов,

скорость второго V2 узлов.

0, V10, V20, T0 Дано: L, V1, V2. Найти: t. Условие: L0, V10, V20, T0 Дано: L, V1, V2. Найти: t. Условие: L0, V10, V20, T0 V1 V2 L " width="640"

Дано: L, V1, V2.

Найти: t.

Условие:

L0, V10, V20, T0

• Дано: L, V1, V2. Найти: t. Условие: L0, V10, V20, T0
• Дано: L, V1, V2. Найти: t. Условие: L0, V10, V20, T0

V1

V2

L

0 " width="640"

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ.

L=S1+S2

S1=V1*T

S2=V2*T

L= V1*T +V2*T = T*( V1 + V2)

T=L / (V1 + V2)

При условии V1 иV2и L0

0 V10 V20 S1=V1* t Решений нет НЕТ ДА S2=V2* t L=t*(V1+V2) ВЫВОД t КОНЕЦ t=L/ (V1+V2) " width="640"

БЛОК-СХЕМА.

НАЧАЛО

ВВОД L,V 1 ,V 2

L0

V10

V20

S1=V1* t

Решений нет

НЕТ

ДА

S2=V2* t

L=t*(V1+V2)

ВЫВОД t

КОНЕЦ

t=L/ (V1+V2)

0 and V10 and V20 THEN GOTO 10 ELSE GOTO 20 10 t =L / (V1 + V2) PRINT t: END 20 PRINT “Решений нет”: END " width="640"

ПРОГРАММА

Rem Определение времени встречи двух траулеров

INPUT L, V1, V2

IF L0 and V10 and V20 THEN GOTO 10 ELSE GOTO 20

10 t =L / (V1 + V2)

PRINT t: END

20 PRINT “Решений нет”: END

Составить блок- схемы по математическим моделям

МЕТОДИЧЕСКОЕ ПОСОБИЕ ДЛЯ

ПРАКТИЧЕСКИХ ЗАНЯТИЙ

СТР. 23-24

• Разобрать примеры 1,2,3

2. Самостоятельно составить блок-схему алгоритмов