Понятие алгоритма. Свойства алгоритма. Основные сведения об алгоритмах

1.

Информатика
ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА АЛГОРИТМА
ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
11 класс

2.

МК
Ключевые слова
алгоритм
исполнитель алгоритма
свойства алгоритма
• дискретность
• детерминированность
• понятность
• результативность
• конечность
• массовость
вычислительный процесс
сложность алгоритма

3.

МК
Исполнитель алгоритма
!
Исполнитель алгоритма – это субъект или устройство, способные
правильно интерпретировать описание алгоритма и выполнить со­
держащийся в нём перечень действий.
Неформальный
Неформальный
исполнитель
исполнитель
понимает смысл алгоритма,
может его корректировать и
изменять, а также отказаться
выполнять
одну и ту же команду
выполняет каждый раз поразному
неформальный
исполнитель
сам отвечает за свои действия
в
роли
неформального
исполнителя
чаще
всего
выступает человек
Художник Василий Тропинин «Золотошвейка» (1826)
Формальный
Формальный
исполнитель
исполнитель
не размышляет над выпол­
няемыми командами, а строго
следует пошаговым инструк­
циям алгоритма
одну и ту же команду всегда
выполняет одинаково
за
действия
формального
исполни­теля отвечает управ­
ляющий им объект
в роли формального исполни­
теля чаще всего выступает
техническое устройство

4.

МК
Понятие алгоритма
!
Алгоритм – точная система предписаний, определяю­щая
содержание и порядок действий исполнителя над некоторыми
объектами (исходными и промежуточными данными) для
получения искомого результата за конечное число шагов.
ПРИМЕРЫ АЛГОРИТМОВ
Закрыть
входную дверь
ключом
Нахождение n первых
простых чисел
(метод Эратосфена)
Построение
перпендикуляра
к прямой

5.

МК
Пример 1
Алгоритм
«Закрыть входную дверь ключом»
1. Вставить ключ в замочную скважину.
2. Повернуть ключ два раза на 180 градусов против часовой стрелки.
3. Вынуть ключ из замочной скважины.
Исполнитель: человек
Объекты алгоритма: ключ, дверь

6.

МК
Пример 2
Алгоритм «Нахождение всех простых чисел не больше заданного числа
n по методу Эратосфена»
1. Выписать подряд все целые числа
от 2 до n (2, 3, 4, …, n).
2. Присвоить переменной p значе­
ние 2 (2 – первое простое число).
3. Зачеркнуть в списке числа, кратные
p: 2p, 3p, 4p, …
4. Найти первое незачёркнутое число
в списке, большее чем p, и прис­
воить p соответствующее значение.
5. Повторять шаги 3 и 4, пока
возможно (пока p2 ≤ n).
6. Незачёркнутые числа и есть все
простые числа от 2 до n.
Простые числа от 2 до 100
23 5 7
11131719
232931 7
3
41434753 59
61 71 79
67 73
83 89 97
Выполнить

7.

МК
Пример 2
Алгоритм «Нахождение всех простых чисел не больше заданного числа
n по методу Эратосфена»
1. Выписать подряд все целые числа
от 2 до n (2, 3, 4, …, n).
2. Присвоить переменной p значе­
ние 2 (2 – первое простое число).
3. Удалить из списка числа, кратные
p: 2p, 3p, 4p, …
4. Найти первое число в списке,
большее чем p, и прис­воить p
соответствующее значение.
5. Повторять шаги 3 и 4, пока
возможно (пока p2 ≤ n).
6. Оставшиеся числа и есть все
простые числа от 2 до n.
Простые числа от 2 до 100
1
1
1
1
2
2
1
1
3
3
1
1
4
4
1
1
5
5
1
1
6
6
1
1
7
7
1
1
8
2
3
1
2
2
2
3
2
4
2
5
2
6
2
7
2
1
1
3
3
2
2
3
3
3
3
3
3
4
4
3
3
5
5
3
3
6
6
3
3
7
7
3
3
8
4
5
6
7
1
4
2
4
3
4
4
4
5
4
6
4
7
4
1
1
5 1
5 6
2
2
5 2
5 6
3
3
5 3
5 6
4
4
5 4
5 6
5
5 5
5 6
6
6
5 6
5 6
5
p7 = 7
3
2
7
5 7
5 6
8
1
1
7
7
2
2
7
7
3
3
7
7
4
4
7
7
5
5
7
7
6
6
7
7
7
7
7
7
8
8
9
1
8
2
8
3
8
4
8
5
8
6
8
7
8
1
1
9
9
2
2
9
9
3
3
9
9
4
4
9
9
5
5
9
9
6
6
9
9
7
7
9
9
8
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0

