АСП2/К3 2020

1. задатак

Поставка

Употребом технике обједињеног уланчавања имплементирати функцију ДЕЛЕТЕ_ЕНТРY која треба да из хеш табеле (табле) физички уклони проследјени^[сиц] кључ (кеy) уколико он постоји. Табела има н улаза, а функција треба да ажурира и индеx фрее тако да не постоји слободна локација са већим индексом.

Решење

Прво тражимо локацију кључа за уклањање а затим, ако је кључ пронађен, превезујемо претходну посећену заузету локацију, бришемо кључ из табеле и ажурирамо показивач фрее.

DELETE ENTRY(table, n, key, free)
prev_adr = -1
adr = h(key)
while (adr ≠ -1) and (key(table[adr]) ≠ key) do
    prev_adr = adr
    adr = next(table[adr])
end_while
if adr ≠ -1 then
    if prev_adr ≠ -1 then
        next(table[prev_adr]) = next(table[adr])
    end_if
    key(table[adr]) = empty
    next(table[adr]) = -1
    if adr > free then
        free = adr
    end_if
end_if

По новијој верзији књиге професора Мила V. Томашевића при обједињеном уланчавању би требало да се на ослобођено место пребацује кључ са краја листе у којој се налазио, и такав приступ се налази испод:

DELETE ENTRY(table, n, key, free)
prev_adr = -1
adr = h(key)
while (adr ≠ -1) and (key(table[adr]) ≠ key) do
    prev_adr = adr
    adr = next(table[adr])
end_while
if adr ≠ -1 then
    if next(table[adr]) = -1 then
        if prev_adr ≠ -1 then
            next(table[prev_adr]) = -1
        end_if
        key(table[adr]) = empty
        next(table[adr]) = -1
        if adr > free then
            free = adr
        end_if
    else
        prev_adr = -1
        last_adr = adr
        while next(table[last_adr]) ≠ -1 do
            prev_adr = last_adr
            last_adr = next(table[last_adr])
        end_while
        next(table[prev_adr]) = -1
        key(table[adr]) = key(table[last_adr])
        key(table[last_adr]) = empty
        if last_adr > free then
            free = last_adr
        end_if
    end_if
end_if

2. задатак

Поставка

Радиx еxцханге алгоритам.

Приказати прве три итерације алгоритма радиx еxцханге над следећом секвенцом 5-битних неозначених целобројних кључева:
Да ли је алгоритам стабилан? Образложити укратко.

Решење

Прво одвајамо кључеве на битове:

4 — 00100
7 — 00111
9 — 01001
10 — 01010
15 — 01111
16 — 10000
18 — 10010
23 — 10111

Прве три итерације *радиx еxцханге* алгоритма над секвенцом
0	1	2	3	4	5	6	7
7	18	23	4	10	16	9	15
7	15	9	4	10	16	23	18
7	4	9	15	10	16	23	18
7	4	9	10	15	16	18	23

Овај алгоритам није стабилан јер функционише по сличном принципу као qуицксорт замена. Стабилност алгоритма подразумева да се једнаки елементи сортирају по индексу у оригиналном поретку, а овде се може десити да се приликом замене елемент који је био први међу једнакима пребаци на крај.

3. задатак

Поставка

Посматра се растуће уређени бинарни хип, који је дат у виду низа кључева хеап. Написати у псеудокоду ефикасну итеративну функцију која мења вредност задатог кључа кеy, на задату вредност неw_кеy. Познато је да хип има н елемената.

Решење

Алгоритам прво проналази кључ у хипу итеративним обиласком низа (не постоји ефикаснија техника од те јер хип не даје никакве гаранције да ће се дати елемент наћи у левом или десном подстаблу).

HEAP CHANGE(heap, n, key, new_key)
pos = -1
for i = 1 to n do
    if heap[i] = key then
        pos = i
        break
    end_if
