авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования «ОРЕНБУРГСКИЙ ...»

-- [ Страница 2 ] --

а) Все рыбы, кроме акул, добры к детям;

б) Не все птицы могут летать;

в) Ты можешь обманывать кое-кого все время, ты можешь обманывать всех некоторое время, но ты не можешь обманывать всех все время;

г) Если кто- нибудь может сделать это, то и Джон может.

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

а) Пусть каждый из трех членов комитета голосует «за», нажимая кнопку.

Построить по возможности простую электрическую цепь, через которую ток проходил бы тогда и только тогда, когда не менее двух членов комитета голо суют «за»;

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

49 Выяснить, являются ли следующие рассуждения логически правиль ными. Для этого проверить, является ли заключение логическим следствием конъюнкции посылок.

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

б) Люди могут мыслить. Машины - не люди. Следовательно, машины не могут мыслить.

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

а) Если вечер скучен, то или Алиса начинает плакать, или Анатоль расс казывает смешные истории. Если Сильвестр приходит на вечер, то или вечер скучен, или Алиса начинает плакать. Если Анатоль рассказывает смешные ис тории, то Алиса не начинает плакать. Сильвестр приходит на вечер тогда и то лько тогда, когда Анатоль не рассказывает смешные истории. Если Алиса на чинает плакать, то Анатоль рассказывает смешные истории.

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

ЧАСТЬ 2 ТЕОРИЯ АЛГОРИТМОВ Введение Понятие алгоритма занимает одно из центральных мест в современной математике.

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

Слово «алгоритм» происходит, по мнению многих, от имени узбекского математика ал – Хорезми, который в IX веке разработал правила четырех ари фметических действий над числами в десятичной системе счисления. С другой стороны, вычислительные процессы, с помощью которых искомые величины определялись из известных величин по заданным правилам, стали возникать в математике на самых ранних ступенях ее развития (Древний Египет, Вавилон, Древняя Греция). В книге Евклида «Начала» (около 300 г до н. э.) имеется алго ритм нахождения наибольшего общего делителя двух чисел, который, не иск лючено, был известен и ранее. Представим его в виде рекурсивной процедуры.

Вход: неотрицательные целые числа а, b (аb).

Выход: НОД (а,b).

Евклид (а, b) 1 если b= 2 то НОД а 3 иначе НОД Евклид (b, а mod b) Реализация: Евклид (30,21) = Евклид (21,9) = Евклид (9,3) = Евклид (3,0)=3;

НОД (3,21)=3.

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

Отметим несколько общих свойств алгоритмов.

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

2) Единицы объема данных и памяти ЭВМ должны быть согласованы. В прикладных алгоритмических моделях объем данных можно измерять числом ячеек памяти, в которых данные размещены. При этом исходят из того, что па мять ЭВМ состоит из одинаковых ячеек, каждая из которых может содержать один или несколько символов алфавита данных.

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

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

5) Если способ получения результата на каком-либо шаге неприменим, то должно быть указано, что считать результатом выполнения алгоритма.

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

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

6) Начальная система величин может выбираться из некоторого потенци ально бесконечного множества, что должно являть массовость алгоритма.

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

Имеется три крупных класса алгоритмов: вычислительные (работают с числа ми, числовыми матрицами и другими числовыми структурами);

информацион ные (работают с большими объемами данных – базами данных – решают задачи поиска, записи, сортировки записей);

управляющие (формируют управленчес кие воздействия на внешние процессы в соответствии с поступающей от них информацией).

Еще следует сказать о детерминированности и корректности алгоритма.

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

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

Приведенное толкование понятия «алгоритм» называется интуитивным.

Оно хотя и нестрогое, но практически не требовало уточнения до двадцатых годов ХХ века, когда возникли так называемые массовые проблемы. Массовая проблема – проблема, когда требуется найти единый метод для бесконечной серии однотипных задач. Пример: построить алгоритм для выяснения имеются ли целые корни у уравнения Р(х1,…,хm)=0, где Р (х1,…,хm)- произвольный мно гочлен с целыми коэффициентами от любого числа m переменных. Задача точ ного определения алгоритма стала одной из центральных математических про блем. Возникла теория алгоритмов, изучаются общие свойства алгоритмов.

В 1936 году А. Черч опубликовал первое уточнение вычислимой функ ции, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма в тер минах идеализированных вычислительных машин. В дальнейшем А.А. Марков предложил ввести понятие «нормального алгоритма». В рамках этих уточнений упомянутая ранее алгоритмическая проблема, известная как 10-я проблема Ги льберта, оказалась неразрешимой.

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

Приложения теории алгоритмов имеются во всех областях математики.

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

1 Вычислимые функции 1.1 Понятие вычислимой функции. График вычислимой функции Вычислимые функции (ВФ) – одно из основных понятий теории алгори тмов. Функция f называется вычислимой, если существует алгоритм, перераба тывающий всякий объект х, для которого определена функция f, в объект f(х) и не приводящий к результату ни для какого х, для которого f не определена /3/.

Графиком ВФ называется множество пар вида (х, f(х)).

Примеры 1 х – любое натуральное число, f(х)=х2;

2 х – пара рациональных чисел х1, х2, f(х)=х1:х2 (эта функция определена лишь для тех х, у которых х20);

3 X – пара матриц X1, X2 с целочисленными элементами, f(X)=X1*X (эта функция определена лишь для тех X, у которых число столбцов в X1 равно числу строк в X2) Аргументами и значениями вычислимых функций могут быть лишь конс труктивные объекты, так как только такими объектами могут манипулировать алгоритмы.

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

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

1.2 Разрешимые и перечислимые множества Областью применимости алгоритма называется совокупность тех объек тов, к которым он применим, то есть дает результат.

Про алгоритм А говорят, что он:

- «вычисляет функцию f», если его область применимости совпадает с областью определения f, и А перерабатывает любой х из своей области приме нимости в f(х);

- «разрешает множество М относительно множества Х», если он приме ним к любому х из Х и перерабатывает любой х из ХМ в слово «да», а любой х из Х\М – в слово «нет»;

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

Множество называется разрешимым относительно Х, если существует ра зрешающий его относительно Х алгоритм. Множество называется перечисли мым, если либо оно пусто, либо существует перечисляющий его алгоритм.

Обнаружены результаты (путем анализа понятия «алгоритм»):

- область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

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

Теорема 1 Функция f вычислима тогда и только тогда, когда перечислим ее график.

Теорема 2 Подмножество М перечислимого множества Х тогда и только тогда разрешимо относительно Х, когда М и Х\М перечислимы.

Теорема 3 Если Р, Q перечислимы, то Р Q, Р Q также перечислимы.

