(Dokument je este vo vyvoji v1.3 20.02.1997 v1.2 16.02.1996 ) Zoznam zapoctovych prikladov pre Praktikum z Programovania. Navrhy oznacene pismenom (B) pokladam za vhodne pre tych, ktori by chceli robit v buducnosti bakalarsku skusku. Programy uvedene v zatvorkach neplatia. Su alebo prilis lahke (to vadi) alebo nie dostatocne sformulovane (to by nevadilo). Pokial je vas priklad toho druhu, ze vysledok je "jedno cislo", zabudujte do programu "ladiace tlace", ktore umoznia sledovat postup vypoctu. V niektorych prikladoch je vlastny algoritmus ulohy pomerne jednoduchy (napr. kompresne algoritmy). V takom pripade rozsirte zaber programu, napr. implementujte niekolko podobnych algoritmov, alebo spravte dokonalejsi uzivatelsky interface. -------------- Ulohy: ++ 1998 - rozsirovatelny editor Specialnymi prikazmi umoznuje rozsirovat svoje (textove) menu. Dodatocne prikazy z menu budu vytvarat textove konstrukcie, napr. HTML alebo TEXove prikazy. - konfigurovatelny (hex)editor strukturovanych suborov Je dany binarny subor a vedla jeho popis. Editor binarny subor zobrazi v citatelnej podobe podla popisu, umozni editaciu a potom vysledok ulozi. Navrhnut jazyk popisu! Spracovavanie zdrojakov: Obecne, t.j. ak nie je povedane inak, je vstup syntakticky spravny zdrojovy kod a vystup je taktiez syntakticky spravny zdrojovy kod. Vystup obsahuje naviac nejake informacie, obvykle v komentarovych zatvorkach, alebo tento program plni nejaku funkciu naviac oproti povodnemu zdrojovemu textu. Nie je nutne podporovat cele C(++), ale rozumne velku podmnozinu. Skoro vsetky tieto priklady je mozne spravit pre vstup v C(++) a pre vstup v Pascale ako dva rozne zadania. - crossreferencie s prislusnostou k definiciam Vystup ma ocislovane riadky a obsahuje tabulku vsetkych identifikatorov pouzitych v programe. Ku kazdemu identifikatoru prida niekolko zoznamov cisel riadkov, kde sa dany identifikator vyskytoval. Jeden zoznam odpoveda jednej definicii daneho identifikatora a vsetkym pouzitiam tejto definicie. Riadky s viacnasobnymi vyskytmi a s definicnym vyskytom by sa mali odlisit. Moze sa rozlisovat niekolko druhov definicii: premenna, typ, prvok struktury ... - formatovac zdrojovych textov (pretty-printer) (B) Vystup je zhodny so vstupom, az na riadkovanie, tabelatory, medzery. Podla zadanych parametrov zmeni graficku upravu zdrojaku, napr. indentuje o dany pocet medzier, prikazone zatvorky vypisuje na zvlastne riadky ... Sucastou ulohy je navrhnut druhy a syntax prikazov. Parametry mozu byt zadane dvomi zakladnymi sposobmi: - parametry z prikazovej riadky (B) Cely zdrojak sa spracuje podla danych parametrov - parametry menene dynamicky v subore (B) Typicky v komentaroch, odlisenych specialnym znakom, su formatovacie prikazy. Pikazy mozu platit lokalne alebo globalne. (- makroprocesor) Ako makroprocesor v C, pripadne este silnejsi: makra mozu generovat definicie inych makier ... - pocitanie poctov prechodov cyklami Vystupny zdrojak sa chova ako vstupny a naviac po ukonceni programu vypise pre vsetky cykly, kolkokrat sa preslo jednotlivymi cyklami. - pocitanie poctov prechodov vetvami Vystupny zdrojak sa chova ako vstupny a naviac po ukonceni programu vypise (na obrazovku alebo do suboru) pre vsetky vetvy programu, kolkokrat sa nimi preslo. Pocty prechodov je schopny nacitat na zaciatku behu programu. Idea: Pre testovanie nejakeho programu vytvorim sadu testovacich dat. Chcel by som, aby testovacie data boli uplne vzhladom k testovanemu programu, tj. aby vyskusali kazdu jeho vetvu. Tento zapoctovy program to umozni zistit. - pracovny retazec Vystupny program je obohateny o datove struktury a zdrojovy kod tak, aby som pocas behu mohol zavolat proceduru 'pracovny_retazec', ktora vypise aktualny stav vnorenia v jednotlivych (aj rekurzivnych) procedurach, pripadne vratane parametrov volania ... - meranie casov cyklov a procedur (off-line profiler) (B) Vystupny program po ukonceni svojho behu vypise, kolko casu stravil v jednotlivych cykloch, procedurach, metodach ... Idea: Kde sa stravilo hodne casu, tam sa vyplati optimalizovat. - oznacovanie beginov a endov urovnou vnorenia - a druhom ukoncovanych struktur (de facto dve rozne ulohy, ale obidve su samostatne prilis lahke, takze vyriesit spolu) Prva: Ku kazdej prikazovej zatvorke (begin, end, {, } ) sa doplni komentar, ktory (lokalne) jednoznacne urci uroven vnorenia, odpovedajucu parovu zatvorku, meno zacinanej, resp. ukoncovanej procedury a pod. Druha: Ku kazdej ukoncovacej prikazovej zatvorke (end, } ) sa doplni komentar, ktory urci vsetky struktury (a ich poradie), ktore ukoncuje tato zatvorka. - oznacovanie beginov a endov podmienkami vstupu do vetvy/cyklu a podmienkami ukoncenia cyklu K prikazovym zatvorkam, else-vetvam, koncom cyklov a pod. sa prida komentar, ktory obsahuje "zdrojovy tvar podmienky", ktora urcuje, kedy sa vstupuje do else vetvy, vyskakuje z cyklu a pod. Priklad: u else vetvy je rozumna negacia podmienky z if-prikazu. - lepsi grep Umoznuje vyhladavanie regularnych vyrazov v texte/suboroch - varianta (B): vratane or-moznosti (disjunkcie) - bezpecne C(++) (B) Zdrojak sa doplni o behove testy pretecenia medzi poli, pripadne medzi pointrovej aritmetiky a pod. - testy inicializacie (- zobrazovac struktury) - prekladac z Pascalu do C (B) - z Pascalu s objektami do C++ (B) - a naopak (?) Zmeni syntax Pascalu na syntax C, resp. ... Najdite vhodne velku podmnozinu konstrukcii, ktore ste schopni transformovat so zarukou. - preprocesor - vypis zlozenych premennych V komentarovych zatvorkach su uvedene poziadavky na vypis zlozenych premennych, poli (celych alebo casti) a pointrov. Program automaticky zisti prislusne typy a vygeneruje na odpovedajuce miesta kod, ktory vypise premenne, ... v pozadovanom tvare do pozadovaneho suboru. - off-line debugger (B) (rozsirenie predchadzajuceho prikladu) Okrem vstupneho zdrojaku je na vstupe subor prikazov typu: :v procedure pp vypis pri kazdej zmene premennej i premenne i a j v tvare tt do suboru ff. :pri kazdom prechode riadkom rr vypis hodnotu indexu a hodnotu prvku pola pred a po zmene Upraveny zdrojak okrem svojej povodnej prace vypise ladiace tisky podla prikazov. Navrhnut druh a syntax prikazov je sucastou ulohy. Interprety a navrh vlastnych "jazykov" - interpret jazyka LOGO (B) LOGO by malo mat podmienky, cykly, procedury (aj rekurzivne). - zelvia grafika (B) Integrovane prostredie pre zelviu grafiku s jednoduchym programovacim jazykom (podmienky, cykly, procedury bez rekurzie). - varianta: multizelvia grafika (viac zelviciek) Ovlada sa sucasne viac zelviciek. Jedna zeva moze v priebehu prace vytvorit svoje "podriadene" zelvy (pripadne rekurzivne). - interpret jazyka Karel Integrovane prostredie pre programovaci jazyk Karel. Podmienky, cykly, procedury bez rekurzie, save, load. Volitelne: editor mapy ako specialny program, alebo ako specialna varianta prostredia, kde Karel dokaze klast steny. - interpret data-flow programov (B) Data-flow program je zadany ako orientovany graf, analogicky hradlovym sietam, ale obvykle nie je acyklicky na rozdiel od nich. Niektore hrany vedu z vonku (vstupne) , ine koncia vonku (vystupne). Vrcholy su ohodnotene zakladnymi funkciami z danej mnoziny funkcii (+, *, and, or ...). Ak to ma zmysel, hradla mozu mat premenny pocet vstupov. Vystup z hradla je obvykle jeden, ale ten sa moze rozdelit na vstupy pre niekolko hradiel, potom na vsetky pridzadza rovnaka hodnota (paket). Hradlo sa moze aktivovat, ak ma data (pakety) na vsetkych vstupoch. V jednom kroku spocita vystupnu hodnotu a posle ju na vystup (resp. vsetky vystupy paralelne). Na vstupe hradla sa mozu data hromadit, metodou FIFO. Uloha: navrhnut syntax data-flow programov a naprogramovat ich interpret. Odladit jednoduchy problem v data-flow syntaxi: napr. faktorial. - animacie algoritmov (ako vyukove programy) - triediacich algoritmov - niecoho rozumneho ineho: - vyhladavanie vzorkov v texte (Aho-Corasickova, ...) - AVL-stromy Vytvorit program, ktory umozni (graficku) animaciu (krokovanie ...) nejakeho vyssie uvedeneho algoritmu alebo triedy algoritmov. - obecny programovatelny animator (B) (rozsirenie minuleho programu; analogia off-line debuggera, ale za inym ucelom) Navrhnut vstupny jazyk a vytvorit prostredie, ktore umozni vyrobu amimacii algoritmov obtiaznosti uvedenej v minulom priklade. Vstupny jazyk by mal umoznit zapisat animovany algoritmus v "pseudokode" spolu s prikazmi co, kedy, kam a ako zobrazit. - (integrovane) generatory - generator zdrojaku okienok v TurboVision - generator zdrojakov/resource pre cokolvek ine Program by mal tvorit integrovane prostredie, ktore umozni nakreslit okienka v TurboVision a potom vygeneruje zdrojak na ovladanie nakreslenych okienok. Analogicky pre ine programove prostriedky. - parametricky lexikalny analyzator (alias LEX) Grafika: - zobrazenie funkcie dvoch premennych (lahke) Je zadana funkcia dvoch premennych, vykresluje sa jej plocha v ciarovom modele s ohladom na viditelnost. Je mozne zadavat rozsah vykreslenia, hustotu ciar, smer pohladu, ... Tieto parametry je mozne menit za behu. - Graficky editor pre 2D grafiku. Umozni kreslenie bodov, useciek, ciar, mnohouholnikov, kruznic, ... pomocou roznych nastrojov (pero, stetec, sprej ...) s roznymi parametrami (hrubka pera, hustota spreja, ...). Volba farby, vyplnovanie, srafovanie, ... Blokove operacie: zvacsenie, zmensenie, posun, rotacia, skosenie atd. Uschovanie a obnova obrazku. - tazsie: kresli sa v niekolkych vrstvach (akoby na slajdy), ktore sa daju spolocne zobrazovat, medzi sebou posuvat, rotovat. - dodatok: V zakladnej variante je kreslenie interaktivne. Postup kreslenia je mozne zachytit do postupnosti prikazov a vypisat ako "program". Program je mozne interpretovat, pripadne programovaci jazyk rozsirit (o cykly, ...) a pouzit pre animacie. - (vektorova grafika) Hry: Obecne: Vytvorit (len) prostredie pre nejaku hru je obvykle pomerne jednoduche. Prostredie by malo kontrolovat pripustnost tahov, navrhovat vsetky pripustne tahy, inicializovat poziciu (napr. rozdat karty), pripadne v specialnom mode dovolit pripravit rozdanie, uschovat a obnovit stav hry, prehrat dokoncenu hru, rozpoznat koniec a spocitat vysledok a pod. Pre sietovo zameranych: je mozne vytvorit prostredie, ktore umozni hru viac hracom po sieti (Novell). Obvykla uloha je integrovat do prostredia aj strategiu pre pocitac, pripadne niekolko na roznom stupni obtiaznosti. Nasledne je skoro "zdarma" demo (pocitac proti pocitacu) a navrh najlepsieho tahu. Tazka uloha je navrhnut jazyk pre popis strategie, ktory sa bude v prostredi interpretovat. Strategia (pripadne podla parametrov) vyda najlepsi tah, ktory prostredie vykona ako tah pocitaca. Popis strategie moze byt dany rozhodovacimi pravidlami, pripadne s ohodnotenim. - marias voleny - marias licitovany - taroky, ... - dama, rozne varianty - zrava dama - piskvorky - 3D piskvorky - ninuki (piskvorky s branim) - vrchcaby - (reversi) - kalah - pasians (rozne druhy) Prostredie pre nejaky druh pasiansu. Pretoze ide o hru jednoho hraca a teda zaujimave je len prostredie, bol by zvyseny doraz na uzivatelskom rozhrani. - prostredie pre spravu partii (databaza) Pre jednu konketnu hru. - sach - dama - go - piskvorky - bridz - ... Vytvorit prazdne prostredie pre spravu partii v (doskovych) hrach. Nacitanie a pridanie partie do "databaze", interaktivne zadavanie, vypustenie, zobrazovanie a prehravanie. Moznost vyhladavania podla charakteristickych znakov partie (postupnost tahov, stav partie na doske ...). Usporna reprezentacia databazy (napr. spolocne zaciatky). Navrh externeho zapisu partie. Rozsirenie: partie maju anotacie (kto, s kym, kedy a kde hral, ako to dopadlo ...), podla ktorych sa da tiez vyhladavat. - Pripadne bez zavislosti na hre (druh hry by sa dal ako parametre) - (sachove koncovky) (prilis caste) - generovanie zaujimavych sachovych koncoviek Rozsirenie minuleho prikladu. Na zaklade casti pozicie, druhu niektoreho tahu, obsadeni alebo ohrozeni poli ... by mal program generovat pozicie a testovat o nich, ci su ziadanym sposobom riesitelne (napr. dvojtazky). Moze k jednej znamej pozicii generovat (hrubou silou) podobne pozicie riesitelne zhodnym trikom. Vstupne data budu urcovat, ktore pozicie sa maju testovat. Je mozne urcovat "zaujimavost" pozicie a riesenia. - varianta: pre exoticke druhy sachu alebo sachovych figur (napr. maharadza - tiahne ako dama alebo kon dzin - tiahne ako veza alebo kon ...) - tabelacia sachovych koncoviek Pre sachove koncovky sa spocita optimalna(!) vyhravajuca strategia. - K + V x K - K + S + S x K (- logik alias Master Mind) - tabelacia opt. strategie Pre logik s k farbami na l polickach spocita optimalnu strategiu hadania, ktora pri lubovolnych odpovediach supera zaruci uhadnutie na minimalny pocet tahov. Dve varianty: s opakovanim a bez opakovania farieb. - bridz - licitacia Automaticky licitator na zaklade svojej ruky a hlasok superov licituje podla nejakeho systemu. Tazsia varianta: Pravidla systemu (utocne aj obranne) su popisane v datovom subore a licitator funguje ako interpret pravidiel. - bridz - zohravka (tazke) Zohrava na zaklade licitacie a svojej ruky a stolu. varianta: dokaze len utocnu alebo len obrannu zohravku - zohravka specialnych druhov koncoviek (skvizy) Zisti, ci nastal urcity druh koncovky a tu potom zohraje. - (lahke?) vynos Na zaklade licitacie, vlastnej ruky a konvencii (systemu) urci vhodny vynos. - konvencie vynosov su popisane v datovom subore. - prostredie pre strategicke hry Prazdne prostredie pre strategicke hry a la Civilizacia, Kolonizacia ... Ulohou je vymysliet vhodny jazyk, v ktorom sa daju popisovat zdroje. Zdroj je zakladny pojem a rozne zdroje reprezentuju mapu alebo jej policko, jednotky, mesta, budovy, ..., a vsetko je parametricke. - interpret zdrojov: vlastna hra - tvorba zdrojov: v podstate rozsireny editor map a vsetkeho ostatneho (- hlavolamy - maltezsky kriz, sadenice Spracovanie textov: - hypertextovy editor (B) Navrh jazyka (a la HTML) pre tvorbu hypertextovych dokumentov a jeho interpret, pripadne kompilator a interpret vnutormej formy (prohlizec). Umozni odkazy na ine miesta textu, podpora vytvorenia odkazov na definicie, rejstrik, ... - textovy korpus System (server), ktory bude spravovat bazu dokumentov a umozni zapamatat si vsetky vyskyty slov v danych dokumentoch (vratane pozicie). Umozni dotazy na pocet slov celkovo a v jednotlivych dokumentoch, na frekvencie (resp. relativne cetnosti), aj podmienene ... - rozsirenie: Umozni najst "susedne" slova k danemu slovu a vypisat okolie slova. - plnotextovy vyhladavaci system varianta minuleho prikladu ... Umozni zistit, v ktorych dokumentoch sa vyskytuje dane slovo, s akou frekvenciou alebo relativnou cetnostou ... Pripadne kombinacie slov s logickymi operatormi. - prazdny tezaurus System (server), ktory umozni vykonavat spravu "pojmov": pridavanie, uberanie, zmeny. Hladanie nadriadenych, podriadenych, ekvivalentnych, asociovanych ... pojmov, s kvalitou urcenou (realnymi) cislami. - tvorba krizoviek Prostredie podporujuce automaticku a semiautomaticku tvorbu krizoviek, spravu slovnikovej databaze, ... Rozne: - hudobny editor (B) Integrovane prostredie, ktore umozni vstup, save, load a zobrazovanie notovych zaznamov. Moze aj prehravat zaznamy. - editor gitarovych akordov Analogicky ako minuly priklad. - sprava a skusanie cudzojazycnych slovicok Integrovane prostredie, ktore umozni vytvarat a udrziavat cudzojazycne slovniky a skusat slovicka/spojenia v nich obsiahnute. rozsirenia: fraze, nepravidelne tvary, spojenia a vazby ... - tvorba testovacich (a vyukovych) programov (B) Program by mal pomoct zostavit test, umoznit jeho vyplnenie a zaverecne vyhodnotenie. Testovacie otazky sa mozu vyberat z databaze otazok (lepsie riesenie) alebo sa popisu priamo v teste. Test by mal umoznovat nielen klasicke vyberacie otazky z a,b,c,d, ale aj ciselne a slovne odpovede. Pri slovnych odpovediach by mal zistit aj ciastocnu zhodu, pri ciselnych umoznit stanovit toleranciu. Moznych rozumnych filozofii navrhu je niekolko. - vyukovy program - kompresia a dekompresia Implementovat kompresny a dekompresny algoritmus. (dost lahke) - varianta: Integrovane prostredie pre spravu archivov - davkovy editor (lahke) Je dany spracovavany subor a subor prikazov - davka. Vykonat vsetky prikazy z davky na dany subor. - tabulkovy kalkulator (spreadsheed) Jednoduchy spreadsheed. - editor grafov Integrovane prostredie, ktore umozni zadavanie a zakladne operacie s grafmi. ---------- z minulych rokov (mozno sa budem opakovat) - geneticke algoritmy Prazdny system podporujuci vyvoj, tvorbu a ladenie genetickych algoritmov a strategii. Implementovat zakladne geneticke operacie (krizenie, nahodne mutacie) a strategie a jednoduchy priklad/model. - analyzator zvukov Vzorkovanie zvukov (off-line, data pripravene inde), Fourierova transformacia, upravy charakteristik (frekvencnych alebo casovych), zvukove efekty: ozvena, stisovanie, doznev ... (prehravanie vysledkov nie je nutne) - OCR (Optical Character Recognition) (?) alias rozpoznavanie tlaceneho textu (- sprava virtualnej pamati) (lahke?) ? mozno testovacie prostredie pre rozne strategie pridelovania a uvolnovania. Animacia, statistiky, ... ---------------------- (- 3D grafika) (- Simulacie (vytahov v Troji)) Prazdne prostredie pre simulacie (- strategicke simulacie)