АНАЛИЗ АЛГОРИТМОВ

Международные поисковые системы

Тематические каталоги

Это первый тип поисковых инструментов. Они представляют собой постоянно обновляющийся и пополняющийся иерархический (древовидный) каталог, на верхнем уровне которого собраны самые общие категории, такие как «бизнес», «наука», «искусство» и т.д., а элементы самого нижнего уровня представляют собой отдельные WWW-сервера с кратким описанием их содержимого. Гарантии того, что вы найдете все, что относится к данной теме, конечно, нет.

Примеры тематических каталогов:

Русскоязычные:

Созвездие Интернет http://www.stars.ru/

Россия - он - лайн http://www.online.ru/rmain/

Международные:

Yahoo http://www.yahoo.com/

Magellan http://www.mckinley.com/

Машины WEB-поиска (Search Engines)

Машинами WEB-поиска называются информационные системы, которые позволяют осуществлять поиск в WEB-пространстве.

К наиболее известным относятся Alta Vista, Excite, Hot-Bot, InfoseeK, Lycos, WebCrawler.

К русскоязычным относятся Яndex, Rambler, Апорт.

Основное преимущество этих систем - большая скорость поиска и поиск по ключевым словам.

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

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

www.altavista.digital.com

www.excite.com

www.hotbot.com

Русскоязычные поисковые системы

www.rambler.ru

aport.ru

yandex.ru

(Лекции 2000)

Санкт-Петербург

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

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

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

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

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

Заметим, что именно асимптотическая сложность определяет в итоге размерность задачи, которые можно решить этим алгоритмом.

Пример

Заметим, что асимптотическая сложность алгоритма характеризует и при изменении характеристик вычислительной установки. Пример, предположим, что достигнуто десятикратное ускорение скорости ЭВМ. Эффект этого ускорения может быть представлен как

Глава 1*. Модели вычислений.

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

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

- машина с произвольным доступом к памяти (РАМ);

- машина с произвольным доступом к памяти и хранимой программой(РАСП);

- машина Тьюринга (МТ);

- стековая машина (СТ).

Машина с произвольным доступом к памяти.

Машина с произвольным доступом к памяти (иначе, равнодоступная адресная машина (РАМ)) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.

РАМ состоит из входного и выходного файлов и памяти. Файлы трактуются как последовательные файлы. Память состоит из последовательности регистров r₀,r₁,…, каждый из которых способен хранить произвольное целое число. На число регистров, которые можно использовать, не установлено верхней границы. Такая идеализация допустима в случае когда

- объем данных задачи достаточно мал так, что все данные могут быть размещены в основной памяти вычислительной машины;

- целые числа, участвующие в вычислениях, достаточно малы так, что их можно помещать в одну ячейку.

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

Все вычисления производятся в регистре R₀, называемым сумматором. Каждая команда состоит из двух частей – кода операции и адреса. В принципе в систему команд можно добавить любые команды, встречающиеся в реальных вычислительных машинах, например, логические или команды сдвига; при этом порядок сложности задач не изменится.

Операнд команды может быть одного из следующих типов:

- =i означает само целое число i и называется литералом;

- i содержимое регистра i (i³0);

- _*i означает косвенную адресацию, т. е. Значение операнда определяет содержимое регистра j, где j – целое число, находящееся в регистре i, если j<0, машина останавливается.

Определим значение программы P с помощью двух объектов: отображение C:Z⁺È{0}®Z и “счетчика команд”, который определяет очередную выполняемую команду. Функция С есть отображение памяти, а именно, C(i) – целое число, содержащееся в регистре i (содержимое регистра i). Вначале C(i)=0 для любого i³0, счетчик команд установлен на первую команду в Р. После выполнения k-ой команды из Р, счетчик команд переходит на k+1 команду, если k-я команда не была командой перехода или останова. Чтобы описать действие команды, зададим значение V(a) операнда а:

V(=i)=i;

V(i)=C(i);

V(_*i)=C(C(i)).

Определим действия по каждой команде:

команда	действие
1. load a	C(0)¬V(a)
2. Store i	C(i)¬C(0)
Store *i	C(C(i))¬C(0)
3. Add a	C(0)¬C(0)+V(a)
4. Sub a	C(0)¬C(0)-V(a)
5. Mult a	C(0)¬C(0)*V(a)
6. Div a	C(0)¬C(0) div V(a)
7. Read i Read *i		В обоих случаях очередным становится следующий элемент входного файла
8 Write a	V(a) помещается в выходной файл
9. Jump b	Счетчик команд устанавливается на команду с меткой b
10. Jgtz b	Если C(0)>0, то счетчик команд устанавливается на команду с меткой b, в противном случае на следующую команду
11.Jzero b	Если C(0)=0, то счетчик команд устанавливается на команду с меткой b, в противном случае на следующую команду
12. Halt	Работа прекращается (останов).

Вообще говоря, РАМ-программа определяет отображение из множества, представленного во входном файле (исходные данные), в множество, полученное в выходном файле (результат работы РАМ-программы). Это отображение можно интерпретировать разными способами, наиболее важные интерпретация в виде функции из Zⁿ®Z и интерпретация в виде языка.

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

Другой способ интерпретировать программу для РАМ – это посмотреть на нее с точки зрения допускаемого ею языка. Алфавит – конечное множество символов, язык – множество цепочек (слов) алфавита. Символы алфавита можно представить целыми числами 1,2,…,k при некотором k. Пусть во входном файле находится цепочка S=a₁…a_n0, причем каждый символ представляет собой отдельный элемент файла. Входная цепочка S допускается РАМ-программой Р, если Р прочитывает все ее символы, выводит в выходной файл 1 и останавливается. Языком, допускаемым программой Р, называется множество всех цепочек (слов) допускаемых ею. Для входных цепочек, не принадлежащих языку, допускаемому программой Р, она может напечатать на выходной ленте символ, отличный от 1 и остановиться, а может даже и не остановиться вообще.

Из теории алгоритмов известно, что язык допускается некоторой РАМ- программой тогда и только тогда, когда он рекурсивен.

Пример 1.пусть xÎZ, nÎZ⁺È{0}, вычислить y=xⁿ.

Входной файл Выходной файл

n x ¾® P ¾® y

Р – построен на основе на бинарного метода возведения в степень, считыванием справа налево двоичных разрядов n.

Программа Р

Begin

Read r1 read (n);

Read r2 read (x);

Load =1

Store r3 y:=1;

Load r1

Jzero 1 while n<>0 do

2 Div 2 begin

Store r4 n1:=n div 2;

Add r4

Sub r1

Jzero 3 if odd(n)

Load r2 then

Mult r3

Store r3 y:=y*x;

3 Load r2

Mult r2

Store r2 x:=x*x;

Load r4

Store r1 n:=n1

Jgts 2 end;

1 Write r3 write(y)

Halt end {останов}.

Замечания. 1.В комментариях к командам использована нотация языка Паскаль.

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

3.Число умножений, необходимых для выполнения алгоритма Р равно ëlog₂nû+n(n), где n(n) – число единиц в двоичном представлении числа n.

4.В модели построенной на основе РАН никоим образом не отражается увеличение числа двоичных разрядов необходимых для хранение степеней целых чисел для больших n.

5.Предложенная модель не проливает свет на построение оптимального алгоритма вычисления xⁿ.

Пример

Вычисление y=x¹⁵ требует 7 умножений: .

Однако, y можно вычислить за 6 умножений: .

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

Вычислительная сложность РАМ-программ.

В терминах РАМ-программы можно дать более точные определения понятий временной и емкостной сложности:

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

Временная сложность в среднем – это среднее, взятое по всем входам размера n, тех же самых сумм.

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

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

Чтобы определить временную и емкостную сложности надо указать время необходимое для выполнения каждой РАМ-команды и объем памяти, используемый каждым регистром. Мы будем рассматривать два весовых критерия для наших программ. При равномерном весовом критерии каждая РАМ-команда затрачивает одну единицу времени и каждый регистр использует одну единицу памяти.

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

тогда логарифмические веса t(a) для всех трех возможных видов операндов а можно выразить следующим образом:

В общем виде веса для различных операндов команд выглядят так

Логарифмический весовой критерий основан на грубом допущении, что цена выполнения команды (ее вес) пропорционален длине ее операндов. Здесь учитывается, что для представления целого числа в регистре требуется ëlog₂nû+1 бит (регистры же, напомним, могут содержать произвольно большие целые числа).

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

Пример. В зависимости от выбранного весового критерия, рассмотренный пример y=xⁿ имеет следующие значения вычислительной сложности в худшем случае:

Замечания 1. Порядок роста сложности с логарифмическим весом здесь разумно интерпретировать как функцию двух целочисленных переменных x и n.

2. Логарифмическая емкостная сложность определяется длиной регистров r2 и r3, в которых может храниться максимальное значение xⁿ.

Упражнение. Выполнитеформальные вычисления для проверки предложенных в примере формул.

Модель с хранимой программой.

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

Будем считать, РАСП-программа находится в регистровой памяти. Каждая РАСП-команда занимает два последовательных регистра памяти. Первый регистр содержит код операции, второй – адрес. Если адрес имеет вид =i, то первый регистр будет содержать (в закодированном виде) указание на то, что операнд является литералом, а во втором регистре будет содержаться i.

Также как для РАМ-машины, состояние РАСМ-машины можно представить с помощью

1⁰ отображения памяти с, где c(i) – содержимое i-го регистра;

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

Вначале счетчик команд устанавливается на некоторый выделенный регистр. Обычно исходное содержимое регистров памяти не состоит из одних нулей, так как в память уже введена программа. Мы требуем, чтобы вначале все регистры, кроме конечного числа, содержали нули, на сумматоре также нуль. После выполнения каждой команды счетчик команд всегда увеличивается на 2, кроме случаев jump i, jgtz i (при положительном сумматоре) и jzero i (при нулевом сумматоре), когда он устанавливается на i. Действие каждой команды в точности то же, что и у соответствующей команды РАМ.

Временная сложность РАСМ-программы можно определить тем же способом, что и РАМ-программы. Здесь используется как равномерный весовой критерий, так и логарифмический. В последнем случае, однако, нужно приписать вес не только вычислению операнда, но и выбору самой команды.

Например,

Вес выполнения команды ADD =i, хранимой в регистрах j и j+1 равен l(j)+l(c(0))+l(i); вес выполнения команды ADD i, хранимой в регистрах j и j+1 равен l(j)+l(c(0))+l(i)+l(c(i)).

В монографии* приводятся доказательства следующих теорем:

Теорема1. Как при равномерном, так и при логарифмическом весе команд для любой РАМ-программы с временной сложностью T(n) существует такая постоянная k, что найдется эквивалентная РАСП-программа, временная сложность которой не превосходит kT(n).

Теорема 2. Как при равномерном, так и при логарифмическом весе команд для любой РАСМ-программы с временной сложностью T(n) существует такая постоянная k, что найдется эквивалентная РАМ-программа, временная сложность которой не превосходит kT(n).

Наряду с теоремами 1 и 2 можно доказать аналогичные теоремы, связывающие РАМ и РАСМ-программы по отношению к емкостной вычислительной сложности.

Простейшая модель вычислений: Машина Тьюринга.

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

Определение. Многоленточной машиной Тьюринга (МТ) называется семерка объектов:

МТ=<Q,T,I,d,b,q₀,q_f>, где

Q – конечное множество состояний управляющей головки;

T – конечное множество символов (алфавит) на лентах;

I – алфавит входной ленты IÍT;

b – пустой символ, bÎT\I;

q₀ – начальное состояние;

q_f – заключительное(или допускающее) состояние;

d – функция (частичная) перехода:

d:Q´T^k®Q´(T´{L,R,S})^k.

Машина Тьюринга может быть интерпретирована следующим образом:

Пусть d(q,a₁,a₂,…,a_k)=(q,(ad₁),(ad₂),,…,(ad_k)) и МТ находится в состоянии q, а ее головка на i-ой ленте обозревает символ а_i, 1£i£k. Тогда за один шаг (такт) эта машина Тьюринга переходит в состояние q,заменяет i-ой ленте символ а_i на aи сдвигает на этой же ленте головку в направлении d_k,1£i£k.

Определим понятие начальной конфигурации МТ – головка находится в состоянии q₀, на входной ленте – входная цепочка, на остальных лентах – пустые символы. На всех лентах головка смотрит на первую позицию.

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