Теорема 4 В каждом бесконечном перечислимом множестве Х существу ет перечислимое подмножество с неперечислимым дополнением. (В силу тео ремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5 Для каждого бесконечного перечислимого множества Х суще ствует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.

Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой об ластью применимости.

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

2 Формальная теория вычислимости 2.1 Рекурсивные функции.

Рекурсивные функции (РФ) – один из наиболее распространенных вариа нтов математического уточнения понятия вычислимой арифметической функ ции, то есть вычислимой функции, аргументы и значения которой – натураль ные числа /4/. РФ являются частичными функциями, то есть функциями, не обязательно всюду определенными. В связи с этим используют термин частич но рекурсивные функции как синоним РФ. РФ, определенные всюду на N, на зываются общерекурсивными. (N – множество всех натуральных чисел).

2.1.1 Операции над числовыми функциями Здесь под числами понимаются натуральные числа или ноль. Обозначим эту совокупность через N={0, 1, 2,...}. Пустое множество обозначается. Час тичные функции из N…N=N(k) в N называются k - местными числовыми фу нкциями. Операции над числовыми функциями называются операторами.

Определение Пусть f1,...,fn - частичные функции переменных x1,...,xm, определенные на множестве A со значениями в множестве B, f - частичная фу нкция n переменных, определенная на множестве B, со значениями в множест ве C. Тогда говорят, что частичная функция g m переменных, определенная на множестве A со значениями в множестве C равенством g(x1,...,xm) = f(f1(x1,...,xm),...,fn(x1,...,xm)), получается операцией суперпозиции из функций f, f1, …, fn. Обозначение операции суперпозиции: Sn+1 (индекс вверху означает чи сло функций).

Определение Числовые функции s1(x)=x+1, оn(x1,…,xn)=0, Inm(x1,…,xn)=xm (1mn, n=1,2,…) называются простейшими. (Индекс 1 иногда будем опускать).

Пример - I23(I12, I13, I22) = I13.

Определение Пусть заданы числовые частичные функции: g - n -местная, h - (n+2) - местная, f - (n+1) - местная, причем f(x1,…,xn,0)=g(x1,…,xn);

(2.1) f(x1,…,xn,y+1)=h(x1,…,xn,y, f(x1,…,xn,y)) Тогда говорят, что функция f возникает из g и h примитивной рекурсией.

Для n=0 (2.1) принимает вид:

f(0)=a - константа;

f(x+1)=h(x, f(x)). (2.2) Равенства (2.1) или (2.2) позволяют последовательно вычислять значения функции в точках y=0, 1, 2,... по значениям функций g и h.

Обозначение операции рекурсии:

f = R(g, h), (2.3) где операция R - двуместная операция, определенная на множестве F всех час тичных функций. Если g, h определены всюду, то f определена всюду.

2.1.2 Примитивно рекурсивные функции Определение Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s,o, Imn конечным числом операций суперпозиции и примитивной рекурсии.

Примечания 1 Операции суперпозиции и примитивной рекурсии, будучи приме ненными к всюду определенным функциям, дают в результате всюду опреде ленные функции. Поэтому примитивно рекурсивные функции всюду опреде лены, а примитивно рекурсивные относительно G определены всюду, если фу нкции из G всюду определены.

2 Операции суперпозиции и примитивной рекурсии, примененные к час тичным примитивно рекурсивным относительно G функциям дают в результа те примитивно рекурсивные относительно G функции.

Примеры 1 Функции s(x)=s1(x)=x+1, o(x)=o1(x)=0, Imn(x1,…,xn)=xm (m,n=1,2,…) при митивно рекурсивны по определению.

2 Функция on(x1,…,xn)=0 примитивно рекурсивна.

3 Произвольная n-местная постоянная функция допускает представление в виде терма s(s(…s(on(x1,…,xn))…))=a.

4Двуместные функции x+y, xy, xy являются примитивно рекурсивными, как удовлетворяющие схемам соответственно:

1) x+0=x=I'1(x), x+(y+1)=(x+y)+1=S(x+y) с начальными примитивно реку рсивными функциями g(x)=I'1(x), h(x, y, z)=z+1;

2) x0=0(x), x(y+1)=xy+x с функциями g(x)=o(x), h(x, y, z)=z+x;

3) x0=1, xy+1=xyx, т.е. g(x)=1, h(x, y, z)=zx;

0, x = 0, 1, x = 0, ( sg x = 1 sgx) удовлетво 4) функции sg ( x) = sg (x) = 1, x 0, 0, x 0.

sg 0 = 0, sg ( x + 1) = 1, ряют примитивно рекурсивным схемам и sg 0 = 1, sg ( x + 1) = 0, т.е. примитивно рекурсивны.

x y, x y, 5) Усеченная разность x y = (всюду определенная) являет & 0, x y ся примитивно рекурсивной. Действительно, функция x1 удовлетворяет при митивно рекурсивной схеме 0 1 = 0 (x + 1) 1 = x с примитивно рекурсив ными начальными функциями o1 и I12. Кроме того, для любых x, y имеем схе му x0 = x, x(y + 1) = (x y) 1, т.е. x y возникает примитивной рекурсией из I11 и h(x, y, z)=z1, что требовалось.

6) Из примитивной рекурсивности функций “+” и “– “следует примитив ная рекурсивность функции / x-y /=(xy)+(yx).

2.1.3 Нумерация n-ок чисел Определение Канторовское расположение двоек (пар) (x,y) чисел из N имеет вид (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3),... (2.4) 1 2 3 4 5 6 7… (пары расположены по возрастанию суммы элементов, а в сумме - по возрас танию первого элемента).

Функции n=c(x,y), x= l(n), y=r(n), где n-номер пары (x,y), называются кан торовскими нумерационными функциями.

Лемма 1 Канторовские нумерационные функции являются примитивно рекурсивными.

Лемма 2 Функция Геделя /1/ Г(x,y)=rest(l(x),1+(y+1)r(x)) примитивно ре курсивна.

Канторовское расположение n-ок чисел из N определяется равенствами:

c 3 ( x1, x2, x3 ) = c(c( x1, x2 ), x3 );

c n+1 ( x1,..., xn +1 ) = c n (c( x1, x2 ), x3,..., xn +1 ).

Число c n ( x1,..., x n ) называется канторовским номером n-ки ( x1,..., x n ).

2.1.4 Операция минимизации. Частично рекурсивные функции Пусть f - n-местная частичная числовая функция, и известен механизм ее вычисления (в интуитивном смысле), причем механизм работает бесконечно тогда и только тогда, когда значение функции не определено.

Рассмотрим относительно y уравнение f(x1,...,xn-1,y)=xn Будем давать пе ременной y значения 0,1,2,... последовательно и вычислять значения функции f соответственно (при фиксированных x1,...,xn). Определим частичную функцию Mf аргументов x1,...,xn следующим образом. Положим ее значение y=a, если выполнены условия:

1) значение f(x1,...,xn-1,y) определено для y=0,1,...,a-1, и f(x1,...,xn-1,y)xn ;

2) f(x1,...,xn-1,a)=xn.

Если для набора (x1,...,xn) числа a, удовлетворяющего указанным услови ям, не существует, значение y будем считать неопределенным.

Определение Оператор M, переводящий функцию f в функцию Mf, назы вается оператором минимизации. Если заданная функция f одноместна то фу нкция Mf называется обратной функцией для f и обозначается f-1.

Примеры 1 Для функций sg и s обратными будут функции x, x = 0, 1 x 1, x sg 1 x = ;

s 1 ( x) =.

не существует, x 1 не существует, x = 2 Рассмотрим функцию y+z. Составим уравнение y+z=x и будем давать переменной z значение 0,1,.... Получим частичную функцию x-y, определен ную для xy;

Определение Частичная функция f называется частично рекурсивной, ес ли она может быть получена из простейших функций o, s, Imn конечным числом операций суперпозиции, примитивной рекурсии и минимизации.

Примечание - Класс частично рекурсивных функций шире класса прими тивно рекурсивных. (Хотя бы потому, что примитивно рекурсивные функции всюду определены, а среди частично рекурсивных встречаются неопределен ные всюду).

2.1.5 Тезис Черча Значение понятия частично рекурсивной функции состоит в следующем.

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

ТЕЗИС ЧЕРЧА Класс алгоритмически (или машинно) вычислимых час тичных числовых функций совпадает с классом всех частично рекурсивных функций.

2.1.6 Общерекурсивные функции Определение Операция Ml, определяемая соотношением Mf, если Mf определена всюду, Ml f = не определена, в противном случае, называется слабой минимизацией функции f.

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

Примечание - Общерекурсивные функции всюду определены.

Теорема Все общерекурсивные функции являются всюду определенными частично рекурсивными функциями.

Доказательство следует из определения слабой минимизации.

Теорема Каждая всюду определенная частично рекурсивная функция общерекурсивна.

Доказательство этой теоремы очень тонкое и здесь не приводится.

Лемма 1 Каждая примитивно рекурсивная функция является общерекур сивной.

Доказательство следует из определения общерекурсивной функции.

Лемма 2 Класс общерекурсивных функций шире класса примитивно ре курсивных функций.

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

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

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

1 ) Внешняя память – конечная лента, разбитая на конечное число ячеек.

aj1 aj2 … ajk … … ajr qi Рисунок 2. В процессе работы машины к существующим ячейкам машина может пристраивать новые ячейки, так что лента может считаться потенциально нео граниченной в обе стороны. Каждая ячейка ленты может находиться в одном из конечного множества состояний. Совокупность их называется внешним алфа витом А={а0,а1,…,аm}. Пустые состояния обозначаются а0. В процессе работы машины ячейки ленты могут изменять свои состояния. Просмотр ленты осуще ствляется слева направо. В каждый такт времени лента имеет некоторую длину r, то есть r ячеек. Состояние ленты описывается словом aj1 aj2 … ajk …ajr, где aj – состояние первой слева ячейки, aj2 – второй и т.д. Пустые символы слева и справа можно опускать.

2) Внутренняя память машины – устройство, о котором известно, что в каждый такт времени оно находится в некотором состоянии. Алфавит внутрен них состояний, или внутренний алфавит Q = q0,q1,…,qn, где q0 – стоп-символ, или символ заключительного состояния, q1, как правило, - символ начального состояния.

3) Указатель – устройство, которое может перемещаться вдоль ленты так, что в каждый такт времени оно указывает на определенную ячейку ленты.

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

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

Состоянием машины Тьюринга, или конфигурацией, называется слово aj aj2 … qi ajk …ajr, образованное вставкой символа внутреннего состояния перед символом обозреваемой ячейки в слове состояния ленты. Это слово конфигура ции называется машинным словом.

Работа машины состоит в том, что из данного состояния по истечении та кта времени она переходит в следующее состояние и так далее. При этом, если машина, имея внутреннее состояние qi и воспринимая ячейку в состоянии aj, переводит внутреннюю память в состояние qs, изменяет aj на аt и передвигает указатель, то говорят, что машина выполняет команду qiaj qsаt D, где D – один из символов: L – сдвиг влево, R – сдвиг вправо, Е – нет сдвига. Совокупность всех команд, которые может выполнять машина, называется ее программой.

Предполагается, что для каждой пары qi aj имеется не более одной команды.

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

Пример - Пусть А = 0,1, Q = q0, q1, q2, программа Р = q10 q20 R, q20 q01Е, q11 q11 R, q21 q21R, начальное слово µ0 = q111. Тогда, приме няя символ перехода состояний =, имеем: q11= 1 q11= 11 q10= 110 q20= q01. Обозначая заключительное слово через µ и символ перехода с произволь ным числом тактов, можно записать: µ0 P µ. Если за конечное число ша гов внутреннее состояние переходит в q0, то говорят, что машина Тьюринга применима к данному слову. В противном случае машина Тьюринга называется «работающей вечно», или неприменимой к данному слову. В частности, возмо жно зацикливание или отсутствие подходящей команды. Существует много модификаций машин Тьюринга, в том числе, многоленточные МТ, имеющие по одному или несколько указателей на каждой из лент. Есть основания считать, что уточнение общего представления об алгоритме в алфавите, произведенное с помощью МТ, является адекватным. В теории алгоритмов известно следующее соглашение.

ТЕЗИС ТЬЮРИНГА Для всякого алгоритма А в каком- либо алфавите может построен тьюринговый алгоритм, дающий при одинаковых исходных данных те же результаты, что и алгоритм А.

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

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

Нормальные алгоритмы оперируют со словами конечной длины, преобра зуя их друг в друга с помощью подстановок, то есть замены одних частей слова на другие. Любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы – упорядоченного конечного списка подста новок типа UV (U заменяется на V), где U, V – слова в алфавите А. Заключи тельная подстановка записывается в виде U • V.

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

Пример - Дан алфавит русского языка и схема S = я у, л у, с м, в б, р m, m•р, о х, н а. Тогда, имея слово «слон», можно получить слово «муха». (Проверьте!) В теории алгоритмов строго доказано, что по своим возможностям пре образования нормальных алгоритмов эквивалентны частичным рекурсивным функциям и машинам Тьюринга. Соглашение о том, что для всякого алгоритма А в каком – либо алфавите может быть построен нормальный алгоритм, носит название принципа нормализации. Этот принцип равносилен тезису Черча и тезису Тьюринга.

2.4 Алгоритмические проблемы Алгоритмическая проблема (АП) – проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии однотипных единич ных задач.

Примеры 1 Найти алгоритм для выяснения, имеются ли целые корни у данного ал гебраического уравнения а0 xn + a1 x n-1 +…+ a n = 0, где а0, a1,…, a n - целые чис ла. Искомый алгоритм существует и основан на факте, что, если такое уравне ние имеет целый корень p, то p должно быть делителем числа a n, и для данного уравнения можно найти все делители числа a n, и все их по очереди проверить.

Эта задача алгоритмически разрешима.

2 Аналогичная проблема для для уравнения P(x 1,…, x m) = 0, где P(x,…, x m ) – произвольный многочлен с целыми коэффициентами от любого чис ла m неизвестных (10 – я проблема Гильберта) неразрешима.

Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), который её решает.

Неразрешимой является «проблема остановки»: по описанию алгоритма A и аргументу x выяснить, остановится ли алгоритм, если исходные данные – x.

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

Теорема Райса Никакое нетривиальное свойство вычислимых функций не является разрешимым.

Смысл этой теоремы: какое бы свойство вычислимых функций ни взять (периодичность, ограниченность, равенство другой, наперёд заданной функции и т. д.), нельзя построить общий алгоритм, например, машину Тьюринга, кото рый по произвольному алгоритму A определял бы, обладает вычисляемая им функция fA этим свойством или нет.

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

Требуется построить алгоритм, вычисляющий функцию f(n) = n(n)+1, если ал горитм применим к числу n, и f(n)=0 в противном случае. Эта проблема нераз решима. Действительно, если такой алгоритм Ak существует, то должно быть f(k)=k(k) и f(k)=k(k)+1, что невозможно.

3 Сложность алгоритмов 3.1 Характеристики сложности вычислений Сложность алгоритма (СА) – величина, характеризующая длину описания или громоздкость процессов его применения к исходным данным /8/.

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

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

Развивается аксиоматический подход к оценке сложности алгоритмов и вычис лений.

Оценивая сложность различных алгоритмов, следует исходить из некото рой модели исполнителя. Здесь используется модель 1RAM – однопроцессор ная машина с равнодоступной памятью /4/.

3.2 Размер входа. Время работы При исследовании сложности вычислений обычно изучают зависимость времени работ от размера входа /5/.

Рассмотрим задачу сортировки.

Вход: Последовательность n чисел (а1, …, а n).

Выход: Последовательность n чисел (а1, …, аn), являющаяся перестанов кой входной последовательности и удовлетворяющая условию: а1 … а n.

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

Пример – Вход : (1,3,2, 4). Выход (1,2,3,4).

Сортировка вставками для этого примера описывается последовательно стью: (1, 3, 2,4) = (1, 3, 2, 4) = (1, 2, 3, 4) =(1, 2, 3, 4).

Запишем в псевдокоде процедуру Sort_Ins, соответствующую сортировке вставками Sort_Ins (А) 1 for j2 to length (A) do k A (j) i j- while i 0 and A (i) k do A(i+1) A (i) i i- A (i+1) k End {Sort_Ins} Здесь n = length (A), j – очередной элемент вставки;

А (1.. (j –1)) – отсор тированный участок, А ((j + 1).. n) – осталось вставить;

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

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

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

Имеем таблицу:

Таблица 3. Номер строки 1 2 3 4 5 6 Стоимость С1 С2 С3 С4 С5 С6 С n n n tJ (tj-1) (tj-1) Кратность n n-1 n-1 n- j=2 j=2 j= Общее время Т(n)=с1n+с2(n-1)+с3(n-1)+с4tj+с5(tj-1)+с6(tj-1)+с7 (n-1);

tj– число раз исполнения строки 4, j =2..n.

Если массив на входе уже отсортирован, то цикл в строке 4 завершается после первой проверки. Общее время минимально: Т(n)=с1n+с2(n-1)+с3(n-1)+с (n-1)+с7(n-1)=аn+b;