end_for
if pos = -1 then
    ERROR(Ključ nije u hipu)
end_if
heap[pos] = new_key
parent_pos = pos / 2
child_pos_1 = pos * 2
child_pos_2 = pos * 2 + 1
if (parent_pos > 0) and (heap[parent_pos] > heap[pos]) then
    while (parent_pos > 0) and (heap[parent_pos] > heap[pos]) do
        heap[pos] = heap[parent_pos]
        heap[parent_pos] = new_key
        pos = parent_pos
        parent_pos = pos / 2
    end_while
else if ((child_pos_1 ≤ n) and (heap[child_pos_1] < heap[pos])) or ((child_pos_2 ≤ n) and (heap[child_pos_2] < heap[pos])) then
    while ((child_pos_1 ≤ n) and (heap[child_pos_1] < heap[pos])) or ((child_pos_2 ≤ n) and (heap[child_pos_2] < heap[pos])) do
        if (child_pos_1 ≤ n) and (heap[child_pos_2] < heap[child_pos_1] < heap[pos]) then
            heap[pos] = heap[child_pos_1]
            heap[child_pos_1] = new_key
            pos = child_pos_1
        else
            heap[pos] = heap[child_pos_2]
            heap[child_pos_2] = new_key
            pos = child_pos_2
        end_if
        child_pos_1 = pos * 2
        child_pos_2 = pos * 2 + 1
    end_while
end_if

4. задатак

Поставка

Подаци се смештају у хеш табелу са 7 улаза применом хеш функције х_п(К) = К мод 7. За разрешавање колизија се користи техника квадратног претраживања. У табелу се умећу редом кључеви 38, 31, 10, 56, 21. Одредити просечан број приступа приликом успешног и неуспешног тражења и вероватноћу попуњавања празних улаза, под претпоставком да су сви кључеви једнако вероватни.

Решење

Овај задатак је решен на презентацији из хеширања на страници предмета.

Попуњена хеш табела
0	10
1	56
2	21
3	38
4	31
5
6

Испитни низови за квадратно претраживање
и / К % 7	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	4	5	6	0	1	2	3
3	2	3	4	5	6	0	1
4	2	3	4	5	6	0	1
5	4	5	6	0	1	2	3
6	1	2	3	4	5	6	0

Уметање:
- 38 % 7 = 3 (1 приступ)
- 31 % 7 = 3 (2 приступа)
  - (3 + 1*1) % 7 = 4
- 10 % 7 = 3 (3 приступа)
  - (3 + 1*1) % 7 = 4
  - (3 + 2*2) % 7 = 0
- 56 % 7 = 0 (2 приступа)
  - (0 + 1*1) % 7 = 1
- 21 % 7 = 0 (4 приступа)
  - (0 + 1*1) % 7 = 1
  - (0 + 2*2) % 7 = 4
  - (0 + 3*3) % 7 = 2
Просечан број успешних приступа: $P_u = \frac{1 + 2 + 3 + 2 + 4}{5} = \frac{12}{5} = 2.4$
Просечан број неуспешних приступа: $P_nu = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =$
$= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67$
Вероватноћа попуњавања:
- 5: $\frac{0 + 1 + 0 + 1 + 1 + 1 + 0}{7} = \frac{4}{7}$
- 6: $\frac{0 + 0 + 1 + 0 + 0 + 0 + 1}{7} = \frac{2}{7}$

5. задатак

Поставка

Приказати изглед биномног хипа након сваке измене, уколико се прво обрише минимум, па се након тога додају кључеви 2, 32, 4 и након тога поново обрише минимум.

Решење

У оригиналној поставци је уместо броја 19 стајао број 9. Хип тада не би био валидан, тако да се у решењу сматра да је ту број 19.

Испод је дато коначно решење задатка, а кораци се могу симулирати у симулатору биномних хипова, редом уметањем кључева 19, 41, 15, 29, 17, 25, 3, 10 и 14, па затим извршавати задате операције.

