Zapoctove programy z Prologu (Programování II)

[rozdeleni] [zadani]

zimní semestr 2001/2002
Ut 12.20 - 13.50 T5
Roman Barták

Zápoètové pøíklady je možné posílat jen do pátku 20.9.2002 do 24:00 SEÈ, øešení zaslaná pozdìji už nebudu pøijímat (jen opravy)!!!!!

Kompletni reseni prikladu muzete zasilat elektronicky na adresu bartak@kti.mff.cuni.cz nebo odevzdat osobne v konzultacni hodiny.

Reseni zapoctoveho prikladu se sklada z:

dokumentace obsahujici

jmeno autora
presne zadani prikladu
slovni popis pouziteho algoritmu
popis datovych struktur
popis spousteni programu vcetne tvaru vstupnich a vystupnich dat

komentovaneho textu programu ve standardním (ISO) Prologu

program je resen jako predikat se vstupnimi a vystupnimi argumenty! veskere I/O operace (tisk vysledku) jsou jen jako nadstavba
pouzivate-li nadefinovane predikaty (member, append ...), uvedte v samostatnem souboru jejich seznam, vyznam a je-li potreba implementaci; rozhodne nepouzivejte predikaty specificke jen pro danou implementaci Prologu
program musi byt spustitelny v prostredi BinProlog, ECLiPSe, Sicstus Prolog nebo Open Prolog!

primerene velkych zkusebnich dat (pripadne generatoru zkusebnich dat, neni-li v zadani specifikovano jinak).

Pokud bude nektera z popsanych nalezitosti chybet, nebude zapoctovy program prijat!!!
Jakekoliv nejasnosti v zadani se mnou okamzite konzultujte, at si vyhnete pripadnemu predelavani programu.

Polynomy

Polynomy lze reprezentovat (nejen v Prologu) nekolika zpusoby, ktere lze rozdelit do nasledujicich skupin:

A) podle mnozstvi uvedenych koeficientu (Pr. x^3+2*x): A.1) ridky tvar - jsou uvedeny pouze nenulove koeficienty s prislusnou mocninou u promenne/promennych (Pr. [[2,1],[1,3]]); A.2) husty tvar - jsou uvedeny vsechny koeficienty v rostoucim/klesajicim poradi (Pr. [0,2,0,1])
B) podle zpusobu shlukovani promennych: B.1) rekurzivni tvar - polynom vice promennych je vyjadren jako polynom jedne promenne, jehoz koeficienty jsou obdobne polynomy v ostatnich promennych; B.2) distributivni tvar - polynom je zapsan jako soucet termu, z nichz kazdy je tvoren soucinem koeficientu a promennych
Ridky rekurzivní zápis: Je dan libovolne uzavorkovany vyraz s celymi cisly, promennymi (reprezentovany atomy), operacemi +, -, *, ^ (mocnina je pouze na prirozena cisla) a seznam promennych urcujici jejich dulezitost (napr. [x,y] znamena, ze hlavni polynom je v promenne x a jeho koeficienty v promenne y). Vytvorte program, ktery prevede polynom do ridkeho rekurzivniho zapisu, a vytvorte program, ktery vraci ridky rekurzivni zapis v "lidskem" tvaru, tj. pomoci operaci +, -, *, ^ bez zbytecnych nul, jednicek apod.
Ridky distributivní zápis: dtto, ale prevod do ridkeho distributivniho zapisu
Husty rekurzivní zápis: dtto, ale prevod do husteho rekurzivního zápisu
Husty distributivní zápis: dtto, ale prevod do hustého distributivního zápisu

Hradlové síte

Hradlova sít je mnozina hradel, kde kazde hradlo ma jediny vystup, sve jedinecne jmeno, operaci a seznam vstupu (v danem poradi). Vstupem jsou bud jmena jinych hradel nebo jmena vstupnich bodu site. Sit je acyklicka, tj. zadne hradlo nezavisi na svem vystupu. Vysledek hradla se posila na vsechny vstupy daneho jmena (muze jich byt i vice).

