Меню раздела

Алгоритм

Содержание

Что такое алгоритм

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

В своем нынешнем смысле слово алгоритм часто ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя (НОД) двух чисел.

Приведем современное описание алгоритма Евклида с использованием блок-схемы (см. “Способы записи алгоритмов”):

Стрелка “”, используемая при описании данного алгоритма, обозначает операцию замещения или присваивания (см. “Операторы языка программирования”). Разумеется, в книге Евклида “Начала” этот алгоритм сформулирован не совсем так (а записан совсем не так). В данном случае мы продемонстрировали современную формулировку этого алгоритма и одну из распространенных наглядных форм записи алгоритмов.

Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (см. “Исполнители алгоритмов”). Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя, а множество команд, которые исполнитель может выполнять, — систему команд исполнителя (СКИ).

Таким образом, алгоритм можно рассматривать как последовательность команд управления работой исполнителя (предписание исполнителю на выполнение последовательности действий).

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

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

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

2. Понятность — алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т.е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на выполнение “не размышляющего” исполнителя. Алгоритм составляется из команд, входящих в СКИ.

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

3. Детерминированность (определенность и однозначность). Каждая команда алгоритма определяет однозначное действие исполнителя, и должно быть однозначно определено, какая команда выполняется следующей. То есть если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат.

4. Результативность — исполнение алгоритма должно закончиться за конечное число шагов, и при этом должен быть получен результат решения задачи. В качестве одного из возможных результатов может быть и установление того факта, что задача решений не имеет.

Свойство результативности содержит в себе свойство конечности — завершение работы алгоритма за конечное число шагов.

5. Массовость — алгоритм пригоден для решения любой задачи из некоторого класса задач, т.е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма.

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

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

Обобщив вышесказанное, сформулируем следующее понятие алгоритма.

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

Приведенное определение не является определением в математическом смысле слова, т.е. это не формальное определение (формальное определение алгоритма см. в статье “Теория алгоритмов”).

Отметим, что для каждого исполнителя набор допустимых действий (СКИ) всегда ограничен — не может существовать исполнителя, для которого любое действие является допустимым. Перефразированное рассуждение И.Канта обосновывает сформулированное утверждение следующим образом: “Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднять. Но это противоречит допустимости действия «Поднять любой камень»”.

Интересно, что существуют задачи, которые человек, вообще говоря, умеет решать, не зная при этом алгоритм ее решения. Например, перед человеком лежат фотографии кошек и собак. Задача состоит в том, чтобы определить, кошка или собака изображена на конкретной фотографии. Человек решает эту задачу, но написать алгоритм решения этой задачи пока чрезвычайно сложно.

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

Методические рекомендации

Данная тема традиционно изучается в базовом курсе информатики основной школы. Содержание статьи “Алгоритм” может рассматриваться в качестве базового минимума информации по этой теме для учеников 8–9-х классов. В пропедевтическом курсе информатики (5–7-е классы) более актуальным является составление конкретных алгоритмов с использованием различных форм их записи, в том числе и для учебных исполнителей (см. “Исполнители алгоритмов”).

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

Пример. Задача “Звонок другу по телефону” подразделяется на следующие этапы (шаги):

1. Поднять телефонную трубку.

2. Если услышал гудок, то набрать номер друга, иначе конец решения задачи с отрицательным результатом (телефон неисправен).

3. Определить тип гудков: “вызов” или “занято”. Если “вызов”, перейти к шагу 4, если “занято”, перейти к шагу 6.

4. Дождаться 6 вызывающих гудков (конкретное число гудков в алгоритме для разных людей может быть различным).

5. Если за это время абонент не поднял трубку, то конец решения задачи с отрицательным результатом (абонент не отвечает). Иначе начать разговор (задача решена успешно).

6. Положить телефонную трубку; конец решения задачи с отрицательным результатом (абонент занят).

Последовательность шагов, приведенная в примере 1, является алгоритмом решения задачи “Звонок другу по телефону”. Исполнитель этого алгоритма — человек. Объекты алгоритма — телефон и телефонные сигналы.

При разборе алгоритма “Звонок другу по телефону” следует обратить внимание на п. 4 (“дождаться 6 вызывающих гудков”): без указания конкретного числа гудков нарушается сразу несколько свойств алгоритма (дискретность, определенность и результативность). Естественно, вместо числа 6 в алгоритме может стоять любое другое разумное число.

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

При изложении теоретического материала необходимо обратить внимание на то, почему приведенное определение алгоритма не является строгим математическим определением, а является только описанием понятия алгоритм, раскрывающим его сущность. Оно не является формальным потому, что в нем используются такие не уточняемые понятия, как “система правил”, “исходные данные”, и т.д.

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

Стоит отметить, что областью применимости данного конкретного алгоритма являются все наборы объектов, которые характеризуются теми же взаимоотношениями, что и Волк, Коза и Капуста. Например, Удав, Кролик и Морковка.

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

Важным при изучении данной темы является и понятие исполнителя. Причем оказывается, что гораздо проще построить алгоритм для программно-управляемого автомата (в том числе компьютера), чем для человека. Подробнее об этом рассказано в статье “Исполнители алгоритмов”. Для управления автоматом или компьютером можно придумать формальный язык описания алгоритмов. Такие языки называются “Языки программирования”, а сам алгоритм, записанный на таком языке, — программой.

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

В курсе информатики средней школы к понятию алгоритма можно вернуться в контексте изучения темы “Моделирование”. Ведь алгоритм можно рассматривать как информационную модель деятельности исполнителя.

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