Алгоритм
<<  Алгоритм создания бизнеса Алгоритм  >>
Алгоритм
Алгоритм
Алгоритм и его свойства
Алгоритм и его свойства
История понятия «алгоритм»
История понятия «алгоритм»
Определение алгоритма
Определение алгоритма
Понятие исполнителя алгоритма
Понятие исполнителя алгоритма
Исполнитель алгоритма
Исполнитель алгоритма
Графическое представление алгоритма
Графическое представление алгоритма
Блок-схема
Блок-схема
Блок-схема
Блок-схема
Развитие структуры «альтернатива»
Развитие структуры «альтернатива»
Дополнительные блоки блок-схемы
Дополнительные блоки блок-схемы
Свойства алгоритмов
Свойства алгоритмов
Первое свойство алгоритма
Первое свойство алгоритма
Второе свойство алгоритма
Второе свойство алгоритма
Третье свойство алгоритма
Третье свойство алгоритма
Четвертое свойство алгоритма
Четвертое свойство алгоритма
Пятое свойство алгоритма
Пятое свойство алгоритма
Алгоритмический язык
Алгоритмический язык
Понятие алгоритмического языка
Понятие алгоритмического языка
Понятие алгоритмического языка (2)
Понятие алгоритмического языка (2)
Понятие алгоритмического языка (3)
Понятие алгоритмического языка (3)
Последовательность записи алгоритма
Последовательность записи алгоритма
Вспомогательные алгоритмы
Вспомогательные алгоритмы
Вспомогательные алгоритмы
Вспомогательные алгоритмы
Рекурсия
Рекурсия
Пример прямой рекурсии
Пример прямой рекурсии
Ветвления алгоритма
Ветвления алгоритма
Выбор
Выбор
Итерация
Итерация
Пример (работа робота)
Пример (работа робота)
Жадный алгоритм
Жадный алгоритм
Жадный алгоритм
Жадный алгоритм
Вопросы
Вопросы

Презентация: «Алгоритм». Автор: . Файл: «Алгоритм.ppt». Размер zip-архива: 139 КБ.

Алгоритм

содержание презентации «Алгоритм.ppt»
СлайдТекст
1 Алгоритм

Алгоритм

2 Алгоритм и его свойства

Алгоритм и его свойства

Понятие алгоритма – одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким и кибернетике. Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике – теории алгоритмов.

2

2

кафедра ЮНЕСКО по НИТ

3 История понятия «алгоритм»

История понятия «алгоритм»

Само слово «алгоритм» происходит от algorithmi – латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами понимали только правила выполнения четырех арифметических действий над многозначными числами.

3

3

кафедра ЮНЕСКО по НИТ

4 Определение алгоритма

Определение алгоритма

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

4

кафедра ЮНЕСКО по НИТ

5 Понятие исполнителя алгоритма

Понятие исполнителя алгоритма

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

5

кафедра ЮНЕСКО по НИТ

6 Исполнитель алгоритма

Исполнитель алгоритма

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

6

кафедра ЮНЕСКО по НИТ

7 Графическое представление алгоритма

Графическое представление алгоритма

Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического описания; с помощью словесного описания; в виде таблицы; в виде последовательностью формул. Графическое описание алгоритма, называется блок-схемой. Блок-схема – это ориентированный граф, указывающий порядок исполнения команд алгоритма.

7

кафедра ЮНЕСКО по НИТ

8 Блок-схема

Блок-схема

Вершины графа могут быть одного из трех типов: Функциональная (имеющая один вход и один выход); Предикатная (имеющая один вход и два выхода ); Объединяющая (обеспечивающая передачу управления от одного из двух входов к выходу).

T

P

F

o

F

8

8

кафедра ЮНЕСКО по НИТ

9 Блок-схема

Блок-схема

Из данных элементарных блоков можно построить четыре блок-схемы, имеющих особое значение для практики алгоритмизации.

Композиция, Следование

Альтернатива, Развилка

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

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

9

9

кафедра ЮНЕСКО по НИТ

10 Развитие структуры «альтернатива»

Развитие структуры «альтернатива»

Неполная развилка Структура «выбор»

10

10

кафедра ЮНЕСКО по НИТ

11 Дополнительные блоки блок-схемы

Дополнительные блоки блок-схемы

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

Выполнение операций, изменяющих команды

Вызов вспомогательного алгоритма

Ввод-вывод данных

11

11

кафедра ЮНЕСКО по НИТ

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

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

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

12

кафедра ЮНЕСКО по НИТ

13 Первое свойство алгоритма

Первое свойство алгоритма

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

13

кафедра ЮНЕСКО по НИТ

14 Второе свойство алгоритма

Второе свойство алгоритма

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

14

кафедра ЮНЕСКО по НИТ

15 Третье свойство алгоритма

Третье свойство алгоритма

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

15

кафедра ЮНЕСКО по НИТ