а=с1+с2+с3+с4+с7, b=-(с2+с3+с4+с7) и является линейной фун кцией размера входа.

Если массив на входе отсортирован в обратном порядке, то tj = j. Общее время максимально: Т(n) = с1n+ с2 (n-1)+с3 (n-1)+с4 (n(n-1)/2 – 1)+ с5 (n-1)/2 + с6(n-1)/2 +с7(n-1)=аn2+bn+c;

а=с5/2+с6/2, в=с1+с2+с3+с4/2–с5/2–с6/2+с7, с=-(с2+с3+ с4 с7);

учтено, что j=2 n j = n(n=1)/2 – 1, j=1 n (j–1)=n(n=1)/2. Сама функция Т(n) уже квадратичная.

Итак, мы рассмотрели худший и лучший случаи. В промежуточном слу чае, если считать, что в среднем около половины элементов массива А (1..(j–1)) больше А(j), и в строке 4 взять tj = j/2, то окажется, что среднее время квадрати чно зависит от размера входа – как и в худшем случае (конечно, коэффициенты другие). Среднее время зависит от распределения вероятностей, которое может не быть равномерным. Худшее время – максимальное время по всем входам.

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

Функцию времени выполнения алгоритма оценивают по возможности полиномам;

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

3.3 Асимптотика роста функций Определение 1 Если f(n), g(n), nN – некоторые функции, то запись f(n) =(g(n)) означает, что существуют числа с1, с2 0 и n0N такие, что 0с1g(n) f(n) с2g(n) для всех nn0 (здесь символ “=“ читается как “ есть “).

Пример – Проверить, что (1/4)n2-3n=(n2).

Проверка – Требуемое неравенство имеет вид с1n2(1/4)n2-3nс2n2, nn0.

Это неравенство эквивалентно следующему: с11/4-3/nс2, n n0. Второе нера венство, очевидно, выполняется при с2=1/4 и любого n0N. Первое неравенство можно записать в виде n 3/(1/4-с1). Если с1=1/5, то достаточно взять n0 = 60.

Если f(n)=((n)), то g(n) называется асимптотически точной оценкой для f(n). Заметим, далее, что если f(n) = (g(n)), то и g(n)= (f(n)).

Определение 2 Если f(n), g(n), nN – некоторые функции, то запись f(n) = О(g(n)) означает, что существуют числа с 0 и n0 N такие, что 0 f(n) с g(n) для всех n n0.

Определение 3 Если f(n), g(n), nN – некоторые функции, то запись f(n) = (g(n)) означает, что существуют числа с 0 и n0 N такие, что 0 сg(n) f(n) для всех n n0.

Таким образом, – обозначение используется для двусторонней оценки (снизу и сверху), а О- и - обозначения используются для односторонних оце нок. Для любых двух функций f(n), g(n), nN свойства f(n)= О(g(n)) и g(n)= (f(n)) равносильны. (Символ «О» читается как «О- большое», символ «» - как «» - большое».) Асимптотические обозначения, О, могут использоваться внутри формул. Например, если имеется запись Т(n) = 2Т(n/2) + (n), то имеет ся в виду, что функция (n) не меньше с1n и не больше с2n для некоторых конс тант с1, с2 и достаточно больших n. А цепочка равенств типа 2n2+3n+ =n2+(n)=(n2) понимается как последовательная асимптотическая оценка функции.

Определение 4 Если f(n) = О(f(n)) и lim n(f(n)/g(n))=0, то применяется обозначение f(n)=о(g(n)) (« f от n есть о – малое от g от n»). При этом предпола гается, что f(n) и g(n) неотрицательны для достаточно больших n.

Определение 5 Если g (n)=o(f(n)), то говорят также, что f(n)= (g(n)) («f от n есть - малое от g от n»). При этом уже предположено, что f(n) и g (n) не отрицательны для достаточно больших n.

Итак, запись f(n)=о(g(n)) означает, что для любого 0 существует n0 N такое, что 0 f(n) g(n) для всех n n0, а запись f(n)= (g(n)) означает, что для любого с 0 существует n0 N такое, что 0 сg(n) f(n) для всех n n0.

Примеры 2n = о (n2), 2n2 о (n2) n2/2=(n), n2/2 (n2) Введенные характеристики асимптотического поведения функций обла дают некоторыми стандартными свойствами. Так, отношения,O,, о, тран зитивны,, О, рефлексивны, симметрично. Пары отношений О и, а так же о и взаимно обратимы.

3.4 Оценки роста стандартных функций 3.4.1 Полином от переменной n имеет вид р(n) = i=0dаini. Будем предпо лагать, что d – степень полинома. Тогда полином р(n)=О(nd). Говорят, что фун кция f(n) полиномиально ограничена, если f(n) = n O(1), или f(n) = О(nk) для не которой константы k.

3.4.2 Экспонента от переменной n определяется как функция n а n, а 0. При а1 экспонента растет быстрее любого полинома, то есть nb = o(an). Для вещественных х выполнено неравенство ех1+х;

если х1, то имеет место оценка 1+хех1+х+х2. Кроме того, можно отметить, что ех=1+х+(х2), х0.

Напомним, что е =2,71828…;

ех = k=0х k/ k!.

3.4.3 Логарифмы – это функции nlogbn, b0.Используются обозначе ния: log(n)=log2(n), ln(n)=loge(n). Напомним, что при х1 выполняется равенс тво ln(1+х)=х-х2/2+х3/3-…. Для х-1 справедливо: х/(1+ х)ln(1+х)х. Говорят, что функция f(n) ограничена полилогарифмом, если f(n)=logO(1)n. Любой поли ном растет быстрее любого полилогарифма, то есть log bn=o (nс), с0.

3.4.4 Факториалы – это функции nn!= n(n–1)!, n=1, 2,…. Полагают 0!=1. Очевидно, n!nn. Более точно, n! = 2n (n/е)n(1+(1/n)), - формула Сти рлинга. Из этой формулы следует, что n!=o(nn), n!=(2n), log(n!)= (n log n).

Наконец, 2n (n/е)nn! 2n (n/е) ne1/12n.

3.4.5 Пример - Числа Фибоначчи Ф(0)=0;

Ф(1)=1;

Ф(n+1)=Ф(n)+Ф(n-1), n=2, растут экспоненциально с ростом n. (Начало последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…).

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

Т(n)=2Т(n/2)+(n), n1. Решить рекуррентное соотношение – значит с его по мощью найти функцию или установить ее асимптотическое поведение. Здесь n – размер входа;

для простоты считаем, что n – степень числа 2. Рассмотрим не которые приемы решения рекуррентных соотношений.

3.5.1 Метод подстановки Пример – Т(n)=2Т(n/2)+n, где n – степень двойки. Зададимся видом Т(n)=О (n log n) (это нужно суметь), то есть предположим, что Т(n)сnlogn для некоторого с. Так как достаточно выполнения оценки, начиная с некоторого n, позаботимся, чтобы с обеспечивало требуемое неравенство при n=2. Предпо ложим теперь, что оценка верна для n/2, то есть Т(n/2)с(n/2)log(n/2). Подста вим ее в соотношение;

получим Т(n)с(n/2)log(n/2)+nсnlog(n/2)+n=сnlog(n) сnlog(2)+n+с nlog(n)-сn+nсnlog(n) (последний переход – при условии с1).

Итак, Т(n)сnlog(n), то есть метод индукции прошел. Делаем вывод:

Т(n)=O(nlog(n)).

3.5.2 Метод итераций Пример – Т(n)=3Т([n/4])+n, где [] - целая часть. Подставляя соотношение в себя, получим Т(n)=n+3Т([n/4])=n+3([n/4])+3Т([n/16])=n+3([n/4])+3([n/16])+ 3Т([n/64])))= … n+3n/4+9n/16+27n/64+ … + 3log n(1)ni=0(3/4)i+(nlog43) =4n+o(n)=O(n). Здесь использовано равенство [ [ n/4 ]/4] = [ n/16 ] и подобные.

