Témata obsazená k 12.5.2020: Řídká matice, AVL strom, B-strom, Misionáři a kanibalové, Kostra grafu, Římské číslice, Šachové koncovky, Vlk, koza a zelí, Grafové algoritmy, Rozklad polynomu
Vstupem je matice n x n uložena v textovém souboru, z části zaplněna čísly (n=4,9,16,25). Prázdná pole jsou reprezentavána 0. Implementujte vhodný algoritmus (např. inteligentnější, ne obyčejný, backtracking) k nalezení kompletního řešení zadané úlohy. Program výsledek vypíše (dle přání uživatele) na obrazovku nebo do souboru.
Implementujte datovou strukturu pro uložení řídké matice NxM tj. takové, která má na každém řádku jen pár nenulových prvků. Implementujte následujicí funkce: násobení matice a vektoru, násobení skalární hodnotou, násobení dvou matic, součet dvou matic, transpozice matice, změna (načtení) libovolného prvku matice, načtení matice ze souboru a její výpis do souboru.
Implementujte algoritmus pro lexikografické třídění textového dokumentu v českém jazyce (podle pravidel pro abecední řazení v češtině). Ukažte funkčnost algoritmu na vhodné aplikaci (např. setřídění řádek v textovém souboru). Program by měl načítat zadání a vypisovat výsledeky z/do souboru. Alternativně pro jiný národní jazyk (po domluvě).
Implementujte vhodnou datovou strukturu pro reprezentaci neorientovaného grafu s ohodnocenými hranami a implementujte alespoň dva odlišné algoritmy pro hledání minimální kostry (např. hladový, Primův, Borůvkův ap.). Příklady algoritmů najdete např. zde. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru.
Implementujste alespoň dva různé algoritmy založené na prohledávání grafu do hloubky nebo do šířky (nebo jeden náročnější algoritmus). Například to mohou být úlohy nalezení topologického uspořádání uzlů grafu, nalezení silně souvislých komponent, zjišťování acykličnosti apod. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru. Je třeba předběžná specifikace konkrétního zadání.
Zvolte si jiný zajímavý grafový algoritmus/algoritmy (podle náročnosti, např. problém nalezení maximálního toku v síti). Navrhněte vhodnou datovou strukturu pro reprezentaci grafu a implementujte nad ní tento algoritmus. Program by měl umět načíst vstup ze souboru a vypsat výsledek do souboru. Je třeba předběžná specifikace konkrétního zadání.
Příkladem může být Goldbergův nebo Ford-Fulkersonův algoritmus pro hledání maximálního toku v síti.
Sedlák má převést na druhý břeh vlka, kozu a zelí tak, aby nikdo nikoho nesežral. Na loďku se vejde jen jedna věc/zvíře. Pokud zůstanou bez dozoru vlk s kozou, vlk kozu sežere. Totéž platí pro kozu a zelí.
Navrhněte program pro řešení této logické hříčky pomocí prohledávání stavového prostoru. Program nalezne všechna řešení úlohy a vhodně vizualizuje výsledek. Implementujte dva postupy řešení: např. pomocí rekurzivní metody a bez rekurze (s využitím zásobníku)
Tři kanibalové a tři misionáři se chtějí přepravit na druhý břeh bez ztrát na životech. Do loďky se vejdou max. dva lidé. Pokud na některém břehu bude v nějakou chvíli více kanibalů než misionářů, budou misionáři sežráni.
Navrhněte program pro řešení této logické hříčky pomocí prohledávání stavového prostoru. Program nalezne všechna řešení úlohy a vhodně vizualizuje výsledek. Implementujte dva postupy řešení: např. pomocí rekurzivní metody a bez rekurze (s využitím zásobníku)
Známá hra Logik. Hra je parametrizována dvěma čísly: počet pozic N (typicky 4) a počet barev M (typicky 6). První hráč na počátku zvolí nějakou N-prvkovou kombinaci daných barev (mohou se i opakovat), druhý se ji snaží uhodnout. V každém tahu druhý hráč navrhne nějakou kombinaci barev a první mu na ni odpoví dvěma čísly: počet správně uhodnutých pozic a počet barev, které sice v utajované kombinaci jsou, ale na jiném místě (tedy například je-li tajná kombinace 1232 a druhý hráč hádá 1423, je odpověď "1,2"). Zadání úlohy specifikuje uživatel, program pak bude úlohu řešit.
Můžete zkusit implementovat algoritmus, který kombinaci barev efektivně hádá – začněte například s množinou všech 6^4 kombinací, z které postupně nepřípustné kombinace vyřazujete. Program v každém kroku hádá takovou kombinaci, která mu nejvíce napoví (průměrně tedy bude moci nejvíce nepřípustných kombinací škrtnout). Minimání požadavky na program jsou, že pro typické zadání úlohy pro N=4 a M=6 bude schopen do 8 tahů a v reálném čase problém vyřešit (jde to i výrazně lépe).
Není třeba vytvářet grafické rozhraní (komunikace s programem může být přes konzoli).
Známá hra, ale lehce modifikovaná. Pole NxM. V případě zlého minesweeperu počítač nejprve několik kol hraje standardně. Potom přepne do zlého modu: počítač na odkrytém poli zobrazí minu právě tehdy, když z dosud zveřejněných informací nelze odvodit, že na této pozici mina být nemůže. Stačí textová verze, výpis stavu hry na obrazovku. Alternativně můžete naprogramovat tzv. hodný minesweeper (pokud pro žádné políčko nelze odvodit, že na něm mina být nemůže, tak ji na právě odkrytém políčku nezobrazí).
Vstupem je matice 8 x 8 uložena v textovém souboru, která reprezentuje stav šachové partie s malým počtem figurek. Program řeší úlohu, zda hráč může vyhrát do n tahů pro malé n zadané uživatelem (maxiálně 4-5). Program poradí hráči, jaká hrát, aby vyhrál.
Protože jsou pravidla pro hraní šachů relativně složitá, lze se případně domluvit na zjednodušené verzi šachů (jen některé typy figurek ap.).
Naprogramujte textovou kalkulačku. Uživatel zadá na vstup aritmetický výraz sestávající z operandů (obecně desetinných čísel a proměnných), závorek a operátorů z předem známé množiny. Výraz se vyhodnotí s ohledem na priority operátorů a závorky. Implementujte možnost zavádění uživatelských proměnných a následné počítání s nimi. Nezapomeňte, že číslo je obecně reprezentováno více znaky, stejně jako název proměnné – je tedy nutné nejdřív výraz rozdělit na jednotlivé elementy. Samozřejmostí je, že si program umí poradit nejen s binárními operátory (levě i pravě asociativními), ale také s unárními, jako je například unární minus.
Vytvořte program, který bude schopen ze zápisu římského čísla (např. MCDXXIII) odvodit arabský zápis (v našem případě 1423). Program by měl umět převést i zadání, která nejsou podle pravidel pro zápis římských čísel (např. MMMMMMXXXXXXIVI ... 6065, XM ap.). Opačnou úlohu, tj. převod arabského zápisu na římský, implementujte také (v tomto případě by měl program generovat správný výsledek podle pravidel). Vstup se v cyklu zadává z klávesnice, program okamžitě napíše správný výsledek, případně oznámí, že je vstup neplatný. Program by měl rovněž umět načíst více hodnot ze souboru zadaného uživatelem a vypsat pro ně výsledek.
Spočítejte hodnotu iracionálního čísla pí na n desetinných míst (n zadá uživatel, např. 1000). Pro výpočet využijte například toho, co víte o Taylorových řadách (postupů existuje více, můžete zvolit i jiný). V rámci řešení úlohy navrhněte vhodnou (vlastní) datovou strukturu pro počítání s dlouhými čísli (například spojový seznam) a implementujte nad ní potřebné aritmetické operace.
Spočítejte hodnotu Eulerovy konstanty na n desetinných míst (n zadá uživatel, např. 1000). Postupů existuje více (např. pomocí vyjádření e pomocí součtu řady). V rámci řešení úlohy navrhněte vhodnou (vlastní) datovou strukturu pro počítání s dlouhými čísli (například spojový seznam) a implementujte nad ní potřebné aritmetické operace.
Na přednášce jste probírali B-strom. Implementujte knihovnu pro B-strom obsahující základní operace nad touto datovou strukturou (vkládání a mazání prvků, vyhledávání, načtení hodnot ze souboru, vizualizace apod.). Funkčnost knihovny demonstrujte na nějaké konkrétní zajímavé aplikaci (evidence knih v knihovně, zvířat v zoo ap.).
Ve skriptech je vysvětlen i AVL-strom. Implementujte knihovnu pro AVL-strom obsahující základní operace nad touto datovou strukturou (vkládání a mazání prvků, vyhledávání, načtení hodnot ze souboru, vizualizace apod.). Funkčnost knihovny demonstrujte na nějaké konkrétní zajímavé aplikaci (evidence knih v knihovně, zvířat v zoo ap.).
Nějaká zajímavá aplikace metody Monte Carlo (např. pro výpočet obsahu obrazce nebo Millerův–Rabinův test prvočíselnosti). Je třeba předběžná specifikace konkrétního zadání.
Nějaká zajímavá aplikace prioritní fronty. Prioritní frontu implementujte pomocí vhodné datové struktury. Je třeba předběžná specifikace konkrétního zadání.
Kochova vločka je jeden ze známých fraktálů. Může být zkonstruován tak, že začneme od rovnostranného trojúhelníku a postupně dělíme všechny úsečky v obrázku na třetiny, přičemž prostřední část vždy vyjmeme a nahradíme dvěma stejně dlouhými částmi tvořícími "osten". Implementujte rekurzivní algoritmus typu rozděl a panuj, který spočítá souřadnice jednotlivých bodů Kochovy vločky daného řádu (řád zadá uživatel, např. 5). Implementujte i druhou verzi algoritmu, kdy rekurzi nahradíte zásobníkem. Výsledkem bude 1) soubor se dvěma sloupci dat (x-ové a y-ové souřadnice bodů), 2) soubor ve formátu SVG (nebo jiném vhodném formátu pro snadné zobrazení obrázku).
Uživatel zadá na vstup polynom v základním tvaru (např. x^5 - 2 x^4 - 10 x^3 + 20 x^2 + 9 x - 18). Program vrátí polynom rozložený na součin celočíselných kořenových činitelů pomocí Hornerova schématu (např. (x-1)(x+1)(x-2)(x-3)(x+3)). Program by měl zvládnout i opačnou úlohu (roznásobení závorek a převod na základní tvar). Vstup se v cyklu zadává z klávesnice, program okamžitě napíše správný výsledek, případně oznámí, že je vstup neplatný. Program by měl rovněž umět načíst více zadání ze souboru zadaného uživatelem a vypsat pro ně výsledek.
Řešení klasické dětské skládačky Patnáctka. Uživatel zadá na vstup zadání úlohy (alternativně program zadání načte ze souboru). Program vypíše postup řešení, např. ve tvaru 15L 5N 7D 4P (L,P,N,D značí směr pohybu dané kostičky), na požádání vypíše do souboru i průběžné rámečky.
Implementujte některý z algoritmů pro vnější třídění (např. přímé slučování).
Uživatel zadá na vstup soustavu algebrogramů.
Příklad:
A * B = CA
A * C = D
D * A = EC
Program vypíše řešení algebrogramu (měl by umět postupně nalézt všechna řešení).
Implementujte 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ě.
Naprogramujte textovou kalkulačku pro polynomy. Uživatel zadá na vstup výrazy ve tvaru (1 + x^2)*(x + 1) nebo (0.3 - x^2)^5. Program vrátí polynom v základním tvaru (např. x^3 + 2*x + 1). Implementujte operace sčítání, odečítání, násobení, "chytré umocňování".
Uživatel zadá na vstup zvolený počet nějaké číslice, např 4444 nebo 333 a hodnotu přirozeného čísla N. Napište program, který pro všechna přirozená čisla od 0 do N zjistí, jak je zapsat za pomoci čtyř čtyřek (respektive jiného počtu jiných číslic dle zadání uživatele) a běžných aritmetických operací (+,-,*,/). Nápověda: zkuste použít dynamické programování. Program vypíše řešení pro zadané N.