Vsebina naloge:
V strojnem učenju pogosto uporabljamo različne drevesne strukture, ki jih je potrebno prikazati uporabniku, bodisi na zaslonu, bodisi v raznih dokumentih in izpisih. Ključni problem pri tem je pozicioniranje vozlišč in povezav drevesa, s katerim želimo doseči čim nazornejši in čim lepši prikaz drevesa ter čim bolje izkoristiti navadno omejeni prostor, ki ga imamo na voljo.
V okviru naloge implementirajte štiri tipe algoritmov za risanje dreves in jih med seboj primerjajte glede na kriterije:
Tipi algoritmov:
a. osnovni, preprosti algoritmi ("top-down", "bottom-up");
b. algoritem s "horizontalno" optimizacijo na osnovi premikanja
poddreves;
c. algoritem tipa "dot" (samo za drevesa; dot namreč obvlada
tudi splošnejše strukture, kot so usmerjeni aciklični grafi);
d. algoritem na osnovi optimizacije kvadratne funkcije z omejitvami (možni
sta izvedbi na osnovi bodisi eksaktnega, bodisi genetskega algoritma).
Algoritme implementirajte v okolju Delphi (Windows). Pri tem razvijte in uporabite enotne mehanizme (objekte) za predstavitev dreves, njihov grafični prikaz na zaslonu in analizo lastnosti algoritmov.
Literatura in viri:
Algoritmi a.: na voljo je implementacija teh algoritmov v pascalu in pripadajoča dokumentacija.
Algoritem b.: članek iz revije Software Practice & Experience, ki ga dobite pri mentorju.
Algoritem c.: dokumentacija sistema "dot", izvorna koda v jeziku C in članek iz revije IEEE.
Algoritem d.: literature (če) ni, ideja in delna realizacija eksaktnega algoritma v pascalu pri mentorju.
Zahteve:
Strojna oprema: PC
Programska oprema: Windows 95 in/ali NT, Borland Delphi (zaželena verzija
3)
Število študentov: 3
Mentor:
Marko Bohanec
Odsek za inteligentne sisteme, soba S-18
Institut Jožef Stefan, Jamova 39, Ljubljana
Tel: 177 3309
EMail: marko.bohanec@ijs.si
Govorilna ura: torek od 9. do 10. ure ali po dogovoru