На этом шаге мы определим понятие "алгоритм".
Компьютерные науки (Computer Sciences) являются важнейшей составной частью информатики, понимаемой как наука об обработке информации. В широком смысле в понятие обработки информации входит ее кодирование (представление в некоторой стандартной форме), передача, преобразование с целью решения некоторой задачи, хранение, преобразование формы. Методы извлечения информации и ее использования относятся к смежным наукам: распознаванию образов, кибернетике и др.
Обрабатывать информацию можно различным образом. Человек, производя вычисления в уме или делая логические умозаключения, несомненно обрабатывает информацию. К сожалению, сегодня довольно плохо представляется то, как он это делает, хотя это очень важно. Дисциплина посвящена более простым вещам - изучению того, как обрабатывает информацию созданная человеком вычислительная машина, каковы пределы ее возможностей.
Здесь мы обсудим понятие решения задачи. С решением задачи с помощью компьютера связаны два термина: программа и алгоритм, довольно близкие по смыслу.
Под программой понимается информация конечного объема, которая, будучи введена в компьютер, приведет к решению им задачи за конечное время. Компьютер воспринимает эту информацию, если она закодирована (представлена) на машинном языке или если в компьютере есть другая программа (транслятор или интерпретатор), преобразующая информацию в машинный код. Различные типы компьютеров могут характеризоваться разными машинными языками. Для компьютеров классической, традиционной архитектуры программа представляется последовательностью команд или строкой текста на языке программирования высокого уровня.
Если есть программа и математическая модель реального компьютера, то можно провести полный анализ характеристик вычислительного процесса - времени работы программы для различных входных данных, требуемый объем памяти, доказать, что программа действительно решает поставленную задачу, а не некоторую другую (правильность программы), исследовать иные проблемы.
Однако анализ на основе программы имеет и свои недостатки. Во-первых, его результаты связаны и с задачей, и с конкретным типом компьютера. Влияние задачи и компьютера на результат трудно разделить. Результаты исследования оказываются непереносимы на другой тип компьютера и это значительно снижает их ценность. Во-вторых, предположение о наличии программы снимает наш первый вопрос о принципиальной возможности решения данной задачи на каком-либо компьютере, т. е. Не все интересующие нас вопросы можем сформулировать. В-третьих, анализ на основе программы зачастую избыточен: может интересовать ответ на простой вопрос или ответ с невысокой точностью, но вынуждены проводить подробный длительный анализ.
Прикладная математика постоянно сталкивается с такими проблемами при исследовании реальных объектов. И давно выработан метод их решения - абстракция. Необходимо абстрагироваться от несущественных деталей и тем самым значительно упростить задачу. Вряд ли кому придет в голову учитывать в математической модели компьютера, созданной для решения поставленных нами задач, его цвет или вес. Но часто можно считать одинаковой и длительность различных элементарных операций, например, сложения и умножения, считать, что память имеет потенциально неограниченный объем и т. п. Следуя по этому пути, можно выделить основные, наиболее существенные свойства программ и исполняющих их компьютеров, ввести соответствующие математические объекты и построить математическую теорию компьютерной обработки информации.
Алгоритм является математической абстракцией программы. Слово «алгоритм» происходит из Средней Азии. В VI в. до н.э. в низовьях Амударьи возникло государство Хорезм, просуществовавшее до 712 г. н. э. В этот год его завоевали арабы, позже оно вошло в состав Монгольской империи. В математике Хорезм известен тем, что там жил Абу-Джафар Мухаммед ибн Муса (787-ок.850 г.), написавший трактат «Китаб аль-джебр валь-мукабала» («Книга о восстановлении и противопоставлении»). Его работы были переведены на латинский язык в XII в. и оказали большое влияние на развитие математики в Западной Европе. Имя и работы Абу-Джафара Мухаммеда ибн Мусы аль-Хорезми (буквально: из Хорезма) внесли в математику два слова: «алгоритм» и «алгебра».
Как и все математические теории (геометрия, арифметика, математическая логика и др.), имеющие приложения, теория алгоритмов кроме точного (формального) определения основного объекта - алгоритма - включает и неформальное его определение, апеллирующее к интуиции, практическому опыту и к примерам из других областей математики.
С такого интуитивного определения и начнем. Математическая энциклопедия (М.: Советская энциклопедия, 1977) так определяет понятие алгоритма:
алгоритм - точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата.
Академик А.И.Мальцев (Алгоритмы и рекурсивные функции. М.: Наука, 1986) уточняет понятие процесса:
алгоритм - это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону из системы величин, имевшихся в предыдущий момент времени.
Профессор Стэнфордского университета Д.Кнут (Калифорния, США) в книге «Искусство программирования для ЭВМ» (Т. 1) отмечает, что современное значение слова «алгоритм» очень схоже со значением слов «рецепт», «процесс», «метод», «способ», «процедура», «программа», но имеет свой дополнительный смысловой оттенок. Это уточнение смысла может быть сформулировано как перечень некоторых свойств, которыми должен обладать любой алгоритм. Не все авторы используют для обозначения свойств одинаковые термины и дают равной длины перечни - на то и неформальное определение. Но в конечном итоге имеется общее понимание того, что является алгоритмом, а что не является.
Прежде всего отметим, что алгоритм - это предписание. Предписание должно быть задано (закодировано) в некоторой форме. Это может быть текст - строка символов в некотором алфавите, таблица, диаграмма, упорядоченный набор пиктограмм и т.д.
На следующем шаге мы рассмотрим основные свойства алгоритма.
