1. Analýza podgrup:
(a) Nalézt všechny podgrupy dané grupy a jejich
vzájemné inkluze.
(b) Pro dvě dané grupy zjistit, zdali jsou
izomorfní. V kladném případě nalézt všechny izomorfismy.
2. Formální manipulace s výrazy: Symbolická integrace (nalézt k dané funkci
funkci primitivní)
+ zjednodušení výsledného výrazu
3. Konečné automaty: Převod mezi regulárním výrazem a konečným automatem (oba směry). Automat lze reprezentovat přímo programem v jazyce Prolog.
4. 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).
Automat lze reprezentovat přímo programem v jazyce Prolog.
5. Řešení soustav algebrogramů. 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).
6. Sehrání šachové koncovky
a) K + V kontra K,
b) K + D kontra K,
c) K + 2S kontra K.
Upozornění: Nejde o implementaci minimaxového algoritmu.
7. Šachové n-tažky: Program pro generování šachových úloh typu "mat třetím tahem".
8. Karetní hry:
a) pasiáns (hraje samostatně nějakou variantu, vypisuje svoje možnosti a zvolené tahy)
b) mariáš
9. Sudoku: Čtvercová matice m ∗ n je rozdělena vertikálně na skupiny o m řádcích, horizontálně na skupiny o n sloupcích. Každá skupina má obsahovat všechna čísla od 1 do m ∗ n.
Cílem je pro zadané m,n vygenerovat zadání (tj. matici s odkrytými hodnotami na některých políčkách) s daným stupněm obtížnosti řešení, obtížnost lze určit např. mírou nedeterminismu při řešení.
10. Rush Hour Puzzle: Obdélníková deska m ∗ n je rozdělena na čtverečky 1x1 a obsahuje nepřekrývající se dominové kostky 1x2 a 1x3 (reprezentují auta), které se mohou pohybovat ve směru svojí delší strany. Cílem je převést určenou kostku z počáteční do cílové polohy, typicky od stěny ke stěně, na co nejmenší počet tahů. Na závěrečné poloze ostatních nezáleží [wiki]. Generování zadání se zadaným stupněm obtížnosti.
11. Ďábelské miny: Po odkrytí stanoveného počtu polí počítač (v roli ďábla) 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.
12. Pro kytaristy: Program pro automatické vygenerování
prstokladu pro kytaristu, zadávají se akordové značky, program generuje všechna řešení, uspořádaná dle "použitelnosti".
13.
Pro křížovkáře: Program pro sestavení křížovky, je-li zadán slovník, tajenka, tvar křížovky.
14. Pro hádankáře: Program pro automatické vytváření dvojrozměrných bludišť. Zadávají se parametry, např. výška & šířka, relativní množství křižovatek, relativní množství alternativních cest k cíli apod. Příklad výstupu:
| n | 1 | 2 | 3 | 4 |
| S(n) | 1 | 4 | 6 | 13 |
Podmínky: Páska je oboustranně nekonečná, na začátku výpočtu prázdná.
V každém kroku se hlava posouvá doleva nebo doprava.
Existuje jediný koncový stav, který se do počtu stavů n nezahrnuje.
Pracovitý bobr je stroj výše popsaného typu, po jehož zastavení bude na pásce S(n) jedniček.
Napište program, který pro zadané (malé) n nalezne pracovitého bobra s n stavy (n < 5).
Poznámka: Pozor, funkce S obecně není vyčíslitelná. Přesná hodnota S(5) je otevřený problém.
24. Ruskey-Savage Conjecture (F.Ruskey, C.Savage, 1993): Hyperkrychle dimenze n je graf, jehož vrcholy jsou všechny n-bitové řetězce, přičemž hrany vedou mezi vrcholy
lišící se v jediném bitu. Podle stále otevřené hypotézy lze každé párování (množina neprotínajících se hran) v tomto grafu rozšířit na hamiltonovskou kružnici
(každým vrcholem prochází právě jednou) [html]. Napište program, který prověří hypotézu pro malé hodnoty n.
25. Vaše vlastní návrhy jsou možné, jen je třeba zadání předem konzultovat se cvíčícím.