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

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

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


Pages:     | 1 | 2 ||

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

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

Таблица 4. Символ a b c d e f Относительная 0,45 0,13 0,12 0,16 0,09 0, частота Равномерный 000 001 010 011 100 код Неравномерный 0 101 100 111 1101 код 100 0 1 0 8 1 4 0 1 0 a 0 5 2 1 2 0 1 0 1 0 1 0 1 0 4 1 1 1 0 0 1 1 1 a b c d e f c b 01 d 0 f e Рисунок 4. 4.6.2 Префиксные коды Коды, в которые из двух последовательностей битов, представляющих различные символы, ни одна не является префиксом другой, называются пре фиксными кодами. Известно, что для любого кода, допускающего однозначное восстановление информации, существует не худший его префиксный код. По этому, в принципе, можно ограничиться префиксными кодами.

При кодировании каждый символ заменяется на свой код. Например, для рассматриваемого неравномерного кода строка abc запишется как 0101100. Для префиксного кода декодирование однозначно (что следует из его определения) и выполняется слева направо. Первый символ текста, закодированного префик сным кодом, определяется однозначно, так как кодирующая его последователь ность не может быть началом кода какого-то символа. Найдя этот первый символ и отбросив кодирующую его последовательность битов, повторяем процесс для оставшихся битов, и так далее. В частности строка 001011101 в случае неравномерного кода разделяется на части 0-0-101-1101 и декодируется как aabc.

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

Зная дерево Т, соответствующее префиксному коду, найдем количество битов, необходимое для кодирования файла. Пусть (S) обозначает число вхо ждений символа S в файл, gT(S) – глубину соответствующего листа в дереве (длину последовательности битов, кодирующей S). Тогда для кодирования файла потребуется B(T)= sS(s)gT(s) битов. Число B(T) называется стоимостью дерева Т. Здесь S={S} - алфавит файла.

4.6.3 Коды Хаффмена Хаффмен построил жадный алгоритм, который строит оптимальный пре фиксный код (код Хаффмена). Фактически алгоритм строит дерево Т, соответс твующие оптимальному коду снизу вверх, начиная с множества |S| листьев и выполняя |S|-1 «слияние». Первому слиянию подлежат листья с наименьшей частотой, а очередным «слиянием» - поддеревья с наименьшей частотой. Для рассмотренного ранее примера последовательность построения дерева дана на рисунке 4.7 (|S|=6=n).

Синтезируя полученный элементы, получим дерево Т, как на рисунке 4.6.

Псевдокод алгоритма можно записать с применением процедур Allocate_Nod, Extract_Min, Insert, знакомых по работе с кучами /4/.

Huffman (S) 1 n|S| 2 0S 3 for i1 to n- 4 do z Allocate_Nod () xleft [z] Extract_Min (0) yright [z] Extract_Min (0) 7 f[z]f[x]+f[y] 8 Insert (0,7) 9 return Extract_Min (0) End {Huffman} 5 9 12 13 16 0) f e c b d a 12 13 14 16 1) 0 5 14 16 25 2) 0 12 25 30 3) 0 14 45 4) 0 25 5) 0 45 Рисунок 4. Время работы алгоритма Huffman для алфавита из n символов есть вели чина 0(n log(n)). При этом предполагается, что для нахождения двух объектов, подлежащих слиянию, используется очередь с приоритетами, а сама очередь реализована в виде двоичной кучи. Присваивание в строке 2 проводится с по мощью процедуры BuildHeap.

Доказательство того, что жадный алгоритм Huffman дает оптимум, про водится в такой последовательности /4/: сначала доказываются леммы 4.1, 4.2, затем теорема 4. Лемма 4.1 Пусть в алфавите S, каждый символ s имеет частоту f[s] и S пусть x,y S-два символа с наименьшими частотами, тогда для S существует оп тимальный префиксный код, в котором последовательности битов, кодирую щие x и y, имеют одинаковую длину и различаются только в последнем бите.

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

Установим теперь свойство оптимальности для подзадач. Пусть фиксиро ван алфавит S и два символа х, у этого алфавита, а S’-алфавит, который полу чится из S, если удалить х и у и ввести новый символ Z. Рассмотрим кодовые деревья для S, в которых х и у представлены листьями-братьями. Каждому та кому дереву соответствует кодовое дерево для S’, которое получится, если уб рать вершины х и у, а их общего родителя считать кодом символа Z. (При этом каждому кодовому дереву для C’ соответствует два кодовых дерева для C: в одном из них х слева, а в другом справа). Пусть f[s]-частота символа s S.

Положим для символов S’ f[z]=f[x]+f[y];

для остальных символов частоты оста вим теми же, что и в S. Теперь для обоих алфавитов определены стоимости ко довых деревьев.

Лемма 4.2 Стоимости соответствующих друг другу деревьев Т и Т' отли чаются на вершину f[x]+f[y] (в принятом описании).

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

Теорема 4.1 Алгоритм Huffman стоит оптимальный префиксный код.

Доказательство Лемма 4.1. показывает, что оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (назовем их х и у) являются братьями. Им соответствуют деревья для алфавита S', в котором символы х, у слиты в один символ z. Считая частоту символа z, равной сумме частот х и у, можно, применив лемму 4.2 и увидев, что остается, найти оптима льное кодовое дерево для алфавита S' и затем добавить к вершине z двух пото мков, помеченных символами х и у. Именно это и записано в алфавите Huff man.

4.6.4 Матроиды Матроидом называется пара М=(S,I), удовлетворяющая условиям:

1) S-конечное непустое множество;

2) I-непустое семейство подмножеств S, которые называются незави симыми, таких, что из B и A следует A Семейство I называется наследст I B I.

венным;

Если A B и A B, то существует элемент x 3) I, I B\A такой, что A{х} Это свойство семейства I называется свойством замены.

I.

Примеры 1 Матричный матроид – Пусть Т – вещественная матрица, S множество её столбцов, и подмножество A называется независимым, если S оно линейно независимо. Тогда получается матроид.

2 Графовый матроид – Пусть G – неориентированный граф;

SG – множество ребер графа, IG состоит из всех ацикличных множеств ребер (то есть являющихся лесами). Тогда (SG, IG) – матроид.

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

Если M=(S, I) – матроид, то элемент x I называется независимым от х, A если множество AU{x} независимо. Например, в графовом матроиде ребро е независимо от А тогда и только тогда, когда его добавление к А не создает цик ла.

Независимое подмножество в матроиде называется максимальным, если оно не содержится ни в каком большем независимом подмножестве. Имеет ме сто теорема:

Теорема 4.2 Все максимальные независимые подмножества данного мат роида состоят из одинакового числа элементов.

Доказательство Пусть А, В – независимые подмножества, и А В. то гда из свойства замены следует, что существует х для которого A{x} неза А, висимо, что противоречит максимальности.

Пример – Пусть G – связный граф, MG – соответствующий матроид. Тог да всякое максимальное независимое подмножество MG должно быть деревом с V -1 ребром (V – множество вершин), соединяющим все вершины G. Такое дерево называется основным деревом графа G.

Матроид M=(S, I) называется взвешенным, если на множестве S задана весовая функция W со значениями в множестве положительных чисел – W:

SR+. Функция W распространяется по аддитивности на все подмножества множества S. Вес подмножества определяется как сумма весов его элементов:

W(A)=x W(x). Например, если MG – графовый матроид, W(e) – длина ребра e, A то W(A) – сумма длин ребер подграфа A.

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

5 Алгоритмы Евклида в кольце полиномов 5.1 Кольцо полиномов от одной переменной Пусть J-область целостности /8/, x - некоторый символ, тогда выражение вида P(x)=anxn+an-1xn-1+…+a1x+a0, (5.1) где ai J, i=0.. n, называется полиномом от x над J. Полином можно за дать набором его коэффициентов (an, …, a0). Два полинома называются равны ми, если они заданы одинаковыми наборами коэффициентов. Подвыражение вида aixi называется членом i-той степени. Коэффициент при xn называется старшим коэффициентом полинома, если он отличен от нуля, то n называется степенью полинома, если равен единице, то полином называется нормирован ным. На множестве полиномов над J введем операцию суммирования и муль тисуммирования, по обычным правилам, то есть, если P(x), Q(x) заданы набо рами (an, …, a0 ), (bn, …, b0 ) соответственно, то сумма P(x)+Q(x) зададим на бором (al+bl, …, a0+b0 ), l=max(m,n), а произведение P(x) Q(x) набором a b, a b ).

( Таким образом, множество полиномов над J становится..., ii ii i + j =m+ n i + j = нетривиальным коммуникативным кольцом. Предположим, что P(x)0, Q(x) (не есть полиномы вида 0xk + … + 0 при некотором k), а m, n –их соответству ющие степени. Тогда am0, bn0 и в силу их принадлежности области целостно сти J их произведение ambn0. Поскольку ambn есть старший k коэффициент по линома P(x)Q(x), этот полином не есть 0. Из этого следует что множество поли номов от x над областью целостности J само является областью целостности.

Обозначим её через J[x]. Эта область содержит, в частности J и x.

Примечание. Если рассматривать полином как отображение xJ в P(x)J[x], то в случае конечной области J не равные между собой полиномы могут иногда осуществлять одно и тоже отражение. Например, если J[x]=Z2[x], то различные полиномы P1(x)=x3-1 и P2(x)=x5-1 равны как функции:

P1(0)=P2(0)=1, P1(1)=P2(1)=0.

5.2 Делимость Говорят, что полином P1(x) делится на полином P2(x), или P2(x) есть де литель полинома P1(x), если существует полином Q(x) такой, что P1(x)=P2(x) Q(x). Если P1(x) 0 как полином, то степень P2(x) не превосходит степени P1(x).

m n Основная теорема Пусть P1(x)= ai x i, P2(x)= bi x i 0 – многочлены i =0 i = степени m, n соответственно над областью целостности J1 и пусть коэффициент bn обратим в J. Тогда существуют единственные полиномы Q(x), R(x)J[x], на зываемые частным и остатком соответственно, для которых P1(x)=P2(x)Q(x)+R(x), (5.2) причём степень R(x) меньше степени P2(x).

Доказательство Применим метод математической индукции по степени делимого P1(x). Если P1(x)=0 или его степень меньше P2(x), то (5.2) выполняет ся для Q(x)=0 и R(x)=P1(x). Если P1(x) 0, то P1(x)= P2(x)+k, k0 ( знак сте пени многочлена). Образуем полином P?(x)=P1(x)-(am /bn ) xk P2(x). Очевидно, P?(x) P?(x). Теперь, если P?(x)=0 или P?(x) P2(x), то существование до казано;

в противном случае по предположению метода имеет место разложение типа (6.2), то есть P?(x)= P2(x)Q0(x)+R(x) для некоторых Q0(x) и R(x) с неравен ством R(x) P2(x). Из построения P?(x) находим в этом случае P?(x)= P2(x) (Q0(x)+(am/bn )xk)+R(x), что доказывает существование Q(x) и R(x). Эти полино мы входят в кольцо J[x], при этом либо R(x)=0, либо R(x) P2(x). Единствен ность доказываем от противного. Если, кроме Q(x), R(x), существуют Q1(x), R1(x), удовлетворяющие условию (6.2). Путём вычитания равенств типа (6.2) находим R(x)-R1(x)=P2(x)(Q1(x)-Q(x)), откуда P2(x)/(R(x)-R1(x)), что возможно лишь при R(x)=R1(x), и затем Q(x)=Q1(x). Теорема доказана.

Примечание Если J-поле, то коэффициент bn обратим.

5.3 Полиномиальное деление с остатком Алгоритм PDF m n Вход: P1(x)= ai x i, P2(x)= bi x i над полем, mn0, b0.

i =0 i = mn n Выход: Q(x)= qi x i, R(x)= ri x i, удовлетворяющие основной теореме.

i =0 i = Шаги алгоритма:

1 Для k от (m-n) до 0 выполнять Qk:=an+k/bn для j от (n+k-1) до k выполнять ai:=ai-qkbj-k {Основной цикл} 2 Вернуть qi, i=0..(m-n) {Коэффициенты полинома Q(x), вычисленного на шаге 1} и ri=ci, i=0..(n-1){Коэффициенты полинома R(x), вычисленные по ci, i=0..(n-1) на шаге 1} {Выход} Пример - Пусть P(x)=7x5+4x3+2x+1, P2(x)=x3+2 –полиномы с целыми коэффициентами. Так как старший коэффициент P2(x) обратим, можно приме нить PDF. (Алгоритм работает над областью целостности J при условии, что bn обратим в J). Опуская запись степеней x, имеем:

704 0 21 700 4-14 4 14 0 14 2 - Таким образом, Q(x)=7x2+4, R(x)=-14x2+2x-7.

5.4 Наибольшие общие делители полиномов над полем Определение. Евклидова область есть область целостности I с функцией степени S: IN такой, что выполняются условия:

1 S ( p1 p2 ) S ( p1 ), p1 p2 0;

2 Для любых p1 p2 I, p2 0, в I существуют элементы q, r, обладаю щие свойством евклидовости, то есть p1 = p2 q + r, S ( r ) S ( p2 ) или r = 0.

Примеры 1 I = Z, S ( p ) = ( p ) - евклидова область, так как для p1, p2 Z, p2 0, сущеествуют q, r такие, что p1 = p2 q + r, 0 r p2. Кроме того, если I – по ле, то I [ x ] c S ( p( x )) =^ ( p( x )) - евклидова область, потому что для любых p1( x ), p2 ( x ) I [ x ], p2 ( x ) 0 в I(x) существуют единственные полиномы q(x), r(x) такие, что p1( x ) = p2 ( x )q( x ) + r( x ), ^ r( x ) ^ p2 ( x ).

2 I=Q (поле рациональных чисел), S(p) = (p) не является евклидовой об ластью, потому что S(5(1/5)) = S(1) S(5), и первое условие определения евк лидовой области не выполняется. Кольцо Z[x], S(p(x)) = ^p(x) также не является евклидовой областью, так как если, например, разделить 7 x 5 + 4 x 3 + 2 x + 1 на 5 x 3 + 2, то частное не принадлежит кольцу Z[x].

Определение Говорят, полином p1(x) делится на полином p2(x) если q(x): p1(x)=p2(x)q(x). Запись: p2(x)|p1(x). Если p1(x)?0, то p2(x) p1(x).

Определение Пусть p1( x ), p2 ( x ) I [ x ], p2 ( x ) 0, I – область целост ности. Тогда наибольшим общим делителем полиномов р1(х), р2(х) называется полином ph(x) I[x], удовлетворяющий условиям:

а) ph(x) / р1(х) и ph(x) / р2(х);

б) если q(x) / р1(х) и q(x) / р2(х), то ^ q(x) ^ ph(x) и q(x) ph(x).

Обозначение : НОД[р1(х), р2(х)] = ph(x).

НОД двух полиномов в I[x], где I – область целостности и р2(х) 0, мо жно найти повторным применением алгоритма деления PDF, рассмотренного ранее. Этот процесс называется алгоритмом Евклида для полиномов. При этом имеет место следующая теорема.

Теорема Пусть p1( x ), p2 ( x ) I [ x ], p2 ( x ) 0, I – область целостности.

Тогда алгоритм Евклида дает НОД [р1(х), р2(х)] – это последний отличный от нуля остаток ph(x).

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

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

Примечание В Z НОД двух целых чисел единствен среди положитель ных;

если брать по абсолютной величине, то, например, числа 6 и 9 имеют НОД: 3 и –3.

Два полинома в I[x] называются взаимно простыми, если любой их НОД – обратимая константа из I. В этом случае говорится, что единичный эле мент кольца I – их наибольший общий делитель.

5.5 Алгоритм Евклида для полиномов над полем Теорема Пусть, p1( x ), p2 ( x ) 0 I [ x ], I – поле. Тогда существуют по u(x), v(x) I[x] такие, что линомы р1(х) v(x) + р2(х) u(x)= ph(x) (5.3) где ph(x)= НОД [р1(х), р2(х)].

Следствие Для того, чтобы два полинома р1(х), р2(х) I[x], I – поле, бы ли взаимно простыми, необходимо и достаточно существования полиномов u(x), v(x) I[x], таких, что р1(х) v(x) + р2(х) u(x)= 1.

Примечание Если u(x), v(x) соответствуют следствию,то полиномы u1( x ) = u( x ) t( x ) p1( x ), v1( x ) = v( x ) + t( x ), p2 ( x ), t I [ x ] тоже соответст вуют следствию. Полиномы u(x), v(x) не единственны;

они могут иметь произ вольно высокую степень, но ограниченную снизу.

Теорема В условиях предыдущей теоремы существуют единственные полиномы f(x), q(x), степени которых ниже степеней полиномов p1(x), p2(x) соо тветственно, для которых p1(x) q(x)+ p2(x) f(x) = ph(x), ph(x) = НОД [p1(x), p2(x)].

Конструктивное доказательство этой теоремы можно усмотреть из при веденного ниже расширенного алгоритма Евклида для полиномов.

5.6 Расширенный алгоритм для полиномов над полем Алгоритм Ext_Euclid_P Вход: р1(х), р2(х) I[x], p2 ( x ) 0, m =^ p1( x ) ^ p2 ( x ) = n;

I - поле.

Выход:

ph ( x ), f ( x ), q( x ) I ( x ) :^ f ( x ) ^ p1( x )^ p2 ( x ), ^ q( x ) ^ p2 ( x )^ ph ( x ), ph ( x ) = НОД [ p1( x ), p2 ( x )] = p1( x )q( x ) + p2 ( x ) f ( x ).

Шаги алгоритма {Инициализация} [p0(x), p1(x)]:= [p1(x), p2(x)];

[q0(x), q1(x)]:=(1,0);

[f0(x),fq1(x)]:=(0,1) {Основной цикл} Пока p1( x ) 0 выполнять q(x):=POF [p0(x), p1(x)] [p0(x), p1(x)]:= [p1(x), p0(x) - p1(x)q(x)] [q0(x), q1(x)]:=[q1(x), q0(x) - q1(x)q(x)] [f0(x), f1(x)]:= [f1(x), f0(x) - f1(x)q(x)] 3 {Выход} Вернуть [ ph ( x ), q( x ), f ( x )] := [ p0 ( x ) q0 ( x ), f 0 ( x )] Пример – Пусть p1( x ) = 7 x 5 + 4 x 3 + 2 x + 1, p2 ( x ) = 5 x 3 + 2 полиномы над полем Z11. Тогда расширенный алгоритм Евклида дает таблицу 5. Таблица 5. Фун- Итерация кция 1 2 3 8x2+ q(x) - 10x+4 8x+10 7x 7x5+4x3+2x 5x3+2 6x2+2x+ p0(x) 9x + 5x3+2 6x2+2x+ p1(x) 9x 6 3x2+ q0(x) 1 0 1 x+ 3x2+ q1(x) 0 1 x+7 3x2+8 3x3+10x2+8x+ 9x4+4x2+3x+ f0(x) 0 1 3x2+8 3 2 4 f1(x) 1 3x +10x +8x 9x +4x +3x+ +1 Проверка: (7x5+4x3+2x+1)(3x2+8)+(5x3+2)(9x4+4x2+3x+10)=6.

Ответ, который дает алгоритм, есть 6. Как ранее отмечалось, лучше в качестве ответа взять нормированный полином (разделить на старший коэффи циент) и его назвать наибольшим общим делителем данных двух полиномов Ответ: НОД [p1(x), p2(x)]=1.

Рассмотренный алгоритм можно применить к вычислению обратного полинома для данного полинома p(x)0 в Zp[x]m(x), где p(x) m(x), p-простое число, m(x)-непрерывный полином в Zp[x]. Действительно, применяем алгоритм Ext_Euclid_P к m(x) и p(x);

получаем полиномы f(x) и g(x), для которых m(x)f(x)+p(x)g(x)=1.

Затем, вычисляем значение в точке =[x]m(x),m()=0;

получается p()g()=1 в Zp[x]m(x), то есть p() обратим Zp[x]m(x).

6 Языки и грамматики Для реализации алгоритмов на ЭВМ требуется составить программу на входном языке этой машины. Обычно под входным языком понимают язык программирования высокого уровня. Такие языки предоставляют пользователю достаточно развитые изобразительные средства и дружественный интерфейс.

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

(Для промежуточного языка снова используется либо транслятор, либо интерп ретатор). Транслятор для языка высокого уровня называется компилятором. В основе методики проектирования компиляторов лежит синтаксически управля емый метод обработки языков. При этом исходная программа рассматривается как композиция разделов описания входного языка: лексики, синтактики, сема нтики, прагматики /9/.

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

6. 1 Нормальные формы Бэкуса Для описания языка программирования используется метаязык. Одним из метасинтаксических языков для языков программирования являются так на зываемые нормальные формы Бэкуса (НФБ).

В форме Бэкуса описываются объекты:

-символы языка программирования;

-имена конструкций языка (металингвистические переменные).

Металингвистическая форма состоит из двух частей (левой и правой), соединённых символом : : = (металингвистическая связка);

означающем «есть по определению». В левой части находится имя конструкции, в правой – вариа нты (один или несколько), реализующие конструкции. Если вариантов несколь ко, они разделяются символом |, означающим «или». Имена конструкции за ключаются в угловые скобки,. В расширенном варианте НФБ используются символы: [, ] – для необязательных элементов и т. д. Существенной чертой ме талингвистических форм является наличие в них рекурсий – явных и неявных.

Пример – НФБ – описание десятичного числа:

десятичное число: : = [±]цифра… цифра: : = 0/1/2/3/4/5/6/7/8/9.

Многоточие в примере означает повторение элемента.

6.2 Формальные языки и грамматики Формальным языком L над алфавитом А называется множество цепочек символов этого алфавита.

Если а1, а2, … А, то а1 … аn –цепочка длины n. Обозначения цепочек,,.... Цепочка называется подцепочкой, если =, где, тоже цепоч ки. Цепочки можно рассматривать как элементы множества * 0 1 0 1 n А =А А …= n =0 A, где А ={}, - пустая цепочка, А =А, …, А =A … A n (n раз). Множество непустых цепочек определяющихся как A+=A*\A0= =1 A n.n Длина цепочки обозначатся через ||, при этом ||=0. На множестве цепочек определяется операция конкатенации. Обозначение:. Для двух цепочек, конкатенация означает приписывание второй цепочки к первой. Например, если =ко, =нец, то ==конец. При этом ==. Операция ассоциатив на, но не коммутативна. Для записи повторяющихся символов можно исполь зовать верхний индекс. Например, xx=x2, xyxyx=(xy)2y=x(xy)2. Кроме того, мо жно писать x0 вместо, x1 вместо x.

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

6.3 Порождающие грамматики Определение Формальной порождающей грамматикой называется чет вёрки П=N, T, P, S, глее Т- конечное непустое множество символов, называ емых нетерминалами;

S – начальный символ, называемый главным нетермина лом;

P – конечное множество правил грамматики. Правила называются двумес тными отношениями вида, где, - цепочки над алфавитом V=TN, причём в левой части должен содержаться хотя бы один нетерминал ;

символ отношения – интерпретируется как «заменить на ».Здесь терминалы будем обозначать через a,b,c, …, нетерминалы – A, B, C, ….Цепочка называ ется непосредственно выводимой из цепочки в грамматике G, если =1 2, =1 2 и существует правило. Запись.

Цепочка называется выводимой из цепочки в грамматике G, если либо =, либо существует последовательность цепочек =0, 1, … n= та кая, что i+1 непосредственно выводима из I, i=0,1,…,n-1, i(NT)*. Запись.

Определение Множество всех цепочек терминальных символов, выво димых из главного нетерминала, называется языком, порождённым этой грам матикой. Обозначение: L(G)={| S, T*}.

Пример - Грамматики G=N, T, P, S, : N={I}, T={a, b, c,,, ¬, (,)}, S={I}, P={I(I I), (I I), I ¬ I, Ia, Ib, Ic} описывает язык булевых фор мул с переменными a, b, c и логическими операциями,, ¬. В частности, имеет место вывод: I(I I) ((I I) I) ((a b) c).

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

6.4 Классификация языков по Хомскому Н. Хомский (американский лингвист) предложил классифицировать фо рмальные языки по типу правил порождающих их грамматик.

Класс 0. Правила вывода имеют вид. Ограничений на строки, не вводится. Языки этого класса близки моделям естественных языков.

Класс 1 Правила вывода имеют вид, где =12, =12,, V, 1, 2 V*.

+ Грамматика называется контекстной грамматикой. Языки, порождённые грамматиками этого типа называются контекстно зависимыми. Относятся к чи слу легко распознаваемых.

Пример – Грамматика G=N, T, P, S : N={I, A, B, C, D}, T={a, b, c}, S={I}, P={IABA, BABCA, Bb, bCbb, ACDC, DCDA, DACA, Aa} имеет класс 1. Она порождает язык anbnan.

Класс 2 Все порождающие правила имеют вид: A, где A – нетерминальный символ, V+. Грамматики этого класса называются контекс тно-свободными. Они играют главную роль при формальном изучении синтак тики языков программирования.

Класс 3 Порождающее правила имеют вид: AbB или Ab, где A, B, bT. Языки этого класса называются регулярными или автоматными, а порождающие их грамматики – автоматными грамматиками. Используются на этапе лексического анализа.

Иерархия языков задаётся включением L0L1L2L3.

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

Интересно отметить, что между НФБ и КС –грамматиками имеется тесная связь;

различия касаются лишь обозначений. В частности связке «: : =» из НФБ соответствует отношение «» в КС – грамматике, металингвистическим пере менным из НФБ соответствуют нетерминалы в КС – грамматике и т.д.

6.5 Лексический анализ Лексический анализ (ЛА)- этап предварительной обработки исходной программы на лексемы и составные таблицы лексем. Сама же программа пред ставляется последовательностью пар – дескрипторов: дескриптор::=(тип лексемы, указатель), где тип лексемы – код класса лексем, указатель – ссы лка на область памяти, где хранится лексема или номер в таблице, куда поме щено значение лексемы. Наиболее распространёнными классами лексем являю тся: идентификаторы, служебные слова, разделители, константы. Содержимое таблиц дополняется на этапе семантического анализа исходной программы ге нерацией объектного кода программы.

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

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

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

Пример – Вход лексического анализатора Program Glob;

Var a, b: integer;

Begin a:=10;

b:=12;

a:=1+b;

writeln(a) End.

Выход лексического анализатора N Идентификатор N Значение константы 1 Glob 1 2 a 2 3 b Последовательность дескрипторов: (10, 1)(30, 1)(20, 1)(10, 6)(30, 2)(20,2)…(30, 3)(20, 9).

Внимание! Здесь используются таблицы:

Таблица служебных слов Таблица разделителей N Служебное N Значение конста слово нты 1 Program 1 ;

2 Begin 2, 3 End 3 + 4 For 4 5 Integer … …………………… 6 Var 9.

… … …………………… В качестве кодов типов лексем используются числа: 10(служебное сло во), 20(разделитель), 30(идентификатор), 40(константа).

6.6 Регулярные языки. Конечные автоматы Порождающая грамматика G=N, T, P, S называется регулярной, если её правила имеют вид: AaB или Cb, где A, B, CN, abT. Язык L(G), по рождаемый регулярной грамматикой, называется регулярным языком.

, Пример – G=N, T, P, S: N={I, K}, T={, u}, S={I}, P={I K, K K, K u}, где, u – терминальные I uK, K v, K символы для обозначения букв и цифр соответственно, является регулярной грамматикой, порождающей идентификаторы. Идентификатором называется последовательность букв и цифр, начинающихся с буквы. В частности, иденти фикатор uu порождается цепочкой: I K uK bK uu.

ubK Поскольку основной задачей ЛА является распознавание лексических единиц, рассмотрим одну из математических моделей распознавателя регуляр ного языка – конечный автомат (КА).

Конечным автоматом называется пятёрка A= V, Q,, q0F, где V={a1, …,am} – входной алфавит, Q={q0, q1, …, qn-1} – алфавит состояний, : QVQ – функция переходов, q0 – начальное состояние КА, FQ – множество конеч ных состояний.

Графическое представление отображения называется диаграммой сос тояний конечного автомата а. Это – ориентированный граф, вершины которого поставлены в соответствие символы алфавита состояний, а другим символы входного алфавита.

Пример – Конечный автомат для грамматики предыдущего примера имеет вид: A= V, Q,, q0F, гдеV=T={, u}, Q=N{Z}={I, K, Z}, q0={S}={I}, f={Z}. Его можно представить диаграммой состояний (рисунок 6.1).

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

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

Различают левосторонние и правосторонние выводы.

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

Пример – КС-грамматики G= N, T, P, S, N={E, R, F}, T={I, +, *, ), (}, S={E}, P={E E+R, E R, R R*F, R FF (E), F i} порождает арифметические выражение, причём идентификатору соответствует термина льный символ i, а арифметическим операциям – символы + и * ;

скобки (и) имеют обычный смысл. В частности, для терминальной цепочки i+i*I левосто ронний вывод представляется цепочкой E E+R R+R F+R I+ * * R I+R F I+F F I+I*F I + I * I, а правосторонний – цепочкой E E+R E+R*F E+R*I E+F*I E+I*I R+I*I F +I*I I + I * i.

Наглядным представлением структуры программы является дерево син таксического разбора. Дерево разбора в КС – грамматике G= N, T, P, S есть упорядоченное дерево, каждая вершина которого взвешена символом XTN.

При этом, если внутренняя вершина помечена символом А, а её прямые потом ки символами X1, …,Xk, то A X1… Xk – правило грамматики G.

На рисунке 6.2 показано дерево синтаксической разборки цепочки i+i*I для грамматики из предыдущего примера. Левостороннему выводу соответст вует обход сверху вниз, слева направо. Для правостороннего вывода ориента цию пути обхода дерева надо менять на обратную.

E R + R R R * F F F i i i Рисунок 6. 6.8 Магазинные автоматы Одной из основных задач при разборке блока синтаксического анализа транслятора является построение алгоритма распознавания языка. Этот алго ритм может быть представлен распознающим устройством. Для КС-языков ис пользуется устройства, с магазинной памятью (МП-автоматы).

Недетерминированным МП-автоматом называется семёрка M= A, Q, Г,,q0, Z0, F, где А-конечный входной алфавит;

Q-конечный алфавит состояний;

Г- конечное множество магазинных символов;

q0Q – начальное состояние ав томата;

Z0Г –начальный символ в магазинной памяти;

FQ – множество ко нечных состояний;

-отображение QAГ в QГ*.

Магазинная память определяется правилом «первый вошел – последний вышел». При записи нового символа содержимое магазинной памяти сдвигает ся в глубь на одно место, а верхнее отдается новому символу. Чтению доступен только введенный последним символ. Он после чтения либо остается в мага зинной памяти, либо извлекается. Такт работы магазинной памяти-автомата предполагает извлечение не более одного символа.

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

над магазином (ввести/вывести один символ или не менять содержимое магазина);

над состоянием (перейти в новое или остаться в прежнем);

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


Магазинная память-автомат называется магазинной памятью-распознавателем, если он имеет два выхода: «допустить», «отвергнуть».

Пример – Автомат А={0,1,}, Q={q1,q2}, Г={z, #}, где - символ конца цепочки на входной ленте, # - маркер дна магазина, q1 – начальное состояние магазина, # - начальное содержимое магазина, имеет управляющую таблицу 6.3.

Таблица 6. Магазин Вход q q10 q z q1 q ввести сдвиг ввести сдвиг отвергнуть # q ввести сдвиг отвергнуть отвергнуть Магазин Вход q20 q21 q z q отвергнуть ввести сдвиг отвергнуть # отвергнуть отвергнуть допустить Этот автомат распознает слова языка L={0n1n | n1}.

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

Таблица 6. Магазин Состояние Вход # q1 000 #z q1 00 # zz q1 0 # zzz q1 # zz q2 #z q2 # q2 Выход Допустить Существуют много других типов автоматов, применяемых в А. соответ ствующие грамматики образуют иерархию. Наиболее известны из них грамма тики предшествования /6/.

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

расп ределение памяти;

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

условия соответствия типов значе ний;

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

В конце трансляции таблица идентификаторов прекращает существование, если не используется во время выполнения программы (например, при отладке).

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

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

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

6.11 Операторные грамматики Контекстно свободные грамматики включают в себя так называемые опе раторные грамматики /10/. Правила этих грамматик таковы, что никакие два нетерминала не являются смежными в правой части. В этом случае лежащий между ними терминал можно представить как оператор. Рассмотрим частный случай операторных грамматик – грамматику операторного предшествования (ГОП).

Определим правила:

ab, если AabP;

здесь,V* и N{};

a b, если A aBP;

здесь B +b, N{} и,,V*;

ab, если A BbP;

здесь B +a, N{} и,, V*;

a, если S +a, N{}, V*;

a, если S +a, N{}, V*.

Здесь символы, и обозначают отношения предшествования:

«имеет меньшее старшинство», «имеет равное старшинство» и «имеет большее старшинство» соответственно. Сами отношения определяются на множестве T{, }, где и - новые символы, ограничивающие предложения.

Пример - EE+T T, TT*P P, P(E) x. Для этой грамматики отно шения предшествования соответствуют таблице Таблица + * ( ) x + * ( ) x Построим вывод предложения x*(x+x) в этой ГОП. Заменяя x целы ми числами, 2, 3, 4, получаем 2*(3+4). Записывая отношения предшество вания под этим выражением, замечаем, как определяется порядок вычислений.

2 *;

;

a) выберем число 2 и сохраним его в стеке:

*(3+, ;

б) аналогично удалим 3 из выражения и поместим в стек:

* ( + 4 ), ;

в) с 4 поступим подобным образом:

* ( + ), ;

г) выполним сложение двух верхних элементов в стеке и результат оста вим там же;

удалим символ +:

* ( ), ;

д) отбросим скобки:

*, ;

е) произведём умножение двух верхних элементов стека, оставляя ре зультат в стеке;

удалим символ *:

;

ж) останов;

ответ находится в стеке.

6.12 Представление промежуточной программы Промежуточная программа представляет собой линейную запись синта ксического дерева программы, легко транслируемую в магнитный код. основ ными терминальными символами промежуточной программы являются опера торы и операнды. Операторы представляются внутри компилятора числовыми кодами, а операнды – указателями на соответствующие таблицы и идентифика торов. Одной из форм представления промежуточной программы является постфиксная польская запись, которая (в отличие от инфиксной) указывает по рядок выполнения операций. Например арифметическое выражение а+b*c в постфиксной польской записи будет выглядеть как аbc*+d+. Расшифровка в постфиксной польской записи выглядит очень просто: выражение просматри вается слева направо, и его элементы помещаются в стек. Если очередной эле мент – знак операции, то (в случае двухместной операции) два верхних элемен та извлекаются из стека, над ними выполняется операция и результат помещае тся в стек;


операция удаляется из входной строки, просмотр продолжается. В постфиксной польской записи можно представить также все операторы исход ной программы. Например, условный оператор if выражение then опера тор1 else оператор2 будет иметь вид: выражение метка1 BZ опера тор1 метка2 BR метка1 оператор2 метка2. Здесь BZ – бинарная опе рация, которая осуществляет переход на метка1, если значение выражение - ложь;

BR – унарная операция, осуществляющая безусловный переход на ме тка2.

Упражнения 1 Доказать, что множество всех рациональных чисел, меньших e (основа ние натуральных алгоритмов), разрешимо.

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

3 Множество тех n, для которых в числе есть не менее n девяток по дряд, разрешимо. Доказать.

4 Доказать перечислимость пересечения и объединения перечислимых множеств.

5 Доказать перечислимость декартова произведения ABNN, если AN и BN перечислимы.

6 Доказать перечислимость множества диофантовых уравнений, то есть уравнений вида P(x1,…,xn)=0, где P – многочлен с целыми коэффициентами.

7 Выяснить перечислимость множества показателей n, для которых суще ствует решение уравнения xn+yn=zn в целых числах.

8 Доказать, что действительное число вычислимо тогда и только тогда, когда множество рациональных чисел, меньших, разрешимо.

9 Пусть U – перечислимое множество пар натуральных чисел, универса льное для класса всех перечислимых множеств натуральных чисел. Доказать, что его «диагональное сечение» K={x|(x,x)U} является перечислимым нераз решимым множеством.

10 Некоторое множество S натуральных чисел разрешимо. Разложим все числа из S на простые множители и составим множество D всех простых чи сел, встречающихся в этих разложениях. Можно ли утверждать, что множество D разрешимо?

11 Построить главную универсальную функцию.

12 Пусть U – главная универсальная функция. Докажите, что для любой вычислимой функции V(m,n,x) существует такая всюду определённая вычис лимая функция S(m,n), что V(m,n,x)=U(s(m,n),x) при всех m,n и x.

13 Пусть h – всюду определённая вычислимая функция, у которой мы хотим найти неподвижную точку. Вычисляющий её алгоритм, допустим, имеет вид:

function Compute_h(x:String):String;

begin … end;

Используя процедуру GetProgramText(var s:String), помещающую текст исходной программы в строку s, записать программу, являющуюся неподвиж ной точкой функции h. Указание: Использовать также процедуру ExecutePro gram(s:String), которая передаёт управление программе, текст которой находит ся в строке s.

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

15 Пусть X, Y – два различных множества. Рассмотрим программы, име ющие доступ к двум оракулам для X и для Y и функции, которые можно вычи слить с помощью таких программ. Укажите такое множество Z, что X – Y – вы числимость совпадает с Z – вычислимостью.

16 Описать конструкцию функции Аккермана.

17 Составить программу для решения на машине Тьюринга задачу удвое ния числа.

18 Составить схему примитивной рекурсии для двуместных функций [x/y] – неполное частное, rest(x,y) – остаток от деления x на y.

19 Составить нормальный алгоритм для функции (x)=x+1.

20 Доказать, что алгоритм распознавания несамоприменимости нормаль ных алгоритмов невозможен.

21Как работает сортировка вставками на входе A=(31,41, 59, 26, 41, 58)?

22 Измените процедуру сортировки вставками так, чтобы она сортирова ла числа в невозрастающем порядке.

23 Рассматривается задача поиска.

Вход: Последовательность n чисел A=(a1,…,an) и число v.

Выход: Индекс i, для которого v=A[i] или NIIL.

Напишите алгоритм (линейного поиска), который последовательно про сматривает A в поисках v.

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

25Дана последовательность чисел x1,…,xn. Покажите, что за время (nlog(n)) можно определить, есть ли в этой последовательности два одинако вых числа.

26 Как записать выражение n3/1000-100n2-100n+3 с помощью - обозна чений?

27 Даны коэффициенты a0,…,a n-1 многочлена;

требуется найти его значе ние в заданной точке x. Естественный алгоритм требует времени (n2). Как вы полнить вычисления за время (n), не используя дополнительного массива?

n Используйте «схему Горнера»: a i x i=(…(an-1x+an-2)x+…+a1)x+a i = 28 Покажите работу сортировки слиянием для массива A=(3, 41, 52, 26, 38, 57, 9, 49).

2, если n = 2, 29 Покажите по индукции, что если T(n)={ 2T (n / 2), если n = 2 n, то T(n)=nlog(n) (при всех n, являющихся степенями двойки).

30 Сортировку вставками можно оформить как рекурсивную процедуру:

желая отсортировать A[1..n], мы (рекурсивно) сортируем A[1..(n-1)], а затем ставим A[n] на правильное место в отсортированном массиве A[1..(n-1)]. На пишите рекуррентное соотношение для времени работы такой процедуры.

31 Пусть сортировки вставками и слиянием исполняются на одной и той же машине и требуют 8n2 и 64n log(n) операций соответственно. Для каких зна чений n сортировка вставками является более эффективной?

32 При каком наименьшем значении n алгоритм, требующий 100n2 опе раций, эффективнее алгоритма, требующего 2n операций?

33 Пусть f(n) и g(n) – неотрицательны для достаточно больших n. Пока жите, что max(f(n), g(n))=(f((n)+g(n)).

34 Покажите, что (n+f)b= (nb) для любого вещественного a и для любого b0.

35 Можно ли утверждать, что a) 2n+1=O(2n);

b) 22n =O(2n).

36 Приведите пример функций f(n) и g(n), для которых f(n)=О(g(n)),но f(n) о(g(n)) и f(n) (g(n)).

