АСП1/Август 2021

Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

1. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).

1. Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje Compressed Sparse Row način čuvanja.
2. Napisati funkciju u pseudokodu koja na osnovu sačuvane Compressed Sparse Row reprezentacije matrice M i unetog broja i štampa sve nenulte elemente i-te vrste.

2. zadatak

Postavka

Navedite načine reprezentacije grafova i njihove prednosti i mane.

Rešenje

Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.

3. zadatak

Postavka

Zadato je binarno stablo S i date su adrese dva čvora x i y. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.

Rešenje

LOWEST_COMMON_ANCESTOR(S, x, y)
return FIND(S,x,y)
FIND(S, x, y)
if S == null
   return null
end_if
if S == x || S == y
   return S
end_if
left = FIND(S.left,x,y)
right = FIND(S.right,x,y)
if left ≠ null && right ≠ null
   return S
else if left ≠ null
   return left
else if right ≠ null
   return right
else
   return null
end_if

4. zadatak

Postavka

Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.

Rešenje

$PE = PI + 2n$, gde je $n$ broj čvorova u stablu izvođenje indukcijom, kao u knjizi/na predavanju.

5. zadatak

Postavka

Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati funkciju u pseudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.

Rešenje

Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena. Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.

PROCESS_IMAGES(images, operations)
S = head(images)
O = head(operations)
while s ≠ NIL do
    while o ≠ NIL do
        data(S) = (operation(O))(data(S))
    end_while
end_while

6. zadatak

Postavka

Huffman-ov algoritam: Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.

Rešenje

Najobičniji statički Huffman za zadatim frekvencijama.

7. zadatak

Postavka

Dat je grad koji je modelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor X) do kuće (čvor Y) najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa G (nije data reprezentacija, rešenje treba da bude konceptualno), zadatih lokacija kuće i škole, Y i X, i opasnog dela grada Z, pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.

Rešenje

Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora Z, za njega se upiše težina beskonačno i ta petlja preskoči sa continue. Na kraju se samo proveri dostižnost ciljnog čvora.

8. zadatak

Postavka

Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.

Rešenje

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

9. zadatak

Postavka

1. Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
2. Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.

Rešenje

Videti zadatak iz julskog roka 2020.

10. zadatak

Postavka

Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.

1. Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uporediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosti elementa skupu za ove dve reprezentacije.
2. Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).

Rešenje

Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).