АСП2/К3 2020 — разлика између измена

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу
м (Dodata provera koje je dete veće pre zamene sa detetom)
Ред 56: Ред 56:
         key(table[adr]) = key(table[last_adr])
         key(table[adr]) = key(table[last_adr])
         key(table[last_adr]) = empty
         key(table[last_adr]) = empty
        next(table[last_adr]) = -1
         if last_adr > free then
         if last_adr > free then
             free = last_adr
             free = last_adr

Верзија на датум 20. јануар 2022. у 13:50

Postavka na stranici predmeta.

1. zadatak

Postavka

Upotrebom tehnike objedinjenog ulančavanja implementirati funkciju DELETE_ENTRY koja treba da iz heš tabele (table) fizički ukloni prosledjeni[sic] ključ (key) ukoliko on postoji. Tabela ima n ulaza, a funkcija treba da ažurira i index free tako da ne postoji slobodna lokacija sa većim indeksom.

Rešenje

Prvo tražimo lokaciju ključa za uklanjanje a zatim, ako je ključ pronađen, prevezujemo prethodnu posećenu zauzetu lokaciju, brišemo ključ iz tabele i ažuriramo pokazivač free. 

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

Po novijoj verziji knjige profesora Mila V. Tomaševića pri objedinjenom ulančavanju bi trebalo da se na oslobođeno mesto prebacuje ključ sa kraja liste u kojoj se nalazio, i takav pristup se nalazi ispod: 

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. zadatak

Postavka

Radix exchange algoritam.

  1. Prikazati prve tri iteracije algoritma radix exchange nad sledećom sekvencom 5-bitnih neoznačenih celobrojnih ključeva:
  2. Da li je algoritam stabilan? Obrazložiti ukratko.

Rešenje

Prvo odvajamo ključeve na bitove:

  • 4 — 00100
  • 7 — 00111
  • 9 — 01001
  • 10 — 01010
  • 15 — 01111
  • 16 — 10000
  • 18 — 10010
  • 23 — 10111
Prve tri iteracije radix exchange algoritma nad sekvencom
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

Ovaj algoritam nije stabilan jer funkcioniše po sličnom principu kao quicksort zamena. Stabilnost algoritma podrazumeva da se jednaki elementi sortiraju po indeksu u originalnom poretku, a ovde se može desiti da se prilikom zamene element koji je bio prvi među jednakima prebaci na kraj.

3. zadatak

Postavka

Posmatra se rastuće uređeni binarni hip, koji je dat u vidu niza ključeva heap. Napisati u pseudokodu efikasnu iterativnu funkciju koja menja vrednost zadatog ključa key, na zadatu vrednost new_key. Poznato je da hip ima n elemenata.

Rešenje

Algoritam prvo pronalazi ključ u hipu iterativnim obilaskom niza (ne postoji efikasnija tehnika od te jer hip ne daje nikakve garancije da će se dati element naći u levom ili desnom podstablu). 

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. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa 7 ulaza primenom heš funkcije hp(K) = K mod 7. Za razrešavanje kolizija se koristi tehnika kvadratnog pretraživanja. U tabelu se umeću redom ključevi 38, 31, 10, 56, 21. Odrediti prosečan broj pristupa prilikom uspešnog i neuspešnog traženja i verovatnoću popunjavanja praznih ulaza, pod pretpostavkom da su svi ključevi jednako verovatni.

Rešenje

Ovaj zadatak je rešen na prezentaciji iz heširanja na stranici predmeta.

Popunjena heš tabela
0 10
1 56
2 21
3 38
4 31
5
6
Ispitni nizovi za kvadratno pretraživanje
i / K % 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
  • Umetanje:
    • 38 % 7 = 3 (1 pristup)
    • 31 % 7 = 3 (2 pristupa)
      • (3 + 1*1) % 7 = 4
    • 10 % 7 = 3 (3 pristupa)
      • (3 + 1*1) % 7 = 4
      • (3 + 2*2) % 7 = 0
    • 56 % 7 = 0 (2 pristupa)
      • (0 + 1*1) % 7 = 1
    • 21 % 7 = 0 (4 pristupa)
      • (0 + 1*1) % 7 = 1
      • (0 + 2*2) % 7 = 4
      • (0 + 3*3) % 7 = 2
  • Prosečan broj uspešnih pristupa:
  • Prosečan broj neuspešnih pristupa:
  • Verovatnoća popunjavanja:
    • 5:
    • 6:

5. zadatak

Postavka

Prikazati izgled binomnog hipa nakon svake izmene, ukoliko se prvo obriše minimum, pa se nakon toga dodaju ključevi 2, 32, 4 i nakon toga ponovo obriše minimum.

Rešenje

U originalnoj postavci je umesto broja 19 stajao broj 9. Hip tada ne bi bio validan, tako da se u rešenju smatra da je tu broj 19.

Ispod je dato konačno rešenje zadatka, a koraci se mogu simulirati u simulatoru binomnih hipova, redom umetanjem ključeva 19, 41, 15, 29, 17, 25, 3, 10 i 14, pa zatim izvršavati zadate operacije.

  • ASP2 K3 2020 zadatak 5 hip postavka.png

    Ispravljena postavka zadatka

  • ASP2 K3 2020 zadatak 5 hip rešenje.png

    Konačni izgleda hipa

6. zadatak

Postavka

Data je sekvenca ključeva: 159, 57, 103, 7, 74, 95, 8, 101, 179, 45, 303, 42, 219. Prikazati rad shell sort algoritma po koracima. Navesti korišćenu sekvencu inkremenata i obrazložiti izbor.

Rešenje

Data sekvenca ima 13 ključeva, i ono što inkrementi u shell sort algoritmu treba idealno da postignu jeste mešanje ključeva između "grupa", te se zato biraju uzajamno prosti inkrementi 7, 5, 3, 2 i 1.

Koraci shell sort algoritma
Inkrement 0 1 2 3 4 5 6 7 8 9 10 11 12
Početak 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. zadatak

Postavka

Neka se kod spoljašnjeg heširanja koristi tehnika dinamičkog heširanja. Heš tabela se sastoji od 4 baketa kapaciteta b = 2. Za heš funkciju se koriste viši bitovi heš funkcije K mod 8. Neka se u tabelu umeću redom ključevi 37, 33, 15, 24, 37, 46, 41 i 54. Ilustrovati stanje tabele nakon svakog razrešenja kolizije pri umetanju i u završnom stanju.

Rešenje

[  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. zadatak

Postavka

Neka je dat niz celih brojeva arr dužine n čiji se elementi nalaze u opsegu od 0 do k-1. Napisati u pseudokodu iterativnu funkciju koja pronalazi element koji se najčešće pojavljuje u nizu. Ukoliko ima više takvih elemenata dovoljno je pronaći jedan. Funkcija treba da ima što je moguće bolju vremensku i prostornu složenost. Dozvoljeno je modifikovati polazni niz.

Rešenje

Ovde su dva rešenja pogodna:

  • Pošto nam je dat opseg vrednosti u nizu, može se koristiti counting sort kako bi se u vremenskoj složenosti i prostornoj složenosti pronašla vrednost koja se najviše ponavlja
  • Pošto nam je dato da se polazni niz može modifikovati, može se koristiti heapsort kako bi se u vremenskoj složenosti i prostornoj složenosti pronašla tražena vrednost

Ispod je dato rešenje pomoću counting sort. 

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
Преузето из „https://siwiki.rs/w/index.php?title=АСП2/К3_2020&oldid=3385”