ДС17о11-Поиск (Лекции Северов Часть 1)
Описание файла
Файл "ДС17о11-Поиск" внутри архива находится в папке "Лекции Северов Часть 1". PDF-файл из архива "Лекции Северов Часть 1", который расположен в категории "". Всё это находится в предмете "вычислительная математика" из 6 семестр, которые можно найти в файловом архиве МФТИ (ГУ). Не смотря на прямую связь этого архива с МФТИ (ГУ), его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Carnegie MellonПоискАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция11, 28ноября,2017Лектор:ДмитрийСеверов,кафедраинформатики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(logN)¢Двоичноедеревопоиска§ Tl<T<Tr,например:Tlll <Tll <Tl<T<rl <Trrl <Trr¢Вероятностьнайтисреди n равновероятныхключей: 2*(lnn+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¢ Th – дерево:=<Th-1,x,Th-2 >,высотаh,вершинnh=nh+1+1+nh+2¢ 0xЧислаЛеонардоTh-1Th-215T1ПервыедеревьяФибоначчи1T4532T3746T2321421116ВставкавАВЛдерево ключаk<nTT:nTTL:nL<nTTR:nR>nT1718Идеяалгоритма¢Вузлехраним§ ключ,баланс,указатели:левый,правый,A,B,C¢Вставка1.2.3.4.пройтипопутипоискаипроверить,чтоданногоключавдеревеещенет;вставитьновыйузелиопределитьполученныйбаланс;вернутьсяпопутипоискаи,принеобходимости,выполнятьбалансировкуесли «высотаподдеревасовставкойувеличилась»,товарианты1.дисбалансисправляетсявставкой2.левоеподдеревона1выше3.балансировка(левоеподдеревона2выше)1.еслилевоеподподдерево выше,тослучай1(A-Bротацияуказателей)2.иначеслучай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)modN – функциярасстановки§ 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)modm¢ Квадратичноеисследованиеh(k,i)=(h’(k)+c1i+c2i2)modm¢ Двойноехешированиеh(k,i)=(h1(k)+ih2(k))modm¢61626364656667.