Впрочем, округление здесь не влияет на результат. Поскольку после i -ой ите рации справа будет содержаться Т([n/4i]) до Т(1) чтобы дойти, нужно [ n/4i] приравнять 1, то есть получить ilog4n. Но заметив, что [ n/4i] n/4i, можно оценить наш ряд геометрической прогрессией со знаменателем (3/4) плюс сла гаемое 3 log4n, относящееся к задачам ограниченного размера, и заменить ука занное слагаемое на nlog43, что есть o(n).

3.5.3 Основной результат Имеет место теорема: Пусть а 1, b 1 – константа, f(n) – функция и ре куррентное соотношение Т(n)=аТ(n/b)+f(n), где под n/b понимается одно из двух ближайших целых чисел. Тогда:

-для f(n)=O(nlogbа-), 0 верно, что Т(n)=(nlogbа);

-для f(n)=(nlogbа) верно, что Т(n)=(nlogbа log(n));

-для f(n)=( nlogbа+), 0, причем аf(n/b)сf(n) для некоторой константы с 1 и достаточно больших n, верно, что Т(n)=(f(n)).

Суть теоремы – в сравнении функции f(n) с nlogbа, если одна из функций растет быстрее другой, то она и определяет порядок роста Т(n). Если функции одного порядка, появляется логарифмический множитель.

3.6 NР – полнота Если время работы алгоритма на входе длины n составляет О(nк) при не котором к, не зависящем от n, то алгоритм называется полиномиальным. Задача называется полиномиально разрешимой, если для нее существует полиномиа льный алгоритм. Для некоторых задач алгоритмы не полиномиальны. Есть так же неразрешимые задачи. Классическая задача – выяснить, останавливается ли данная программа на данном входе, - не может быть решена никаким алгорит мом. Специалисты считают полиномиальные алгоритмы практически приемле мыми, а алгоритмы, требующие времени, «большего», чем полиномиальное, представляющими лишь теоретический интерес. К характеристике полиномиа льных алгоритмов следует добавить их замкнутость: композиция (последовате льное выполнение) полиномиальных алгоритмов есть полиномиальный алго ритм. Достаточно полное изложение вопросов сложности алгоритмов имеется в /5/. Здесь приводятся лишь некоторые сведения.

3.6.1 Задачи разрешения. Класс P Рассмотрим абстрактную задачу – бинарное отношение между элемен тами множества условий U и множества решений V. Например, в задаче обхода графа условиями являются матрицы смежностей, а решениями – последовате льности вершин. Задачами разрешения называются задачи, в которых требуется ответить («да» или «нет») на поставленный вопрос, то есть построить функцию f с областью определения U и множеством значений V= 0,1. Если предпола гать, что входные данные для алгоритма представлены последовательностью битов (или последовательностью символов другого алфавита мощности 2), то абстрактная задача переходит в так называемую строковую задачу. Строковая задача называется полиномиальной, если существует алгоритм, который решает ее при длине входа n за время О (nк) для некоторого к.

Множество полиномиальных строковых задач разрешения называется сложностным классом Р. Функция f: 0,1*0, 1 называется вычислимой за полиномиальное время, если существует полиномиальный алгоритм, перево дящий х0,1* в y0, 1. Если существуют две вычислимые за полиномиа льное время функции f12, f21, переводящие два представления множества U друг в друга, то эти представления называются полиномиально связанными. Справе дливо следующее утверждение.

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

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

3.6.2 Допускающие и распознающие языки Языком L над алфавитом А называется некоторое множество последова тельностей символов (слов) алфавита А (построенных по определенным прави лам) Пример –L =, 0, 1, 0110, 11, 001, … A={0,1}.

Символ означает пустое слово, символ Ф означает пустой язык. Язык, состоящий из всех возможных слов над заданным алфавитом А обозначается через А*. Таким образом L А* для любого языка L над алфавитом А.

На примере языков L0,1* введём ещё несколько понятий из теории формальных языков. Говорят, что алгоритм A допускает слово x{0, 1}*, если А (х) = 1;

отвергает, - если А(х) = 0. Алгоритм называется допускающим язык L, если алгоритм допускает все слова L и только их. Если алгоритм допускает все слова из L и не допускает слова из СL, то говорят, что этот алгоритм распо знает язык. Язык L допускается распознается за полиномиальное время если каждое слово языка допускается распознается за время не большее O(nк) (n – длина слова х, к не зависит от х, соответствующим допускающим распознаю щим языком. На основании введенных понятий можно определить класс Р сле дующим образом: Р = L 1 * существует алгоритм А, распознающий язык 0, за полиномиальное время. Имеет место теорема: Р = L L допускается за полиномиальное время. Таким образом, в рассмотренной ситуации допуска ющие и распознающие за полиномиальное время языки эквивалентны.

3.6 3 Проверяющие алгоритмы Рассмотрим задачу разрешения, связанную с задачей поиска кратчайшего пути в графе. Дан неориентированный граф G = (X, Y), X – множество вершин, Y – множество ребер. Требуется для двух вершин графа построить кратчайший путь между ними. Это задача о кратчайшем пути. Здесь условием u является тройка (G, x1, x2),x1, x2 а решением v – последовательность (x1, …,x2) вер X, шин графа, составляющих требуемый путь. Одна из задач разрешения: по двум вершинам графа и числу k определить, существует ли в графе путь, связываю щий заданные вершины, длина которого k. Теперь условием u является (G, x1, x2, k), а решение v {0, 1}, причём`v =1, если такой путь есть;


v = 0 в против ном случае. Существует алгоритм поиска в ширину на графе, с помощью кото рого сформулированная задача решается за полиномиальное время.

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

более точно, время работы такого алгоритма равно (2 n), где n – длина представления графа. ( Напомним, что число перестановок из m эле ментов равно m!. («эм – факториал»). Имеет место теорема: задача о гамильто новом цикле является NP – полной. К раскрытию понятия NP – полноты мы и переходим в следующих пунктах.

Проверяющим алгоритмом называется алгоритм А, имеющий два параме тра;

первый – входная строка, второй – образец (или сертификат). Такой алго ритм считаем допускающим вход u, если существует образец v, для которого А (и, v) = 1. Языком, проверяемым алгоритмом А, называется язык L =u 0,1 * (v 0,1 * А (u, v) = 1).

Итак, алгоритм А проверяет язык L, если для любого слова uСL найдет ся образец v, с помощью которого А может проверить принадлежность слова и языку L, а для строки не принадлежащей языку такого образца нет. В задаче о гамильтоновом цикле образцами могут быть последовательности вершин, обра зующие гамильтонов цикл. Гамильтоновость цикла в графе можно проверить за полиномиальное время.

3.6.4 Класс NP Множество языков, для которых имеются работающие полиномиальное время проверяющие алгоритмы ( с образцами, ограниченными по длине неко торыми многочленами) называется сложностным классом NP. Заметим, что проверка языка в данном контексте несколько отличается от проверки языка как таковой. А именно: для U L могут существовать длинные образцы, кото рые в данном контексте отбрасываются (и потому остаются непроверенными в прежнем смысле). Очевидно, всякую задачу из Р можно считать входящей в NP: полиномиальный алгоритм, распознающий язык, в этом случае уже сущес твует, и для этого языка строится проверяющий алгоритм, не учитывающий второй параметр. Итак, Р NP. Совпадают ли классы Р и NP?. Большинство специалистов полагают, что в NP есть задачи, не решаемые за полиномиальное время.

3.6.5 Сводимость языков. NP – полнота языков Обычно мы полагаем, что одна задача сводится к другой, если (возможно) преобразованные входы первой задачи являются входами другой. Говорят, что язык L1 сводится к языку L2, если существует такая функция f: 0, *0,1*, что для любого x 0,1* свойства x L1 и f(х) L2 эквивалентны.

Функция f называется сводящей функцией, а алгоритм, вычисляющий функцию f, – сводящим алгоритмом. Если функция f вычислима за полиномиальное вре мя, то говорят, что язык L1 сводится к языку L2 за полиномиальное время и используют запись: L1 р L2. Сводящая функция переводит любое слово x L1 в слово f(х) L2, а слово х L1 – в слово f(х) L2. Поэтому по ответу на вопрос: «f(х) 2?» мы получаем ответ на вопрос «х L1?». Справедливо утверждение: Если языки L1, L2 0,1*, и L1 р L2, то из L2 Р следует, что L1 Р. При этом запись L1 р L2 можно интерпретировать так, что слож ность языка L1 не более чем полиномиально превосходит сложность языка L2.

Основное определение Язык L1 0, 1* называется NP – полным, если выполняются условия:

1) L1 NP;

для любого L2 NP выполняется отношение L2 р L1.

2) Язык L1 0,1* называется NP – трудным, если выполнено условие 2), а условие 1) может выполняться или не выполняться.

Основная теорема Если некоторая NP – полная задача разрешима за по линомиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не разрешимая за полиномиальное время, то все NP – полные задачи таковы.

Доказательство Если некоторый язык L1 является NP – полным и в то же время разрешимым за полиномиальное время, то для любого языка L2 NP из свойства 2) основного определения следует, что L2 р L1. Последнее означает, что L2Р. Утверждение в первой формулировке доказано. Вторая формулиров ка теоремы эквивалентна первой. В соответствии с этой теоремой предположе ние о том, что Р NP означает, что NP – полные задачи не могут быть решены за полиномиальное время. Пока никто не предъявил полиномиальный алгоритм для решения NP – полной задачи, и никто не доказал N NP.

3.6.6 Примеры NP – полных задач Имеется множество NP – полных задач в различных разделах математи ки: логике, графах, алгебре и так далее. Рассмотрим несколько примеров.

1 Задача о выполнимости схемы Дана схема, состоящая из элементов «и», «или», «не». Требуется выяснить, является ли эта схема выполнимой. При этом схема из функциональных элементов с несколькими входами и одним выходом называется выполнимой, если существует входной булев вектор, для которого выходной скаляр есть единица. Как уже известно, эта задача сводится к задаче о выполнимости пропозициональной формулы ((х1х2) ((х1 х3) х )) х2 имеет выполняющий набор (х1, х2, х3, х4) = (0, 0, 1, 1). (проверьте!) Вы полнимость можно проверить, перебрав все наборы значений переменных (для формулы с n переменными их 2n). В данном случае достаточно проверку прове сти для представленного образца. Переборный алгоритм как видно, не является полиномиальным. Имеет место теорема: задача о выполнимости формулы NР полна. Предупреждение: естественный способ построение формулы, которая вычисляет туже функцию, что и заданная схема, состоящий в последовательной записи подформул, отвечающих тому или иному элементу (например, для вы хода элемента «и» формула имеет вид 1 2, где 1, 2 – формулы, соответс твующие входам элемента), не является полиномиальным. Общая идея состав ления формулы, которую строит «нужный» сводящий алгоритм – в том, что вводится дополнительная переменная для каждого провода в схеме (а не только ее входов). Например, схеме (рисунок 3.1) соответствует формула = х8 (х (х7 х6)) (х7 (х4 х5)) (х6 (х2 х3) (х5 х3) (х4 (х1 х2)). Та кое построение приводит к схеме полиномиального размера и выполняется за полиномиальное время.

х1 х х2 V х х х х3 V х V Рисунок 3. 2 Задача о клике Дан граф. Найти максимальный размер клики в этом графе.

Напомним, клика в неориентированном графе есть полный подграф данного графа. Размером клики называется число ее вершин.

3 Задача о суммах подмножеств Требуется выяснить, существует ли подм ножество данного множества с заданной суммой элементов.

4 Разработка алгоритмов и программ 4.1 Основные технологии Программа – это запись алгоритма на языке, понятном исполнителю. С массовым внедрением вычислительных машин процесс программирования для них превращается в промышленное изготовление программ. Для этой цели соз даются разнообразные технологии программирования. Основные из них: нис ходящее программирование и восходящее программирование. Нисходящее программирование (программирование «сверху – вниз») основывается на идее декомпозиции исходной задачи на ряд подзадач: строится программа, в которой эти подзадачи выступают как некоторые именованные процедуры и к ним ор ганизуется обращение. Те подзадачи, которые еще не обработаны. Временно заменяются «заглушками». Затем по отношению к подзадачам применяется та кой же прием. Выходящее программирование (программирование «сверху – вниз») основано на противоположном процесс: сначала пишутся и отлаживают ся программы самого нижнего уровня;

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

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

В программировании выделяют два направления: прикладное програм мирование и системное программирование. Цель первого – разработка средств подготовки задач к решению на ЭВМ, цель второго – создать программное обе спечение реализации вычислительного процесса на ЭВМ и обмена информаци ей ЭВМ с внешним миром. Основные задачи системного программирования – разработка и совершенствование языков программирования, а также транслято ров для перевода программ с этих языков на машинный уровень;

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

Поскольку язык реальной ЭВМ достаточно беден, в программировании имеет дело с виртуальной вычислительной машиной, состоящей частично из аппаратуры и частично из программного обеспечения, то есть программа моде лируется более мощной входной язык. Перевод входного языка в машинный выполняют программы трансляторы. Трансляция может быть одно- и многоша говой, в зависимости от числа уровней в иерархии виртуальных ЭВМ. Уже раз работаны тысячи языков программирования, существуют различные их клас сификации. Одна из них делит языки программирования на языки низкого, вы сокого и сверхвысокого уровня. Все языки низкого уровня ориентированы на тип аппаратуры. Популярными считаются языки ассемблеров для систем ко манд IBM – PC и VAX.Языки высокого уровня ориентированы на систему опе раторов (присваивание, перехода, цикла, условные операторы, операторы ввода – вывода) и описаний данных. Используемых в программе. Языки высокого уровня – ФОРТРАН, АЛГОЛ, ПАСКАЛЬ, АДА. К языкам сверхвысокого уров ня относят Algol – 68 и APL;

они обладают дополнительными средствами опи сания обработки данных. По другой классификации языки программирования делятся на вычислительные и языки символьной обработки. К последним отно сятся ЛИСП, ПРОЛОГ, РЕФАЛ. С прикладной точки зрения ФОРТРАН, АЛ ГОЛ- 60, ПАСКАЛЬ ориентированы на научные и инженерные расчеты, КО БОЛ – типичный язык обработки экономической информации, СИМУЛА – 67 – язык имитационного моделирования.


4.2 Сортировка Пусть задан файл, состоящий из записей: (1),…,(n). Каждой записи поставим в соответствии ключ ki, i=1…n.Обычно ключ – это какое-либо отде льное поле или комбинация полей записи (некоторый признак записи). Будем предполагать, что на множестве ключей задано отношение линейного порядка (следования) с обычными свойствами. Задача сортировки файла ставится так:

найти перестановку записей µ (1),…,µ (n) такую, чтобы их ключи располага лись в неубывающем порядке: k µ(1) … k µ(n). Во многих случаях не требуется реально иметь перестановку, а достаточно, например, составить список индек сов (адресов) элементов перестановки в исходном файле. Составление списка индексного списка называют индексный сортировкой. Впрочем, имея индекс ный список. Нетрудно произвести собственно сортировку.

Пример – Дан массив чисел (4, 5, 3, 8, 1, 9, 3, 2). Обычная сортировка: 1, 2, 3, 5, 4, 5, 8,9;

индексная сортировка: 5, 8, 3, 7, 1, 2, 4, 6.

Имеется много алгоритмов сортировок /6/.

4.2.1 «Пузырьковая сортировка»

Название ассоциирует перемещение «малых» элементов со «всплытием».

Итак, пусть S – числовой массив а (1), …,а (n). Говорят, элементы а (i), а(j) об разуют инверсию, если i j и а (i) а(j). Тогда алгоритм «пузырьковой сорти ровки» состоит в последовательных просмотрах от конца к началу массива S и обмена местами соседних элементов с инверсией.

Вход: массив S(1), …, S(n).

Вывод: массив S(1) S … S(n).

Процедура Рus(S,n) 1 for i 2, to n do 2 for j n to I do 3 if a(j – 1) a(j) then swap(A(j-1),A(j)) End {Pus} Трудоемкость этого алгоритма равна О(n2), то есть при любых S и n он решает задачу за сn2 операций сравнений и обменов, где с – константа, не зави сящая от n.

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

4.2.2 Сортировка с помощью двоичного (бинарного) дерева Бинарное дерево – ациклический граф с выделенной вершиной (корнем), у которой нет предшественников. Адрес корня – 1.Любая другая вершина имеет Уровень Уровень Уровень Уровень Рисунок 4. только одного предшественника и одного или двух преемников. (рисунок 4.1).

Для каждой вершины k, k=1…n, могут быть вычислены адреса предшест венников и преемников по формулам:

- для родителей х(k) =k\2, k=1… n;

- для потомков слева у(k)= 2k, k=1…(n\2), yk=0, k (n\2), - для потомков справа z(k)= 2k+1, k=1…((n-1)\2), z(k)= 0, k (n-1)\2.

Нумерация вершин (адресация) идет по уровням (сверху–вниз, слева– направо).

Сортировка с помощью бинарного дерева выполняется следующим обра зом. Элементы массива помещаем в вершины нижнего уровня (рисунок 4.2).

Первый этап – построение дерева. На первом шаге попарным сравнением надстраиваем уровень дерева и помещаем в вершины – родители меньшие эле менты пары потомков. На втором шаге надстраиваем очередной уровень дере ва (по аналогичному правилу) и т.д. В результате построения дерева его корнем будет минимальный элемент.

Второй этап – собственно сортировка. Объявляем число µ в корне дерева очередным элементом сортированного массива и спускаемся в дереве Д по обо значенному им пути. Если путей несколько, выбираем тот, который включает потомков слева. Заменяем в нижнем уровне µ на + и выполняем пересчет вер хних уровней с учетом замены. Результат пересчета показан на рисунке 4.3.

После n-кратного выполнения этапа 2 дерево D будет состоять из значений +, и процесс сортировки закончится. Для однократного выполнения второго этапа требуется выполнить log n сравнений. Поэтому общая трудоемкость сортиров ки составляет O(n log n) операций.

1 4 1 9 4 5 12 9 8 14 9 1 Рисунок 4. 4.2.3 Быстрая сортировка Пусть S(k), k=1..n – одномерный массив и х S(k) Просматриваем S сле ва направо, пока не найдем а х, и просматриваем S справа налево, пока не найдем b х. Меняем местами а и b Продолжая этот процесс, придем к после довательности, разделенной на две части S1 и S2 такой, что элементы из S1 не превосходят х, а элементы из S2 не меньше х.

Пример – Массив – 6;

23, 17, 8, 14, 25, 6, 3, 30, Последовательность: 6, 7, 3, 8, 6 25, 14, 17, 30, 23.

Значение х для массива будем выбирать так: если количество элементов в S нечетно, то это будет средний элемент, если четно, то из двух средних выби рать элемент с меньшим индексом. Итак, мы рассмотрим процедуру разделе ния. Теперь опишем процедуру быстрой сортировки. Разобьем S на две части S1 и S2 как только что было описано. Теперь поступим также с каждой из час тей S1 и S2 и так далее, пока каждая из частей не будет содержать ровно 1 эле мент. В результате получится отсортированный массив. При реализации этой процедуры на ЭВМ надо предусмотреть хранение адресов раздваиваемых по дмассивов. Если каждый раз продолжать работу с меньшей из полученных час тей, отправляя адреса начала и конца второй части на хранение, то потребуется запоминание не более 2 log(n) адресов (чисел). Можно хранить эти адреса в ви де наращиваемого стека, обрабатывается первым. С другой стороны. Следует иметь в виду, что для «быстрой сортировки» нет гарантированной трудоемкос ти типа 0 (n log n), где n – число элементов массива. В иных ситуациях трудое мкость достигает 0 (n^2) (например, для упорядоченных массивов). По образ ному выражению Н.Вирта, «быстрая сортировка напоминает азартную игру, где следует рассчитать, сколько можно позволить себе проиграть в случае невезе ния».

4.3 Поиск Типичными примерами поиска служат работа со справочником, катало гом в библиотеке, таблицами.

Пусть файл состоит из записей (1),…, (n) с ключами kµ(i),i=1..n, k – некоторое значение. Рассматривается четыре вида простейших задач поиска:

1) Требуется определить по крайней мере одну запись в µ имеющую k своим ключом;

2) Требуется определить все записи в µ, имеющие k своим ключом;

3) Если в µ нет записей с ключом k, то добавить в µ новую запись;

4)Включить в µ новую запись.

Число k называют аргументом поиска, или запросом, задачи 1 и 2 – прос тым поиском, 3 и 4 – поиском со вставкой. Поиск в задачах 1 и 2 может быть безрезультатным. В задачах 1-3 поиск может быть организован по выполнению условия а kµ(i) b, где а и b – константы и других условий. Здесь, как и ран нее, под файлом будем понимать одномерный или двумерный числовой или символьный массив, то есть вести поиск в одномерной или двумерной таблице.

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

4.3.1 Просмотр всех подряд записей до получения решения задач 1-3 на зывается последовательным поиском.

4.3.2 Бинарный поиск упорядоченного массива состоит в следующем.

Сначала К сравнивается со средним ключом в таблице. Результат сравнения или приводит к решению задачи, или позволяет определить, в какой части мас сива продолжить поиск. Применяя этот принцип к «половинному» массиву, че рез не более чем log n сравнений, получается положительный или отрицатель ный ответ.

4.3.3 Задача поиска в сети ставится следующим образом. Пусть задана ориентированная сеть S= (Р, R, d), где Р – множество вершин, R – множество дуг;

d – функция, определенная на R со значениями в множестве действитель ных чисел. Иногда d(х, у) интерпретирует как длина дуги (х, у) R.

Основными подзадачами в алгоритмах оптимизации на сетях являются:

- определение всех дуг сети вида (х, у) для фиксированной вершины х Р, то есть определение всех выходов у для данного х;

- определение всех дуг сети вида (у, х) для фиксированной вершины х Р, то есть определение всех входов у для данного х;

Рассмотрим способ ускорения поиска в сети. Пусть решается задача определения выходов (рисунок 4.3). Считаем, что S представлена в оператив ной памяти в виде массива дуг µ (таблица 4.1).

4 4 3 1 1 1 2 1 3 Рисунок 4. Отсортируем файл y по ключу х. В этом случае среднее время нахожде ния всех дуг (х, у) даже при последовательном поиске сократится примерно вдвое.

Таблица 4. Индекс х Дуга у d Индекс х Дуга у d 1 7 8 3 9 1 3 2 3 4 4 10 1 7 3 5 9 1 11 6 4 4 9 5 3 12 1 6 5 4 5 2 13 6 8 6 8 9 1 14 6 5 7 3 6 1 15 6 9 8 7 6 Пусть имеется некоторый вспомогательный массив А, в позициях x кото рого записан адрес А(х) расположения в µ начальной дуги вида (x, y). В этом случае проблема поиска всех дуг (x, y) сводится к выборам адреса А(х). Если, например, требуется найти в µ все дуги вида (х0, у), то получив А(х0) = у0 мы попадаем на подмассив выходов из х0. Этот способ решения задачи полагает, что хР – это натуральные числа. Для минимизации объема дополнительной памяти, то есть величина t=maxxP(x), удобно иметь последовательную нумера цию вершин, начиная с 1.

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

4.4 Алгоритмы перебора 4.4.1 Полный перебор Рассмотрим задачу генерации перестановок (ГП).

Постановка задачи Дано множество n попарно различных действитель ных чисел: S = {a1, …, an}. Требуется перечислить все N = n! перестановок эле ментов ак, к = 1…n этого массива.

Алгоритм ГП Шаг 1 Производится сортировка массива по убыванию его элементов.

Полученная перестановка считается начальной и выводится. Далее идет работа с индексами элементов i {1… n}.

Шаг 2 Находится наименьший индекс i{2… n}, для которого аi - 1 аi.

Шаг 3 Находится наименьший индекс j{1…(n - 1)}, для которого аj аi.

Шаг 4 Обмен значениями аi и аj.

Шаг 5 Обмениваем значениями компоненты в парах: (а1,аi - 1),…,(ак,аi - к ), к = [(i - 1) / 2].

Шаг 6 Вывод полученной перестановки. Если число выведенных пере становок N, переход на шаг 2, в противном случае задача решена.

Алгоритм требует осторожности при работе с большими n, так как N = n!

растет очень быстро. Например, 10! = 3628800.

Пример – Для начальной перестановки (3, 2, 1) следующими выводами перестановками будут: (2,3,1), (3,1,2), (1,3,2), (2,1,3), (1,2,3). (Имеется множест во других алгоритмов).

4.4.2 Метод ветвей и границ Рассмотрим задачу о коммивояжере.

Постановка задачи Дано множество пунктов S = {1 … n} и сеть сообще ний между ними. Конкретный пример дан рисунком 4.4 (граф) и матрицей A.

Элемент aij, i,j {1…n}, матрицы А показывает некоторую характеристику дуги (стоимость проезда) из пункта i (номер строки) в пункт j (номер столбца). Тре буется составить замкнутый маршрут, соединяющий все пункты и проходящий через каждый пункт ровно один раз. Дополнительное условие: сумма характе ристик дуг маршрута (суммарная стоимость проезда) – минимальна. Решение задачи для небольших n может быть проведено следующим образом. Строим последовательно перестановки из номеров пунктов и для допустимых переста новок запоминаем лучшие суммы. Таким образом, для n пунктов просматривае тся (n - 1)! маршрутов. При n = 5, (n - 1)! = 24. Для больших n (но не очень – факториал быстро растет) применяется метод ветвей и границ.

18 28 22 4 12 22 19 8 A= 2 7 18 29 16 10 Рисунок 4. Приведем алгоритм ветвей, дающий все допустимые маршруты коммиво яжера.

Пусть S – цепочка элементов. Полагаем S = ( ), i = 1.

Шаг 1 Выбор базы. В матрице А выбираем элемент ai j (можно с ме ньшим j), если существует. (Если такого элемента нет, продвижение в этом на правлении невозможно).

Шаг 2 Ветвление. По матрице А строим матрицы А1, А2.

Построение А1 Полагаем S = S + ai j. Берем матрицу А, полагаем элементы i – строки, j – столбца равными. Сам элемент ai j не меняем. Предотвращаем циклы, полагая a j i = (в общем случае для цепочки (ai j, a j к, a lm) полагаем a m i = ).

Построение А2 Полагаем ai j в матрице А (остальные элементы – без из менения). С каждой из матриц А1, А2 и соответствующими цепочками идем на выполнение шага 1. При этом поиск базы производим в общем случае цепочки (ai j, a j к, a lm) в m – строке.

Шаги 1, 2 выполняются до достижения длины n цепочки (есть маршрут) или цепочка имеет меньшую длину, но очередной выбор базы невозможен (ма ршрута с таким подмаршрутом нет). По достижении длины n – 1 вместо предо твращения надо провести проверку: если ami, то присоединяя ami к цепочке, получаем маршрут, если ami =, маршрута с подмаршрутом, соответствующим имеющейся цепочке, нет. Конец алгоритма.

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

Для приведённого примера оптимальный маршрут коммивояжера: (а12, а23, а35, а54, а41) имеет стоимость 56. Маршрут можно записать также в виде:

123541.

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

1 Ханойские башни Существует легенда: «В храме Бендареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота. Наибо льший диск лежит на бронзовой плите и с остальными образует пирамиду, су жающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:

1) диски можно перемещать с одного стержня на другой только по одно му;

2) нельзя класть больший диск на меньший:

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

Когда все 64 диска будут перенесены с одного стержня на другой, насту пит конец света».

Рекурсивная программа на языке программирования Turbo Pascal пере мещения дисков может выглядеть следующим образом. Здесь N – число дисков, X, Y, Z – переменные диски, A, B, C – их конкретные имена.

PROGRAM HANOI;

VAR N: INTEGER;

X, Y, Z: CHAR;

PROCEDURE HAN(N: INTEGER;

VAR X, Y, Z: CHAR);

BEGIN IF N0 THEN BEGIN HAN(N-1, X, Z, Y,);

WRITELN(X,’’,Y,’ ’);

HAN(N-1, Z, Y, X) END END;

BEGIN WRITELN(‘ВВОД N, X, Y, Z’);

READ(N, X, Y, Z);

HAN(N, X, Y, Z);

WRITELN END.

В результате запуска программы может получиться:

ВВОД N, X, Y, Z 4ABC AC CB AC BA BC AC AB CB CA BA CB AC AC AB CB (Стрелки означают перемещение диска со стержня с именем, указанным слева, на диск с именем, указанным справа.) Примечание – Ввод достаточно больших чисел требует модификации программы.

2 Задача Фибоначчи (1228) «Некто поместил пару кроликов в некоем ме сте. Природа кроликов такова, что каждый месяц пара кроликов производит на свет другую пару, а начинают рождать через 2 месяца после своего рождения.

Сколько пар кроликов будет через 12 месяцев?»

Эта задача сводится к последовательности чисел 1, 1, 2, 3, 5, 8, 13, 21, …, при этом каждое следующее число, начиная с третьего, равно сумме двух предыдущих.

Программу можно составить с применением рекурсивной функции FIB.

PROGRAM CROL;

VAR N, CR:INTEGER;

{N - число месяцев, CR – число кроликов} FUNCTION FIB(N:INTEGER):INTEGER;

BEGIN IF (N=1) OR (N-2) THEN FIB:=1 ELSE FIB:=FIB(N-1)+FIB(N-2) END;

BEGIN WRITE (‘Ввод N’);

READ(N);

CR:=FIB(N);

WRITE(‘Число пар кроликов =’,CR: END.

Первый вызов функции происходит в основной программе, а затем выпо лняется рекурсивный вызов внутри функции. Пример выполнения программы:

Ввод N Число пар кроликов = 233.

4.6 Жадные алгоритмы Жадный алгоритм – это алгоритм, на каждом шаге которого выбирается оптимум, соответствующий условиям этого шага. Такой локально оптимальный алгоритм далеко не всегда дает глобальный оптимум. В то же время имеются классы жадных алгоритмов, дающих глобальный оптимум /5/.

Пример – Кратчайший путь из А в B имеет длину 16 (АЕВ, например);

по локально оптимальному алгоритму получается длина, равная 30 (ACFDGEB) (рисунок 4.5).

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

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

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

A 9 C 10 E 4 1 D F 6 7 G 8 B Рисунок 4. Если задача порождает множество подзадач, то, как правило, необходимо динамическое программирование. Например, непрерывная задача о рюкзаке решается с помощью жадного алгоритма, а дискретная динамического про граммирования. Напомним дискретную задачу о рюкзаке: имеется n вещей сто имостями ci и весами vi, i=1..n. Требуется отобрать вещи с наибольшей общей стоимостью и общим весом V. В случае непрерывной задачи вес vi произво лен для каждого i=1..n.

4.6.1 Равномерные и неравномерные коды Допустим, строится посимвольный двоичный код, то есть каждый символ кодируется конечный битовой последовательностью, называемый кодовым словом. Если все кодовые слова имеют одинаковую длину, код называется рав номерным. Например, если длина кода 4, то можно закодировать 16 различных символов. Для файла длина 1000 символов длина кода будет 4000. Общую дли ну кода файла можно сократить, если использовать неравномерный код, то есть часто встречающиеся символы закодировать короткими битовыми последова тельностями, а редко встречающиеся – более длинными. Каждому двоичному коду – равномерному и неравномерному соответствует двоичное дерево.

Пример – задана таблица кодов (таблица 4.2) Соответствующие деревья изображены на рисунке 4.6.



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.