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

описание алгоритма и выполнить содержащийся в нём перечень действий.

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

Исполнитель алгоритма
не размышляет над выполняемыми командами, а строго следует пошаговым инструкциям алгоритма
одну и ту же команду всегда выполняет одинаково
за действия формального исполнителя отвечает управ­ляющий им объект
в роли формального исполнителя чаще всего выступает техническое устройство

Неформальный исполнитель

Формальный исполнитель

исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата за конечное число шагов.

ПРИМЕРЫ АЛГОРИТМОВ

Закрыть входную дверь ключом

Нахождение n первых простых чисел (метод Эратосфена)

Построение перпендикуляра к прямой

ключ в замочную скважину.
Повернуть ключ два раза на 180 градусов против часовой стрелки.
Вынуть ключ из замочной скважины.

по методу Эратосфена»

Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
Присвоить переменной p значе­ние 2 (2 – первое простое число).
Зачеркнуть в списке числа, кратные p: 2p, 3p, 4p, …
Найти первое незачёркнутое число в списке, большее чем p, и прис­воить p соответствующее значение.
Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
Незачёркнутые числа и есть все простые числа от 2 до n.

Простые числа от 2 до 100

Выполнить

по методу Эратосфена»

Простые числа от 2 до 100

p = 2

p = 3

p = 5

p = 7

Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
Присвоить переменной p значе­ние 2 (2 – первое простое число).
Удалить из списка числа, кратные p: 2p, 3p, 4p, …
Найти первое число в списке, большее чем p, и прис­воить p соответствующее значение.
Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
Оставшиеся числа и есть все простые числа от 2 до n.

лежащую на прямой с помощью циркуля и линейки»

Выполнить

Провести окружность с центром в точке O и радиусом 1 см.
Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
Провести окружность с центром в точке A и радиусом равным AB.
Провести окружность с центром в точке В и радиусом равным AB.
Обозначить точки пересечения окружностей: верхнюю - C, нижнюю - D.
Провести прямую СD.

лежащую на прямой с помощью циркуля и линейки»

О

А

В

С

D

Провести окружность с центром в точке O и радиусом 1 см.
Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
Провести окружность с центром в точке A и радиусом равным AB.
Провести окружность с центром в точке В и радиусом равным AB.
Обозначить точки пересечения окружностей: верхнюю - C , нижнюю - D.
Провести прямую СD.

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

программирования

с помощью блок-схемы – стандартных графических объектов (геометрических фигур)

запись алгоритма с помощью формул, рисунков, таблиц

процессе этого алгоритма.

Лучшим среди них считается алгоритм, имеющий наименьшую сложность.

Эффективность
количество элементарных операций…
количество памяти…

объёма входных данных.
Задание. Оцените сложность алгоритмов:

Сложность алгоритма будет O(log2n).
Таким образом, в книге объёмом в 1000 страниц страница с нужной фамилией находится не больше, чем за O(log21000) ≈ 10 раз.

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

При линейном поиске – последовательной проверки всех книг подряд – сложность, в худшем случае, будет равна количеству книг, т.е. O(n) = 1000.

В старинной библиотеке в одном из 1000 томов, посвященных кладам и тайникам, спрятана книга-сейф. Надо найти ее.

в двоичной системе счисления.
Заменим каждую 1 парой букв КХ, а каждый 0 – буквой К.
Вычеркнем крайнюю левую пару КХ.
Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X – как операцию умножения результата на х. Вначале результат равен х.

К

К

Х

К

К

К

х2

х4

х5

х10

х20

х40

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

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

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

Решение:
Единственный способ разбить запись 1711 на два числа – это 17 и 11.
Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11.
Сумма значений двух последних цифр равна 17. Не трудно заметить, что 17 = 8 + 9 = 9 + 8. Других вариантов нет.
Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст ме́ньшее число.
Ответ: 298.

«столбиком» при условии, что одно из них состоит из n, а второе – из m десятичных цифр.

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

на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.

Графический способ решения: