Návrhy zápočtových programů: Požadavky na zápočtový program: * Řádně okomentovaný program. Součástí programu je též jméno autora a přesné zadání úlohy. * Uživatelská a programátorská dokumentace: samostatny dokument v rozumném formátu (text, html, doc, rtf, ps nebo pdf). Dokumentace by měla obsahovat především jméno autora, přesné zadání úlohy, slovní popis použitého algoritmu, popis použitých datových struktur a popis spuštění programu včetně tvaru vstupních a výstupních dat. * Testovací příklady vstupu: samostatně - v jednom samostatném textovém souboru nebo v těle zprávy. * Program musí být spustitelný v prostředí SWI-Prolog a BinProlog. Nepoužívejte předdefinované predikáty specifické jen pro určitou implementaci Prologu. 1) Polynomická kalkulačka - polynomy zapíšu jako termy (1 + x^2)*(x + 1) - operace: roznásobení podle exponentů sčítání, odečítání, násobení, dělení se zbytkem, chytré umocňování - chytré umocňování: p(x)^1000 = p(x)^(512+256+...) - spočítám p^1, p^2, atd. (umocňováním na druhou) a vynásobím ... nejvýš 2 log n - inteligentní "kalkulačková" komunikace s programem 2) Kalkulačka pro dlouhá čísla (operace sčítání, odečítání, násobení, dělení se zbytkem, chytré umocňování) - moc jednoducjhé 3) Kalkulačka pro komplexní čísla - moc jednoduché 4) Kalkulačka pro nějaké těleso (zadané na vstupu)- moc jednoduché 5) Symbolické integrování - primitivní funkce - heuristika - substituce nebo per partes + nemusí být 100% úspěšnost 6) Konečné automaty: Převod mezi regulárním výrazem a konečným automatem. 7) Zásobníkové automaty: Pro danou bezkontextovou gramatiku sestrojit zásobníkový automat rozpoznávající gramatikou generovaný jazyk (konstrukce top-down i bottom-up). 8) Syntaxe vybraného programovacího jazyka - kontrola, zda je syntaxe dobře nebo špatně - vypsat seznam funkcí, proměnných, struktury... - hezké formátování (indentace) zdrojáku 9) HRY A HŘÍČKY Karetní hry: a) pasiáns (hraje samostatně nějakou variantu, vypisuje svoje možnosti a zvolené tahy) b) mariáš Zlý minesweeper - Po odkrytí stanoveného počtu polí počítač na odkrytém poli zobrazí minu právě tehdy, když z dosud zveřejněných informací nelze odvodit, že ta této pozici mina být nemůže. Křížovka - vygenerovat křížovku daných rozměrů (na vstupu specifikuji tvar, tajenku, kde může a kde musí být zeď) Osmisměrka - vygenerovat Kódované obrázky - řešení nebo ověření správnosti zadání Sudoku a) řešení pro obecné m*n mřížky (čísla od 1 do m*n) b) vygenerovat zadání s daným stupněm obtížnosti řešení (a vyřešit) Zebra - moc jednoduché 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. Piškvorky - hra, řešení např. pomocí ohodnocovací funkce, MIN-MAX algoritmus Reversi - hra Backgamon - heuristika, řešení např. pomocí ohodnocovací funkce, MIN-MAX algoritmus Šachy a) koncovky - dá se na k tahů (např. 4) vyhrát? ANO/NE b) mám rozmístění figurek a hledám (co) nejlepší tah c) Šachové n-tažky: Program pro generování šachových úloh typu "mat třetím tahem". Rubikova kostka - aplikace pravidel Řešení LLoydovy 15 (pole nxm), pro libovolné zadání, které má řešení. Moc jednoduché. 10) 11) IDOS - a) noční Praha (nebo jiné město) + hledám spojení, které zabere nejméně času b) rozhodovací úloha: sestrojit jízdní řád 12) Gaussova eliminace pro řešení soustavy rovnic, Varianta: Gaus-Seidel - pozor na správné řešení rovnic s nekonečným počtem řešení (řešením je přímka, rovina,...). 13) Řešení soustavy lineárních nerovnic - běžně, simplexová metoda 14) Grafové algoritmy maximální tok v sítích (stačí si vybrat jeden algoritmus): goldbergův, edmons-karpův algoritmus, dinicův, případně 3 indové - plus vhodná vizualizace průběhu algoritmu komponenty souvislosti + komponenty 2-souvislosti a artikulace kostry grafu - implementace několika (alespoň 3 výrazně odlišných) algoritmů. některý sofistikovaný algoritmus nad hypergrafy,... 15) Rozpoznávání zkratek měst - mám databázi měst, zadám město podivnou zkratkou, jak moc je pravděpodobné, že je to ono? 16) Chemie a) chemické vzorce - netriviální převod názvy-vzorce pro anorganickou či organickou chemii b) chemické rovnice 17) Limity funkcí, sčítání řad - aplikace pravidel 18) Hudba a) akordy (generování prstokladu), stupnice b) Program pro automatické vygenerování druhého hlasu (vícehlasu), zadává se notopis melodie a akordové značky. 19) Formule převeď na prenexní tvar (+ vnitřek na CNF nebo DNF) 20) Regulární výrazy - jako v Perlu (vhodná podmnožina), zadány jako term, vyhledá je v textu 21) Automatický rozbor publikačních údajů - z textu do Bibtexu 22) ELIZA a spol. Eliza sekretářka - dohadování schůzek Vyplňování dotazníku - rozhovor, program klade otázky, ověřuje získané informace, poděkuje (program musí zvládat alespoň 4 typy hodnot v dotazníku: např. číslo, výčet, řetězec, datum.) Eliza Matfyzák - zodpoví otázky uchazečů na Dni otevřených dveří 23) Řešení soustav algebrogramů. - bylo na prednasce -> NE Příklad: A * B = CA + - + A * C = D - - - - - D * A = EC Požadavky: alespoň operace +,-,*, celočíselné dělení (div, mod), konstanty, proměnný počet řádků/sloupců, různá písmena reprezentují různé cifry vždy/nikoliv nutně (obě varianty). 24) Mechanické dokazování vět: Systém pro dokazování vět (systém axiomů, odvozovací pravidla - např. v planimetrii). Volba vhodné heuristiky. 25) generování důkazů ve výrokové logice. Na vstupu teorie,... 26) celulární automaty - generování s dostatečnou obtížností, Game of life 27) Rozvrhování a) mám popis školy - učitelé, třídy, omezení (na učebny, volnost učebny), cílem je sestrojit přípustný rozvrh b) umísťování letadel na stojánky, hostů do hotelových pokojů, atd. c) Optimální rozmístění studentů při písemce (studenti, témata, co kdo zvládá)+ chci, aby konzultační vzdálenost byla co největší, 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.