В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 2

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

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

В связи с этим получила развитие проблематикаполучения “относительных” нижних оценок, так называемая теория NPполноты, связанная с труднорешаемостью переборных задач.Рассмотрим неформально, что именно в интуитивном понятии алгоритмануждается в уточнении.Основные требования к алгоритмам.1.

Каждый алгоритм имеет дело с данными - входными, промежуточными,выходными. Для того, чтобы уточнить понятие данных, фиксируется конечныйалфавит исходных символов ( цифры, буквы и т.п.) и указываются правилапостроения алгоритмических объектов. Типичным используемым средствомявляется индуктивное построение. Например, определение идентификатора вАЛГОЛЕ: идентификатор - это либо буква, либо идентификатор, к которомуприписана справа либо буква, либо цифра.

Слова конечной длины в конечныхалфавитах - наиболее обычный тип алгоритмических данных, а число символов вслове - естественная мера объема данных. Другой случай алгоритмическихобъектов - формулы. Примером могут служить формулы алгебры предикатов иалгебры высказываний. В этом случае не каждое слово в алфавите будетформулой.2. Алгоритм для размещения данных требует памяти. Память обычносчитается однородной и дискретной, т.е. она состоит из одинаковых ячеек,5причем каждая ячейка может содержать один символ данных, что позволяетсогласовать единицы измерения объема данных и памяти.3. Алгоритм состоит из отдельных элементарных шагов, причеммножество различных шагов, из которых составлен алгоритм, конечно.Типичный пример множества элементарных шагов - система команд ЭВМ.4.

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

Требование 1соответствует цифровой природе ЭВМ, требование 2 - памяти ЭВМ, требование3 - программе машины, требование 4 - ее логической природе, требования 5, 6 вычислительному устройству и его возможностям.Имеются также некоторые черты неформального понятия алгоритма,относительно которых не достигнуто окончательного соглашения. Эти чертысформулируем в виде вопросов и ответов.7.Следует ли фиксировать конечную границу для размера входных данных?8.Следует ли фиксировать конечную границу для числа элементарныхшагов ?9.Следует ли фиксировать конечную границу для размера памяти ?10.Следует ли ограничить число шагов вычисления ?На все эти вопросы далее принимается ответ “НЕТ”, хотя возможны идругие варианты ответов, поскольку у физически существующих ЭВМсоответствующие размеры ограничены.

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

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

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

Основной теоретической моделью этого типа являютсянормальные алгоритмы Маркова.Теория алгоритмов оказала существенное влияние на развитие ЭВМ ипрактику программирования. В теории алгоритмов были предугаданы основныеконцепции, заложенные в аппаратуру и языки программирования ЭВМ.Упоминаемые выше главные алгоритмические модели математическиэквивалентны; но на практике они существенно различаются сложностнымиэффектами, возникающими при реализации алгоритмов, и породили разныенаправления в программировании. Так, микропрограммирование строится наидеях машин Тьюринга, структурное программирование заимствовало своиконструкции из теории рекурсивных функций, языки символьной обработкиинформации ( РЕФАЛ, ПРОЛОГ ) берут начало от нормальных алгоритмовМаркова и систем Поста.Авторы обзора [17] основных достижений теории алгоритмов на стр.230пишут:“Алгоритмические концепции играют в процессе обучения и воспитаниясовременного человека фундаментальную роль, сравнимую лишь с рольюписьменности”.7§ 2 Машина Тьюринга и функции,вычислимые по Тьюрингу.10 )Опишем алгоритмическую модель, предложенную А.Тьюрингом в ЗО-хгодах и оказавшую влияние на разработку ЭВМ.Машина Тьюринга состоит из следующих элементов:1) Ленты , разбитой на ячейки и бесконечной в обе стороны .В каждой ячейкеможет быть записан один из символов конечного алфавита А ={ a 0 , a1 ,..., a m } ,называемого внешним алфавитом Условимся считать,что символ a0 являетсяпустым символом ( также обозначаемым λ ).2)Управляющего устройства ,которое может находиться в одном из конечногочисла внутренних состояний Q = { q0 , q1 ,..., qn }.

Число элементов в Qхарактеризует объем внутренней памяти машины. В множестве Q выделены дваспециальные состояния : q 0 и q 1 , называемые заключительным и начальнымсостояниями соответственно. Машина начинает работу в состоянии q1 ,попав всостояние q0 , машина всегда останавливается.З) Считывающей\пишущей головки, которая может перемещаться вдоль ленты ив каждый момент времени обозревает (считывает) одну из ячеек ленты.Функционирование машины Тьюринга осуществляется в дискретные моментывремени t=0,1,2,... и заключается в следующем.

В зависимости от внутреннегосостояния машины и считываемого символа на ленте машина Тьюринга:а) записывает в эту ячейку символ внешнего алфавита;б) сдвигает считывающую головку на один шаг влево или один шаг вправо илиоставляет ее на месте,в) переходит в новое внутреннее состояние.Таким образом, работа машины определяется системой команд видаqi a j (1)→ q k al dгдеqi- внутреннее состояние машины,aj- считываемый символ,qk- новоевнутреннее состояние a l - новый записываемый символ, d - направлениедвижения головки), обозначаемое одним из символов L (влево),R (вправо),E (наместe).Предполагается, что для каждой пары q i a j , где i=1..n , j=0..m имеетсяточно одна команда вида (1).

Множество этих команд называется программоймашины и, значит, в программе имеется n(m+1) команд.Работа машины заключается в изменении конфигураций. Конфигурацияпредставляет собой совокупность внутреннего состояния, состояния ленты (т.е.размещения букв внешнего алфавита по ячейкам или слова, записанного наленте), положения головки на ленте.8Предположим, что в начальный момент времени на ленте все ячейки,кроме конечного их числа, содержат пустой символ.