KDP/K 2022
Kolokvijum 2022. godine za RTI održan je 26. novembra. Postavka ovog roka nije dostupna na stranici predmeta. Problem je bio da se napravi nedvosmislena postavka drugog zadatka. Rešenja su imala rekordan broj mrtvih i živih blokiranja.[1]
1. zadatak
Postavka
Koristeći monitore sa Signal and wait disciplinom rešiti problem berberina koji spava (The Sleeping Barber Problem). Berbernica se satoji od čekacionice sa n=5 stolica i berberske stolice na kojoj se ljudi briju. Ukoliko nema mušterija, brica spava. Ukoliko mušterija uđe u berbenicu i sve stolice su zauzete, mušterija ne čeka, već odmah izlazi. Ukoliko je berberin zauzet, a ima slobodnih stolica, mušterija seda i čeka da dođe na red. Ukoliko berberin spava, mušterija ga budi. Obezbediti da se mušterije opslužuju po redosledu dolaska. Uslovne promenljive nisu FIFO niti imaju prioritetne redove čekanja.
Rešenje
Videti prezentacije sa predavanja.
2. zadatak
Postavka
Posmatra se jedan uzak i relativno kratak put kroz kanjon, kojim prolaze kauboji i Indijanci. Ako njime prolaze samo kauboji ili samo Indijanci, oni će biti fini i proći će jedni pored drugih. Ako kroz klisuru žele da prođu i kauboji i Indijanci, primenjuje se "zakon jačeg", tj. onih kojih ima više imaju prvenstvo prolaza kroz kanjon. Treba obezbediti da jednom dobijeno prvenstvo ne važi zauvek - kada se odnos snaga promeni, treba zabraniti dolazak novih osoba koje su do tada bile brojnije, kako bi oni drugi (sada brojniji[2]) mogli da dobiju prvenstvo prolaska kroz kanjon. Koriteći uslovne kritične regione napisati program koji rešava ovaj problem. [3]
Rešenje
Napomene
- ↑ Za blokiranja koja se javljaju u samo određenim sutacijama skidano je šest i po poena, a za potpuna blokiranja deset poena. Za izgladnjivanje je u proseku skidano osam poena.
- ↑ Gleda se zbira broja koji čeka i onih koji su u kanjonu
- ↑ Na uvidu je asistentkinja objasnila da je bilo zamišljeno (mada se i sama složila ne nužno napisano) da ukoliko je došlo do promene prvenstva, svi koji su do tada čekali treba da prođu pre obrtanja prava prvenstva, bez obzira na brojno stanje.