- Алгоритм и его свойства. Исполнитель
- Способы записи алгоритмов
- Понятие сложности алгоритмов
- углубить представления о понятии « алгоритм», алгоритмизации, способах записи алгоритма (блок-схема, словесный и т. д.), исполнителе
- уметь определять результат выполнения алгоритма при заданных исходных данных, выполнять несложные алгоритмы для готового исполнителя пошагово
- знать свойства алгоритма
- иметь представление об оценке сложности алгоритма
- С какими словами у вас ассоциируется слово «алгоритм»?
- Существует ли связь между алгоритмом и исполнителем?
- Как вы думаете, являетесь ли вы исполнителем алгоритмов?
Алгоритм и его свойства. Исполнитель
Каждый из нас постоянно решает множество задач: как быстрее добраться на работу, как лучше спланировать дела текущего дня и многие другие. Некоторые задачи мы решаем автоматически, так как на протяжении многих лет привыкли к их выполнению, другие требуют длительного размышления над решением, но в любом случае решение каждой задачи делится на простые действия. Последовательность таких действий (команд) можно назвать алгоритмом.
Сегодня алгоритм тесно связан с компьютером и программированием, с него начинается написание любой программы.
Историческая справка
Слово «алгоритм» появилось задолго до появления компьютеров. Впервые данное определение мы можем встретить в трудах известного восточного учёного-математика аль-Хорезми, родоначальника науки алгебры. Аль-Хорезми обозначал словом алгоритм любую последовательность действий, приводящую к решению задачи. Попытки разработать формальное определение алгоритма привели к возникновению в 20–30 годах XX века теории алгоритмов. Дать определение алгоритма попытались такие учёные, как А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.
Разработка алгоритма зависит от того, для кого пишется алгоритм, кто будет его выполнять.
Субъект или устройство, правильно понимающий и исполняющий алгоритм, называется исполнителем алгоритма. Исполнители бывают формальные («неразмышляющие») и неформальные.
В отличие от неформального, формальный исполнитель строго следует алгоритму (инструкции) и одну и туже команду всегда выполняет одинаково.
Рис. 1. Типы исполнителей
Все команды алгоритма должны быть однозначно идентифицированы исполнителем. В алгоритме должны быть только такие команды, которые исполнитель в состоянии выполнить (любой исполнитель имеет свой набор команд). Некоторые исполнители привязаны к определённой среде, в рамках которой существуют.
Алгоритм — это точная, конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) результата.
Алгоритм состоит из команд. Команда — отдельная инструкция в описании алгоритма.
Чтобы разработать алгоритм для конкретного исполнителя, нужно знать, что дано (исходные данные) и что нужно найти (результат).
Рис. 2. Разработка алгоритма
Пример 1
Исполнитель «Счетовод» имеет набор из двух команд:
1. Прибавь 3;
2. Умножь на 4.
Напишите алгоритм, содержащий не более 4 команд, который получает число 27 из числа 3.
Решение
Давайте рассмотрим все варианты получения числа 27 из числа 3. Для этого нарисуем дерево всевозможных решений, начинающихся с цифры 3, слева от числа — команда «+1», справа — команда «*4».
Рис. 3. Пример 1
Из рис. 3 видно последовательность команд, приводящих к нужному решению, — это 1 (3 + 3 = 6), 2 (6 * 4 = 24), 1 (24 + 3 = 27).
Ответ: 121.
Упражнение 1
Определите исполнителей для следующих алгоритмов:
- уборка мусора во дворе;
- перевозка пассажиров в автобусе;
- расчёт заработной платы работника;
- приготовление еды в столовой.
Упражнение 2
Исполнитель «Счетовод» имеет набор из двух команд:
1. Прибавь 2;
2. Умножь на 3.
Напишите алгоритм для Счетовода, содержащий не более 5 команд, который получает число 35 из числа 5.
Чтобы некоторую последовательность команд можно было назвать алгоритмом, для неё должны выполняться следующие свойства.
Свойства алгоритмов
- Дискретность. Любой алгоритм должен состоять из конечной последовательности шагов (команд), выполнение которых происходит «друг за другом», т. е. только выполнив одно действие, можно приступать к другому.
- Детерминированность. Все команды алгоритма должны быть однозначными и всегда приводить к одному и тому же результату при одинаковом наборе входных данных.
- Понятность. Каждая команда в алгоритме должна быть однозначно расшифрована исполнителем.
- Результативность. Алгоритм должен за конечное число шагов приводить к верному результату. В частности результатом также является установление факта, что решения нет.
- Массовость. Для всех задач одного класса алгоритм должен давать правильный результат.
Пример 2
Мальчик Петя пришёл домой из школы и обнаружил сообщение от бабушки: «Открой холодильник, достань жёлтую кастрюлю, поставь суп в микроволновку, поешь суп». Будет ли данная последовательность действий алгоритмом?
Решение
В данной последовательности действий нарушено свойство детерминированности, т. к. в холодильнике может быть 2 жёлтые кастрюли. Не сказано, что делать с микроволновкой, какую программу выбрать и на сколько минут (свойство — результативность). Т. о. сообщение от бабушки не является алгоритмом.
Упражнение 3
Дополни сообщение бабушки так, чтобы оно стало алгоритмом.
Способы записи алгоритмов
Существует несколько способ записи алгоритмов.
- Словесный способ. Алгоритм записывается по шагам на естественном языке. Используется, например, в математике.
- Запись алгоритма псевдокодом. Псевдокод — это гибрид естественного языка и элементов языка программирования. Как правило, используется в учебных целях.
- Блок-схема. Представление алгоритма в виде графа с помощью стандартных блоков, соединённых линиями. Используется, если нужно добиться наглядности.
- Запись на языке программирования. Алгоритм, готовый к реализации, должен быть записан на языке, понятном исполнителю.
Понятие сложности алгоритма
Разработка алгоритма — творческое занятие. Для одной и той же задачи может существовать большое количество различных решений, а значит, и алгоритмов. Возникает вопрос, по какому принципу выбирать из множества решений лучшее для реализации алгоритма. Теория алгоритмов предоставляет аппарат для анализа алгоритмов, на основе которого можно выбрать наиболее эффективный из них.
Вычислительный процесс — это последовательность шагов алгоритма, пройденных при его исполнении.
Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе алгоритма.
Шаг алгоритма — это отдельное действие, выполняемое по команде исполнителем алгоритма.
Число операций при выполнении алгоритма зависит от количества обрабатываемых данных. Поэтому сложность алгоритма выражают в виде функции от объёма входящих данных:
- f(n) = O(1) — константная;
- f(n) = O(n) — линейная функция;
- f(n) = O(nm) — полиномиальная функция (квадратичная, кубическая и т. д.)
Эффективным является алгоритм, который выполняется за меньшее количество времени и занимает меньше памяти.
Пример 3
Вычислим сложность вычисления степени натурального числа xn.
Решение
Допустим, что в алгоритме используется цикл, в котором х умножается сам на себя n раз. В таком случае сложность выполнения алгоритма будет линейной — O(n), т. к. мы выполним n операций.
Ответ: O(n).
Итоги
Алгоритм — конечная последовательность команд, сформулированных на языке исполнителя, которая определяет переход от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности, массовости.
Исполнитель алгоритма — субъект или устройство, способное правильно понять все команды алгоритма и выполнить их.
Запись алгоритма может быть различной. Это блок-схема, естественный язык, псевдокод, язык программирования и т. д.
Алгоритм состоит из команд. Команда — отдельная инструкция в описании алгоритма. Шаг алгоритма — отдельное действие, которое исполнитель выполняет по команде.
Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе алгоритма.
Контрольные вопросы
- Что такое алгоритм?
- Перечислите свойства алгоритма.
- Приведите примеры алгоритмов из жизни.
- Для чего нужны различные способы записи алгоритмов?
- Что такое команда алгоритма?
- Какие бывают исполнители алгоритмов? Какие характеристики есть у исполнителей?
- Влияет ли набор исходных данных на результат выполнения алгоритма? Если влияет, то каким образом?
- Что такое сложность алгоритма? От чего она зависит?
Упражнение 1
Дворник; шофёр; бухгалтер; повар.
Упражнение 2
11121
Упражнение 3
Открой холодильник, достань жёлтую кастрюлю с супом ёмкостью 5 литров, налей суп в тарелку, поставь тарелку с супом в микроволновку, режим «разогреть» на 1 минуту, вынь тарелку с супом из микроволновки и поставь на стол, возьми ложку, поешь суп.