Исправљена поставка задатка
Коначни изгледа хипа

6. задатак

Поставка

Дата је секвенца кључева: 159, 57, 103, 7, 74, 95, 8, 101, 179, 45, 303, 42, 219. Приказати рад схелл сорт алгоритма по корацима. Навести коришћену секвенцу инкремената и образложити избор.

Решење

Дата секвенца има 13 кључева, и оно што инкременти у схелл сорт алгоритму треба идеално да постигну јесте мешање кључева између "група", те се зато бирају узајамно прости инкременти 7, 5, 3, 2 и 1.

Кораци *схелл сорт* алгоритма
Инкремент	0	1	2	3	4	5	6	7	8	9	10	11	12
Почетак	159	57	103	7	74	95	8	101	179	45	303	42	219
7	101	57	45	7	42	95	8	159	179	103	303	74	219
5	95	8	45	7	42	101	57	159	179	103	303	74	219
3	7	8	45	57	42	101	95	159	74	103	303	179	219
3	7	8	45	57	42	74	95	159	101	103	303	179	219
2	7	8	42	57	45	74	95	103	101	159	219	179	303
1	7	8	42	45	57	74	95	101	103	159	179	219	303

7. задатак

Поставка

Нека се код спољашњег хеширања користи техника динамичког хеширања. Хеш табела се састоји од 4 бакета капацитета б = 2. За хеш функцију се користе виши битови хеш функције К мод 8. Нека се у табелу умећу редом кључеви 37, 33, 15, 24, 37, 46, 41 и 54. Илустровати стање табеле након сваког разрешења колизије при уметању и у завршном стању.

Решење

[  00  |  01  |  10  |  11  ]
                  |
               [37   ]

[  00  |  01  |  10  |  11  ]
   |              |
[33   ]        [37   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33   ]        [37   ][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37   ][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37 37][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37 37][15 46]

    [  00  |  01  |  10  |  11  ]
       |             |      |
     /   \           |      |
   |      |          |      |
[24   ][33 41]    [37 37][15 46]
000... 001...

    [  00  |  01  |  10  |  11  ]
       |             |      |
     /   \         /      /   \
   |      |      |      |      |
[24   ][33 41][37 37][46 54][15   ]
000... 001...        110... 111...

8. задатак

Поставка

Нека је дат низ целих бројева арр дужине н чији се елементи налазе у опсегу од 0 до к-1. Написати у псеудокоду итеративну функцију која проналази елемент који се најчешће појављује у низу. Уколико има више таквих елемената довољно је пронаћи један. Функција треба да има што је могуће бољу временску и просторну сложеност. Дозвољено је модификовати полазни низ.

Решење

Овде су два решења погодна:

Пошто нам је дат опсег вредности у низу, може се користити цоунтинг сорт како би се у временској сложености $\mathcal{O}(n)$ и просторној сложености $\mathcal{O}(k)$ пронашла вредност која се највише понавља
Пошто нам је дато да се полазни низ може модификовати, може се користити хеапсорт како би се у временској сложености $\mathcal{O}(n \log n)$ и просторној сложености $\mathcal{O}(1)$ пронашла тражена вредност

Испод је дато решење помоћу цоунтинг сорт.

FIND MAX REP(arr, n, k)
rep_max = 0
rep_elem = 0
for i = 0 to k-1 do
    c[i] = 0
end_for
for i = 1 to n do
    c[arr[i]] = c[arr[i]] + 1
    if c[arr[i]] > rep_max then
        rep_max = c[arr[i]]
        rep_elem = arr[i]
    end_if
end_for
return rep_elem

АСП2/К3 2020

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

7. задатак

Поставка

Решење

8. задатак

Поставка

Решење

Мени за навигацију

АСП2/К3 2020

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

7. задатак

Поставка

Решење

8. задатак

Поставка

Решење

Мени за навигацију

Претрага