8.

МК
Пример 3
Алгоритм «Построение перпендикуляра к прямой, проходящей через
заданную точку O, лежащую на прямой с помощью циркуля и линейки»
1. Провести окружность с центром в
точке O и радиусом 1 см.
2. Обозначить точки пересечения
окружности с прямой: левую - A,
правую - B.
3. Провести окружность с центром в
точке A и радиусом равным AB.
4. Провести окружность с центром в
точке В и радиусом равным AB.
5. Обозначить точки пересечения
окружностей:
верхнюю - C,
нижнюю - D.
6. Провести прямую СD.
Выполнить

9.

МК
Пример 3
Алгоритм «Построение перпендикуляра к прямой, проходящей через
заданную точку O, лежащую на прямой с помощью циркуля и линейки»
1. Провести окружность с центром в
точке O и радиусом 1 см.
2. Обозначить точки пересечения
окружности с прямой: левую - A,
правую - B.
3. Провести окружность с центром в
точке A и радиусом равным AB.
4. Провести окружность с центром в
точке В и радиусом равным AB.
5. Обозначить точки пересечения
окружностей: верхнюю - C ,
нижнюю - D.
6. Провести прямую СD.
С
А
О
D
В

10.

МК
Свойства алгоритма
!
Алгоритм – конечная система правил, сформулированных на
языке исполнителя, которая определяет последовательность
перехо­да от допустимых исходных данных к конечному результату
и обла­дает свойствами дискретности, детерминированности,
понятности, результативности, конечности и массовости.
Дискретность
Детерминированность
Понятность
Результативность
Массовость
Массовость
Дискретность
Детерминированность
Понятность
Результативность
Выполнение
Каждая
При
Алгоритм
точном
команда
пригоден
не
алгоритма
исполнении
алгоритма
должен
для решения
разбивается
определяет
содержать
команд
любой
на
последовательность
однозначное
предписаний,
алгоритма
задачи
из некоторого
процесс
действие
смысл
должен
законченных
класса
которых
исполнителя,
прекратиться
задач,
может
дейст­
т. е.
и
вий-шагов.
недвусмысленно
восприниматься
за
алгоритм
конеч­ное
правильно
Только
число
исполнителем
указывает,
шагов,
работает
выполнив
и при
нанеодно­
какая
одно
этом
неко­
действие,
команда
знач­
должен
тором
но, множестве
т.
быть
должна
е. можно
запись
получен
выполняться
исходных
алгоритма
ответ
приступать
на данных,
должна
следую­
вопроск
выполнению
щей.
быть
задачи.
которое
настолько
Многократное
Вназывается
качестве
следующего.
чёткой
одного
областью
выполнение
и полной,
из Произвести
возможных
примени­
чтобы
алго­
у
каждоеалгоритма.
ритма
исполнителя
ответов
мости
при
отдельное
может
одном
не возникло
быть
действие
иустановление
томпотребности
исполнителю
же наборе
тогов
предписывает
входных
принятии
факта,
что задача
данных,
каких-либо
специальное
решений
дает
самостоятельных
неодинаковые
указание
имеет.
в
записи алгоритмаи –выходной
промежуточные
решений.
команда.результаты.

11.

МК
Давайте обсудим
?
Можно ли кулинарный рецепт считать алгоритмом?
Ответ обоснуйте с точки зрения свойств алгоритма.

12.

МК
Способы записи алгоритмов
Нахождение максимума
Шахматный
из 10 целыхэтюд
чисел
Мат
в дваалгоритма
хода.
запись
словесная
Белые
и выигрывают
наначинают
естественном
языке
запись алгоритма на языке
программирования
Сложение смешанных дробей
Нахождение НОД
1. Привести дробные части чисел
Program
NOD; с помощью
запись
алгоритма
к наименьшему
общему
var
a,
b,
n:
integer;
формул, рисунков, таблиц
знаменателю.
Begin
2. Сложить только целые части.
writeln ('Введите два числа: ');
3. Отдельно сложить дробные
readln (a, b);
части.
while a <> b do
4. Сложить результаты,
if a>b then a := a - b
полученные в п.2 и п. 3.
Решение:
else b := b – a;
5.
Если
при
сложении дробных
№ Белые
n:= a; Черные № Белые Черные
получилась
с1помощью
блок-схемы
–
Ф f1-a1
K h8-g8
Ф частей
f1-a1 g6-g5
writeln
('НОД = ',1 n);
неправильная
дробь,
выделить
стандартных
графических
2 Ф a1-a8
2 KEnd.
f6-f7
целую часть из этой дроби и
объектов
№ Белые Черные
к полученной
(геометрических
фигур)целой
1 Ф прибавить
f1-a1
С h7-g8
2 K части.
f6-g6
6. Сократить полученную дробь.

13.

МК
Блок-схема
СИМВОЛ
ФУНКЦИЯ
Пуск/остановка. Начало, конец, прерывание процесса
обработки данных или выполнения программы
Ввод/вывод. Преобразование данных в форму, пригодную для
обработки (ввод) или отображения результатов (вывод)
Процесс. Выполнение операций или группы операций, в
результате которых изменяется значение, форма представления
или расположение данных
Решение. Выбор направления выполнения алгоритма или
программы в зависимости от некоторых переменных условий
Модификация. Выполнение операций, меняющих команды или
группу команд, изменяющих программу
Предопределённый процесс. Использование ранее созданных и
отдельно описанных алгоритмов или программ
Правила выполнения блок-­схем, внешний вид графических блоков и их назначение
определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ,
данных и систем. Обозначения условные и правила выполнения».

14.

МК
Понятие сложности алгоритма
Теория алгоритмов предоставляет аппарат анализа различных
алгоритмов решения одной и той же задачи, на основе которого можно
выбрать самый эффективный (наилучший) алгоритм.
!
Вычислительным
процессом,
порождённым
алгоритмом,
называется последовательность шагов алгоритма, пройденных при
его ис­полнении.
Сложность алгоритма – количество элементарных шагов
(действий) в вычислительном процессе этого алгоритма.
Для решения задачи могут быть разработаны алгоритмы, имеющие
разную сложность. Лучшим среди них считается алгоритм, имеющий
наименьшую сложность.
Эффективность оценивается количеством элементарных операций,
которые необходимо выполнить для решения задачи, а также
количеством памяти, требующейся для выполнения алгоритма.

15.

МК
Временная сложность
Сложность алгоритма выражают в виде функции от объёма входных
данных.
Задание. Оцените сложность алгоритмов:
«Найти книгу с секретом»
В
в одном из 1000
томов,
Пристаринной
линейномбиблиотеке
поиске – последовательной
проверки
посвященных
кладам
и тайникам,
спрятана
всех книг подряд
– сложность,
в худшем
случае, книгабудет
сейф.
найти книг,
ее. т.е. O(n) = 1000.
равна Надо
количеству
«Поиск в телефонной книге»
В сейфе оказался клочок страницы с фамилией и первой цифрой
номера телефона. Надо найти страницу с нужной фамилией в
телефонном справочнике, в котором 1000 страниц .
ВСложность
данном случае,
алгоритма
за счет
будет
сортировки
O(log2n). имен по алфавиту,
можно
применив
метод
половинного
Таким сократить
образом, поиск,
в книге
объёмом
в 1000
страниц
деления
книгу примерно
в не
середине,
мы
страница с(открыв
нужной фамилией
находится
больше, чем
уменьшаем
размер
«оставшейся проблемы» вдвое).
за O(log21000)
≈ 10 раз.

16.

МК
Пример 4
Алгоритм «Возведение числа в натуральную степень (xn)»
1. Запишем n в двоичной системе счисления.
2. Заменим каждую 1 парой букв КХ, а каждый 0 – буквой К.
3. Вычеркнем крайнюю левую пару КХ.
4. Полученная строка, читаемая слева направо, даёт правило быстрого
вычисления хn, если букву К рассматривать как операцию возведения
результата в квадрат, а букву X – как операцию умножения результата
на х. Вначале результат равен х.
Задание. Найти
X
40
40 =
К возведение результата в Квадрат
Х умножение результата на Х
1
0
КХ К
х2
х4
1
0
КХ К
х5
0
К
0
К
х10 х20 х40
2

17.

МК
Самое главное
Алгоритм – конечная система правил, сформулированных на языке
исполнителя, которая определяет последовательность перехода от
допустимых исходных данных к конечному результату и обладает
свойствами
дискретности,
детерминированности,
понятности,
результативности, конечности и массовости.
Исполнитель алгоритма – субъект или устройство, способные правильно
интерпретировать описание алгоритма и выполнить содержащийся в нём
перечень действий.
Один и тот же алгоритм может быть записан разными способами: на
естественном языке, псевдокодом, с помощью блок-схем, на языке
программирования и т. д.
Теория алгоритмов предоставляет аппарат анализа различных
алгоритмов решения одной и той же задачи, на основе которого можно
выбрать самый эффективный (наилучший) алгоритм.

18.

МК
Самое главное
Алгоритм состоит из команд. Команда – отдельная инструкция в описании
алгоритма. Шаг алгоритма – отдельное действие, которое исполнитель
выполняет по команде. Вычислительным процессом, порождённым
алгоритмом, называется последовательность шагов алгоритма,
пройденных при его исполнении.
Сложность алгоритма – количество элементарных шагов (действий) в
вычислительном процессе этого алгоритма. Наряду со сложностью
важной
характеристикой
алгоритма
является
эффективность.
Эффективность оценивается количеством элементарных операций,
которые необходимо выполнить для решения задачи, а также
количеством памяти, требующейся для выполнения алгоритма.

19.

МК
Вопросы и задания
Задание 1. Автомат получает на вход трёхзначное число. По этому числу
строится новое число по следующим правилам:
1. Складываются первая и вторая, а также вторая и третья цифры
исходного числа.
2. Полученные два числа записываются друг за другом в порядке
убывания (без разделителей).
Укажите наименьшее число, в результате обработки которого автомат
выдаст число 1711.
Решение:
1. Единственный способ разбить запись 1711 на два числа – это 17 и 11.
2. Чтобы число было меньше, надо чтобы сумма первой и второй цифр
была наименьшей, в данном случае 11.
3. Сумма значений двух последних цифр равна 17. Не трудно заметить,
что 17 = 8 + 9 = 9 + 8. Других вариантов нет.
4. Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст ме́ньшее число.
Ответ: 298.

20.

МК
Вопросы и задания
?
Задание 2. Подсчитайте сложность алгоритма сложения двух
натуральных чисел «столбиком» при условии, что одно из них состоит из
n, а второе – из m десятичных цифр.
Решение:
Сложение двух чисел столбиком в случае, если одно из них состоит из n, а
другое – из m цифр требует не более max(n, m) сложений и не
более max(n, m) запоминаний (в случае перехода через десяток).
Т.е. данный алгоритм имеет сложность порядка O(n+m).
Выражение показывает только порядок величины – постоянные факторы
в нем не учитываются.

21.

МК
Вопросы и задания
?
Задание 3. Есть двое песочных часов: на 3 и на 8 минут. Для
приготовления эликсира бессмертия его надо варить ровно 7 минут. Как
это сделать? Придумайте систему команд исполнителя Колдун. Запишите
с их помощью план действий исполнителя по приготовлению эликсира.
Графический способ решения:

22.

МК
Вопросы и задания
?
Задание 4. Приведите примеры алгоритмов, с которыми вы встречались
на биологии, математике, физике.

23.

МК
Вопросы и задания
?
Задание 5. Двое мальчиков катались на лодке. К берегу подошли два
солдата. Лодка так мала, что на ней могут переправиться двое мальчиков
или только один солдат. Как солдатам переправиться через реку?

24.

МК
Информационные источники
https://img2.goodfon.ru/original/1920x1080/a/91/zamok-klyuch-otverstie-svet.jpg
http://biblo-ok.ru/biblio-ok/Kartiny1/79.files/image001.jpg
http://cheeseberry-sibir.ru/photos/vyshivka-na-odejde-izgotovlenie-6259-large.jpg
http://europeansectionarcipreste.blogspot.ru/2011_11_01_archive.html
http://www.imasitalia.com/wp-content/uploads/2016/04/fogli.jpg
http://atotarho12.narod.ru/clipart/k/kar/karanda44.png
https://s-media-cache-ak0.pinimg.com/originals/73/96/fd/7396fd0a921a5f895bafd81830adcaa5.jpg
https://chessok.net/zadachi/1165-reshit-legkuyu-dvuhhodovku.html
http://pikabu.ru/story/metod_byistrogo_umnozheniya_karatsubyi_4226758
http://ozon.ru. Сейф-книга "Вид на реку"
https://openclipart.org/image/800px/svg_to_png/171487/1344190891.png
http://vamotkrytka.ru/_ph/54/2/531435092.gif
http://www.gifmania.ru/Animated-Gifs-Veb-dizayn/Animations-Geometry/Images-Geometric-Stars/Geometric-Stars-89830.gif
http://www.freeiconspng.com/free-images/potion-icon-png-15620