ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

З.1 Понятие об алгоритмах и программах

Одним из фундаментальных понятий в информатике является понятие алгоритма.

Происхождение термина «алгоритм» связано с математикой. Эго слово происходит от Algorithmi - латинского написания имени Мухаммеда аль-Хорезми (787 - 850), выдающегося математика средневекового Востока. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами.

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

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

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

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

Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными?

В 1920-х задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы:

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

Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков - К. Гедель, К. Черч, С. Кличи, А. Тьюринг, Э. Пост, А. Марков, А. Колмогоров и многие другие.

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

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

Исследования Гёделя инициировали поиск и анализ различных формализаций понятия «алгоритм».

Первые фундаментальные работы но теории алгоритмов были опубликованы в середине 1930-х гг. Аланом Тьюрингом ^[1], Алоизом Черчем ’и Эмилем Постом Машина Тьюринга, машина Поста и класс рекур-

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

В 1950-х гг. существенный вклад в развитие теории алгоритмов внесли работы А.Н. Колмогорова и основанный на теории формальных грамматик алгоритмический формализм А.А. Маркова, который, используя термин «алгорифм» , ввел понятие нормального алгоритма.

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

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, используемых в формальных грамматиках Н. Хомского.^{[2] [3] [4] [5]}

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

• 1. Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
• 2. Определенность (детерминированность) - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвольных действий. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
• 3. Результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов.
• 4. Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

К перечисленным свойствам алгоритмов, предложенным Марковым, впоследствии добавили еще одно - формализованноегь.

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

На основании этих свойств иногда дается следующее определение алгоритма:

«Алгоритм - это последовательность математических, логических или вместе взятых операций, отличающихся детерменированно- стью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов».

В начальный период применения ЭВМ иногда требовалось, чтобы операции алгоритма были представлен на одном языке.

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

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

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

Алгоритмом также называется информационный процесс, обладающий следующими свойствами:

• • Наличие исполнителя преобразований (с его системой последовательности команд).
• • Разбиение всего процесса преобразования на отдельные команды (понятные исполнителю).
• • Определение начального состояния объекта (над которым производится преобразование) и его требуемого конечного состояния (цель преобразования).

Под исполнителем алгоритма понимается объект, который выполняет алгоритм. Исполнителем алгоритма может быть человек, компьютер и др.

Исполнителя характеризуют:

• 1) среда;
• 2) элементарные действия - результаты вызова команды;
• 3) система команд, для каждой из которых заданы условия применимости (в каких состояниях среды они могут быть выполнены) и описаны результаты выполнения;
• 4) отказы, возникающие, если команда вызывается при недопустимом для нее состоянии среды.

Среда исполнителя - условия, при которых возможно исполнение алгоритма.

Система команд исполнителя - эго перечень действий, которые способен правильно интерпретировать и выполнить исполнитель.

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

Создание алгоритма - процесс творческий. Долгое время считалось, что алгоритмы может формировать только человек.

Появление доступных ЭВМ привело в 1960—1970-х гг. к расширению исследований алгоритмов и вычислительных задач. Выделилось несколько разделов теории алгоритмов:

• • Классическая т еория алгоритмов.
• • Теория асимптотического анализа алгоритмов.
• • Теория практического анализа алгоритмов.
• • Методы создания 'эффективных алгоритмов.

Эти теории являются предметом специальных курсов для подготовки инженеров-профаммистов.

• [1] 2 Успенский В.А. Теорема Гёделя о неполноте / В.А. Успенский. - М.: Наука,1982.-112 с. " Мишины Тьюринга и рекурсивные функции: со. - М.: Мир, 1973. ' Черч Л. Введение в математическую логику / Л. Черч. - М.: Изд-во Ин. лит.,1960.-С. 66-80.
• [2] Яблонский С.В. Функции алгебры логики и классы Поста / С.В. Яблонский. - М.: Наука, 1966.
• [3] : Колмогоров А.Н. Теория информации и теория алгоритмов / А. Н. Колмогоров. — М.: Наука, 1987. — 304 с.
• [4] ' Марков А.А. Теория алгорифмов / А.А. Марков // Труды математическогоинститута АН СССР. - 1968. - № 38.
• [5] Хомский Н. Три модели для описания языка / Н. Хомский // Кибернетический сборник - М.: Изд.-во ИЛ, 1951. - Вып 2.