Тема 6. Алгоритмические основы информатики

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

Понятие алгоритма используется давно. Сам термин «алгоритм» произошел при переводе на европейские языки имени арабского математика IXв. Аль-Хорезми, которым были описаны правила (алгоритмы) выполнения основных арифметических действий в десятичной системе счисления.

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

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

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

По разновидности алгоритмы можно разделить на три крупных вида:

· вычислительные;

· информационные;

· управляющие.

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

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

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

1. Дискретность. Процесс решения задачи должен быть разбит на последовательности отдельных шагов, каждый из которых называется командой. Примером команд могут служить пункты инструкции, нажатие на одну из кнопок пульта управления, рисование графического примитива (линии, дуги и т.п.), оператор языка программирования. Наиболее существенным здесь является тот факт, что алгоритм есть последовательность четко выделенных пунктов – такие «прерывные» объекты в науке принято называть дискретными.

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

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

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

4. Результативность. Результат выполнения алгоритма должен быть обязательно получен, т.е. правильный алгоритм не может обрываться безрезультатно из-за какого-либо непреодолимого препятствия в ходе выполнения. Кроме того, любой алгоритм должен завершиться за конечное число шагов. Большинство алгоритмов данным требованиям удовлетворяют, но при наличии ошибок возможны нарушения результативности.

5. Корректность. Любой алгоритм создан для решения той или иной задачи, поэтому нам необходима уверенность, что это решение будет правильным для любых допустимых исходных данных. Указанное свойство алгоритма принято называть его корректностью. В связи с обсуждаемым свойством большое значение имеет тщательное тестирование алгоритма перед его использованием. При этом важно не столько количество проверенных сочетаний входных данных, сколько количество их типов. Например, можно сделать сколько угодно проверок для положительных значений аргумента алгоритма, но это никак не будет гарантировать корректную его работу в случае отрицательной величины аргумента.

6. Массовость. Алгоритм имеет смысл разрабатывать только в том случае, когда он будет применяться многократно для различных наборов исходных данных. Но массовость алгоритма в отдельных случаях может нарушаться: к числу подобных исключений можно отнести алгоритмы пользования некоторыми простыми автоматами (для них входными данными служит единственный тип монет).

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

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

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

Для более сжатого и наглядного описания алгоритма используется графическое описание.

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

Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.

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

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