Главная | Обратная связь | Поможем написать вашу работу!

Элементы теории алгоритмов

Предварительное обсуждение.

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

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

Компьютерные науки (Computer Sciences) являются важнейшей составной частью информатики, понимаемой как наука об обработке информации. В широком смысле в понятие обработки информации входят ее кодирование (представление в некоторой стандартной форме), передача, преобразование с целью решения некоторой задачи, хранение, преобразование формы. Методы извлечения информации и ее использования относятся к смежным наукам: распознаванию образов, кибернетике и др.

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

Рассматриваются вопросы:

1. Можно ли решить данную задачу с помощью компьютера?

2. Как заставить компьютер решить данную задачу?

3. Как быстро компьютер может решить задачу?

4. Как можно ускорить процесс решения?

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

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

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

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

Алгоритм является математической абстракцией программы. Слово «алгоритм» происходит из Средней Азии. В VII-VI вв. до н.э. в низовьях Амударьи возникло государство Хорезм, просуществовавшее до 712 г. н.э. В этот год его завоевали арабы, позже оно вошло в состав Монгольской империи. В математике Хорезм известен тем, что там жил Абу-Джафар Мухаммед ибн Мусса (787- ок. 850 г.), написавший трактат «Книга о восстановлении и противопоставлении». Его книги были переведены на латинский язык и оказали большое влияние на развитие математики в Западной Европе. С его именем связывают появление слов: алгоритм и алгебра.

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

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

Профессор Стэндфордского университета Д. Кнут в книге «Искусство программирования» [11] утверждает, что современное значение слова алгоритм ассоциируется со словами «рецепт», «способ», «процедура», «программа», но имеет свой дополнительный смысловой оттенок. Это уточнение смысла может быть сформулировано как перечень некоторых свойств, которыми должен обладать любой алгоритм. Не все авторы используют для обозначения свойств одинаковые термины и дают равной длины перечни. Но существует общее понимание того, что является алгоритмом, а что не является.

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

1. Дискретность.

2. Элементарность шагов.

3. Детерминированность.

4. Конечность (финитность).

5. Массовость.

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

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

С алгоритмами, т.е. с эффективными процедурами, однозначно приводящими к результату, математика имела дело всегда. Школьные методы умножения столбиком и деления углом, метод исключения неизвестных при решении системы линейных уравнений, правила дифференцирования сложной функции-все это алгоритмы. Однако пока основными задачами математики были вычисления, потребность в исследовании понятия алгоритма не возникала. Во второй половине ХIХ века возникновение математики нечисловых объектов - неэвклидовых геометрий, абстрактных алгебраических теорий типа теории групп - стимулировали появление новых областей математики: основания математики или метаматематики. Главным математическим приложением теории алгоритмов явилось доказательство невозможности алгоритмического, т.е. точного и однозначного, решения некоторых математических проблем.

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

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

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

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

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

⇐ Предыдущая 19 20 21 22 23 242526 27 28 Следующая ⇒