Priklad: Hradlova sit pro vyraz x*y+z+x muze vypadat takto: [h(h(1),plus,[h(2),z,x]),h(h(2),krat,[x,y]), kde h(1) a h(2) jsou jmena hradel a x, y, z jsou jmena vstupnich bodu site.

Prevod vyrazu na hradlovou sít (prilis lehke): Vstupem programu je dany vyraz v podobe prologovskeho termu s cisly, identifikatory, operacemi +, *, -, / a libovolnymi funkcemi, napr. 2*a+cos(b)/sin(b). Vytvorte k danemu vyrazu hradlovou sit, ktera vyraz pocita stejnym zpusobem, jako je zadan, tj. bez optimalizaci. K dispozici jsou hradla s operacemi plus, times, minus, div a prislusnymi funkcemi. Hradla s operacemi plus a times mohou mit libovolny pocet vstupu a jejich vstupem nesmi byt vysledek stejne operace.
Optimalizace hradlove site (hledaní ekvivalencí): Je dana hradlova sit. Najdete v ni vsechna ekvivalentni hradla a vytvorte novou sit, ve ktere jsou vsechna navzajem ekvivalentni hradla nahrazena jednim z nich.; Def.: Hradla v siti jsou ekvivalentni, pokud maji stejnou operaci a ekvivalentni nebo shodne vstupy.
Vypocet hradlove site (s externe zadanymi procedurami): Je dana hradlova sit a externi procedury pro vypocet vystupu hradel (jejich jmena se shoduji s operacemi v hradlech a maji vzdy dva argumenty: seznam vstupu a vystup, napr. plus([1,2,3],X)). Napiste program, ktery provede vypocet hradlove site, jsou-li znamy hodnoty vstupnich bodu.
Kompilace hradlove site (s externe zadanymi procedurami): Je dana hradlova sit a externi procedury pro vypocet vystupu hradel (jejich jmena se shoduji s operacemi v hradlech a maji vzdy dva argumenty: seznam vstupu a vystup, napr. plus([1,2,3],X)). Napiste program, ktery vygeneruje kód pocitajici hradlovou sit, napr. plus([1,2,3],X),krat([1,2],Y),plus([X,Y],Z]), jsou-li znamy hodnoty vstupnich bodu.
Linearizace hradlové síte + lokalizace registru: Je dana hradlova sit. Vytvorte program, ktery:; a) usporada hradla tak, aby se kazde hradlo nachazelo az za hradly, ktera pocitaji jeho vstupy; b) priradi vstupnim bodum site a vystupum hradel co nejmensi pocet "registru CPU". Dany registr je mozne opakovane pouzit, musi byt ale vzdy odlisny od registru prirazenych vstupum hradla.

Barvení grafu (splnovaní podmínek)

Je dan graf, ve kterem vrcholy odpovidaji promennym s domenami (obory hodnot) a hrany jsou oznaceny jmenem podminky mezi promennymi. Obarvete graf, tj. priradte kazde promenne hodnotu z jeji domeny tak, aby byly splneny vsechny podminky. Navrhnete vlastni reprezentaci grafu a vytvorte generator, ktery pripravi graf pro reseni problemu N-dam.

Dopredna kontrola (forward checking): Po "obarveni" vrcholu se z domen vsech okolnich vrcholu vyradi nekonzistentni hodnoty, viz Constraint Propagation.
Pohled dopredu (look ahead): Po "obarveni" vrcholu se z domen vsech okolnich vrcholu vyradi nekonzistentni hodnoty, viz. Constraint Propagation.
Lokalni prohledavani s Tabu seznamem: Nejprve se "nahodne" obarvi vsechny vrcholy. Pokud existuje nejaky vrchol, ktery je v konfliktu se svym okolim (neni splnena podminka na hrane), program najde pro tento vrschol jinou barvu tak, aby se konflikt zmensil. Pro odstraneni lokalniho minima pouzijte techniku Tabu seznamu (viz Heuristics and Stochastic Algorithms).
Back-jumping (inteligentní navracení): Barvení se provádí podobne jako pri backtrackingu, ale program se pri nalezeni nekonzistence nevraci pouze o jednu uroven, ale vraci se az na uroven, ktera nekonzistenci zpusobila.

