Алгоритмы (Computer Science) 2008 г. Осенний семестр, Третий курс. - презентация

1 Алгоритмы (Computer Science) 2008 г. Осенний семестр, Третий курс

2 Примерный план Бинарный поиск Сортировка Структуры данных Двоичное дерево поиска Хэш-таблицы Алгоритмы для строк Суффиксное дерево Сложность текста и сжатие Графы, поиск в ширину и в глубину Связная компонента, покрывающее дерево, Эйлеров цикл Оптимальный путь и динамическое программирование Полукольца Минимальное время работы сортировки NP и NP-полные задачи Примеры NP-полных задач Стохастические алгоритмы

3 Пример: упорядочить числа

4 Алгоритм 1. Идем вдоль массива и находим инверсию 2. Находим в массиве место куда надо вставить «неправильный» элемент 3. Освобождаем место для вставки 4. Вставляем элемент 5. Идем дальше вдоль массива до следующей инверсии 6. Переходим к шагу 2

5 Алгоритмы везде! Как попасть на лекцию 1. Выйти из дома и дойти до остановки автобуса 2. Доехать до станции метро 3. Сесть в поезд и доехать до станции «Университет» 4. Дойти до факультета 5. Подняться на 4-й этаж 6. Войти в аудиторию

6 Алгоритм предполагает умение Надо уметь ходить Надо знать в какой автобус сесть Надо уметь войти в метро и сесть в правильном направлении Надо знать как дойти до факультета

7 Алгоритмы для компьютера Нам важно, что Компьютер состоит из процессора и памяти Процессор умеет делать некоторые элементарные операции (сложение, сравнение и т.п.) Есть линейная память Большинство компьютеров имеет один или небольшое (ограниченное) количество процессоров

8 Алгоритм для компьютера Входные данные Программа Временные данные Результат Входные данные Программа Временные данные Результат Это одна и та же программа!

9 Свойства алгоритма Для любых входных данных алгоритм должен закончить свою работу за конечное время Следствие. Алгоритм использует конечное количество памяти Результат должен соответствовать поставленной задаче

10 Элементы булевой алгебры Булева переменная принимает одно из значений true (истина) или false (ложь) Основные операции : – or – логическое или – and – логическое и – not – отрицание

11 Значение булевой функции обычно записывают в виде матрицы… andX Y& not~ orx y|

12 … или таблицы X, Yand X, Yor Xnot X,Y,Zf (X,Y,Z)

13 Пример F(X,Y) = ( X & Y ) | ( X & ~Y) = ? x y F(X,Y) X

14 Несколько дополнительных функций XORx y^ EQx y== x y=>

15 Задачи Сколько всего разных булевых функций от двух переменных ? от n переменных? Написать таблицу значений для функций: f1= ((x & y) | (x & z)) & ~ z f2= (x & y) | (~x & ~y) f3= (x & y) | ~(x &~y) | ~(~x & y) | (~x & ~y) f4= (x & y) | (x &~y) | (~x & y). что э то за функция?

16 Задача потруднее Построим булеву функцию от n переменных x1,x2,…,xn следующим образом: для начала напишем все комбинации вида ([~]x1 & [~]x2 & … & [~]xn), где [~] означает, что в каких-то комбинациях берем отрицание, а в каких-то – нет. Сколько всего разных комбинаций такого вида? Затем все полученные комбинации объединяем знаком |. Чему равно значение этой функции. Потренируйтесь на n=1,2,3. Выдвиньте гипотезу. Докажите ее.

17 Важные тождества ~ ( X | Y ) ( ~X ) & ( ~Y ) ~ ( X & Y ) ( ~X ) | ( ~Y ) X | true true X & true X X | false X X & false false X ^ Y ( X | Y ) & (~X | ~Y ) X==Y ( X & Y ) | (~X & ~Y ) X ^ Y ~(X==Y)

18 Теорема Любая логическая функция любого количества аргументов может быть представлена в виде комбинации операций not, or, and

19 Соображения к доказательству x y zff = 0001(~x &~y &~z)| 0010false 0100false 0110false 1001(x &~y &~z)| 1011(x &~y & z)| 1100false 1111(x &y &z)

20 Доказательство Доказательство по индукции. для n=1: есть 4 типа функции от одной переменной: true, false, x, ~x. (x | ~x); (x & ~x); (x); (~x) Для любого n f(x 1,x 2,…,x n-1,x n )= (f(x 1,x 2,…,x n-1, true) & x n ) | (f(x 1,x 2,…,x n-1,false) &~x n ) Отметим, что f(x 1,x 2,…,x n-1, true) и f(x 1,x 2,…,x n-1,false) являются функциями n-1 переменной, и по предположению индукции могут быть представлены в виде комбинации базовых операций

21 Двоичная и шестнадцатеричная арифметика * =00004=01008=1000C=1100 1=00015=01019=1001D=1101 2=00106=0110A=1010E=1110 3=00117=0111B=1011F=1111

22 Основные типы данных Байт Целое число без знака Целое число со знаком Число с плавающей точкой

23 Организация данных в памяти (очень приблизительно) тип размер byte1 int4 float4 double8 pointer(4) BF C BF C BF C BF C BF C BF C BF C BF C BF C BF C BF CA BF CB BF CC BF CD BF CE BF CF BF D BF D BF D BF D3 0A0ABF21FAC1C0A C BFC5 bintfloatbbintpointer Адреса Данные

24 Массивы BF21FAC1C0A C BF0A0AC5 A[0]A[1]A[2]A[3]A[4] Пронумерованное множество заранее определенного размера: A[0..5] К элементу можно обратиться по его индексу (номеру) A[0] A[i] Массив лежит в памяти подряд! Размер всех элементов одинаковый

25 Более сложные данные (структуры) валя иванов петров сидоров тяня Телефонный номер: иванов петров сидоров таня валя

26 Отступление про использование указателей тяняpWash5667 валяpWash7654 ивановpMoscow1234 петровpChicago2345 сидоровpChicago4556 pWash301 pMoscow095 pChicago312 Таблица кодов Изменение одного кода приводит к одновременному изменению кодов в основной таблице

27 Структуры Описание структуры: Telephone { byte name[14]; byte areaCode[3]; byte phone[4]; } Отдельная запись выглядит так: Telephone Ivanov; Доступ к элементам структуры будем записывать так: code = Ivanov.areaCode;

28 Массив Пронумерованное множество заранее определенного размера Telephones[5] К элементу можно обратиться по его индексу (номеру) Ivanov=Telephones[0] Persone=Telephones[i] Массив лежит в памяти подряд! Размер всех элементов одинаковый Массив не обязательно упорядочен

29 Поиск в массиве Задача: найти Сидорова 1.i=0 2. Берем элемент i 3. Проверим не Сидоров ли он 4. Если Сидоров, то Ура 5. Иначе переходим с следующему элементу: i=i+1 6. Если массив не кончился, то идем к 2 7.Увы!

30 Другая запись Telephone SearchPersoneByName (String searchName ) { for(i=0; i

31 Анализ алгоритма Сколько записей надо просмотреть, чтобы найти Сидорова? Если Сидорова нет, то nTelephones Если он есть, то примерно nTelephones/2 Итого: время поиска пропорционально N T=O(N)

32 Чем хороши упорядоченные (сортированные) массивы ? Вспомним, как ищется слово в словаре. Алгоритм: Делим массив пополам. Проверяем, попало ли слово на середину, и если да, то Ура Смотрим, следует ли искать слово в левой или в правой половине Ищем в соответствующей половине Для такого поиска хорошо бы иметь процедуру поиска в части массива

33 Схема поиска слова "Добро" Автор Ангар Бензин Викинг Добро Квадрат Клюв Лень Обзор Пингвин Порыв Рассвет Сказка Яхта Автор Ангар Бензин Викинг Добро Квадрат Клюв Лень Обзор Пингвин Порыв Рассвет Сказка Яхта Автор Ангар Бензин Викинг Добро Квадрат Клюв Лень Обзор Пингвин Порыв Рассвет Сказка Яхта Автор Ангар Бензин Викинг Добро Квадрат Клюв Лень Обзор Пингвин Порыв Рассвет Сказка Яхта Автор Ангар Бензин Викинг Добро Квадрат Клюв Лень Обзор Пингвин Порыв Рассвет Сказка Яхта

34 Схема алгоритма 0,N i1 =N/2 0, i1 i2=i1/2 i1,N i2=(i1 +N)/2 0, i2 i3=i2/2 i2, i1 i3=(i2+i1)/2 i1,i2 i3=(i1 +i2)/2 0, i3 i4=i3/2 i3, i2 i4=(i3+i2)/2 i2, i3 i4=(i3+i2)/2 i3,i1 i4=(i1 +i3)/2 i2,N i3=(i2 +N)/2 i3,N i4=(i3 +N)/2 i1, i3 i4=(i1+i3)/2 i3, i2 i4=(i3+i2)/2 i2,i3 i4=(i2 +i3)/2 0, i2 i3=i2/2 i2, i1 i3=(i2+i1)/2 i2,N i3=(i2 +N)/2 i2, i1 i3=(i2+i1)/2 i1,i2 i3=(i1 +i2)/2 i2, i1 i3=(i2+i1)/2 i1,i2 i3=(i1 +i2)/2 i2, i1 i3=(i2+i1)/2 i2,N i3=(i2 +N)/2 ip, iq is=(ip+iq)/2 ip, isis, iq Дерево бинарного поиска

35 Бинарный поиск Telephone BSearch(String name) {return BSearch(name,0,nTelephones);} Telephone BSearch (String name, int i0, int i1) { if(i0 == i1) return not found; int i=(i0+i1)/2; if(Telephones[i].name == name) return Telephones[i]; if(Telephones[i].name > name) return BSearch (name, i0, i); else return BSearch (name, i+1, i1); }

36 Рекурсия В программе мы вызывали функцию из себя самой. Это называется рекурсией Еще пример рекурсии – рекурсивное представление факториала: factorial(n)={1, n==1; n*factorial(n-1)} Рекурсивные вычисления – это продолжение метода математической индукции.

37 Анализ алгоритма В худшем случае время работы алгоритма равно количеству делений массива пополам, т.е. высоте дерева поиска. Если высота дерева известна и равна k, то возможно k делений, и для размера массива N имеем оценку: 2 k-1 N 2 k или k-1 log 2 N k Откуда получаем, что время работы алгоритма T(N)=O(logN)

38 Сравнение с наивным алгоритмом поиска Наивный алгоритм: T naive (N)=O(N) Бинарный поиск: T binary (N)=O(logN) Если размер массива 10 6 (это один миллион), то T naive = * 10 6 = 10 T binary = * log(10 6 ) = 2*10 -4 Это время на элементарный шаг

39 Как правильно сортировать массив? MergeSort Представим себе, что массив разбит на два отсортированных подмассива: и мы умеем сливать два отсортированных массива. Тогда Разбиваем массив пополам Сортируем каждую половину и сливаем

40 А как сортировать каждую половину? MergeSort(A,i1,i2) { if(i1==i2) return; i=(i1+i2)/2; A1=MergeSort(A, i1, i); A2=MergeSort(A, i+1, i2); Merge(A1,A2,A); } Разбиваем ее пополам, каждую половину от половины сортируем и потом сливаем.

41 Слияние массивов > > > < < < < Задание: Написать программу слияния массивов

42 Анализ Алгоритма Время работы: T(N)=2*T(N/2)+O(N) Есть теорема, показывающая, что в этом случае T(N)=O( N*log (N)) Недостаток: нужен дополнительный массив

43 Теорема о рекурсии Merge-Sort Если T(N)=2*T(N/2)+O(N) 2*T(N/2)+bN то существует C такое, что для любого N T(N) C N log N Индукция : При N=3 T(N) равен чему-то, например, T(3) = с 3 log 3. Допустим Допустим, утверждение верно для n/2. Тогда T(n) 2 T(n/2)+ bn C n log n/2 +bn = = C n log n + n (b - C log 2) [полагая С > b/log2 ] C n log n

44 Быстрая сортировка QSort Свойство отсортированного массива. Массив отсортирован тогда и только тогда, когда для любого элемента q все элементы массива слева не больше его, а все элемента справа – не меньше Идея: для какого-нибудь q переставим элементы массива так, чтобы все, что слева было меньше всего, что справа (при этом не будем заботиться об упорядоченности левой и правой частей)

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

46 QSort QSort (Array A) {QSort (A, 0, N);} QSort (Array a, int i0, int i1) { if(i0==i1) return; int i=Partition (A,i0,i1); QSort (A,i0,i); QSort (A,i+1,i1); } Задание: написать процедуру Partition

47 Анализ алгоритма QSort Точный анализ выходит за рамки курса Алгоритм делит массив на части, но не равные. В среднем происходит деление почти пополам, так что в среднем оценка T=O(N log(N)) Худший случай – когда массив уже отсортирован. В этом случае время работы алгоритма T=O(N 2 ) Можно за время O(N) перетасовать массив случайным образом и затем отсортировать его за время T=O(N log(N))

48 Что лучше? По мере добавления элементов вставлять их на правильное место Сначала собрать массив, а потом отсортировать. Сборка массива: на каждом этапе надо найти место для вставки: T~log i сделать вставку T~i Итого

49 Упорядоченный массив - недостатки Добавление элемента требует усилий Надо: 1. Найти место куда вставить (T=O (log N)) 2. Освободить место для вставки (T=O(N)) 3. Вставить элемент Нет гарантии, что размер массива позволит вставить элемент

50 Связный список Иванов Петров Сидоров Валя Таня Катя Данные Указатель на следующий элемент

51 Связный список (односвязный список) LinkListItem { Telephone Data; pLinkListItem next; } LinkListItem root;

52 Добавление элемента InsertAfter(LinkList item, LinkList newItem) { LinkList nextItem = item.next; item.next = newItem; newItem.next = nextItem; }

53 Удаление элемента Remove(LinkList item) { LinkList current; for(current=root; current!=null; current=current.next) { if(current.next==Item) { current.next=Item.next; return; } ERROR } Для удаления элемента надо найти предыдущий элемент (T=O(N))

54 Двусвязный список Иванов ПетровСидоров Данные Указатель не следующий элемент Указатель не предыдущий элемент

55 Двусвязный список BiLink { pBiLink previous; Telephone Data; pBiLink next; }; BiLink root;

56 Удаление элемента Remove(BiLink item) { BiLink prevItem = item.previous; BiLink nextItem = item.next; if( prevItem != null) prevItem.next = nextItem; if( nextItem != null) nextItem.previous = prevItem; } Задача. Напишите алгоритм вставки элемента

57 Распределение памяти Память организована в виде цепочки занятых и свободных участков Участки имеют в своем составе контрольные блоки Контрольные блоки содержат: –Размер свободного участка –Указатель (адрес) следующего контрольного блока –Указатель (адрес) предыдущего контрольного блока Данные Свободное место Контрольный блок

58 Операции с памятью CB{ size, // размер блока памяти next, // адрес следующего контрольного блока prev, // адрес предыдущего контрольного блока free, // признак занятости блока памяти } Операции: –Занять память –освободить память

59 Освобождение памяти Надо: 1. проверить если предыдущий блок свободен, то объединить блоки 2. Если следующий свободен, то объединить блоки 3. Пометить блок как свободный

60 Захват памяти Дан размер области, который надо занять Надо: 1. пройти по цепочке блоков и найти подходящий блок памяти: он (1) должен быть свободен; (2) его размер не должен быть меньше, чем запрашиваемая область 2. Разбить блок на две части, одну из которых пометить занятой, а другую - свободной

61 Очередь (Queue) Очередь. Множество элементов, позволяющее добавлять один элемент и извлекать один элемент. При этом соблюдается правило: первым извлекается элемент, пришедший первым (FIFO). (Вспомните очередь в столовой) Строится на базе двусвязного списка Задача: Построить структуру типа очередь. Должны быть реализованы функции Put и Get. Функция Get удаляет извлеченный элемент

62 Стек (Stack) Стек. Множество элементов, позволяющее добавлять один элемент и извлекать один элемент. При этом соблюдается правило: первым извлекается элемент, пришедший последним (LIFO). (Представьте себе стопку тарелок) Строится на базе (обратного) связного списка Задача: Построить структуру типа Стек. Должны быть реализованы функции Push и Pop. Функция Pop удаляет извлеченный элемент

63 В компьютере очередь – очередь задач стек – стек вызовов процедур Вызвали подпрограмму ret b a точка возврата локальн.перем. ret b a точка возврата локальн.перем. ret b a точка возврата локальн.перем. Вызвали подпрограмму ret b a точка возврата локальн.перем. ret b a точка возврата локальн.перем. ret b a точка возврата локальн.перем. return

64 Проблема: Плохо искать У нас нет возможности найти середину списка!

65 Еще структура BTree { BTree parent; BTree left; BTree right; Data data; } Если дерево организовано правильно, то и вставлять и удалять и искать сравнительно легко Бинарное дерево

66 Двоичное дерево поиска Бинарное дерево Для любой вершины выполнено: left and all childs < this, если left существует this

67 Поиск в двоичном дереве Если ключ равен вершине, то Ура Если он меньше вершины, то переходим на левую дочернюю вершину Иначе переходим на правую дочернюю вершину

68 Поиск в двоичном дереве TreeSearch(treeElm, key) { if(treeElm == null) return "not found"; if(treeElm.data == key ) return treeElm; if(treeElm.data < key) return TreeSearch(treeElm.right,key); else return TreeSearch(treeElm.left,key); } Анализ Алгоритма: Время поиска есть T=O(h), где h – высота дерева

69 Добавление элемента Идем по дереву вниз также, как и при поиске до первого свободного места, и туда вставляем новый элемент в качестве листа дерева

70 Добавление элемента (рекурсивная форма) Tree_Insert(tree_elm, new_elm) { if(new_elm > tree_elm) { if(tree_elm.right==null) { tree_elm.right=new_elm; new_elm.parent=tree_elm; return; } Tree_Insert(tree_elm.right, new_elm); } else … //Аналогично для left }

71 Добавление элемента (в виде цикла) InsertTree(tree_elm, new_elm) { while(true) { if(tree_elm

72 Замечания про рекурсию Рекурсивный тип алгоритма представляется более прозрачным. Часто можно записать алгоритм в виде цикла, но не всегда это легко сделать Использование цикла предпочтительно, поскольку несколько быстрее, и нет опасности переполнения стека.

73 Поиск минимального (максимального) элемента в поддереве Минимальный элемент в поддереве – самый левый узел Максимальный элемент – самый правый узел MinElm(treeElm) { while(treeElm.left!=null) treeElm=treeElm.left; return treeElm; }

74 Поиск следующего (по возратанию) элемента Следующий элемент либо самый левый лист в правом поддереве, либо родитель(Почему?) GetNext(treeElm) { if(treeElm.right!=null) return MinElm(treeElm.right); if(treeElm.parent != null && treeElm.parent.left==treeElm) return treeElm.parent; return null; } Задача: написать алгоритм поиска предшественника: GetPrev(treeElm)

75 Удаление элемента. 1. Элемент не имеет детей Надо просто его удалить. И все…

76 Удаление элемента. 2. Элемент имеет одного ребенка Элемент удаляется, а его ребенок усыновляется его родителем

77 Удаление элемента. 3. Элемент имеет двух детей На его место ставится его предшественник Задание: записать алгоритм удаления элемента

78 Результаты Поиск, удаление и вставка элемента требует времени порядка T=O( h ), где h – высота дерева Для одного и того же набора данных данных можно построить несколько деревьев. Обычно деревья хорошие: h=O ( log ( N ) ) Деревья можно балансировать Задача: написать программу, которая печатает все элементы Задача*: написать программу, которая печатает все элементы в порядке возрастания

79 Красно-черные деревья. Бинарное дерево поиска Добавлены фиктивные листья Любая вершина либо черная либо красная Следствие:Листья (фиктивные) – черные. Следствие: любая внутренняя вершина имеет двух детей. У красной вершины дети черные Все пути от корня до листьев имеют одинаковое количество черных вершин (черная высота) Следствие. Следствие. Любое поддерево является RB-деревом

80 Красно-черные деревья

81 Красно-черные деревья. высота дерева bh – черная высота дерева Лемма КЧ-дерево с n внутренними вершинами имеет высоту не более h 2·log (n+1) Доказательство: по индукции докажем, что число внутренних вершин в поддереве не меньше, чем n 2 bh – 1. Для поддерева из одного листа – очевидно. Пусть поддерево имеет bh=k. Тогда оба ребенка имеют bh не менее k – 1 (красный ребенок имеет bh=k-1, черный – bh=k). Тогда по предположению индукции количество внутренних вершин n 2 k k =2 k -1. По меньшей мере половину всех вершин на пути (кроме корня) составляют черные вершины. Поэтому h 2 · bh. Следовательно n 2 h/2 – 1, h 2 · log(n+1)

82 Красно-черные деревья. преобразование деревьев Преобразование дерева: Вращение Задача: написать алгоритм для вращения. На входе вершина x a d xc y dc y a x

83 Красно-черные деревья: Добавление элемента Добавляем как в обычное дерево поиска и красим в красный цвет. Восстановление RB-свойства, если только одно нарушение типа красный ребенок имеет красного родителя Дядя красный. перекрашиваем предыдущий уровень и родителя Родитель красный, "ближний" дядя черный. Вращаем Родитель красный, "дальний" дядя черный. Вращаем и перекрашиваем родителя (7) и деда (11)

84 Красно-черные деревья. Вставка элемента 1. При восстановлении RB всегда движемся наверх 2. RB – свойства на поддеревьях сохраняются 3. Время работы алгоритма восстановления не больше высоты дерева O(log(n)).

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

86 Красно-черные деревья. Восстановление RB после удаления A B CE D Брат красный, родитель черный – вращаем и красим A B CE D A B CE D Брат и племянники - черные. Пусть станет красным A B CE D A B D E С Брат Ч, ближ. плем. К, дальн. плем. Ч A B CE D A B C E D Брат Ч, дальн. плем. К Дважды черная Цвет не важен A B C E D

87 Красно-черные деревья: Операции Добавление элемента – как обычно, новая вершина красная. Далее – восстановление дерева Удаление элемента – как обычно, потом восстановление дерева. После удаления может измениться bh, поэтому алгоритм несколько другой.

88 Динамические порядковые статистики Если в бинарном дереве хранить дополнительную информацию, то можно делать другие вещи. Поиск по номеру элемента (напр. найти пятый по возрастанию элемент) –Достаточно хранить в узлах размер (количество элементов) поддерева –При модификации дерева необходимо обновлять эту информацию Задачи: 1. Написать алгоритм поиска элемента заданного номера 2. Написать алгоритм определения номера элемента

89 Хэш-Таблицы I База данных d1d6d3 d4d7 d9 Данные KeyRef k1&d1 k3&d3 k4&d4 k6&d6 k7&d7 k9&d9 Индексная таблица

90 Хэш-Таблицы II Если заранее знать все мыслимые ключи, то можно было бы заранее создать индексную таблицу (быть может с пустыми строками), то нет проблем со вставкой, удалением и поиском (все операции происходят за O(1), поиск за O(log(nKey))) Проблема: Полный список ключей заранее неизвестен и может быть очень велик KeyRef k1&d1 k2 k3&d3 k4&d4 k5 k6&d6 k7&d7 k9&d9

91 Хэш-Таблицы III Если сделать отображение: key -> int h причем заранее известно, что 0

92 Хэш-Таблицы IV Пример: aa0ga8 ac1gc9 ag2gg10 at3gt11 ca4ta12 cc5tc13 cg6tg14 ct7tt15 gagttttatcgcttccatgacgcagaagttaacactttcg ,3080,18,24, 119,31,33910,21, 21,23,26,10 37,16,112, 27, 415,22,32126,29, 514,138,13,37 69,20,381417, 711,34153,4,5,12,28,35,36 Хеш-функция Хэш-таблица

93 Хэш -Таблицы V Пример: найти cat. Вычисляем хэш-значение h=4. Лезем в таблицу и находим, что cat может встретиться в позициях 15,22,32 Проверяем, что в этих позициях лежит, и убеждаемся, что 15 позиция подходит Примерно так работает BLAST

94 Хеш-Таблицы VI Видно, что во многих ячейках больше одного элемента (коллизия) Решение: в соответствующей ячейке хранится связный список. Хэш-таблица строится за время T=O(N) Поиск происходит за время, пропорциональное заполненности таблицы T=O(1)*k

95 Строки Задача поиска подстроки. Дано: длинная строка S=s 0,s 1,…,s n и короткая строка P=p 0,p 1,…,p k, k

96 Наивный алгоритм Время работы в худшем случае T=O(n*k); bool SubStrCmp(String s, int pos, String p) { for(i=0; i

97 Оценка среднего времени работы Среднее время работы равно (количество вызовов SubStr_Cmp=n) * (среднее время исполнения SubStr_Cmp) Среднее время исполнения SubStr_Cmp = 1q+2pq+3p 2q+…+(m-1)p m-2q+mp m-1 = (1+2p+3p 2 +…+(m-1)p m-2 )q+mp m-1 = qd/dp(p+p 2 +…+p m-1 ) +mp m-1 1/q p=1/A; q=1-p= (A-1)/ A; A – размер алфавита Среднее время работы равно E(T)=O(n* A/(1 – A) );

98 Алгоритм Рабина-Карпа Допустим, что алфавит состоит только из 9 цифр: A={1,2,3,4,5,6,7,8,9}, тогда слово – есть число и две строки равны, если соответствующие числа равны. 0 исключен, поскольку в этом случае много разных строк будет порождать одно число: 0067=067=67. Слово P может быть за время O(k) преобразовано в число N(P) Построка {s 0 …s k } может быть за то же время преобразована в число N(S(0,k)); Сравнение строк есть сравнение чисел. Если N(P)==N(S(i,i+k)), то имеем вхождение Далее мы двигаемся вдоль строки S и получаем число N(S(i+1,k+i+1). Это можно сделать за O(1). (как?)

99 Алгоритм Рабина-Карпа int StrToNum(String p, int l) { n=0; for(i=0; i

100 Свойства алгоритма Время работы T=O(n) Поиск больших паттернов приводит к появлению больших чисел (больше, чем позволяет разрядная сетка) Очень хорош для поиска в нуклеотидных последовательностях – алфавит содержит 4 буквы, поэтому использование int позволяет искать паттерны длиной до 16, а применение long – до 32. Кроме того операции *, /, % заменяются на соответствующие логические операции сдвиг и логическое &

101 Задача * Написать программу поиска точного вхождения в нуклеотидную последовательность

102 Алгоритм Кнута-Морриса- Пратта Если q первых символов совпало, а в позиции q+1 есть несовпадение, то из анализа только слова P можно сказать насколько имеет смысл сдвигать образец Ясно, что сдвигать на 1 бессмысленно, а для следующей попытки правильно сдвинуть на 2 ababaca bacbababaabcbab ababaca bacbababaabcbab

103 Префикс и суффикс Префикс – любое подслово, начинающееся с 0 Суффикс – окончание слова aabacacbbacabac aabacacbba aabaca aaba acacbbacabac cabac ac Префиксы Суффиксы

104 Алгоритм Кнута-Морриса- Пратта Попробуем вычислить величину сдвига при условии совпадения q символов. a1 ab1 abc2 abce3 abcea5 abceab5 abceabc6 abceabca4 abceabcab8 abceabcabd7 abceabcabd10

105 Определения sp i (P) – длина наибольшего суффикса подслова P[1..i] совпадающего с префиксом P sp' i (P) – длина наибольшего суффикса подслова P[1..i] совпадающего с префиксом P, при условии P[i+1]!=P[sp' i +1] d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 00 a1a1 b2b2 c3c3 a4a4 e5e5 a6a6 b7b7 c8c8 a9a9 b 10 d 11 суффикс P[1..9]префикс P d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 0 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 00 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 0 00 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i сдвиг

106 Алгоритм Кнута-Морриса-Пратта Если несовпадение встретилось в позиции i+1 в слове P, то можно смело переместить образец на величину i + 1 – (sp' i +1)=i – sp' i Кроме того, после сдвига образца совсем не обязательно повторять сравнение первых sp i символов. В любом случае происходит не более 2n сравнений (оценка в худшем)

107 Препроцессинг Сдвигая образец вдоль самого себя и проводя сравнение слева на право можно вычислить sp i. Этот алгоритм работает за время не более T=O(m 2 ), m=|P|; Есть алгоритм препроцессинга, работающий за время не более T=O(m). d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 00 b10b10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i 0 00 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i e5e5 a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i a4a4 c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i c3c3 b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i b2b2 a1a1 d 11 b 10 a9a9 c8c8 b7b7 a6a6 e5e5 a4a4 c3c3 b2b2 a1a1 sp i a1a1

108 Препроцессинг abxabqabxabrabxabqabxabx k sp(k) sp(k+1) sp(sp(k)) k sp(k) Пусть для всех k нам известно sp(k) (sp(k)

109 Препроцессинг sp[1]=0; for (k=1; k0 && P[v+1]==x) sp[k+1]=v+1; else sp[k+1]=0; } Время работы алгоритма T(m)=O(m)

110 Некоторые обозначения x [ y – x префикс y x ] y – x суффикс y Если T – строка, то T i – префикс строки длиной i Σ* ΣОбозначение Σ* - множество всех возможных слов над алфавитом Σ

111 Конечные автоматы Конечный автомат = – конечное множество (состояния) – начальное состояние – подмножество допускающих состояний – конечный входной алфавит – функция: функция переходов

112 Конечные автоматы. Пример. ab Вход Состояния Функция переходов a a b b abba – допускается baaab – не допускается Допускаются слова, в конце которых нечетное число символов a q0q0q0q0 A

113 Конечные автоматы. 2. φ: Σ*Q φ(w) wфункция φ: Σ*Q функция конечного состояния: φ(w) – конечное состояние автомата при предъявлении ему слова w Рекурсия : φ(ε)=q 0 φ(wa)=δ(φ(w),a) w, a φ(wa)=δ(φ(w),a) для любых w, a

114 Конечные автоматы для поиска образца образец P=abab a bab b a b aa b

115 Конечный автомат для поиска образца Суффикс функция для образца P σ: Σ*{0,1,…,m} σ(x)=max {k: P k ] x} – длина максимального суффикса x, который совпадает с префиксом P Пример: P=ab, σ(ε)=0; σ(ccaca)=1; σ(ccab)=2; Свойства σ(x)= m суффикс x совпадает с P если x ] y, то σ(x) σ(y)

116 Конечный автомат для поиска образца Множество состояний Q={0,1,…,m} Начальное состояние q 0 =0; Допускающие состояния A={m} Функция переходов δ: δ(q,a)= σ(P q a)

117 Свойства суффикс-функции Лемма 1. σ(xa) σ(x)+1Лемма 1. σ(xa) σ(x)+1 Допустим σ(xa) > σ(x)+1. Тогда отбросим последний символ от наибольшего суффикса xa, совпадающего с префиксом P. Тогда получим суффикс строки x, который длиннее σ(x) и является префиксом P, что противоречит определению. Лемма 2. Пусть q= σ(x). Тогда σ(xa)= σ(P q a).Лемма 2. Пусть q= σ(x). Тогда σ(xa)= σ(P q a). q= σ(x) Действительно, поскольку σ(xa) σ(x)+1=q+1, σ(xa) не изменится, если отбросить начало от строки xa, оставив только последние q+1 символов (поскольку q= σ(x)), т.е. σ(xa) = σ(P q a) Теорема: φ(T i ) = σ(T i ).Теорема: φ(T i ) = σ(T i ). Доказательство по индукции. При i=0 – очевидно. Если верно при некотором i, то по лемме 2 будет верно и при i+1: φ(T i+1 )= δ (φ(T i ),t i+1 )= δ(σ (T i ),t i+1 )= σ(P q t i+1 )= σ(T i+1 ). Следствие. Автомат приходит в Допускающее состояние только если суффикс T i совпадает с образцом P

118 Обобщение Можно искать вырожденные образцы. P=a?ab P={a n } {b n } {a n }b a bab b a b a a b a bab b b a a

119 Недетерминированные конечные автоматы Недетерминированным конечным автоматом является автомат, функция переходов которого есть отображение {q,a}{q*}, где q* - множество множеств возможных q. Функция переходов – из состояния в множество (может быть пустое) состояний Возможен пустой переход (без снятия символа) a b a a

120 Регулярное выражение просто символ два регулярных выражения написанные друг за другом регулярное выражение в скобках регулярное выражение с приписанным спец символом '*' регулярное выражение с приписанным спец символом '+' R::= символ | RR | (R) | R* | R+

121 ( )* c a ( ) + a b Разбор регулярных выражений: построение автомата ab ε ac ε ε

122 Разбор регулярных выражений: Обход автомата На первом этапе строим множество N 0 – q 0 +множество состояний, достижимых из q 0 по ε-переходам При считывании очередного символа перестраиваем множество состояний Если множество состояний пересекается с множеством допустимых состояний, но репортируем находку

123 Обобщение на множество ключей абрау абрек брусья руслан русь р с л а н ь у б р у с а брау е к ь я Функция неудач – куда надо идти, если идти некуда: f(v): VV Метка ребра, идущего в вершину: g(v): VΣ

124 Автомат Ахо-Корасик абрау абрек брусья руслан русь р с л а н ь у б р у с а брау е к ь я 1. Сортируем вершины по уровням 2. Вершины 1-го уровня – в корень Цикл по уровням и вершинам: a. f(v prev )=w. ищем вершину u из w next : g(u)=g(v); f(v)=u; b. f(v prev )=0. ищем вершину 1-го уровня u : g(u)=g(v); f(v)=u; c. Если в a и b ничего не нашли, f(v)=0;

125 Статистика слов AAAB AAA20 AAB11 ABA01 ABB01 BAA10 BAB01 BBA00 BBB00 44 E(AA)=0.5 D(AA)=0.5 E(AB)=0.5 D(AB)=0.25

126 Суффиксные деревья a1a1 b2b2 c3c3 a4a4 e5e5 a6a6 b7b7 c8c8 a9a9 b 10 d 11 ab a c b d c a d c a d b d b d b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d

127 Свойства суффиксного дерева Листьев столько же сколько и позиций На ребрах определены строки (метка ребра) Каждый путь от корня до листа – суффикс Можно построить такое дерево за время T=O(n) На листьях указаны позиции начал соответствующих суффиксов Задача* Придумать алгоритм построения суффиксного дерева (любой)

128 Зачем этот наворот? Если для строки однажды построить такое дерево, то им можно пользоваться для поиска образца за время T=O(||P||) – пропорционально длине искомого слова Можно решать задачу поиска общего подслова для двух слов. Для этого слова объединяют и строят суффиксное дерево для объединенного слова. Вершины, имеющие пометки адресов к обоим словам определят общие подслова. Повтор – путь между двумя не-листьями

129 Преобразованиее в ориентированный граф ab a c b d c a d c a d b db d b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d ab a c b d c a d c a d b db d b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d e a b c a b d ab a c b d c a d c a d b db d b d e a b c a b d ab a c b d c a d c a d b db d b d e a b c a b d ab a c b d c a d c a d b d e a b c a b d ab a c b d c a d c a d b d e a b c a b d ab b d c a d d b d e a b c a b d ab b d c a d d b d e a b c a b d b d ab b c a d e a b c a b d b d ab b c a d e a b c a b d b d ab c a d e a b c a b d b d a b c a d e a b c a b d

130 Конечный автомат b d a b c a d e a b c a b d

131 Суффиксный массив 11i 8ippi 5issippi 2ississippi 1mississippi 10pi 9ppi 7sippi 4sissippi 6ssippi 3ssissippi Храним только позиции (слово-то у нас есть) Когда ищем слово, то делаем бинарный поиск (сколько времени надо для поиска образца длиной m?) Построение возможно за линейное время

132 Сложность текста Попробуйте описать следующий текст: aaaaaaaaaaaattttttttatatatatatatatatatat 12 a, 8 t,10 at А такой: gcttccatgacgcagaagtttgcttgtttatcaaaaactg Гораздо длиннее (проще его просто прочитать)

133 Пример a,(1,1),(1,2),(1,4),(1,4),t,(13,1),(13,2),(13,4) 9 команд, 20 букв Самые сложные тексты – случайные aaaa aaaa aaaaaaaa aaaa aaaaaaaaaaaa t ttaaaaaaaaaaaattttaaaaaaaaaaaatttttttt aaaaaaaaaaaatttttttt

134 Пусть Z = {0,1}* - множество всех слов на 0,1 Определим так, что Это называется системой описания текстов. На самом деле похоже на разархивирование Замечание. Для одного текста y существует множество описаний x. Сложность текста относительно программы: Описание текста

135 Сложность Системы описания: Π 1 не хуже Π 2, если Теорема если есть две системы описания, то можно построить систему, которая не хуже каждой. Доказательство: в начале описания поставим признак: какую программу надо использовать (тем самым увеличим длину описания), а за тем напишем описание в соответствии с выбранной программой

136 Сложность по Колмогорову Все мыслимые программы можно пронумеровать и построить универсальную программу, которая считывает сначала номер, а потом исполняет соответствующую программу. Это называется Универсальной программой. Сложность по Колмогорову: длина самого короткого описания текста (относительно фиксированной универсальной программы). Сложность не вычислима.

137 Сложность и случайность Количество слов W сложности K: 2 K-C W 2 K+1 Случайный текст – текст, любое описание которого не короче самого текста.

138 Пример программы сжатия Пример программы. Элементарные команды описания: –Добавить заданный символ –Скопировать фрагмент текста из уже сгенерированной последовательности

139 Сжатие информации по Лемпелю-Зиву Для сжатия информации строится суффиксное дерево (время O(n)). Пусть уже упаковано i-1 символов. Нам надо вычислить следующую команду (s i,l i ). Берем суффикс S(i..n) и пропускаем его через дерево T(S(1,i-1))(как при поиске слов) и либо находим максимальное слово, которое является префиксом S(i..n), и тогда ставим команду скопировать это слово. В противном случае генерируем новую букву. Суффиксное дерево можно генерировать одновременно с поиском.

140 Графы Формальное определение: (ориентированным) Графом на множестве вершин M называется отображение E= { MM { true, false } } Пары вершин v1,v2, для которых E(v1,v2)==true называются ребрами Если отображение коммутативно (E(v1,v1) == E(v2,v1)), то граф называется неориентированным

141 Представление графов Матрица смежности: Матрица, отображающая определение графа. Для неориентированного графа M T =M Списки ребер Списки смежных вершин AB CD E ABCDE A01010 B00000 C10010 D01001 E00000 Матрица Смежности

142 Представление графов Списки ребер AB CD E AB AD CA CD DB DE

143 Представление графов В каждой вершине записываем списки смежных вершин AB CD E A:BD/ B:E/ C:AD/ D:BE/ E:/

144 Поиск в ширину Алгоритм обхода графа: Цвета: белый – вершина, которую еще не видели серый – вершина, которая находится в стадии обработки черный – вершина, для которой обработка завершена Вначале – все вершины - белые 1. Берем произвольную вершину, помещаем в очередь и красим в серый цвет. 2. Изымаем очередную вершину из очереди (красим в черный цвет) и все смежные не пройденные (белые) вершины помещаем в конец очереди и красим в серый цвет 3. Если очередь не пуста, переходим к Если остались не присмотренные вершины, то берем из них произвольную, помещаем в очередь и переходим к 2

145 Поиск в ширину ABCD EFGH B ABCD EFGH FA ABCD EFGH ACG ABCD EFGH CGE ABCD EFGH GED ABCD EFGH ED ABCD EFGH D ABCD EFGH H ABCD EFGH

146 Алгоритм wideSearch(){ for( all v from V){ if(v.color==white) wideSearch(v); } wideSearch(v){ queue Q; Q.put(v); v.color=gray; for(; Q is not empty;){ u=Q.get(); for( all w сосед u){ if(w.color=white){ q.put(w); q.color=gray; } u.color=black; }

147 Определение расстояния между вершинами Задача: найти расстояние от вершины s до вершины v. Делаем поиск в ширину, начиная с s до тех пор, пока не встретим v. Вопросы: 1. Если есть путь от s до v, то найдем ли этот путь (т.е дойдем ли вообще до v? 2. Будет ли этот путь кратчайшим? 3. Доказательство по индукции и от противного: если бы это был не кратчайший путь, то вершина на кратчайшем пути встретилась бы раньше при просмотре Задача: доказать, что если путь существует, то при поиске в ширину мы дойдем от s до v

148 Поиск в глубину Алгоритм обхода графа: Стек 1. Берем произвольную вершину и помещаем в Стек (красим в серый цвет) 2. Если есть белые смежные вершины, то Берем произвольного соседа и помещаем в стек (красим в серый) и переходим к Если нет смежных вершин, то берем вершину из стека и заканчиваем ее обработку (красим в черный) и переходим к Если остались не присмотренные вершины, то берем из них произвольную, помещаем в стек и переходим к 2

149 Поиск в глубину ABCD EFGH B ABCD EFGH AB ABCD EFGH EAB ABCD EFGH FB ABCD EFGH CFB ABCD EFGH DCFB ABCD EFGH HDCFB ABCD EFGH GFB ABCD EFGH

150 Свойства поиска в глубину В результате поиска в глубину получается дерево (лес). Каждая вершина имеет время окончания обработки. Типы ребер графа uv Ребра деревьев Прямые: v, u принадлежат дереву и t(u) > t(v) Обратные: v, u принадлежат дереву и t(u) < t(v) Перекрестные - остальные s z y x w v t u

151 Построение покрывающего дерева Строим лес поиска в глубину. Если есть перекрестное ребро из листа одного дерева в корень другого дерева, то включаем это ребро Когда все такие ребра исчерпаны, получим покрывающее дерево.

152 Связные компоненты Пример. Вершины графа – белки из базы данных. Ребро проводится если e- value лучше 1.e-6. Тогда связную компоненту можно рассматривать как семейство белков (достаточно условно)

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

154 Поиск циклов в графе В ориентированном графе – ищем покрывающее дерево. Все обратные ребра порождают цикл. В неориентированном графе – ищем покрывающее дерево. Все ребра, не принадлежащие дереву, порождают циклы.

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

156 Эйлеров путь Существует только если две вершины нечетные Проведем ребро между нечетными вершинам и и сведем задачу к поиску цикла.

157 Эйлеров цикл 1. Помечаем все ребра, как не пройденные 2. Ищем цикл в графе по не пройденным ребрам. Записываем последовательность ребер в связный список. Он проходит через все вершины 3. Если не все ребра пройдены, то находим вершину, из которой выходит не пройденное ребро. (Доказать, что это существует) 4. Находим цикл, проходящий через заданную вершину. 5. Вставляем в список новый цикл. Переходим к п. 3.

158 Построение Эйлерового цикла

159 Топологическая сортировка Брюки Рубашка Галстук Ремень Носки Ботинки Пиджак Часы брюкирубашка галстукпиджак носкичасыботинки ремень

160 Топологическая сортировка Задача: расположить вершины ориентированного графа на горизонтальной оси так, чтобы ребра шли слева направо. Если в графе есть циклы, то задача не имеет решения.

161 Алгоритм Делаем поиск в глубину. По окончании обработки вершины пишем ее в начало списка. брюкирубашка галстук пиджакноски часыботинки ремень пиджак ременьботинкибрюкигалстукчасы носки рубашка

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

163 Оптимальный путь в графе Пример. В результате секвенирования большого фрагмента ДНК (например, генома) получен ряд последовательностей Строим граф. Вершина – прочитанная последовательность. Ребро проводится, если суффикс первой последовательности равен префиксу второй. Вес равен длине общей части Путь с наибольшим весом дает последовательность генома

164 Оптимальный путь в графе a b c d e f g h

165 Динамическое программирование a b c d e f g h W(a,h) = max { 5 + W(b,h), 3 + W(c,h) }

166 Динамическое программирование a b c d e f g h a b c d 8 5 g h a b c g h a b c h a b h a h h W(V)=max { W(V prev )+W(E(V->V prev ) } prev

167 Выравнивание последовательностей Del=-2; Match=1; Mismatch=-1 aacggatcg a a g g a t t c g

168 Полукольцо Множество M с двумя операциями: (+), () Операции обладают свойствами: (a + b) + c= a + (b + c) (a b) c = a (b c) a (b + c) = a b + a c 0 : a + 0 = 0 + a = a; 1: a 1 = 1 a = a a 0 = 0

169 Примеры Задачи 1.Показать, что приведенные примеры действительно полукольца 2. Придумать еще примеры полуколец Множество Опер. (+)Опер. () { true, false }|& натуральные числа+ действительные числа, +, - max+

170 Динамическое программирование на графах Когда мы искали оптимальный путь на графе, мы использовали две операции: (max, +) причем использовалось то, что эти операции образуют полукольцо (ассоциативность и дистрибутивность) Можно обобщить рекурсию динамического программирования на: W(V)=W(V 1 ) () W(E 1 ) (+) W(V 2 ) () W(E 2 ) (+) … Если мы заменим эти операции на (+,), то сможем подсчитать количество путей по графу между указанными точками

171 Подсчет числа путей в графе На каждом ребре записываем 1 Строим рекурсию W(V)=W(V 1 ) W(E 1 ) + W(V 2 ) W(E 2 ) + … В результате в каждой вершине определяем количество путей, ведущих из нее в финальную вершину (почему?)

172 Алгоритм Дейкстры В каждой вершине пишем текущий вес пути до конца. If(d(v) > d(u)+w(u,v)){ d(v)=d(u)+w(u,v) π(v)=u } v u d(u) d(u) d(v) d(v) w(u,v) w(u,v) Релаксация Релаксация для вершины v, соединенной ребром веса w(u,v) с вершиной u:

173 Алгоритм Дейкстры , , ,7, ,8, ,8, , Алгоритм 1. Все вершины необработанны (голубые, вес ), кроме последней (красная, стоит в очереди, вес 0), 2. Снимаем вершину из очереди и для всех соседей делаем Relax, и, если они не красные, то помещаем в очередь. Алгоритм применим только если веса положительные ! Структура данных – очередь с приоритетами: первым выходит тот, кто имеет наименьший вес, но если несколько наименьших весов, то выходит тот, кто раньше пришел. Реализуется, например, в виде двоичного дерева. Те, кто окончательно обработан (вышел из очереди) – черные, кто стоит в очереди – красные, кто еще не встал в очередь – голубые.

174 Правильность алгоритма Дейкстры S u ys x t Пусть S – множество черных вершин, и для них d=δ. Пусть u – красная вершина с наименьшим d: u=argmin z=красные d(z) Тогда d(u)= δ(u). 1. Никакое ребро в черную вершину не лучше (поскольку красные – релаксированы). 2. Допустим есть путь из u в s, лучше, чем (uts). Тогда этот путь пройдет через красную вершину y (uys). Но: w(uys) = w(uy)+w(yxs) w(yxs)=d(y) > d(u)=w(uts) (u=argmin!) w(uy) > 0 (веса положительны!) противоречие! Поэтому w(uys) > w(uts) – противоречие! На каждом этапе красные вершины релаксированы относительно черных!

175 Время работы алгоритма Дейкстры Каждая вершина проходит одну релаксацию относительно всех соседей, поэтому надо потратить время O(E). Но организация очереди стоит времени, причем перестройка очереди происходит при просмотре каждого ребра. В худшем случае T=O(E log V)

176 Алгоритм Беллмана-Форда Повторяем |V| раз релаксацию всех ребер. Если на последнем шаге хоть одно ребро релаксировало, то есть отрицательный цикл Время T=O(V*E) Задача: найти кратчайший путь, если есть ребра отрицательного веса и нет циклов отрицательного веса, а если есть отрицательные циклы, то этот факт обнаружить Теорема Алгоритм находит оптимальный путь (!) Доказательство. Если есть оптимальный путь {v 1,..v n }, то на i-шаге будет определена длина пути от i-вершины до конца. Доказательство по индукции. Инициация тривиальна. Пусть на i-шаге d(v i )=δ(v i ). Тогда на следующем шаге произойдет релаксация ребра (v i, v i+1 ) и таким образом определится вес оптимального пути от v i+1.

177 Потоки в сетях. Определения Сеть: G(V,E) c(e) {u,v} с(u,v)=0 –ориентированный граф G(V,E), в котором на каждом ребре определено неотрицательное число c(e) (пропускная способность). Для пар вершин {u,v}, не соединенных ребром, определим с(u,v)=0 st –Выделены две вершины s и t (источник и сток). s ~> v ~> t –Для любой вершины v существует путь s ~> v ~> t

178 Потоки в сетях. Определения f:V x V R:Поток – функция f:V x V R: –f(uv) c(uv), c(uv) – заданное ограничение (пропускная способность) –f(uv)= – f(vu) – u V f(u,v) = 0 – u из V f(u,v) = 0 для любого v из (V – {s,t}) Величина потока: |f|=F(s) = v V f(s,v) |f|=F(s) = v из V f(s,v) Задача: доказать, что F(t)= F(s) Задача: доказать, что F(t)= – F(s) Проблема: найти максимальный поток в сети. Проблема: найти максимальный поток в сети. Можно определить поток между множествами, простым суммированием по ребрам

179 Потоки в сетях Gf Остаточная сеть для G и f определяется так: f G(V,E)u,v Пусть определен некоторый поток f в сети G(V,E). Тогда для любой пары вершин u,v определим остаточную пропускную способность: f(u,v) < 0 Остаточная сеть может содержать встречные ребра. Они соответствуют случаям, когда f(u,v) < 0

180 Метод Форда-Фалкерсона GfG f f f+f Пусть G сеть, f – поток G f – остаточная сеть и f – поток в остаточной сети. Тогда f+f является потоком и его величина Надо проверить несколько свойств f+f: Кососимметричность Ограничение на пропускную способность Закон сохранения

181 Метод Форда-Фалкерсона Дано сеть G и поток f. Дополняющий путь p – простой путь из s в t. Остаточная пропускная способность c f (p): Если даны сеть, поток и существует дополняющий путь, то определим дополняющий поток f p

182 Разрезы в сетях Разрезом сети называется разбиение множества вершин e=(u,v) Ребро e=(u,v) принадлежит разрезу, если Пропускная способность разреза = сумма пропускных способностей ребер разреза Минимальный разрез – разрез с минимальной пропускной способностью

183 Потоки между множествами Лемма

184 Теорема о минимальном разрезе Теорема о максимальном потоке и минимальном разрезе G=(V,E)f Пусть G=(V,E) – сеть и f – поток в сети. Тогда следующие утверждения равносильны 1. Поток f максимален 2. Остаточная сеть не содержит дополн. путей (S,T)G | f |=c(S,T). 3. Для некоторого разреза (S,T) сети G выполнено равенство | f |=c(S,T). G, f, (S,T).f(S,T) |f|. Лемма. Даны: G, f, (S,T). Тогда поток f(S,T) равен величине потока |f|.

185 Доказательство (1)(2) – от противного (почти очевидно) (2)(3): В сети G f нет пути из s в t. Рассмотрим множество (S, T) |f| c(S, T) (3)(1) для любого разреза (S, T) выполнено |f| c(S, T), поэтому из равенства |f|=с(S, T) следует, что поток максимален T=V – S STE f f(u,v)=c(u,v) Положим T=V – S. Это деление является разрезом. По построению никакое ребро из S в T не принадлежит E f. Поэтому f(u,v)=c(u,v). Тогда по предыдущей лемме

186 Паросочетания в двудольном графе Двудольный граф – множество вершин можно разбить на два подмножества, так, что нет ребер внутри этих подмножеств. Паросочетания – множество ребер в графе, такое, что нет ребер, имеющих общую вершину. Добавляем источник и сток, пропускные способности устанавливаем на всех ребрах графа =1. Ищем максимальный целочисленный поток st 1 1 1

187 Задача сортировки. Нижние оценки Задача: дан массив элементов, для которых определены соотношения < и =, так, что для каждой пары элементов x и y выполняется одно из: x

188 Решающие деревья a1:a2 a1:a3 a2:a3 1, 2, 3a2:a3 1, 2, 3 a2:a31, 2, 3 > > > > Любому алгоритму сортировки соответствует дерево решений: надо сделать сравнение и в зависимости от результата что-то сделать (например переставить два элемента) и затем сделать следующее сравнение Узлы дерева – операции сравнения, листья – возможные перестановки

189 Время работы алгоритма сортировки Время работы алгоритма сортировки равно высоте h дерева решений. Максимальное число листьев в дереве высоты h равно 2 h Число листьев в дереве решений равно n!, поскольку каждому листу соответствует одна перестановка элементов массива. Поэтому для любого алгоритма должно выполняться n! 2 h, или h log(n!). n! > (n/e) n Окончательно: T(n)=ch > c(n log(n) – n log(e)) = O(n log(n))

190 Формальные языки Вход любого алгоритма сводится к строке (любая программа имеет на входе двоичный файл) Время работы алгоритма правильно оценивать как функцию длины входной строки Алфавит – некое (конечное) множество {α i }. Слово длины n – последовательность из n символов алфавита. Множество всех слов всех длин обозначается {α i }* Язык L – подмножество {α i }*: L {α i }* Поскольку алфавит конечен, то есть отображение множества всех слов в алфавите {α i } на множество всех слов в алфавите {0,1}. Далее будем рассматривать языки над алфавитом {0,1}.

191 Алгоритмы и языки Алгоритм A допускает слово x L, если A(x)=1. Алгоритм A отвергает слово x L, если A(x)=0. Алгоритм может не допускать и не отвергать некоторый слова. Возможно, что алгоритм не дает никакого ответа (например, зацикливается) Алгоритм допускает язык L, если он допускает те и только те слова, которые принадлежат L. Алгоритм распознает язык L, если он допускает все слова из L и отвергает все другие слова. Язык допускается за полиномиальное время, если существует допускающий алгоритм A, причем его время работы порядка O(n k ), где n – длина слова. Язык распознается за полиномиальное время если существует распознающий алгоритм A и число k такие, что его время работы порядка O(n k ), где n – длина слова.

192 Проверяющие алгоритмы Проверяющий алгоритм A(x,y) это алгоритм с двумя аргументами: словом x L и сертификатом y {0,1}*. Проверяющий алгоритм допускает слово x, если существует сертификат y, такой, что A(x,y)=1 для x L и не существует сертификата для других слов Пример. графы гамильт. графы гамильт. {0,1}* Посл. вершин Проверка: последовательность вершин y образуют гамильтонов цикл

193 Попросту говоря … Проверяющий алгоритм – это такой алгоритм, который может сказать является ли представленное (Оракулом) решение правильным, но при этом он ничего не говорит о том как получить решение.

194 Сводимость Язык L 1 сводится к L 2 за полиномиальное время, если существует отображение f: {0,1}* {0,1}*, такое, что x L 1 f(x) L 2 причем алгоритм вычисления f полиномиален. Тогда пишут, что L 1 p L 2 L1L1L1L1 {0,1}* L2L2L2L2 f x f(x) A1A1 A2A2 Результат

195 Класс языков NP Язык L принадлежит классу NP, если существует полиномиальный проверяющий алгоритм A, причем длина сертификата также ограничена полиномом от длины входной строки. Язык L принадлежит классу NP полных (NPC), если: 1. L NP 2. L p L для любого L NP, иными словами, это задачи полиномиально не менее сложные, чем любая NP-задача

196 NP и NP- полные задачи Благодаря сводимости существует ОДНА и только одна NP- полная задача. Если для хотя бы одной NP- полной задачи найдется полиномиальный алгоритм, то ВСЕ NP- полные задачи можно будет решить за полиномиальное время NP NP- полные

197 Примеры NP полных задач Задача о выполнимости булевой формулы (SAT). Дана булева формула F, содержащая некоторое количество аргументов x i, стандартные операции,,, между ними и скобки. Определить, существует ли такой набор аргументов x i, для которых F (x i ) =true Задача о выполнимости 3-CNF – формул (3-CNF- SAT). 3-CNF – формула это формула вида: (t 1 t 2 t 3 )... (t k t k+1 t k+2 ), где t i =x i или t i = x i это частный случай предыдущей задачи, поэтому она решается не медленнее задачи 1. С другой стороны, можно с помощью некоторого дерева и введением дополнительных переменных из любой булевой формулы получить 3-CNF.

198 Сведение SAT к 3-CNF Дана формула: φ(x 1, x 2, x 3, x 4 )=((x 1 &x 2 )|!x 3 )&x Строим дерево разбора формулы и вводим новые переменные в узлах дерева: & x4x4 | & !x 3 x1x1 x2x2 y1y1 y2y2 y3y3 2. Переписываем формулу: φ =y 1 & (y 1 (y 2 & x 4 )) & (y 2 (y 3 | !x 3 )) & (y 3 (x 1 & x 2 )) 3. Каждую тройку преобразуем к 3- CNF. y 1 y 2 x 4 (y 1 (y 2 & x 4 )) (y1 | !y2 | !x4) & (!y1 | y2 | x4) & (!y1 | !y2 | !x4) & (!y1 | !y2 | x4)

199 Еще примеры NP полных задач Задача о клике (CLIQUE). Дан граф G. Выяснить есть ли в нем клика, содержащая более k вершин. Проверка решения задачи тривиальна, поэтому это NP- задача. Оценим ее полноту. Для этого покажем, что 3-CNF-SAT p CLIQUE, Пусть дана 3-CNF формула. Построим по ней граф, причем такой, что если в нем есть k-клика, то эта формула выполнима. Формула: C 1 C C k ; C i =(l 1i l 2i l 3i ) для каждого C i рисуем 3 вершины. Вершины v ir и v js соединены ребром, если они принадлежат разным тройкам (r s) и если они совместимы (не являются взаимным отрицанием). Если формула разрешима, то существует набор переменных, когда все C i истины. Тогда есть в каждом С i есть истинный литерал. Соответствующие вершины образуют клику. Обратное тоже верно.

200 Граф для 3-CNF f = (x 1 | !x 2 | x 3 ) & (!x 1 | x 2 | x 3 ) & (x 1 | !x 2 | !x 3 ) X1X1 ! X 2 X3X3 ! X 1 X2X2 X3X3 X1X1 ! X 2 X3X3 x 1 =1; x 2 =0; x 3 =1;

201 Что же делать? Не все NP- полные задачи для общего случая являются таковыми для некоторых специальных случаев. –Пример: задача о максимальной клике является NP- полной для общего вида графов, но является тривиальной для деревьев (Почему?) Строить приближенные эвристические алгоритмы –Для таких алгоритмов надо делать оценки их качества работы "Мы знаем, что задача не имеет решения, но нам надо знать как ее решать" Стругацкие. "Понедельник начинается в субботу"

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

203 ε-граф ε-граф – граф, в котором число ребер равно |E|=(1+ ε)|V|, ε

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

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

206 Искусственный отжиг (Annealing) Общая схема 1. Выбираем случайное допустимое решение (состояние i = 1) 2. Определяем его вес W i 3. Выбираем случайное элементарное преобразование и вычисляем вес нового состояния W* i+1 4. Если вес нового состояния меньше веса исходного состояния (W* i+1

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

208 Задача коммивояжера

209 Генетические алгоритмы Основная идея Допустимое решение описывается как массив значений (например, битов). Допустимое решение должно обладать свойством: – Если мы возьмем часть значений из одного допустимого решения, а остальные значения из другого, то получим снова допустимое решение Далее создается популяция допустимых решений Шаги алгоритма: –Мутации (в некоторых членах популяции случайным образом меняются некоторые значения) –Скрещивание (кроссинговер). В результате появляются новые члены популяции –Отбор - самые слабые (плохие в смысле оптимизируемой функции) особи вымирают Эволюция популяции приводит к появлению оптимальных особей

210 Задача Придумать схему генетического алгоритма для задачи коммивояжера Подсказка: надо использовать другое определение для допустимого решения, допускающее даже отсутствие цикла.