|
Reseni zapoctoveho prikladu se sklada z: 1.dokumentace obsahujici jmeno autora presne zadani prikladu slovni popis pouziteho algoritmu popis datovych struktur popis spousteni programu vcetne tvaru vstupnich a vystupnich dat 2.komentovaneho textu programu ve SWI Prologu nebo Haskellu Hugs 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 SWI prolog resp. Hugs. Pokud k němu nemáte přístup, domluvte se předem! 3.primerene velkych zkusebnich dat (pripadne generatoru zkusebnich dat, neni-li v zadani specifikovano jinak). Možná realizace testovacích dat a demo příkladu demo:-data(X),my_main(X,V),write(in(X)-out(V)),fail. 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.
|
Table of Contents
Obecné hledání optimální (herní) strategie
Optimalizace hradlove site (hledaní ekvivalencí)
Vypocet hradlove site (s externe zadanymi procedurami)
Kompilace hradlove site (s externe zadanymi procedurami)
Linearizace hradlové síte + lokalizace registru
Barvení grafu (splnovaní podmínek)
Dopredna kontrola (forward checking)
Lokalni prohledavani s Tabu seznamem
Je dana jeskyne (matice MxN), vstup jeskyne je na pozici 1,1. V jeskyni se mohou vyskytovat tyto prvky: nejvyse 1x Zlato, nejvyse 1x Wumpus, libovolne x Diry. Na jednom policku muze byt pouze dvojice Zlato a Wumpus. Pocitac resi agenta (na zacatku behu programu je na souradnicich vstupu do jeskyne, s timze o jeskyni nevi zhola nic), ktery ma, pokud mozno, projit jeskyni, zastrelit Wumpuse, vzit zlato, a odejit s nim z jeskyne. Agent umi jit Vpred, zahnout Vlevo, zahnout Vpravo, Vzit zlato, Polozit zlato, Vystrelit. Pri vstupu na Diru nebo Wumpuse je agent mrtev. Agent umi poznat okoli pomoci predikatu vjem, ktere zjisti, zdali je na okolnich polickach (okolni policko je vzdalene o 1 ve vertikalnim xor 1 v horizontalnim smeru) Od diry tahne, Wumpus smrdi, pokud Agent stoji na Zlate, tak ho vidi. Dale ma Agent 1 sip, ktery muze kdykoliv Vystrelit ve smeru, kterym je otocen. Doleti-li sip na policko s Wumpusem je Wumpus mrtev, jiz lze na nej bez postihu slapnout a uz nesmrdi.
Loni byl VOJTECH HLAVES tak hodny, ze Vam udelal prostredi - spousti se go. . Vymazala jsem ale veci tykajici se agenta, takze na Vas zbyla trocha prace.
Je zadaný slovník, tajenka (případně I její poloha), tvar křížovky (případně neúplný), úloha je sestavit křížovku.
Kdybyste fakt nemeli zadny slovnik, tak tady je seznam skupin pismen, u delsich jsou to dokonce slova. Joo, kdyby tak nekdo vytvoril i rozumnejsi slovnik.
Program hádá i vyhodnocuje. Cást, která vyhodnocuje, je inteligentní podvodník: vybere si takovou správnou odpověd, která poskytuje největší počet možných řešení.
K názvu chemické sloučeniny vyrobit vzorec.
hraje nějakou verzi pasiánsu; možnost, aby hrál uživatel.
Daná plocha se má přesně pokrýt danými obrazci. Tvary obrazců jsou součástí zadání, jsou složeny ze základních čtverců.
vygenerovat pro danou pozici všechny možné tahy (včetně tahů dámy).
Bridž - pro dané informace o stole, vlastní ruce a dosavandí sehrávce se pokusí dopočítat karty ostatních hráčů (můžete, ale nemusíte přidat informace z licitace).
Napiste program, ktery resi sachovou koncovku s kralem a vezi.
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.
Grupa je daná abstraktním rozhraním, např. pomocí predikátů elem(G,X), elems(G,Xs), unit(G,X), inv(G,X,IX) a oper(G,X,Y,XY),
které určují pro danou grupu G postupně jednotlivé prvky, seznam všech prvků, jednotku, inverzní prvek a binární operaci. Operace i ostatní součásti mohou být dané bud tabulkou, nebo předpisem výpočtu (napr. grupa násobení modulo 1001).
Zadání: Je daná grupa a množina generátorů. Ulohou je najít nejmenší generovanou podgrupu a vyjádřit každý její prvek pomocí generátorů.
Pro danou konečnou grupu najděte všechny její podgrupy. Pro každou podgrupu určete množinu generátorů a určete jejich vzájemné inkluze.
Pro dané dvě grupy určete, zda jsou izomorfní, a vydejte všechny izomorfismy v datové struktuře (ne backtrackingem).
Orientovaný hypergraf je zadán dvěma množinami: množinou
vrcholů V a množinou hyperhran H. Každá hyperhrana h je aspon
dvouprvková podmnožina V, ve které je určen jeden výstupní
vrchol, ostatní? vrcholy hyperhrany jsou vstupní.
Je-li v1 výstupní vrchol hyperhrany h1 a všechny vstupní vrcholy h1 jsou dosažitelné z M, potom je v1 dosažitelný z M. Ríkáme, že jsme použili hranu h1. Minimální počet použitých hran, pomocí kterých je v1 dosažitelný z M, je vzdálenost vrcholu v1 od M.
Zadání: Vstup je orientovaný hypergraf G a počáteční množina
vrcholů M. Najděte všechny vrcholy G, které jsou dosažitelné z M a vzdejte množinu dosvědčujících hran. Výsledek vratte jako datovou strukturu.
(Použijte např. variantu Dijkstrovho algoritmu)
Pro daný graf G určete jeho hranovou souvislost.
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.
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.
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.
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.
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.
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.
Po "obarveni" vrcholu se z domen vsech okolnich vrcholu vyradi nekonzistentni hodnoty, viz Constraint Propagation.
Po "obarveni" vrcholu se z domen vsech okolnich vrcholu vyradi nekonzistentni hodnoty, viz. Constraint Propagation.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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))
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]
Můžete se nechat inspirovat i Záp. příklady dr. Hrice a Záp. příklady dr. Bartáka,
ale např. lehké příklady (u dr. Hrice označené (1)), u dr. Bartáka např. Hra NIMM nejsou dovoleny, čili nejdřív se zeptejte, pak teprve na něčem začněte pracovat.