37 Покажите, что свойства f(n)=o(g(n) и f(n)= g(n не могут быть выпол нены одновременно.

38 Докажите, что log(n!)= (nlog(n)) и что n!=o(nn).

39 Будет ли функция log(n) ! полиномиально ограниченной? Будет ли функция log(log(n)) полиномиально ограниченной?

40 Покажите, что из T(n)=T(n/2)+1 cледует T(n)=O(log(n)), а из T(n)= T(n/2+n следует T(n)=(nlog(n)), и тем самым T(n)= (nlog(n)).

41 Используя основную теорему, найдите асимптотически точные оценки для соотношений:

а) T(n)=4T(n/2)+n;

б) T(n)=4T(n/2)+n2.

42 Используя основную теорему, покажите, что соотношение T(n)=T(n/2)+ (1) (для двоичного поиска) T(n)= (log(n)).

43 Докажите, что для непрерывной задачи о рюкзаке выполнен принцип жадного алгоритма.

44 Разработайте основанный на динамическом программировании алго ритм для решения дискретной задачи о рюкзаке. Алгоритм должен сработать за время O(nW), где n – количество вещей, W – максимальный вес рюкзака.

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

46 Найдите код Хаффмена для алфавита, в котором частоты символов со впадают с первыми восемью числами Фибоначчи: a:1 b:1 c:2 d:3 e:3 f:8 g: h:21Что будет, если в алфавите n символов, частоты которых совпадают с пер выми n числами Фибоначчи?

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

48 Пусть S – конечное множество, k – натуральное число, Ik – семейство всех подмножеств S, содержащих не более k элементов. Покажите, что (S, Ik) – матроид.

49 Покажите, что отношение p транзитивно, то есть из L1 pL2 и L2 pL следует L1 pL3.

50 Множество вершин VV графа G=(V, E) называется независимым, если никакие две его вершины не соединены ребром. Задача о независимом множестве состоит в отыскании в данном графе независимого множества мак симального размера. Сформулируйте соответствующую задачу разрешения и докажите её - полноту.

51 Показать, что в алгебре N;

+ число 2 порождает множество всех по ложительных чисел, число 1 – положительных чисел, а совокупность {0;

1} по рождает всю алгебру.

52 Выяснить, что все подалгебры алгебры N;

+;

- исчерпываются следу ющими: 1) подалгебра, порожденная нулем и состоящая из него;

2) подалгебра, порожденная числом 1 и совпадающая с самой алгеброй;

3) подалгебра, порож денная произвольным числом a1 и состоящая из чисел 0, а, 2а, 3а,… 53 Каждая подалгебра алгебры N;

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

Доказать.

54 Рассмолтрим алгебру N;

+, *, -, где “-“ – частичная операция:

x y, x y, Какие функции представляются термами: 0(x-(x+1)), (x-y)+y, x y = &, x y.

(x+y)-y? Показать, что функция 2-х переменных не может быть представлена термом в указанной алгебре (т.е. термом, записанным в алфавите {x, +, *, -}).

55 Операция подстановки одноместной функции в одноместную функ цию дает снова одноместную функцию. Эту операцию обозначим *. Таким образом, по определению f * g = S (f,g), (f * g)(x) =f (g(x)) Операция * ассоциативна, но не коммутативна: f * (g*h)= (f*g) * h, s * sg = sg * s Показать, что для любой одноместной функции f I11*f=f*I11, f-1*f*f-1=f-1.

Если f-1 всюду определена, то (f* f-1)(x)=x.

Показать, что существуют одноместные функции f, для которых f-1 всюду определена и в то же время f-1fI11.

56 Для двуместных функций введем операцию полагая f(x,y)=f(x,y).

Операция удовлетворяет следующим соотношениям: f=S3(f,I22,I12), µx(f(x,y)=z)=(Mf)(y,z).

57 Если x-вещественное число, то символом [x] обозначим целую часть x, т.е. наибольшее целое число, не превосходящее x. Показать, что функция q(x)=x-[ x]2 удовлетворяет соотношениям q-1(2x)=x2+2x, q-1(2x+1)=x2+4x+2.

58 Пусть F-множество всех частичных функций на N от любого числа переменных. F;

M,R,S, S, …. Основное определение частичной рекурсивнос ти дает: совокупность всех частичных функций, частично рекурсивных относи тельно заданной системы частичных функций G, есть подалгебра алгебры (1), порожденная в (1) системой G, Imn, O, S.

Обозначим через Fl совокупность всех всюду определенных функций из F и рассмотрим частичную подалгебру Fl;

Ml, R, S2, S3,… (2) алгебры (1). Тогда совокупность всех общекурсивных функций есть подалгебра алгебры (2), порожденная в (2) простейшими функциями 0,s,Imn.

59 Доказать, что каждая всюду определенная функция, равная натура льному числу a везде, за исключением конечного числа точек, является прими тивно рекурсивной.

60 Доказать примитивную рекурсивность двуместных функций [x/y], rest (x,y), где [x/y] означает (неполное) частное, а rest(x,y) - остаток от деле ния x на y. По определению полагаем также, что [x/0]=x и rest (x,0)=x.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1 Новиков П.С. Элементы математической логики. - М: Наука, 1973. 328с.

2 Новиков Ф.А. Дискретная математика для программистов. – СПб: Пи тер, 2000. – 304с.

3 Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. – М.: МЦНМО, 1999. – 176с.

4 Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392с.

5 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 1999. – 960с.

6 Информатика / Учебное пособие для пед. спец. высш. учеб. заведений. – М.: Просвещение, 1991. – 288с.

7 Поддубная Л.М., Шаньгин В.Ф. Мне нравится Паскаль. – М.: Радио и связь, 1992. – 160с.

8 Акритас А.Основы компьютерной алгебры с приложениями./ Пер. с англ. – М.: Мир, 1994. – 544с.

9 Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программиро вание. / Учебное пособие для высших и средних учебных заведений. – СПб:

КОРОНА принт, 2000. – 256с.

10 Кук Д., Бейз Г. Компьютерная математика. / Пер. с англ. – М.: Мир, 1990. – 384с.



Pages:     | 1 | 2 ||
 





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

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