Jednostavni problemi 1. Unesi u ljusku Prologa program za planiranje putovanja avionom. Postavi mu slijedece upite: * Kako se moze cetvrtkom letjeti od Ljubljane do Edinburgha? * Kako se moze obici Milano, Ljubljanu i Zurich ako se u utorak mora krenuti iz Londona a u petak vratiti u London na nacin da se svaki dan putuje tocno jednom? * Koje dane u tjednu je moguc direktan let iz Londona u Ljubljanu? 2. Napisi program za simulaciju nedeterministickog konacnog automata bez epsilon prijelaza. Pomoc: * Automat definiraj relacijama prijelaz/3 i kraj/1. Neka relacija prijelaz(S1, X, S2) vrijedi ako se iz stanja S1 u stanje S2 moze prijeci ako je X slijedeci ulazni simbol. Relacija kraj(S) neka vrijedi ako je S zavrsno stanje automata. * Rad automata opisi relacijom prihvaca(Stanje, Niz) gdje je Stanje pocetno stanje automata, a Niz lista ulaznih simbola. Neka relacija vrijedi ako automat prihvaca ulazni niz Niz pocevsi iz stanja Stanje. Relaciju izvedi analogno relaciji moze_uzeti/2 iz programa o majmunu i banani. 3. Program za simulaciju nedeterministickog konacnog automata prosiri tako da podrzava i automat sa epsilon prijelazima. Provjeri tocnost programa za automat sa slike tako da pronad/es sve dozvoljene ulazne nizove od tri simbola te iz kojih stanja automat prihvaca koje nizove od sedam simbola. Pomoc: * Za definiciju automata uvedi novu relaciju epsilon(S1,S2) koja vrijedi ako postoji epsilon prijelaz iz S1 u S2. * Epsilon prijelaze opisi dodatnim stavkom relacije prihvaca/3. 4. Automatu iz 3. zadatka dodaj jos jedan epsilon prijelaz, od stanja s3 do stanja s1. Postavi upit: ?-prihvaca(s3,[a]). Da li su rezultati izvrsavanja zadovoljavajuci? Problem rijesi tako da sprijecis petlju u epsilon prijelazima tijekom prihvata jednog znaka. Rjesenje mora biti dovoljno opcenito da program moze simulirati proizvoljni automat. 5. Unesi u ljusku Prologa program za rjesavanje problema osam kraljica u kojem se odrzavaju liste nepotrosenih stupaca , redaka, uzlaznih i silaznih dijagonala. Prosiri podrucje primjene programa tako da definiras proceduru rjesenje(N, Raspored) koja pronalazi sve rasporede N kraljica u kojima se one med/usobno ne napadaju na sahovskoj ploci dimenzija N*N. 6. Definiraj predikat skoci(Polje1,Polje2) koji je istinit ako je moguc sahovski potez skakacem s polja Polje1 na polje Polje2. Strukturu objekata za predstavljanje pozicije odredi sam. Mozes pretpostaviti da je argument Polje1 vec vezan, a Polje2 treba unificirati s rjesenjem. 7. Definiraj relaciju put/1 tako da vrijedi ako joj je argument lista pozicija koja predstavlja moguc put skakaca po praznoj sahovnici. Provjeri ispravnost relacije slijedecim upitom: kako skakac moze s polja B2 u cetiri poteza doci na suparnikov kraj sahovnice tako da se nakon drugog poteza nalazi na polju E5. 8. Definiraj relaciju put_bez_ponavljanja/1 tako da vrijedi ako joj lista pozicija iz argumenta predstavlja moguc put skakaca po sahovnici na nacin da skakac ni na jednu poziciju ne doskoci vise od jednom. Pomocu nje, pronad/i put skakaca po praznoj sahovnici od 58 skokova. 9. Definiraj predikat put_bez_ponavljanja/1 koji moze pronaci put skakaca po praznoj sahovnici od 64 skoka bez ponavljanja. Ovaj zadatak nije uvjet za predavanje vjezbi.