Jednostavni problemi

1. Unesi u ljusku Prologa program za planiranje putovanja avionom. Postavi mu slijedeće upite:

• Kako se može četvrtkom letjeti od Ljubljane do Edinburgha?
• Kako se može obići Milano, Ljubljanu i Zurich ako se u utorak mora krenuti iz Londona a u petak vratiti u London na način da se svaki dan putuje točno jednom?
• Koje dane u tjednu je moguć direktan let iz Londona u Ljubljanu?

2. Napiši program za simulaciju nedeterminističkog konačnog automata bez epsilon prijelaza.

Pomoć:

• Automat definiraj relacijama prijelaz/3 i kraj/1. Neka relacija prijelaz(S1, X, S2) vrijedi ako se iz stanja S1 u stanje S2 može prijeći ako je X slijedeći ulazni simbol. Relacija kraj(S) neka vrijedi ako je S završno stanje automata.
• Rad automata opiši relacijom prihvaca(Stanje, Niz) gdje je Stanje početno stanje automata, a Niz lista ulaznih simbola. Neka relacija vrijedi ako automat prihvaća ulazni niz Niz počevši iz stanja Stanje. Relaciju izvedi analogno relaciji moze_uzeti/2 iz programa o majmunu i banani.

3. Program za simulaciju nedeterminističkog konačnog automata proširi tako da podržava i automat sa epsilon prijelazima. Provjeri točnost programa za automat sa slike tako da pronađeš sve dozvoljene ulazne nizove od tri simbola te iz kojih stanja automat prihvaća koje nizove od sedam simbola.

Pomoć:

• Za definiciju automata uvedi novu relaciju epsilon(S1,S2) koja vrijedi ako postoji epsilon prijelaz iz S1 u S2.
• Epsilon prijelaze opiši dodatnim stavkom relacije prihvaca/3.

4. Automatu iz 3. zadatka dodaj još jedan epsilon prijelaz, od stanja s3 do stanja s1. Postavi upit:

    ?-prihvaca(s3,[a]).
  

5. Unesi u ljusku Prologa program za rješavanje problema osam kraljica u kojem se održavaju liste nepotrošenih stupaca , redaka, uzlaznih i silaznih dijagonala. Proširi područje primjene programa tako da definiraš proceduru rjesenje(N, Raspored) koja pronalazi sve rasporede N kraljica u kojima se one međusobno ne napadaju na šahovskoj ploči dimenzija N*N.

6. Definiraj predikat skoci(Polje1,Polje2) koji je istinit ako je moguć šahovski potez skakačem s polja Polje1 na polje Polje2. Strukturu objekata za predstavljanje pozicije odredi sam. Možeš pretpostaviti da je argument Polje1 već vezan, a Polje2 treba unificirati s rješenjem.

7. Definiraj relaciju put/1 tako da vrijedi ako joj je argument lista pozicija koja predstavlja moguć put skakača po praznoj šahovnici. Provjeri ispravnost relacije slijedećim upitom: kako skakač može s polja B2 u četiri poteza doći na suparnikov kraj šahovnice 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 moguć put skakača po šahovnici na način da skakač ni na jednu poziciju ne doskoči više od jednom. Pomoću nje, pronađi put skakača po praznoj šahovnici od 58 skokova.

9. Definiraj predikat put_bez_ponavljanja/1 koji može pronaći put skakača po praznoj šahovnici od 64 skoka bez ponavljanja.
Ovaj zadatak nije uvjet za predavanje vježbi.