Шпаргалка по "Теории Алгоритмов"

Определение 3. Множество MÍN называется (рекурсивно, или эффективно, или алгоритмически) перечислимым, если М либо пусто, либо есть область значений некоторой вычислимой функции или, другими словами, если существует алгоритм для последовательного порождения (перечисления) всех его элементов.

Пример. Рассмотрим множество М={1,4, 9, 16, 25, 36, …} квадратов натуральных чисел. Оно перечислимо: для получения его элементов нужно последовательно брать числа 1, 2, 3, 4,… и возводить их в квадрат. Другими словами, М есть область значений вычислимой функции f(x)= x²;  
М={1², 2², 3², 4²,…}. Более того, это множество является также и разрешимым: для проверки того, принадлежит или нет некоторое число данному множеству, нужно разложить число на простые множители, что позволит выяснить, является ли оно точным квадратом.

Теорема 1. Если множества М и L перечислимы, то перечислимы множества МÇL и МÈL.

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

Теорема 3. Существует перечислимое, но неразрешимое множество натуральных чисел.

7. Частичная рекурсивность функций, вычислимых на машинах Тьюринга.

Теорема 10.3. Всякая арифметическая функция, вычислимая на машинах Тьюринга, является частично рекурсивной функцией. Доказательство этой теоремы - дополнительный материал, который можно при первом чтении опустить. Доказательство Пусть м.Т.   вычисляет функцию f(x₁,…, x_n). Пусть также Q ={q₀,q₁,… ,q _k-1 }, q_f=q₁ и Σ = {a₀= , a₁, … , a _R-1= | }. Предположим также, не ограничивая общности, что   никогда не пишет пустой символ   (как перестроить программу произвольной м.Т., чтобы она удовлетворяла этому условию ?). Определим кодирование элементов конфигураций   целыми числами. Пусть конфигурация   имеет вид K=(w₁,q_i,a_j,w₂), где   - слово на ленте левее головки,q_i - состояние м.Т., a_j - наблюдаемый в данной конфигурации символ и w₂= a_j0a_j1 … a_jp} - слово на ленте правее головки. Кодом символа a_j   Σ будет число j, кодом состояния q_i - число i. Слова w₁ и w₂ будем рассматривать как числа в R-ичной системе счисления, читаемые в противоположных направлениях (из наших предположений следует, что i_m   0 при m >0и j_p   0 при p>0) :

и т.д.

 

8. Понятие алгоритмической неразрешимости проблем, примеры.

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

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

Массовая проблема (П) называется алгоритмически разрешимой, если соответствующая ей характеристическая ф-ия вычислима.

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

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

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

М-ды:

1) «от противного» 2)метод сведения проблем

П1 сводится к массовой П2, когда существует алгоритм А, который  для любой индивидуальной задачи П1 строит индивидуальную задачу П2, так  что индивидуальная задача П1 имеет ответ Да тогда и только тогда, когда индивидуальная задача П2 может иметь ответ ДА.

Примеры

П распознавания самоприменимости алгоритмов – это П построения единого м-да алгоритма.

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

Проблема распознавания  самоприменимости алгоритмов алгоритмически неразрешима.

 

9. Анализ временной сложности алгоритмов. Асимптотические обозначения, порядок роста.

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

Физ.время работы алгоритма -  это величина примерно равная произведению кол-ва элементов операций, выполняемых в ходе работы алгоритма на среднее время выполнения 1ой элемента операции.

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

Пример Сортировка вставками

1)  For i:=2 to n do begin                           C1          n

2)   x:=A[i];                                                C2         n-1

3)  j:=i-1;                                                    C3         n-1

4) While (j>0) and (A[j]>x) do begin        C4      

5) A[j+1]:=A[i];                                        C5     

6) dec(j);   end;                                           C6     

 

7) A[j+1]:=x; end;                                      C7       n-1

Тогда время работы алгоритма  будет определяться выражением

.

Асимптотические обозначения

Определение 1. Говорят, что время работы алгоритма T(n) имеет порядок роста g(n), если существуют натуральное число n₀ и положительные константы c₁ и c₂ (0<c₁≤c₂), такие, что для любого натурального n начиная с n₀ выполняется неравенство c₁∙g(n)≤T(n)≤ c₂∙g(n). Обозначение: T(n)=Θ(g(n)).

 

Замечание. Говорят, что время работы алгоритма T(n) имеет порядок роста g(n) (T(n)=Θ(g(n))), если и сверху и снизу время работы ограничено функцией с одной и той же степенью роста, если это не так, то говорят о верхних (оценка худшего случая) и нижних (оценка лучшего случая) оценках.

Определение 2. Говорят, что время работы алгоритма T(n) имеет нижнюю оценку g(n), если существуют натуральное число n₀ и положительная константа c, такие, что для любого натурального n начиная с n₀ выполняется неравенство c∙g(n)≤T(n). Обозначение: T(n)=Ω(g(n)).

Определение 3. Говорят, что время работы алгоритма T(n) имеет верхнюю оценку g(n), если существуют натуральное число n₀ и положительная константа c, такие, что для любого натурального n начиная с n₀ выполняется неравенство T(n)≤ c∙g(n). Обозначение: T(n)=О(g(n)).

Таким образом, для сортировки вставками справедливы следующие  оценки: T(n)=Ω(n) и T(n)=О(n²).

Пример. Доказать, что функция T(n)=3∙n³+2∙n² имеет верхнюю оценку О(n³).

Положим n₀=1, тогда должно выполняться неравенство . Преобразуем это неравенство , т. е. с≥5.

Таким образом, найдены  натуральное число n₀=1 и положительная константа c=5, такие, что для любого натурального n начиная с n₀ выполняется неравенство 3∙n³+2∙n²≤ c∙ n³, следовательно, T(n)=О(n³).

10. Время работы алгоритма в худшем, среднем, лучшем случаях. Порядок роста.

Лучший  случай – самый благоприятный случай, когда массив уже отсортирован, тогда на каждой итерации внешнего цикла действие цикла While (4-я строка алгоритма) прекращается сразу же после первой проверки, следовательно, все t_i=1, тогда , , т. е.

  Худший случай – массив отсортирован в обратном порядке, тогда на каждой i-й итерации внешнего цикла 4-я строка алгоритма выполняется i раз, следовательно, все t_i=i. Тогда

,

, т. е.

Определение 1. Говорят, что время работы алгоритма T(n) имеет порядок роста g(n), если существуют натуральное число n₀ и положительные константы c₁ и c₂ (0<c₁≤c₂), такие, что для любого натурального n начиная с n₀ выполняется неравенство c₁∙g(n)≤T(n)≤ c₂∙g(n). Обозначение: T(n)=Θ(g(n)).

 

Замечание. Говорят, что время работы алгоритма T(n) имеет порядок роста g(n) (T(n)=Θ(g(n))), если и сверху и снизу время работы ограничено функцией с одной и той же степенью роста, если это не так, то говорят о верхних (оценка худшего случая) и нижних (оценка лучшего случая) оценках.

Определение 2. Говорят, что время работы алгоритма T(n) имеет нижнюю оценку g(n), если существуют натуральное число n₀ и положительная константа c, такие, что для любого натурального n начиная с n₀ выполняется неравенство c∙g(n)≤T(n). Обозначение: T(n)=Ω(g(n)).

Определение 3. Говорят, что время работы алгоритма T(n) имеет верхнюю оценку g(n), если существуют натуральное число n₀ и положительная константа c, такие, что для любого натурального n начиная с n₀ выполняется неравенство T(n)≤ c∙g(n). Обозначение: T(n)=О(g(n)).

Таким образом, для сортировки вставками справедливы следующие  оценки: T(n)=Ω(n) и T(n)=О(n²).

11.Анализ сортировки  методом прямого включения.

VAR 

I,J,N,X:INTEGER; 

A:ARRAY[0..50] OF INTEGER;

BEGIN 

WRITELN(‘Введите  длину  массива’); 

READ(N); 

WRITELN(‘Введите  массив’); 

FOR I:=1 TO N DO READ(A[I]); 

FOR I:=2 TO N DO BEGIN  

X:=A[I];  

A[0]:=X;  

J:=I;  

WHILE X<A[J-1] DO BEGIN   

A[J]:=A[J-1];   

DEC(J)  

END;  

A[J]:=X 

END; 

WRITELN('Результат:'); 

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

Такой  типичный  случай  повторяющегося  процесса  с  двумя  условиями  окончания  позволяет  нам  воспользоваться  хорошо  известным  приемом “барьера” (sentinel). Анализ  метода  прямого  включения. Число  сравнений  ключей  (C_i)  при  i- м  просеивании  самое  большее  равно  i-1, самое  меньшее – 1; если  предположить, что  все  перестановки  из  n ключей  равновероятны, то среднее  число  сравнений – I/2. Число  же  пересылок  M_i  равно C_i + 2(включая  барьер). Поэтому  общее  число  сравнений  и   число  пересылок  таковы: 

 

C_min = n-1                 (2.1.)                  M_min = 3*(n-1)                    (2.4.)

C_ave = (n²+n-2)/4      (2.2.)                  M_ave = (n²+9*n-10)/4          (2.5.)

C_max = (n²+n-4)/4     (2.3.)                  M_max = (n²+3*n-4)/2  

17.Анализ временной сложности рекурсивных алгоритмов. Сортировка слиянием.

Сортировка  слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. 
Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе. 
Для решения задачи сортировки эти три этапа выглядят так: 
1. Сортируемый массив разбивается на две части примерно одинакового размера; 
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; 
3. Два упорядоченных массива половинного размера соединяются в один. 
Cортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. А именно, вместо разделения по опорному элементу массив просто делится пополам.// a - сортируемый массив, его левая граница lb, правая граница ub template<class T> 
void mergeSort(T a[], long lb, long ub) { long split; // индекс, по которому делим массив 
if (lb < ub) { // если есть более 1 элемента 
split = (lb + ub)/2; 
mergeSort(a, lb, split); // сортировать левую половину  
mergeSort(a, split+1, last);// сортировать правую половину  
merge(a, lb, split, ub); // слить результаты в общий массив}} 
Функция merge на месте двух упорядоченных массивов a[lb]...a[split] и a[split+1]...a[ub] создает единый упорядоченный массив a[lb]...a[ub]. 
Пример работы на последовательностях 2 3 6 7 и 1 4 5 
Результатом является упорядоченная последовательность, находящаяся в буфере. Каждая операция слияния требует n пересылок и n сравнений, где n - общее число элементов, так что время слияния: Theta(n). 
template<class T> 
void merge(T a[], long lb, long split, long ub) {// Слияние упорядоченных частей массива в буфер temp 
// с дальнейшим переносом содержимого temp в a[lb]...a[ub] 
// текущая позиция чтения из первой последовательности a[lb]...a[split] 
long pos1=lb; // текущая позиция чтения из второй последовательности a[split+1]...a[ub] 
long pos2=split+1; // текущая позиция записи в temp 
long pos3=0;  
T *temp = new T[ub-lb+1]; // идет слияние, пока есть хоть один элемент в каждой последовательности 
while (pos1 <= split && pos2 <= ub)