Nabídka zápočtových příkladů Ondřej Bojar 2004-11-04, 2010-03-24 Správně odevzdaný zápočtový příklad obsahuje: - komentovaný program (spustitelný v "běžném prologu") - testovací data - dokumentaci, která uvádí: - jméno autora, popis zadání (tj. příp. zpřesnění) - popis, jak program spustit na testovacích datech - popis formátu testovacích dat, často stačí příkladem. - popis výstupu programu - popis algoritmu a použitých datových struktur Postup odevzdávání zápočtových příkladů: (v ideálním případě, že na první pokus bude všechno jasné a všechno v pořádku) - v dohledné době dodáte specifikaci svého programu, abychom si byli navzájem jisti, že víte, co děláte. - až budete hotovi, pošlete program, dokumentaci i testovací data, společně s návrhem, kdy se nad programem sejdeme - při schůzce vysvětlíte jak program funguje a případně provedete drobnou úpravu na místě Pokud máte s řešením zvolené úlohy obtíže, neváhejte se *včas* ozvat. Jednou můžete eventuelně i zadanou úlohu změnit, pokud by vás zadání mělo chytit do slepé uličky. . Karel v bludišti Zadáte rozměr bludiště, program vytvoří náhodné bludiště (kde jsou zdi, kde je start a kde cíl; vytvořte alespoň tři odlišné algoritmy generování bludiště, bludiště musí být "normálně hezké"), a Karel vypíše všechny nejkratší posloupnosti tahů, kterými od startu dojde do cíle. Cesta samozřejmě nemusí existovat. Navíc program bude (na textové konzoli) vykreslovat krok po kroku nalezenou cestu. (Napřed cestu najít, pak volitelně nechat vykreslit.) . Generátor křížovek Program má vestavěný slovník. Zadá se tvar křížovky (zadává se rozměr čtvercové sítě a poloha povinných a volitelných "zdí" -- kde musí být hranice mezi slovy a kde smí být hranice mezi slovy pokud se to programu bude hodit) a tajenka (text i poloha), program bude navrhovat jednu křížovku za druhou. Křížovka musí mít normální křížovkové vlastnosti: každé políčko je buď zdí, nebo je zapojeno jako součást slova, neexistují nevyužitá políčka. Jakmile jsou dvě a více políček vedle sebe nebo pod sebou, musí být v tom směru od zdi ke zdi platné slovo. Bojíte-li se slovníku, buď si jej stáhněte z webu (např. http://quest.ms.mff.cuni.cz/pdt/Morphology_and_Tagging/Morphology/), nebo úlohu formulujte tak, že vezmete existující křížovku a ona se vám "rozsype". Úkolem programu je poskládat křížovku zpět, nebo říct, že to nejde. . Regulární výrazy a jejich kompilace Definujte datový typ pro reprezentaci (zjednodušené varianty) regulárního výrazu. Datový typ musí umožňovat operace tradičně zapisované speciálními znaky: ^ $ . * + [] | () Pro daný regulární výraz program vygeneruje deterministický prologový kód, který tento výraz vyhledává ve vstupním textu a vrací seznam "vyznačených oblastí", které našel. Regulární výraz stačí zadat jako prologovský term vámi definovaného formátu, není nutné načítat tradiční reprezentaci řetězcem. . Generátor pohádek Program bude z vestavěného slovníku generovat gramaticky správné české věty. Musí být schopen generovat věty obsahující: - shodu podmětu s přísudkem - předložka plus shodný přívlastek k podstatnému jménu (podle toho velkého červeného medvěda) - vedlejší větu vztažnou (medvěd, který usnul) - řečnickou otázku a odpověď (Byl ten medvěd zlý? Nebyl.) - zájmeno, pokud už v předchozím textu vygeneroval něco, k čemu se to zájmeno může vztahovat Program se zavolá jednoduše: chci pohádku o délce deseti vět. Výstupem je seznam slov a interpunkce. Doporučené vestavěné limity: (Ať lze snadno nastavit jinak!) - maximální počet přívlastků: 3 - maximální počet vnořených vedlejších vět: 3 - maximální vzdálenost mezi podstatným jménem a zájmenem: přes 1 větu . Primitivní strojový překlad Program dostane anglickou větu a vyrobí větu českou. Vestavěn má jednoduchý slovník, kde jsou uvedeny jedno- až cca tříslovné výrazy a jejich jedno- až cca tříslovné překlady). Výstupní věta musí být gramaticky správně v těchto ohledech: - shoda podmětu s přísudkem - shoda v předložkové skupině a přívlastcích (na modrém stole) Na anglické straně stačí umět zpracovávat: - přítomný čas průběhový a prostý (I sleep regularly more than 9 hours. I'm sleeping.) - minulý čas prostý (He left at six o'clock.) Program bude postupně vracet více možných překladů vstupní věty, protože jistě více možných překladů bude. . Poetizér Pro daný český text program bude na základě vestavěného slovníku navrhovat mírné proházení slov a volbu synonym, tak aby se text rýmoval. Součástí volání programu bude též předepsaný formát rýmu, ideálně vzorec ve tvaru: přízvučná slabika, nepřízvučná, nepřízvučná, přízvučná, nepřízvučná, přízvučná ("dokola plyne proud") a s nějakým zadáním toho, které slabiky se mají s kterými rýmovat. (Při dostatečně bohatém slovníku by program mohl zvládnout i vnitřní rým! :-) Slovník slovních tvarů: http://quest.ms.mff.cuni.cz/pdt/Morphology_and_Tagging/Morphology/ Jako slovník synonym lze použít překladový slovník (např. http://slovnik.zcu.cz/) české slovo přeložím do anglického a za česká synonyma prohlásím vše, na co lze zpětně přeložit nalezené anglické výrazy . Prostředí pro genetické algoritmy Navrhnout reprezentaci individua a reprezentaci požadovaného postupu "genetického hledání optima" (kolik individuí v populaci, jak moc mutovat, jak moc křížit, jak moc kopírovat individua z předchozí generace, kdy prohlásit dosavadního vítěze za pravděpodobně nejlepší řešení...). Programu se pak zadá konkrétní požadovaný postup hledání a predikát, který dané individuum ohodnocuje. Program bude provádět genetické experimenty s cílem najít nejlepší řešení, po každé generaci vypíše, jak si zatím nejlepší jedinec stojí. . Automatický rozbor publikačních údajů Program dostane na vstup řetězec obsahující publikační údaje (např. "Validating plans with durative actions via integrating Boolean and numerical constraints [PDF] R. Barták. ITI Series 2004-184, Prague, 2004, 8 pages." nebo "Ondřej Bojar, Cyril Brom, Milan Hladík, Mikuláš Vejlupek, Vojtěch Toman, and David Voňka. 2003. ENTI - Simulátor přirozeného prostředí lidského světa. In MIS 2003, pages 3-14. MATFYZPRESS, January 18-25, 2003. MSM113200006, LN00A063." ap.). Program bude postupně navrhovat *smysluplná* čtení těch údajů a vypisovat je ve formátu BibTeXu: např.: @InProceedings{enti_mis:2003, author = {Bojar, Ondřej and Brom, Cyril and Hladík, Milan and Vejlupek, Mikuláš and Toman, Vojtěch and Voňka, David}, title = "{ENTI -- Simulátor přirozeného prostředí lidského světa}", BookTitle = {MIS 2003}, Pages = {3--14}, Publisher = {MATFYZPRESS}, PubAddress = {Praha}, Year = {2003}, Month = {January 18--25}, Note = {MSM113200006, LN00A063} } Více o BibTeXu na webu. Např. http://newton.ex.ac.uk/tex/pack/bibtex/btxdoc/btxdoc.html . Optimální rozmístění studentů při písemce Zadáním bude seznam témat, která studenti mají k písemce umět, přehled o přihlášených studentech a tématech, která jednotlivci zvládají, a tvar učebny. Program navrhne rozmístění studentů tak, aby "opisovací/konzultovací vzdálenost" byla co nejnižší, ať už písemková úloha bude jakéhokoli tématu. Taktéž se může stát, že písemka bude zadána ve dvou odděleních, algoritmus by i tak měl navrhnout rozumné řešení. . Vyplňování dotazníku po telefonu Program dostane popis dotazníku, který uživatel musí po telefonu vyplnit. (Např.: přihláška na VŠ, žádost o kolej, rezervace jízdenky a ubytování, objednání pizzy...) Program pak s uživatelem vede rozhovor tak, aby uživatel odpověděl na všechny potřebné otázky. Odpovědi uživatele i programu jsou v normální češtině (ev. angličtině, je-li vám to jednodušší kvůli tvarosloví). Program z odpovědí vyzobe hledané informace, nakonec uživateli poděkuje a odevzdá vyplněný dotazník. V rozhovoru: - program musí usilovat o rychlý průběh hovoru -- dát uživateli možnost odpovědět na víc kolonek zároveň - pokud uživatel vypadá nechápavě a komunikace vázne, musí program přejít do volnějšího režimu a ptát se krok po kroku - uživatel musí mít možnost upozornit program, že něco vyzobnul nesprávně (program musí tedy uživateli již během hovoru dávat najevo, jaké kolonky a jak vyplnil) Program musí být přípraven alespoň na čtyři různé typy hodnot v kolonkách (číslo, telefonní číslo, výběr z výčtu ap.). . Měření podobnosti dvou prologovských programů Program načte dva prologovské programy a určí jejich podobnost. Podobnost se měří jako počet identických prologových procedur. Identické jsou dvě procedury, pokud se mezi nimi podaří najít izomorfismus -- jak stačí přejmenovat volané predikáty a použité proměnné a proházet konjunkce a disjunkce, abychom převedli jednu proceduru na druhou. . Rozličné úlohy známé z předmětů Datové struktury, algoritmy, diskrétní matematika, lineární algebra... . Rozličné deskové/karetní ap. hry - zde se nabízejí např. ďábelské miny -- program na hraní min, který však po počátečním rozehrání naschvál dává miny hráči pod prsty tam, kde mina teoreticky být může. (Jde o algoritmus, nejde o rozhraní.) . Rozličné úlohy z jiných oborů (např. převod anorganického vzorce na český název sloučeniny)... Vyberte si, co si chcete zkusit implementovat, a navrhněte si zadání. Já ho upřesním a potvrdím.