Osvježena lista zanimljivih problema

Rješenja navedenih problema, dakako, trebaju biti implementirana u programskom jeziku Java.

P1. Očitavanje upisanih znamenaka

Na listu papira broj se unosi popunjavanjem predloška, gdje je svaka znamenka prikazana kao znamenka na LCD display-u. Primjer je prikazan u nastavku.

Gornji red znamenki je unaprijed odštampan popunjen (svih 10 znamenki) i služi kao uzorak. Čovjek popunjava red ispod. Funkcija kao ulaz dobiva takvu sliku (slika je nastala skeniranjem), a kao izlaz treba vratiti prepoznati broj. Na mjestu znamenki za koje nije sigurno što su, smije se vratiti upitnik. Što algoritam smije pretpostaviti? Idealno: ništa. Unaprijed ne zna koliko ima znamenki odnosno koja im je veličina. Slabija varijanta algoritma bi mogla tražiti da se kao parametar uz sliku preda i očekivani broj znamenki. Slika koja se dobije je 256-nijansi sive boje.

P2. Pronalaženje optimalnog plana zamjena u burzi grupa

Na početku kolegija studentima se nudi mogućnost zamjena grupa. Međutim, trenutno je podržana isključivo mogućnost zamjena 1 na 1, u smislu da ako student S1 (koji je u grupi A) želi u grupu B, a student S2 (koji je u grupi B) želi u grupu A, to se može provesti. Složeniji je slučaj sljedeći: S1 želi iz A u B, S2 želi iz B u C a S3 želi iz C u A. Dva studenta direktno se nikako ne mogu zamijeniti, iako je očito da se zamjena može obaviti ako se uključe sva tri studenta. Općenitije, problem je sljedeći: postoji nekoliko tisuća ponuda oblika Si želi iz Gj u Gk. Potrebno je generirati takav plan koji će osigurati da se najvećem mogućem broju studenata želja ispuni (drugim riječima, pametno pronaći dvojke, trojke, četvorke, ... tako da se postigne maksimalni broj zamjena; uočite da se ovo neće dogoditi ako se krene pohlepnim algoritmom tipa nađi najveće grupacije, ili nađi najmanje grupacije). Ovaj algoritam pokretao bi se primjerice jednom svakih sat vremena i izvršavao napravljene planove.

P3. Očitavanje slova u tablici

Na listu papira nalazi se tablica s korekcijama (jedno slovo po ćeliji) - koristi se kod obrazaca za ispite na zaokruživanje. Slika je 256-nijansi sive boje. Zadatak je napisati funkciju koja će primiti sliku, pronaći tablicu u njoj (ništa osim tablice nema u slici), i potom za svaku ćeliju pročitati što unutra piše (ništa ili ako nešto piše, koje je slovo). Evo primjera.

Ovo naravno nikada neće biti 100% uspješno, jer je ponekad naprosto nemoguće pročitati što je netko napisao:

No već i 90% točnosti bi bilo izvrsno. Neugodna stvar kod ovog algoritma jest da ako nije siguran u nešto, onda to treba i reći, i odbiti proglasti slovo nečime za što nije siguran - tada je bolje za to pitati čovjeka koji će sam procijeniti o čemu se tu radi.

Izazovi

Stvaranje interaktivnih primjera za studente koji slušaju kolegije Digitalna Logika i Digitalna Elektronika, on-line ispita i vježbi sa trenutnim ocjenjivanjem, optimizacija postojećeg koda itd.

Također, sastavni dio Projekta čini sam programski jezik Java kao i osnove objektno-orijentiranog programiranja.

U nastavku slijedi još nekoliko konkretnih zadataka koje treba riješiti.

Izrada Web aplikacija

Dodatak aplikaciji Nescume - podsustav za rad s porukama

Slanje poruka studenata i otvorenih pitanja vezanih uz neki dio kolegija (nešto tipa bug-report); praćenje statusa poruka, odgovaranje na poruke (od strane više ljudi koji na to imaju pravo) i sl.

Dodatak aplikaciji Nescume - podsustav za vođenje bodovanja laboratorijskih vježbi (STATUS: 100%)

dodjela studenata asistentima, evidencija tko se je pojavio na labosu, koliko je bodova dobio za koju stavku ocjenjivanja i sl.

Dodatak aplikaciji Nescume - Burza grupa: podsustav za vođenje grupa studenata i izmjene istih (STATUS: 100%)

dodjela studenata grupama, samostalno mijenjanje trenutne grupe, zamjene uz potvrdu i direktne zamjene grupa, itd.

Proširenje sustava StudTest - složeni algoritmi

Dodatak aplikaciji StudTest - odabir zadataka iz kolekcije zadataka na temelju programa (STATUS: 60% gotovo)

StudTest, između ostalog, radi s kolekcijama zadataka, pri čemu su zadaci razvrstani u grupe. Odabir zadataka koji ulaze u neki test trenutno se radi po vrlo jednostavnom algoritmu, tipa: izaberi 10 zadataka iz grupe XYZ. Potrebno je napraviti podsustav koji će ponuditi složeniji kriterij za odabir zadataka. "Kriterij" se zadaje u obliku programa (tekst, tj. skripte) za koji najprije treba napraviti parser, isparsirati program i zatim u skladu s tim programom odabrati zadatke. Program treba imati mogućnost definiranja složenih kriterija, poput: "za treći zadatak testa odaberi jedan od zadataka iz podgrupe XYZ1 ili iz podgrupe XYZ2", "za peti zadatak testa odaberi jedan od zadataka iz podgrupe XYZ3", "za sve ostale zadatke testa odaberi zadatak iz podgrupe XYZ4".

Dodatak aplikaciji StudTest - ručna evaluacija zadataka

Kako bi se kroz sustav podržalo rješavanje zadataka koji su u proznom stilu te se ne mogu ispravljati automatski, potrebno je nadograditi sustav kako bi ponudio mjesto na kojem ispravljači zadataka mogu preuzimati zadatke koje je potrebno evaluirati, obave evaluaciju i daju svoje komentare. Također, treba omogućiti da različiti ispravljači vide / preuzimaju samo one zadatke koje trebaju ispravljati.

Dodatak aplikaciji StudTest - adaptivno vođenje testova

U sustavu StudTest za vođenje testa definirana je komponenta TestController. Zadatak ove komponente jest, između ostalog, odabir zadataka koji ulaze u neki test. U sustav je trenutno ugrađen vrlo jednostavan TestController, koji na početku pisanja testa odjednom stvori sve zadatke koji ulaze u test. U sklopu rješenja ovog zadatka potrebno je napraviti TestController komponentu koja testove vodi adaptivno. To znači da najprije odabere nekoliko zadataka koje student riješi; nakon toga, u skladu s rješenjima studenta odabere sljedećih nekoliko zadataka (itd.).

Razno - algoritmi

Minimizacija Booleove funkcije

Razviti algoritam koji je u stanju za proizvoljnu nepotpuno specificiranu Booleovu funkciju od 5 varijabli pronaći jedan minimalni oblik u najviše 10ms (na računalu s procesorom Pentium na 2GHz, 512MB RAM-a).

Razviti algoritam koji je u stanju za proizvoljnu nepotpuno specificiranu Booleovu funkciju od 5 varijabli provjeriti je li zadani oblik (npr. zada se algebarski zapis funkcije) jedan od minimalnih oblika te funkcije u najviše 10ms (na računalu s procesorom Pentium na 2GHz, 512MB RAM-a).

Razviti algoritam koji je u stanju za proizvoljnu nepotpuno specificiranu Booleovu funkciju od 5 varijabli pronaći sve minimalne oblike te funkcije u najviše 100ms (na računalu s procesorom Pentium na 2GHz, 512MB RAM-a).

Kao osnova za razvoj ovih algoritama može poslužiti, primjerice, Quine-McCluskey. Također, prethodni zadaci podrazumjevaju razumnu/ekonomičnu uporabu memorije računala. Implementacije moraju voditi računa o podršci za istovremeno izvođenje više minimizacija.

Analiza i obrada slike

Kako bi se omogućilo automatsko ispravljanje raznih oblika pisanih ispita, potrebno je razviti podsustav za automatsko prepoznavanje raznih skeniranih obrazaca. Primjer je programirani PLA sklop gdje je potrebno očitati raspored programiranih sklopki. Dizajn treba biti modularan tako da se mogu dodavati "prepoznavači" za druge sklopove. Također, uključena je i analiza bar-koda. Ovaj zadatak uključit ce pojmove poput registracije slike, a radi robusnosti, za prepoznavanje dijelova slike mogu se koristiti neuronske mreže.

Više informacija uskoro...