Hricky

NIM (prilis lehke): Je dano N hromadek zapalek, ze kterych stridave odebiraji dva hraci tak, ze mohou odebrat libovolny pocet zapalek z jedne hromadky. Vyhrava ten, kdo odebral posledni zapalku. Napiste program, ktery hleda optimalni strategii pro jednoho hrace.
NIM (varianta): Je dano N hromadek zapalek, ze kterych stridave odebiraji dva hraci tak, ze mohou odebrat libovolny pocet zapalek z jedne hromadky pripadne odebrat stejny pocet zapalek ze dvou hromadek. Vyhrava ten, kdo odebral posledni zapalku. Napiste program, ktery hleda optimalni strategii pro jednoho hrace.
Prelevani vody: Je dano N nadob, jejich objem, pocatecni naplneni a koncove naplneni. Vytvorte program, ktery najde nejkratsi posloupnost preliti vedouci z pocatecniho stavu do koncoveho stavu.
Prelevani vody se zdrojem a kanalem: dtto, ale k dispozici je navic nevycerpatelny zdroj vody a nepreplnitelny kanal.
Lloydova 15 (moc lehke na zapoctak): Ve ctverci N*N je N*N-1 kosticek a jedno volne pole. Vytvorte program, ktery slozi kosticky tak, aby byly usporadane.
Vazeni: Je dáno N identickych predmetu. Nejvyse jeden z techto predmetu je vadny, coz se pozna podle jeho mensi resp. vetsi hmotnosti (nevite, ktera varianta plati). Napiste program, ktery pro dane N zjisti nejmensi pocet vazeni na rovnoramennych vahach, tak aby se zjistilo, ktery predmet je vadny a zda je tezsi nebo lehci nez ostatni. Program take vrati doporuceny postup vazeni.
Zebra: Napiste program, ktery je schopen resit ulohy typu Zebra (napr. jsou ctyri domy, v kazdem bydli jeden clovek majici nejake zamestnani a auto a jsou dany podminky typu "doktor jezdi v mercedesu" apod., najdete prislusne rozlozeni obyvatel domu).
Mastermind (Logik): Napiste program, ktery resi hru Mastermind (pocet policek a barev je vstupnim parametrem) sofistikovanym zpusobem, tj. ne prohledavanim vsech alternativ. K dispozici by mely byt dve varianty programu, jedna umoznuje zadavat ohodnoceni zvenku (rucne), druha ohodnocuje automaticky podle zadaneho vzoru.
Sachova koncovka: Napiste program, ktery resi sachovou koncovku s kralem a vezi.
Ortogonalni latinske ctverce (moc lehke na zapoctak): Latinsky ctverec radu n obsahuje cisla 1 az n, kazde n krat, rozmistene tak, ze v zadnem sloupci ani radku se zadne cislo nevyskytuje dvakrat. Ortogonalni latinsky ctverec obsahuje dvojice cisel <i,j>, 1=<i,j<=n, kazdou jedenkrat, tak, ze v prvni i druhe slozce tvori latinsky ctverec.
Naprogramujte generovani ortogonalniho latinskeho ctverce daneho radu tak, aby se co nejdrive vyloucily nevyhovujici moznosti (tj. ne jednoduchy backtracking, ale napriklad dopredna kontrola).
Obecné hledání optimální (herní) strategie: Je dana hra dvou hracu (pri hre se stridaji), ktera je definovana procedurami mozny_tah, vitezna_pozice apod. Napiste program, ktery hraje optimalni hru za jednoho z hracu.

Rozvrhování a plánování

Letiste: Je dana mnozina typu letadel a pro kazdy typ letadla je dan seznam stojanek, u kterych muze stat. Na kazde stojance muze v dany cas stat pouze jedno letadlo, s vyjimkou stojanky "volna plocha", na ktere muze stat libovolne mnoho letadal (existuji ale letadla, ktere nemohou stat na volne plose - napr. Concorde). Dale je dan letovy plan, tj. seznam letadal s urcenim jejich typu, doby priletu a odletu. Napiste program, ktery rozvrhne letadla na jednotlive stojanky tak, aby co nejvice letadel bylo obhospodareno stojankami (tj. ne na volne plose). Letiste je definovano mnozinou vsech stojanek.
Alokace pultu na letisti: Letiste je popsano jako mnozina pultu, ktere jsou po nekolika sdruzeny do "ostrovu". Dale je dan letovy rad, kde je u kazdeho letu zadan cas odbaveni (iterval od-do) a pocet pultu, ktere jsou potreba. Napiste program, ktery provede rozmisteni pultu pro lety tak, ze vsechny pulty daneho letu se nachazeji ve stejnem ostrove.
Nemocnice: Je dana mnozina sester, kazda sestra ma prirazenu mnozinu cinnosti, ktere muze vykonavat (kvalifikaci). Dale je dan rozvrh pozadavku na cinnosti v danem casovem obdobi. Napiste program, ktery vytvori rozvrh pro konkretni sestry tak, aby pozadavky byly naplneny a pritom zadna sestra neslouzila dele jak tri smeny za sebou.
Vyrobni podnik: Je dana mnozina stroju a mnozina produktu. Kazdemu produktu je prirazena mnozina stroju a doba, za kterou dany stroj produkt vyrobi. Dale je dana mnozina preferenci rikajicich, jaky produkt musi byt vyroben pred jinym produktem. Napiste program, ktery naplanuje vyrobu tak, aby trvala co nejkratsi dobu.
Reklamy: Je dana sada reklam a u kazde reklamy je zadan interval, ve kterem musi byt vysilana. Spojite za sebou smi byt promitnuto jen M reklam a mezi reklamnimi bloky musi byt minimalne N volnych casovych jednotek. Napiste program, ktery provede rozvrzeni reklam.
Obchodní cestující: Je dán graf, ve kterem vrcholy predstavuji mesta a hrany jsou ohodnoceny casem nutnym pro cestu mezi dvema mesty. Kazdemu mestu/vrcholu je prirazena dvojice: delka jednani a interval, ve kterem musi jednani probehnout. Vytvorte program, ktery najde cestu obchodniho cestujiciho zacinajici a koncici v danem meste tak, ze se zucastni vsech jednani.

Omezující podmínky

