ДСо18-11-Поиск (1238949)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonПоискАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 11, 16 ноября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Термины1. Поиск - быстрое извлечение по конкретномупризнаку части информации, накопленной вкомпьютере2. Ключ – специальное поле записи, однозначнохарактеризующее эту запись.3. Таблица или файл – набор всех записей.4. Результаты поиска:1. удачный – запись с искомым ключом найдена;2.

неудачный – запись не найдена.2ЗадачаЕсть элементы S, с ключами K,имеющими отношение порядка.¢ Определить отображение Н ключей K вадреса А памяти машины так, чтобыпоиск элемента с заданным ключомтребовал как можно меньше ресурсов?¢3Линейный поиск O(N)template <typename T> class List {Item<T> *front,*back; T rab;Item<T>* find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL) {if(F->get_node()==k) break; ptr=F; }return ptr; }4Линейный поиск места включения вупорядоченном спискеItem<T>* Find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL)if(F->get_node()<k) ptr=F;else if(F->get_node()==k) break;else { F=NULL; return back; }return ptr; }566789Идеи ускорения с ценой¢Самоорганизующаяся таблица (кеш)§ обнаруженную запись – в «начало» таблицы и частоиспользуемые записи будут в «начале» таблицы§ нужно «начало» и переупорядочениеБинарный поиск§ посмотрим ключ в «середин廧 нужен произвольный доступ и упорядочение¢ Правильное дерево§ ищем за ≈m проверок среди ≈2m элементов§ нужна перестройка при записи и удалении¢10Поиск в дереве O(log N)¢Двоичное дерево поиска§ Tl < T < Tr,например: Tlll < Tll < Tl < T < rl < Trrl < Trr¢Вероятность найти среди n равновероятныхключей: 2*(ln n + g -1)0КонстантаЭйлера0,577…T1Tl2Tll3TlllTrTlrTrlTrrTrrl11Идеально сбалансированное деревоДвоичное дерево поиска + | nr – nl | £ 1¢ Вероятность найти среди n равновероятныхключей: log2 – 1, что лучше любого двоичногодерева поиска в 2ln2 ≈ 1,39…¢¢Выигрыш превышает затраты ?§ Если много узлов§ Если много поисков и мало вставок12Идеально сбалансированное дерево40201030603050105502010205020603530540406010705603050704013А если не идеализировать?¢Дерево сбалансированное идеально| nr –nl | £ 1¢АВЛ-дерево, сбалансированное «неидеально», нопрактично по Адельсону-Вельскому и Ландису| hr –hl | £ 1log2 (n+1) < hb(n) < 1,4404* log2 (n+2) – 0.328¢Какое АВЛ-дерево самое «плохое» - минимум узловпри заданной высоте ?14Дерево ФибоначчиT – деревo: высота 0, вершин 0¢ T1 – дерево: высота 1 , вершин 1¢ 0T – дерево: = < Th-1, x, Th-2 >, высота h,вершин nh=nh-1+1+nh-2¢ hxЧислаЛеонардоTh-1Th-215T1Первые деревья Фибоначчи1T4532T3746T2321421116Вставка в АВЛ дерево ключа k<nTT:nTTL:nL<nTTR:nR>nT1718Идея алгоритма¢В узле храним§ ключ, баланс, указатели: левый, правый, A, B, C¢Вставка1.2.3.4.пройти по пути поиска и проверить, что данного ключа в дереве еще нет;вставить новый узел и определить полученный баланс;вернуться по пути поиска и, при необходимости, выполнять балансировкуесли «высота поддерева со вставкой увеличилась», то варианты1.2.дисбаланс исправляется вставкойлевое поддерево на 1 выше3.балансировка (левое поддерево на 2 выше)1.2.если левое подподдерево выше, то случай 1 (A-B ротация указателей)иначе случай 2 (A-B-C ротация)19202021212222232350(-1)30(-1)20(0)15(0)70(0)40(0)60(0)80(0)25(0)2450(-1)30(-1)20(0)15(0)10(0)40(0)70(0)60(0)80(0)25(0)left = new Item<T>(K); h++;2550(-1)30(-1)20(-1)15(-1)10(0)40(0)70(0)60(0)80(0)25(0)case 0: b--; break;…case 0: b--; break;2650(-1)30(-1)30(-1)20(-1)15(-1)10(0)40(0)70(0)60(0)80(0)25(0)case -1: A = left;If( A->b == -1){ B = new Item<T>; *B=*this;2750(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)80(0)40(0)B->b=0; right = B; key=A->key;2850(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)80(0)40(0)B->left = A->right;2950(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)left = A->left;3050(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)delete A;3150(-1)20(0)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)b = 0; h=0;3250(-1)30(0)70(0)20(0)15(0)40(0)25(0)35(0)60(0)80(0)45(0)3350(-1)30(0)70(0)20(0)15(0)40(0)25(0)35(0)60(0)80(0)45(0)37(0)else { if(right) right->ins(K); else { right = new Item<T>(K); h++;}3450(-1)30(1)70(0)20(0)15(0)40(-1)25(0)35(1)60(0)80(0)45(0)37(0)else{ if(right) right->ins(K);…if(K < key) { if(left) left->ins(K);3550(-1)50(-1)30(1)70(0)20(0)15(0)40(-1)25(0)35(1)60(0)80(0)45(0)37(0)C = new Item<T>; *C = *this; B = A ->right;3640(-1)50(-1)45(0)50(-1)30(1)20(0)15(0)70(0)35(1)25(0)60(0)80(0)37(0)A ->right = B->left;3740(-1)45(0)40(-1)30(1)20(0)15(0)50(-1)35(1)25(0)37(0)70(0)60(0)80(0)right = C; key = B->key;3840(-1)40(-1)30(0)20(0)15(0)50(1)35(1)25(0)37(0)45(0)70(0)60(0)80(0)C->left = B->right;C->b = (B->b==-1)1:0);A->b = (B->b==1)-1:0);3940(0)30(0)20(0)15(0)50(1)35(1)25(0)37(0)45(0)70(0)60(0)80(0)delete B; b=0; h=0;40Эффективность ?¢Вопросы§ Какова средняя высота АВЛ-деревьев n! равновероятныхперестановок n ключей?§ Какова вероятность балансировки вставки?¢Ответы§ Математического исследования нет, а на практик姧¢h = log(n)+ 0.25Вероятность балансировки 0.5Вывод§ Трудно превзойти простейший алгоритм вставки в дерево§ Эффективность балансировки - условна41Удаление элемента из АВЛ дерева - 15(0)3(-1)2(-1)1(0)4(0)8(0)7(-1)6(0)10(0)9(0)11(0)42Удаление элемента из АВЛ дерева - 25(0)3(-1)2(-1)1(0)4(0)8(0)7(-1)6(0)10(0)9(0)11(0)43Удаление элемента из АВЛ дерева - 35(1)3(-1)8(0)2(0)7(-1)1(0)6(0)10(0)9(0)11(0)44Удаление элемента из АВЛ дерева - 45(1)2(0)1(0)8(0)3(0)7(-1)6(0)10(0)9(0)11(0)45Удаление элемента из АВЛ дерева - 55(1)2(0)1(0)8(0)3(0)7(-1)6(0)10(0)9(0)11(0)46Удаление элемента из АВЛ дерева - 65(1)2(0)1(0)7(1)3(0)6(0)10(0)9(0)11(0)47Удаление элемента из АВЛ дерева – 75(1)2(0)1(0)7(1)3(0)6(0)10(0)9(0)11(0)48Удаление элемента из АВЛ дерева - 85(1)2(0)1(0)7(1)3(0)10(0)9(0)11(0)49Удаление элемента из АВЛ дерева5(1)2(0)1(0)10(-1)3(0)7(1)11(0)9(0)50Удаление элемента из АВЛ дерева - 95(1)2(0)1(0)10(-1)3(0)7(1)11(0)9(0)51Удаление элемента из АВЛ дерева - 103(1)2(-1)1(0)10(-1)7(1)11(0)9(0)52Удаление элемента из АВЛ дерева - 113(1)1(0)10(-1)7(1)11(0)9(0)53Удаление элемента из АВЛ дерева - 127(0)3(-1)1(0)10(0)9(0)11(0)54~O(1)ХЕШ-ТАБЛИЦЫ:ПОИСК НА ОСНОВЕ МАССИВА55H: KàANB: поиск по ключамf.e.: Поиск по фамилии, состоящей не болеечем из 10 букв.¢Множество возможных ключей ~3010¢Множество индексов массива ~10356Выбор функции преобразованияH(k) = ord(k) mod N – функция расстановки§ ord(k) = ∑ αi ·30i§ N – простое число§ H(k) Î {0,…,N-1}¢a = H(k') = H(k") – конфликт¢Получение альтернативного индекса –задача разрешения конфликтов¢57Разрешение конфликтов1.

Привлечение дополнительной памяти дляразмещения элементов с одинаковымпервичным индексом – область переполнения2. Размещение элементов с одинаковымипервичными индексами в незанятых ячейкахтого же массива – открытая адресация581. Область переполнения5959602. Открытая адресацияH(k,i)§ i – номер исследования¢ Линейное исследованиеh(k,i) = (h’(k) + i) mod m¢ Квадратичное исследованиеh(k,i) = (h’(k) + c1i + c2i2) mod m¢ Двойное хешированиеh(k,i) = (h1(k) + ih2(k)) mod m¢61626364656667.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций