KDP/Jul-1 2025

Ispit iz KDP-a u roku Jul-1 2025. godine održan je 20. avgusta. Postavka roka trenutno nije dostupna onlajn.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koje internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bilo moguće. Potrebno je rešiti problem koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice. Proces koji je ranije uputio wait zahtev treba ranije da obavi svoju operaciju. Pretpostaviti da u bilo kom trenutku maksimalno N procesa može uputiti zahtev za pristup semaforu.

2. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Automobili koji dolaze sa severa i juga moraju da pređu reku preko mosta (One lane bridge problem). Na mostu postoji samo jedna vozna traka. Znači, u bilo kom trenutku mostom može da prođe jedan ili više automobila koji dolaze iz istog smera (ali ne i iz suprotnog smera). Obezbediti da se smer saobraćaja menja svaki put nakon što ga pređe 10 automobila iz istog smera, ako su za to vreme jedan ili više automobila čekali da ga pređu iz suprotnog smera. Napisati monitor sa signal and wait disciplinom koji rešava dati problem.

3. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Filterska mreža za traženje minimuma niza. Element mreže na svoje ulaze prima dve^[sic] niza celih brojeva koja se završavaju sa vrednošću EOS. Element na jednom izlazu treba da generiše vrednost koja odgovara minimalnoj vrednosti iz primljenih nizova, i nakon toga vrednost EOS. Prikazati filtersku mrežu koja najbrže nalazi minimum 11 vrednosti.

4. zadatak

Postavka

Pretpostaviti da postoji $N$ putnika i jedno vozilo na toboganu (The roller coaster problem). Putnici se naizmenično šetaju po luna parku i voze na toboganu. Tobogan može da primi najviše $K$ putnika pri čemu je $K < N$. Vožnja toboganom može da počne samo ukoliko se sakupilo tačno $K$ putnika. Koristeći C-Lindu napisati program koji rešava ovaj problem.

Rešenje

const int N, K; // K < N

void putnik(int i) {
    while (true) {
        // setnja
        in("ticket");
        out("ready");
        in("start_ride");
        // voznja
        in("end_ride");
    }
}

void tobogan() {
    while (true) {
        for (int i = 0; i < K; i++) out("ticket");
        for (int i = 0; i < K; i++) in("ready");
        for (int i = 0; i < K; i++) out("start_ride");
        // voznja
        for (int i = 0; i < K; i++) out("end_ride");
    }
}

void init() {
    eval(tobogan);
    for (int i = 0; i < N; i++) {
        eval(putnik, i);
    }
}