Reseni aritmetickych podmínek: Je dana mnozina promennych a jejich domen ve tvaru a::[1, 5..10] (definujte prislusne operatory). Dale je dan seznam linearnich aritmetickych podminek s rovnostmi (=) a nerovnostmi (\=) napr. a+2*b=c. Vytvorte program, ktery nejprve zredukuje domeny promennych propagaci pres podminky (napr. a::[1..5], b::[1..5], a+1=b prejde na a::[1..4], b::[2..5]) a nasledne najde reseni podminek, tj. omezi vsechny domeny na jeden prvek (dalsi reseni vyda pomoci backtrackingu).
Reseni aritmetickych podmínek 2 (algebrogramy): Je dana mnozina promennych a jejich domen ve tvaru a::[1, 5..10] (definujte prislusne operatory). Dale je dan seznam aritmetickych podminek s rovnostmi (=) a operacemi +, -, *, napr. a+a*b=c, a podminky ve tvaru alldiff([a,b,c]) zarucujici ruznost promennych. Vytvorte program, ktery nejprve zredukuje domeny promennych propagaci pres podminky (napr. a::[1..5], b::[1..5], a+1=b prejde na a::[1..4], b::[2..5]) a nasledne najde reseni podminek, tj. omezi vsechny domeny na jeden prvek (dalsi reseni vyda pomoci backtrackingu).
Obecne reseni podminek: Je dana mnozina promennych a jejich domen (napr. jako v predchozim priklade). Dale je dan seznam podminek ve tvaru constr(SeznamPromennych,Reduktor), kde Reductor je nazev predikatu slouziciho pro redukci domen promennych pri zmene domeny nektere promenne ze SeznamuPromennych. Kazdy Reduktor ma dva argumenty, prvni je seznam vstupnich domen promennych (v danem poradi) a druhy (ten se pocita) je seznam redukovanych domen (mohou byt i prazdne). Napiste program, ktery nejprve maximalne zredukuje domeny promennych pomoci reduktoru a potom najde reseni podminek, tj. omezi vsechny domeny na jeden prvek, pripadne zjisti, ze podminky nelze vyresit. Pro vyzkouseni navrhnete vlastni reduktory.
Binarizace podmínek: Je dana mnozina promennych a jejich konecnych domen (napr. jako v predchozich prikladech). Dale je dan seznam podminek ve tvaru constr(SeznamPromennych,Podminka), kde Podminka je predikat, ktery testuje, zda je podminka splnena pri danych hodnotach promennych, napr. constr([x,y],'=') pouziva test xa=yb (xa je hodnota promenne x, yb hodnota y). Navrhnete program, ktery danou sadu podminek prevede na ekvivalentni seznam binarnich podminek.
Kompilace podminek: Je dana sada podmínek ve tvaru constr(SeznamPromennych,PopisZavislosti), kde PopisZavislosti je seznam trojic: nazev prevodni funkce, vstupni promenne, vystupni promenne. Prevodni funkce ma dva argumenty, prvni argument je vstupni a obsahuje seznam hodnot vstupnich promennych, druhy argument je vystupni (je pocitan) a obsahuje seznam hodnot vystupnich promennych (napr.: constr([a,b,c],[[plus,[a,b],[c]],[minus,[c,a],[b]],[minus,[c,b],[a]]]) je zachycenim podminky a+b=c). Vytvorte program, ktery jako vstup dostane seznam podmínek a seznam vstupnich promennych a jako vystup vyda prologovsky cil skladajici se z volani prevodnich funkci, ktery resi danou soustavu podminek.
Reseni linearnich podminek eliminaci: Je dana mnozina promennych a mnozina linearnich rovnosti a nerovnosti nad temito promennymi. Napiste program, ktery resi podminky postupnou eliminaci promennych (podobne jako pri symbolickem reseni soustav rovnic a nerovnic pomoci Gaussovy a Fourierovy eliminace).

Ostatní

Prepisovaci pravidla: Je dana sada prepisovacich pravidel tvaru Vzor<=>Prepis|Straz a Vzor=>Pridej|Straz, kde Vzor a Prepis jsou seznamy termu a Straz je prologovsky cil, ktery muze pripadne chybet (pr.: [X<=Y,Y<=Z]=>[X<=Z] nebo [X<=X]<=>[]). Interpretace pravidel je nasledujici: je-li vzor nalezen ve vstupnim seznamu predikatu a je-li splnena Straz, potom
a) v pripade <=> je vzor nahrazen seznamem Prepis
b) v pripade => je pridan seznam Pridej.
Napiste program, ktery prevede seznam termu na redukovany seznam termu aplikaci vsech moznych prepisovacich pravidel.
Analyza vyrazu s operatory: Vstupem programu je seznam definic operatoru ve tvaru op(Priorita,Asoc,Nazev) a seznam tokenu (atomy, cisla a zavorky). Analyzujte posloupnost tokenu podle operatoru a prevedte ji do struktury prologovskeho termu.; Napr.: ?-analyzuj([op(4,yfx,plus),op(2,yfx,times)],[a,plus,b,times,c],X).; vraci: X = plus(a,times(b,c))
Splnitelnost logickeho vyrazu: Je dan logicky vyraz se spojkami and, or, not, xor, impl, equiv (definujte pomoci operatoru) obsahujici logicke konstanty true, false a promenne (reprezentovane atomy). Vytvorte program, ktery rozhodne, zda je zadany vyraz pravdivy resp. splnitelny, pripadne vyda nutne ohodnoceni promennych tak, aby byl vyraz splnen.; Napr.: ?-sat((x or not x) and y, R). vraci R=[y/true]