16 Четвертое свойство алгоритма

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

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

16

кафедра ЮНЕСКО по НИТ

17 Пятое свойство алгоритма

Пятое свойство алгоритма

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

17

кафедра ЮНЕСКО по НИТ

18 Алгоритмический язык

Алгоритмический язык

кафедра ЮНЕСКО по НИТ

18

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

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

Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Между понятиями «алгоритмический язык» и «языки программирования» есть различие; прежде всего, под исполнителем в алгоритмическом языке может подразумеваться не только компьютер, но и устройство для работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно предназначена компьютеру. Практическая же реализация алгоритмического языка -отдельный вопрос в каждом конкретном случае.

19

кафедра ЮНЕСКО по НИТ

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

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

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

20

кафедра ЮНЕСКО по НИТ

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

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

Алгоритм, записанный на алгоритмическом языке, должен иметь название. Название желательно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывают служебное слово АЛГ (АЛГоритм). Для указания начала и конца алгоритма его команды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец). Команды записывают последовательно.

21

21

кафедра ЮНЕСКО по НИТ

22 Последовательность записи алгоритма

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

АЛГ название алгоритма НАЧ серия команд алгоритма КОН Например, алгоритм, определяющий движение исполнителя-робота. АЛГ в_склад НАЧ вперед поворот на 90° направо вперед КОН

22

22

кафедра ЮНЕСКО по НИТ

23 Вспомогательные алгоритмы

Вспомогательные алгоритмы

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

23

кафедра ЮНЕСКО по НИТ

24 Вспомогательные алгоритмы

Вспомогательные алгоритмы

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

24

24

кафедра ЮНЕСКО по НИТ

25 Рекурсия

Рекурсия

Алгоритм может содержать обращение к самому себе как вспомогательному и в этом случае его называют рекурсивным. Если команда обращения алгоритма к самому себе находится в самом алгоритме, то такую рекурсию называют прямой. Возможны случаи, когда рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение. Такая рекурсия называется косвенной.

25

кафедра ЮНЕСКО по НИТ

26 Пример прямой рекурсии

Пример прямой рекурсии

АЛГ движение НАЧ вперед вперед вправо движение КОН

26

26

кафедра ЮНЕСКО по НИТ

27 Ветвления алгоритма

Ветвления алгоритма

Алгоритмы, при исполнении которых порядок следования команд определяется в зависимости от результатов проверки некоторых условий, называют разветвляющимися. Для их описания в алгоритмическом языке используют специальную составную команду - команда ветвления. Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную форму. ЕСЛИ условие ЕСЛИ условие ТО серия 1 ТО серия ИНАЧЕ серия2 ВСЕ ВСЕ

27

27

кафедра ЮНЕСКО по НИТ

28 Выбор

Выбор

Запись на алгоритмическом языке команды выбора, являющейся развитием команды ветвления: ВЫБОР ПРИ условие 1: серия 1 ПРИ условие 2: серия 2 … ПРИ условие N: серия N ИНАЧЕ серия N+1 ВСЕ

28

28

кафедра ЮНЕСКО по НИТ

29 Итерация

Итерация

Алгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация» и может принимать следующий вид: ПОКА условие НЦ НЦ серия Серия ДО условие КЦ КЦ

29

29

кафедра ЮНЕСКО по НИТ

30 Пример (работа робота)

Пример (работа робота)

АЛГ перенос АЛГ в_угол3 АЛГ до_края НАЧ НАЧ НАЧ в_угол3 до_края ПОКА не_край ЕСЛИ есть вправо НЦ ТО до_края вперед взять вправо КЦ в_угол3 КОН КОН установить перенос ИНАЧЕ в_угол3 ВСЕ КОН

30

30

кафедра ЮНЕСКО по НИТ

31 Жадный алгоритм

Жадный алгоритм

Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская что конечное решение также окажется оптимальным. Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами характерны две особенности: к ним применим Принцип жадного выбора (последовательность локально оптимальных выборов даёт глобально оптимальное решение). они обладают свойством Оптимальности для подзадач (оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач).

31

кафедра ЮНЕСКО по НИТ

32 Жадный алгоритм

Жадный алгоритм

Пример1. Размен монет. Задача. Монетная система некоторого государства состоит из монет достоинством a1 = 1 < a2 < ... < an. Требуется выдать сумму S наименьшим возможным количеством монет. Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства an: xn=[S/an]. Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д. Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 10 копеек монетами в 1, 5 и 6 коп. жадный алгоритм разменивает так: 6 коп. — 1 шт., 1 коп. — 4 шт., в то время как правильное решение — 2 монеты по 5 копеек. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

32

кафедра ЮНЕСКО по НИТ

33 Вопросы

Вопросы

33

кафедра ЮНЕСКО по НИТ

«Алгоритм»
http://900igr.net/prezentacija/informatika/algoritm-242520.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды