ДС17о11-Поиск (1238906)

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

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

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.

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

Тип файла PDF

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

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

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