Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2021-03-17 | 79 |
5.00
из
|
Заказать работу |
|
|
Рис. 5
Decreasing a key
BINOMIAL-HEAP-DECREASE-KEY(H, x, k) 1 if k > key [ x ] 2 then error "new key is greater than current key" 3 key [ x ] ← k 4 y ← x 5 z ← p [ y ] 6 while z ≠ NIL and key [ y ] < key [ z ] 7 do exchange key [ y ] ↔ key [ z ] 8 ▸ If y and z have satellite fields, exchange them, too. 9 y ← z 10 z ← p [ y ]
Рис. 6
Deleting a key
BINOMIAL-HEAP-DELETE(H, x)1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)2 BINOMIAL-HEAP-EXTRACT-MIN(H)
Fibonacci Heaps
Structure of Fibonacci heaps
Pic. 1
Inserting a node
FIB-HEAP-INSERT(H, x) 1 degree [ x ] ← 0 2 p [ x ] ← NIL 3 child [ x ] ← NIL 4 left [ x ] ← x 5 right [ x ] ← x 6 mark [ x ] ← FALSE 7 concatenate the root list containing x with root list H 8 if min [ H ] = NIL or key [ x ] < key [ min [ H ]] 9 then min [ H ] ← x 10 n [ H ] ← n [ H ] + 1
Pic. 2
Uniting two Fibonacci heaps
FIB-HEAP-UNION(H 1, H 2)1 H ← MAKE-FIB-HEAP()2 min [ H ] ← min [ H 1]3 concatenate the root list of H 2 with the root list of H 4 if (min [ H 1] = NIL) or (min [ H 2] ≠ NIL and min [ H 2] < min [ H 1])5 then min [ H ] ← min [ H 2]6 n [ H ] ← n [ H 1] + n [ H 2]7 free the objects H 1 and H 28 return H
Extracting the minimum node
FIB-HEAP-EXTRACT-MIN(H) 1 z ← min [ H ] 2 if z ≠ NIL 3 then for each child x of z 4 do add x to the root list of H 5 p [ x ] ← NIL 6 remove z from the root list of H 7 if z = right [ z ] 8 then min [ H ] ← NIL 9 else min [ H ] ← right [ z ]10 CONSOLIDATE(H)11 n [ H ] ← n [ H ] - 112 return z
Pic. 3
CONSOLIDATE(H) 1 for i ← 0 to D (n [ H ]) 2 do A [ i ] ← NIL 3 for each node w in the root list of H 4 do x ← w 5 d ← degree [ x ] 6 while A [ d ] ≠ NIL 7 do y ← A [ d ] ▹ Another node with the same degree as x. 8 if key [ x ] > key [ y ] 9 then exchange x ↔ y 10 FIB-HEAP-LINK(H, y, x)11 A [ d ] ← NIL12 d ← d + 113 A [ d ] ← x 14 min [ H ] ← NIL15 for i ← 0 to D (n [ H ])16 do if A [ i ] ≠ NIL17 then add A [ i ] to the root list of H 18 if min [ H ] = NIL or key [ A [ i ]] < key [ min [ H ]]19 then min [ H ] ← A [ i ]FIB-HEAP-LINK(H, y, x)1 remove y from the root list of H 2 make y a child of x, incrementing degree [ x ]3 mark [ y ] ← FALSE
|
Структуры данных для непересекающихся множеств
Make_ Set(x) x - представитель
Union (х, у)
Find_Set(x)
a | b | c | d | e | f | g |
a | b | c | d | e | f | g |
a | b | c | d | e | f | g |
a | b | c | d | e | f | g |
a | b | c | d | e | f | g |
Весовая эвристика – короткий список присоединяем к длинному
Pic. 3
Первая эвристика - объединение по рангу (высота)
Вторая эвристика - сжатие пути при выполнении Find_Set
Pic. 1
Pic. 2
Find_Set(x) – O(1)
Union(х, у) – O(n)
Хеш-таблицы
1 | 3 |
Колизии
Index = key%m – hash функция
Разрешение коллизий в самом массиве
1 | 11 | 3 | 31 |
Удаление 11
1 | -1 | 3 | 31 |
1 | 12 | 3 | 31 |
Удаление 2
1 |
1 | 31 | 3 |
Двойное хеширование
h (k, i) = (h1 (k) + i*(1+h2 (k))) mod m,
Построение хеш-функции методом умножения
к
A
1 |
kA
Pic. 1
H(k) =kA&0xffff
m = 2p ; p=16;
Универсальное хеширование
|
ha,b(k)=((ak+b) mod p) mod m; 1<a<p; 0<b<p; p>max(k)
Пространственноехеширование
Pic. 2
(28 bits) | Y (2 bits) | X (2 bits) |
Y (16 bits) | X (16 bits) |
Pic. 3
CRC алгоритм
10011011
+11001010
--------
01010001
10011011
-1 1001010
--------
01010001
10000: 10101
10101 1
0101
110000: 10101
10101 11
11010
10101
1111
100000: 10101
10101 10
01010
00000
1010
100000: 0101
0101 10
01010
1010
1010000: 0101
01010
0101
11110
0101
1011
Pic. 4
Pic. 5
Pic. 6
r=*p++;
while (len--)
{
t = r;
r = *p++;
r^=table[t];
}
Поиск подстроки
Рис 1
The naive string-matching algorithm NAIVE-STRING-MATCHER(T, P)1 n ← length [ T ]2 m ← length [ P ]3 for s ← 0 to n - m 4 do if P [1 ‥ m ] = T [ s + 1 ‥ s + m ]5 then print "Pattern occurs with shift" s
Рис 2
Procedure NAIVE-STRING-MATCHER takes time O ((n - m + 1) m)
The Rabin-Karp algorithm
Пусть Σ = {0, 1, 2,..., 9}
p = P [ m ] + 10 (P [ m - 1] + 10(P [ m - 2] + · · · + 10(P [2] + 10 P [1]))).
t 0 <= T [1 ‥ m ] in time Θ(m)
m=5
10(31415 - 10000 · 3) + 2 = 14152.
=> сложность O(n)
h=d^(m-1)
q – простое число
dq<maxint
Рис 3
RABIN-KARP-MATCHER(T, P, d, q) 1 n ← length [ T ] 2 m ← length [ P ] 3 h ← dm -1 mod q 4 p ← 0 5 t 0 ← 0 6 for i ← 1 to m ▹ Preprocessing. 7 do p ← (dp + P [ i ]) mod q 8 t 0 ← (dt 0 + T [ i ]) mod q 9 for s ← 0 to n - m ▹ Matching.10 do if p = ts 11 then if P [1 ‥ m ] = T [ s + 1 ‥ s + m ]12 then print "Pattern occurs with shift" s 13 if s < n - m 14 then ts +1 ← (d (ts - T [ s + 1] h) + T [ s + m + 1]) mod q=> сложность O(n) в среднем и O(n*m) в худшем случае.
|
|
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!