Понятие алгоритма. Свойства алгоритма +ДЗ20. Основные сведения об алгоритмах. Информатика. 11 класс

1.

ПОНЯТИЕ АЛГОРИТМА.
СВОЙСТВА
АЛГОРИТМА+ДЗ20
ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

2.

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

3.

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

4.

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

5.

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

6.

МК
Способы записи алгоритмов
Нахождение максимума
Шахматный
из 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
1 Ф частей
f1-a1
g6-g5
writeln
('НОД =графических
', n);
стандартных
дробь,
выделить
2 Ф a1-a8
2 K неправильная
f6-f7
End.
объектов
целуюЧерные
часть
из этой дроби и
№ Белые
(геометрических
фигур)целой
к полученной
1 Ф прибавить
f1-a1
С h7-g8
2 K части.
f6-g6
6. Сократить полученную дробь.

7.

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

8.

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

9.

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

10.

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

11.

У исполнителя Калькулятор две команды, которым присвоены
номера:
1. отними 2
2. раздели на 3
Выполняя первую из них, Калькулятор отнимает от числа на экране
2, а выполняя вторую, делит его на 3 (если деление нацело
невозможно, Калькулятор отключается).
Запишите порядок команд в программе получения из числа 37
числа 3, содержащей не более 5 команд, указывая лишь номера
команд.

12.

У исполнителя Квадр две команды, которым присвоены номера:
1. прибавь 1,
2. возведи в квадрат.
Первая из этих команд увеличивает число на экране на 1, вторая возводит в квадрат. Программа для исполнителя Квадр - это последовательность номеров команд. Запишите программу для исполнителя Квадр, которая преобразует число 3 в число 10001 и содержит
не более 6 команд. Если таких программ более одной, то запишите
любую из них.

13.

Автомат получает на вход трёхзначное число. По этому
числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также вторая и третья
цифры исходного числа.
2. Полученные два числа записываются друг за другом в
порядке возрастания (без разделителей).
Пример. Исходное число: 348. Суммы: 3+4 = 7; 4+8 = 12.
Результат: 712.
Укажите наименьшее число, в результате обработки
которого автомат выдаст число 1115.

14.

Некоторый исполнитель может выполнить только 2
команды:
1. К числу прибавить 1
2. Число умножить на 2
Запишите порядок команд в программе получения из
числа 17 числа 729, содержащей не более 13 команд,
указывая лишь номера команд

15.

У исполнителя УТРОИТЕЛЬ две команды, которым
присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая –
увеличивает его в три раза. Запишите порядок команд в
программе получения из числа 3 числа 16, содержащей не
более 5 команд, указывая лишь номера команд.

16.

У исполнителя Отличник две команды, которым присвоены
номера:
1. прибавь 1
2. умножь на 5
Выполняя первую из них, Отличник прибавляет к числу на экране 1,
а выполняя вторую, умножает его на 5. Запишите порядок команд в
программе, которая из числа 2 получает число 101 и содержит не
более 5 команд. Указывайте лишь номера команд.

17.

Автомат получает на вход четырёхзначное десятичное
число, в котором все цифры нечётные. По этому числу
строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и
четвёртая цифры.
2. Полученные два числа записываются друг за другом в
порядке неубывания (без разделителей).
Пример. Исходное число: 7511. Суммы: 7 + 5 = 12; 1 + 1 =
2. Результат: 212.
Сколько существует чисел, в результате обработки
которых автомат выдаст число 616?

18.

Автомат получает на вход пятизначное число. По этому
числу строится новое число по следующим правилам.
1. Складываются отдельно первая, третья и пятая цифры, а
также вторая и четвёртая цифры.
2. Полученные два числа записываются друг за другом в
порядке неубывания без разделителей.
Пример. Исходное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 +
7 = 10. Результат: 1016.
Укажите наименьшее число, при обработке которого
автомат выдаёт результат 621.

19.

Автомат получает на вход четырёхзначное число. По этому
числу строится новое число по следующим правилам:
1. Складываются первая и вторая, а также третья и
четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в
порядке возрастания (без разделителей).
Пример. Исходное число: 2366. Суммы: 2 + 3 = 5; 6 + 6 =
12. Результат: 512.
Укажите наибольшее число, в результате обработки
которого автомат выдаст число 117.

20.

Автомат получает на вход четырёхзначное число (число не может
начинаться с нуля). По этому числу строится новое число по
следующим правилам.
1. Складываются отдельно первая и вторая, вторая и третья, третья и
четвёртая цифры заданного числа.
2. Наименьшая из полученных трёх сумм удаляется.
3. Оставшиеся две суммы записываются друг за другом в порядке
неубывания без разделителей.
Пример. Исходное число: 1982. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 2 =
10. Удаляется 10. Результат: 1017.
Укажите наибольшее число, при обработке которого автомат выдаёт
результат 1315.

21.

Автомат получает на вход четырёхзначное десятичное число, в
котором все цифры нечётные. По этому числу строится новое число
по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры.
2. Полученные два числа записываются друг за другом в порядке
неубывания (без разделителей).
Пример. Исходное число: 7511. Суммы: 7 + 5 = 12; 1 + 1 = 2.
Результат: 212.
Сколько существует чисел, в результате обработки которых автомат
выдаст число 414