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

«Алгоритм» является базовым основополагающим понятием информатики, а алгоритмизация и программирование – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, даётся множеством самых разнообразных определений – от «наивно-интуитивных» («алгоритм – это план решения задачи») до «строго формализованных» (нормальные алгоритмы Маркова). Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники.

Термин «алгоритм (алгорифм)» появился в Средние века, когда европейцы знакомились со способами выполнения арифметических действий в десятичной системе счисления по книге узбекского математика Абу Джафара Муххамада ибн Мусы аль-Хорезми (783–850 г.) «Арифметика индусскими цифрами», получившей широкую известность. Слово «алгоритм» есть результат европейского произношения слов «аль-Хорезми» («аль-Хорезми» – человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана).

Единого определения понятия алгоритма нет. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем алгоритмом стали называть точное предписание, определяющее порядок действий, обеспечивающий получение требуемого результата из исходных данных за конечное число шагов.

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

Алгоритм (по А. Н. Колмогорову) – это система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

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

Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин «вычислительный процесс» распространяется и на обработку других видов информации, например, символьной, графической или звуковой.

Алгоритм должен обладать следующими свойствами:

− дискретностью;

− массовостью;

− определённостью;

− результативностью;

− формальностью.

Дискретность (разрывность, раздельность). Каждый алгоритм состоит из отдельных законченных действий, т.е. делится на шаги.

Массовость – применимость алгоритма ко всем задачам некоторого класса, различающимся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

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

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

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

Исполнители алгоритмов

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

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

Наиболее используемые типы исполнителя алгоритмов – человек или автомат (компьютер).

Человек как исполнитель алгоритмов – совокупность исполняющих подсистем (мышечная, двигательная, зрительная, обонятельная и др.) и управляющей подсистемы (нервная, нейронная).

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

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

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

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

В непосредственную (сенсорную) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память (память сознания). Далее она пересылается в долговременную память с привлечением подсознания («укладывается на полочки» с соответствующими названиями «Формы поведения», «Объекты и образы», «Правила и процедуры обнаружения и идентификации объектов», «Правила выборки и организации информации», «Жизненный опыт», «Бытовые навыки и умения», «Профессиональные навыки и умения» и др.).

Пример. Увиденный человеком конкретный компьютер ассоциируется с абстрактным понятием «Компьютер» (из долговременной памяти) – например, со сведениями об этом устройстве – информационными кодами, которые определяют объект (связь, понятие). Коды связываются между собой, создавая образ конкретного компьютера.

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

Способы описания алгоритмов

В настоящее время используются следующие способы описания алгоритмов:

- словесно-формульное описание алгоритма;

- псевдокод;

- табличный способ;

- языки программирования (программа);

- графический способ (блок-схема).

Словесно-формульное описание алгоритма представляет структуру алгоритма и содержание выполняемых действий средствами естественного языка, представлено ниже в тестовых заданиях с решениями 9.1 ÷ 9.6. Достоинства этого способа: общедоступность, возможность описывать алгоритм с любой степенью детализации. Недостаток этого способа – многословность, низкая наглядность, громоздкость, возможна неоднозначность толкования.

Тестовое задание 9.1.

Чему равны значения переменных а и b после выполнения следующего фрагмента алгоритма:

1) а = 3;

2) b = 7;

3) b = a;

4) a = b;

5) b = b*2

Ответы:

1) a = 3; b = 6

2) a = 14; b = 7

3) a = 7; b = 14

4) a = 6; b = 3

5) a = 3; b = 14

Решение.

Выполняем алгоритм последовательно по шагам:

1) а = 3;

2) b = 7;

3) b = a; знак равенства «=» в этом случае трактуется как знак присваивания «=:», следовательно, переменной b присваивается значение переменной а=3; т.е. переменная b примет значение b=3;

4) a=b; переменной а присваивается значение переменной b=3; следовательно, переменная а примет значение а =3;

5) b=b*2; переменной b присваивается значение b*2 (к этому моментупеременная b имеет значение b=3); следовательно, переменная b примет значение b= b·2=3·2=6.

Таким образом, в результате выполнения алгоритма переменные а и b примут значения a = 3 b = 6.

Тестовое задание 9.2.

Какие результаты будут получены в результате выполнения фрагмента алгоритма в каждом из следующих случаев: 1) x = 3; 2) x = 1 (от y решение не зависит):

1) ввести координаты точки x и y;

2) если x ≥ 2, то вывод «точка находится в области В» иначе вывод «точка находится в области А»?

Ответы:

1-й случай:

1) точка находится в области В;

2) точка находится в области А;

2-й случай:

1) точка находится в области А

2) точка находится в области В

Решение.

Выполняем алгоритм последовательно по шагам:

1-й случай − x = 3:

1) вводим координаты точки x = 3;

2) x ≥ 2? Подставляя значение x = 3, имеем 3 ≥ 2? Ответ: да, следовательно, выполняется вывод «точка находится в области В»;

2-й случай − x = 1:

1) вводим координаты точки x = 1;

2) x ≥ 2? Подставляя значение x = 1, имеем 1 ≥ 2? Ответ: нет, следовательно, выполняется вывод «точка находится в области А»;

Можно проиллюстрировать условие задачи рисунком 9.1.

Рис. 9.1. Рисунок, иллюстрирующий условие задания 9.2

Замечание. Тот же алгоритм можно записать следующим образом:

1) Ввести координаты точки x и y;

2) eсли x ≥ 2, то вывод «точка находится в области В», перейти к 4);

3) вывод «точка находится в области А».

4) вычисления прекратить.

В этом варианте, если условие x ≥ 2 не выполняется, то выполнение алгоритма переходит к следующему шагу, т.е. к 3-му шагу.

Тестовое задание 9.3.

Какие результаты будут получены в результате выполнения следующего фрагмента алгоритма?

1) i = 1;

2) вывод i;

3) i = i + 1;

4) если i ≤ 4, то перейти к 2)

5) прекратить вычисления.

Ответы:

1) 1 2 3 4;

2) 1 2 3 4 5;

3) 2 3 4 5;

4) 1 3 5 7;

5)

Тестовое задание 9.4.

Сколько раз при выполнении предыдущего задания будет повторена последовательность шагов 2), 3) и 4)?

1) 4;

2) 2;

3) 3;

4) 1.

Решение тестовых заданий 9.3 и 9.4.

Выполняем алгоритм последовательно по шагам:

При этом последовательность шагов 2), 3) и 4) будет повторена 4 раза.

Тестовое задание 9.5.

Какие результаты будут получены в результате выполнения следующего фрагмента алгоритма:

1) а = 15;

2) b = 4;

3) если а < b, то перейти к 6);

4) а = а-b;

5) перейти к 3);

6) вывод а.

Будет вывод числа:

1) 3;

2) 11;

3) 7;

4) -2.

Тестовое задание 9.6.

Сколько раз при выполнении предыдущего задания будет повторена последовательность шагов 3), 4) и 5)?

1) 3;

2) 2;

3) 1;

4) 4.

Решение тестовых заданий 9.5 и 9.6.

Выполняем алгоритм последовательно по шагам:

При этом последовательность шагов 3), 4) и 5) будет повторена 3 раза.

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

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

При проектировании визуальных алгоритмов используют специальные графические символы.Результатом алгоритмизации решения задачи является блок-схема алгоритма, состоящая из некоторой последовательности графических блоков, связанных по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий. Блоки могут нумероваться. Порядковые номера проставляются слева в верхней части символов. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Для визуального представления алгоритмов обычно используют символы в соответствии с ГОСТ 19.701–90 «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения» [1]. Наиболее часто употребляемые символы представлены в таблице 14.

Таблица 14