поддержка
проекта:
разместите на своей странице нашу кнопку!И мы
разместим на нашей странице Вашу кнопку или ссылку. Заявку прислать на
e-mail
код нашей кнопки:
Алгоритм
Содержание понятия "алгоритм" можно определить следующим образом.
Алгоритм - предписание, однозначно задающее процесс преобразования
исходной информации в виде последовательности элементарных дискретных
шагов, приводящих за конечное число их применений к результату.
Алгоритмы возникли вместе с появлением математики. Школьный курс
математики предлагает большой выбор алгоритмов:
алгоритмы сложения и умножения "столбиком", деления "углом", приведения
дробей к общему знаменателю, построения биссектрисы угла и т. д. В
высшей математике алгоритмов еще больше, причем наряду с численными
алгоритмами (решение дифференциальных уравнений, задач математического
программирования и др.) появляются алгоритмы над нечисловыми объектами (логическими
выражениями, последовательностями произвольных символов, графами и т.
п.).
Алгоритм - это точная инструкция, а инструкции встречаются практически
во всех областях человеческой деятельности. Возможны алгоритмы
проведения физического эксперимента, сборки шкафа или телевизора,
обработки детали. Однако не всякая инструкция есть алгоритм. Инструкция
становится алгоритмом только тогда, когда она удовлетворяет определенным
требованиям. Эти требования частично сформулированы в начале статьи,
хотя упомянутые в определении понятия однозначности и элементарности
сами нуждаются в уточнении. Алгоритм однозначен, если при применении к
одним и тем же данным он дает один и тот же результат. Но как по
описанию алгоритма определить, однозначен он или нет? В каком случае
шаги считаются элементарными?
Может возникнуть встречный вопрос: а так ли уж необходимо иметь точное
определение алгоритма? В конце концов, в течение более двух тысячелетий
люди создавали различные алгоритмы, не задумываясь над тем, что такое
алгоритм вообще. Ответ на этот вопрос связан с двумя аспектами:
теоретическим и практическим. С точки зрения самой математики желательно
иметь дело только с точно определенными понятиями. Это нужно, например,
для того, чтобы утверждать о некотором процессе, что он является
алгоритмом или не является таковым. Точное определение важно и тогда,
когда возникает желание доказать что-либо, относящееся к свойствам
алгоритмов или к их возможностям. Этот аспект проблемы отражен в статье
"Теория алгоритмов" .
Здесь же речь пойдет о практическом аспекте, связанном с понятием
алгоритма и с широким использованием этого понятия в программировании и
вычислительной технике. Ведь всякий алгоритм есть некоторая программа
действия, а машинные программы с этой точки зрения и есть точные
инструкции на выполнение некоторых процедур. Это наводит на мдлсль, что
программы - это записи некоторых алгоритмов, а программирование есть
процесс перевода записей алгоритмов на язык, понятный машине.
От программ мы ожидаем практической результативности. Вряд ли могут
представлять интерес программы, которые никогда не приводят к результату.
Поэтому и в практическом аспекте важно уточнить понятие алгоритма.
Возвратимся к тому словесному определению, которое было приведено в
начале статьи. Если используемые там на интуитивном уровне понятия
однозначности, элементарности и результативности попытаться определить
через какие-то другие понятия, то они, в свою очередь, также потребуют
уточнения. Получается замкнутый круг. Чтобы вырваться из него, можно
использовать следующий путь. Исходно задается лишь общая схема
определения алгоритма. А ее детализация производится с помощью
конкретного набора средств, которыми разрешается пользоваться в рамках
данной алгоритмической модели. Эти модели могут быть теоретическими (см.
Теория алгоритмов) и практическими. Последний тип моделей связан с
реализацией алгоритмов на ЭВМ.
Схема определения алгоритма в практической модели выглядит следующим
образом.
1. Всякий алгоритм применяется к исходным (входным) данным и выдает
результаты (выходные данные). Кроме того, в ходе работы алгоритма
появляются различные промежуточные данные. Поэтому должны быть указаны
виды данных, с которыми могут работать алгоритмы. Для описания данных,
во-первых, фиксируется набор элементарных символов (алфавит данных) и,
во-вторых, даются правила построения сложных данных из простых. Примеры
простых данных: целые и действительные числа, логические переменные,
символьные переменные. Примеры сложных данных: массивы чисел,
изображения на экране ЭВМ.
2. Данные для своего размещения требуют памяти. В ЭВМ память состоит из
одинаковых ячеек, каждая из которых может содержать один или несколько
символов алфавита данных. Таким образом, единицы объема данных и памяти
согласованы, и в прикладных алгоритмических моделях объем данных можно
измерять числом ячеек, в которых данные размещены.
3. Элементарные шаги алгоритма состоят из базовых действий, число
которых конечно. В прикладных алгоритмических моделях под действиями
можно подразумевать машинные команды, входящие в состав системы команд
ЭВМ. При записи алгоритмов на языках программирования более высокого
уровня, чем машинный язык, в качестве базовых действий могут выступать
операторы, входящие в состав синтаксиса данного языка программирования.
4. Последовательность шагов алгоритма должна быть однозначной. Не
допускается произвола при выборе очередного шага алгоритма. Обязательно
должны быть зафиксированы начальный и заключительный шаги алгоритма.
Все шаги, которые встречаются в алгоритме, можно разделить на условные и
безусловные. После безусловного действия либо выполняется действие,
расположенное вслед за ним в описании, либо однозначно указывается,
какой шаг надо выполнять. Условное действие связано с проверкой условия
и указывает два действия, которые могут последовать за ним: одно
выполняется, если условие соблюдено; другое - если не соблюдено.
Примером такого действия является команда условного перехода.
5. Точность записи алгоритма связана с использованием жесткого
синтаксиса. Любая синтаксическая вольность (скажем, замена запятой на
точку с запятой), любая ошибка в синтаксисе будут обнаружены и потребуют
исправления.
6. Всякая алгоритмическая модель предполагает некоторый механизм
исполнения алгоритмов, который обеспечивает доступ к ячейкам памяти, а
также имеет средства для выполнения всех элементарных действий и
управления процессом вычисления (т. е. пуском, остановкой и соблюдением
нужной последовательности действий). Физическая реализация этого
механизма (электронная, механическая или какая-либо другая) с
алгоритмической точки зрения несущественна, хотя, разумеется, от нее
зависят такие важные показатели, как скорость реализации алгоритма,
надежность и т. д. Речь идет лишь о функциональной схеме механизма. В
машинных моделях он описан непосредственно (машина и есть такой
механизм). Для языковой модели путь от описания к реализации лежит через
транслятор - специальную программу, которая перерабатывает текст на
алгоритмическом языке в последовательность машинных команд. В роли
исполнителя алгоритма может выступать и человек.
Как видим, для того чтобы набор инструкций можно было назвать
алгоритмом, он должен удовлетворять многим достаточно жестким
требованиям. Поэтому при описаниях алгоритмов, предназначенных для
передачи другому человеку (например, в научных публикациях или при
постановках задач), эти требования в полном объеме, как правило, не
соблюдаются. Последствия такого несоблюдения могут быть различными. В
одних случаях их выполнение связано лишь с некоторой рутинной работой,
требующей профессиональных навыков и времени. Такие описания
воспринимаются однозначно и в уточнениях нуждаются
только тогда, когда дело доходит до программирования. В других случаях
процесс уточнения может привести к полной переделке исходного текста.
Короче говоря, путь от полуалгоритмического описания, имеющего лишь
некоторые черты алгоритма, до настоящего алгоритма (который, как
правило, имеет вид программы) может быть трудным. Пройти его - задача
программиста. Однако, если в исходном описании есть неоднозначности,
программисту может потребоваться помощь автора предлагаемой процедуры.
Чтобы пояснить, о чем идет речь, рассмотрим простой пример.
Дано: последовательность чисел.
Требуется: найти в этой последовательности максимальное число.
Метод решения:
1. В некоторой памяти М запоминаем первое число.
2. Следующее число последовательности сравниваем с числом, лежащим в М.
Записываем в М большее из этих чисел (т. е. либо сохраняем в М прежнее
число - если оно больше, - либо записываем вместо него следующее).
3. Повторяем шаг 2 до конца данной последовательности.
Сразу же возникают вопросы, которые можно разделить на две группы (хотя
они и связаны).
Вопросы к постановке задачи:
а) Каково представление чисел, т. е. представлены ли они целыми числами,
десятичными дробями (действительными числами), простыми дробями или
арифметическими выражениями типа 2 + VT? Непосредственно можно
сравнивать только целые или действительные числа. Поэтому если в
исходной последовательности встречаются арифметические выражения (а
простые дроби - это тоже арифметические выражения, содержащие только
операцию деления), то их сравнению должно предшествовать их вычисление,
т. е. к предлагаемому алгоритму добавится еще ряд шагов.
б) Что значит "найти максимальное число" - просто дать его значение или,
кроме того, указать еще и его место в последовательности? Предлагаемый
метод решения дает только значение. Если нужно указывать место числа, то
числа последовательности нужно как-то нумеровать или именовать, а метод
решения изменить. Кроме того, как быть, если найдено несколько
одинаковых максимальных чисел - указывать все их места или, например,
первое по порядку?
Ответы на эти вопросы неоднозначны. Дать их может только тот, кто ставит
задачу. Предположим, что в нашем случае ответы таковы: числа - целые
и кроме значения результата нужно указать еще и номер первого по порядку
максимального числа, поэтому числа последовательности должны быть как-то
пронумерованы.
Вопросы к методу решения:
а) Как искать следующее число? В длинной последовательности это требует
аккуратности даже при ручной работе. Можно, например, зачеркивать или
как-то удалять уже просмотренные числа, и тогда следующее число - это
первое незачеркну-тое, а можно иметь некоторый указатель, работать
с числом, на которое он указывает, а потом передвинуть его на следующее
число. Поскольку уже решено, что числа последовательности будут
пронумерованы, то таким указателем может служить специальная переменная
- счетчик номеров, значение которой после каждого сравнения
увеличивается на единицу.
б) Как определить конец последовательности? Есть два стандартных способа:
либо при ее вводе указать количество ее элементов (чисел), либо ввести
дополнительный элемент - признак конца. Остановимся на первом варианте.
Теперь описанный выше процесс можно описать более точно. Для записи
чисел в память будем пользоваться обычным для языков программирования
оператором присвоения. Например, М: = х означает, что переменной Л/
присвоено значение переменной х; в терминах машинной памяти это значит,
что в ячейку памяти М записано содержимое ячейки х.
2. е: = п (в ячейке е лежит число элементов по- следовательности).
3. i: = 1 (счетчик номеров устанавливаем в начальное положение).
4. М: = р(\) (в М - первое число).
5..N: = 1 (ъ N - его номер).
6. i: - i + 1 (счетчик увеличивается на 1).
7. Если p(i) < М, то перейти к п. 10; иначе перейти к следующему шагу
(п. 8).
8. М: = p(i) (в М - новое число ).
9. N: = i (в N - его номер).
10. Если i < е,то перейти к п. 6; иначе - к следующему шагу.
11. Конец алгоритма.
Это описание уже близко к программе на языке программирования. Для
машинной реализации остается выбрать язык программирования, уточнить с
его помощью шаг 1 (он не элементарен и в разных языках будет уточнен
по-разному), вставить после шага 10 шаг, связанный с выводом результата
(на печать или экран), и записать алгоритм на выбранном языке, строго
соблюдая его синтаксис.
Алгоритм является фундаментальным понятием информатики. Можно выделить
три крупных класса алгоритмов: вычислительные, информационные и
управляющие. Вычислительные алгоритмы, как правило, работают со
сравнительно простыми видами данных (числа, матрицы), но сам процесс
вычисления может быть долгим и сложным. Информационные алгоритмы
представляют собой набор сравнительно простых процедур (например, поиск
числа или слова, удовлетворяющего определенным признакам), но работающих
с большими объемами информации. Таковы алгоритмы в различных базах
данных. Для того чтобы они работали эффективно, важно иметь хорошую
организацию данных. Например, чтобы в картотеке можно было быстро найти
нужные сведения, эти сведения нужно постоянно поддерживать в
определенном порядке (по разделам, внутри разделов по алфавиту и т. д.).
Управляющие алгоритмы характеризуются тем, что данные к ним поступают от
внешних процессов, которыми они управляют. Результаты работы этих
алгоритмов представляют собой различные управ-
ляющие воздействия. Поэтому значения данных в ходе работы управляющих
алгоритмов меняются (иногда очень быстро), и алгоритм должен вовремя
правильно отреагировать, т. е. выдать нужный управляющий сигнал в нужный
момент.