Мгновенное описание (текущая конфигурация) k-ленточной машины Тьюринга определяется как набор (a₁,…,a_k), где a_i для каждого i представляет собой слово xa_ky, причем xy – слово, а q текущее состояние машины. Головка на i-ой ленте обозревает символ, стоящий справа от q.

Если мгновенное описание a переходит в мгновенное описание b за один шаг МТ, то пишут ab. Если a₁a₂…a_n, то пишут a₁a_n. Если a₁=a_n, либо a₁a_n, то пишутa₁a_n.

Можно рассматривать МТ как задающую вычислимую функцию (частичную) f:Zⁿ®Z. Числа кодируются на входной ленте в виде слов со специальным маркером #, отделяющим их друг от друга. Если МТ останавливается, имея на ленте выделенной в качестве выходной, целое число y (значение функции), то полагают f(x)=y.

Можно также определить понятие преобразователя.

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

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

Замечание. Наряду с определением машин Тьюринга, у которых функция перехода представляет собой однозначную частичную функцию, в теории рассматриваются машины Тьюринга с неоднозначными функциями перехода. Если функция перехода однозначна, машина Тьюринга называется детерминированной, в противном случае – недетерминированной. Функционирование недетерминированной машины определяется следующим образом. В случае если на некотором шаге МТ попадает в конфигурацию, для которой функция перехода определена неоднозначно, то считается, что, начиная с этого момента, запускаются все возможные варианты работы машины и если хотя бы один из них попадет в заключительную конфигурацию, то считается, что недетерминированная машина Тьюринга распознала входную цепочку.

Пример. Машина Тьюринга с двумя лентами распознающая “правильную структуру” арифметического выражения.

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

1. общее число во всей цепочке х открывающихся скобок совпадает с числом закрывающихся скобок в х.

2. в любом префиксе цепочки х количество открывающихся скобок не меньше числа закрывающихся.

Проверку этих двух условий обеспечивает следующая машина Тьюринга с двумя лентами:

Комментарий. Фактически предлагаемая машина Тьюринга на рабочей ленте в единичной системе считает разность между открывающимися и закрывающимися скобками. При этом первую открывающуюся скобку помечает символом Z₀, а остальные Z₁. Эти символы стираются с рабочей ленты при чтении закрывающихся скобок на входной ленте. МТ переходит в начальное состояние при стирании Z₀, которое обеспечивает переход в заключительное состояние при чтении на входной ленте символа _. Если в префиксе входной цепочки число закрывающихся скобок превысит числа открывающихся, то МТ “сломается” по попытке сдвинуться влево за начальный маркер рабочей ленты. Если входная цепочка представляет собой префикс правильной скобочной структуры, то предлагаемая машина Тьюринга попадет в конфигурацию, для которой функция перехода неопределенна (ситуация d(q₁, _, _)).

Заметим, что как временная вычислительная сложность, так и емкостная предложенной машины имеет порядок О(n), где n – длина входной цепочки.

Определение. Говорят, что неотрицательные функции f₁(n) и f₂(n) полиномиально связаны (почти эквивалентны), если найдутся такие полиномы p₁(x) и p₂(x), что для любого n справедливо неравенства f₁(n)£p₁(f₂(n)) и f₂(n)£p₂(f₁(n)).

Пример. f₁(n)=2n² и f₂(n)=n⁵ полиномиально связаны: можно взять p₁(x)=2x ибо 2n²£2n⁵ и p₂(x)=x³ ибо n£(2n²)³ для любого n.

Но n² и 2ⁿ не являются полиномиально связанными, так как нет такого полинома p(x) такого, что p(n²)³2ⁿ для любого n.

Теорема 1. При логарифмическом весе команд для любой РАМ-программы существует эквивалентная машина Тьюринга, временные (емкостная) сложность которой полиномиально связана с временной (емкостной) сложностью РАМ-программы.

Теорема 2. При равномерном, весе команд для любой РАМ-программы, несодержащей команд умножения, существует эквивалентная машина Тьюринга, временные (емкостная) сложность которой полиномиально связана с временной (емкостной) сложностью РАМ-программы.