Programování 2 - Matematici 
21.04.2026 úterý
24.04.2026 pátek
28.04.2026 úterý

Stav a Procházení stavového prostoru

- Diskuze, co je to "stav" a příklady stavů různých systémů.
- Sousední stav a akce na stavu (souvislost s příklady z Lineární algebry;)
- Procházení stavového prostoru DFS a BFS a jejich vlastnosti 
- jak jsme zobecňovali struktury na cvičení a jejich průchody: BT -> T -> connected Graph -> Graph -> State Space




1. Mějme standardní šachovnici. Na šachovnici je zadáno startovní (S) políčko, cílové (C) políčko a figurka.

Následuje série úloh:
1.1 Dostanu se figurkou ze startu do cíle?
Rozhodněte, zdali lze ze startovního políčka dosáhnout cílové políčko pomocí koně (figurka šachů).
1.2 Jaká je nejkratší cesta ze startu do cíle?
V kolika nejméně tazích koněm (figurka šachů) lze dosáhnout cílové políčko ze startovní pozice (figurka šachů), pokud nelze vraťte hodnotu "-1".
1.3 Vypsat-evidovat nejkratší cestu
Vypište nějakou nejkratší cestu koněm (figurka šachů) ze starotvního políčka do cílového.


1.5 Modifikace předchozích úkolů (jak dosažení, nejkratší cesta (délka) tak nejkratší cesta (výpis)), pro:
1.5.2 jiné figurky: střelec, věž, dám, baba jaga, ... (obecně jiný druh pohybu po šachovnici)
1.5.3 nestandardní šachovnice: s překážkami (zakázané pole), nestandardní rozměry (třeba 11x11 nebo obdélníková 7x21), toroidní (cirkulární) pole, ...


Kdy se hodí, na které úlohy a jaké jsou limity DFS a BFS?


3. Mějme šachovnici a startovní políčko a figurku. Úkolem je zjistit, zdali (a jak) lze ze startovního políčka a danou figurkou proskákat všechna políčka šachovnice za podmínky, že na každé políčko vstoupím právě jednou.
https://ksvi.mff.cuni.cz/~topfer/ppt/A10%20prohledavani%20do%20hloubky.pdf

- jak eviduji navštívená pole? (více způsobů: list navštívených polí, 2D list, ...)
- vracím, True\False, že lze proskákat nebo bracím i kudy jsem proskákal?
- změní se mi reprezentace navštívených polí?

3.3 Napište lidský pseudokod algoritmu
3.4 Napište pseudokód algoritmu do Vašeho IDE
3.5 A podle psedudokódu následně funkce, "nebojme se vetsi dekompozice" program nemusi (a nemel by byt) jeden velky "blob"
v pseudokodu: "sloveso ... funkce, podstatne jmeno ... proměnna"
3.6 Program doprogramujte 

POZNAMKY ZE CVICENI:




3.3 Modifikace předchozího, na šachovnici (stejně jako v domácím úkolu) jsou zakázaná políčka (na které není možné vstoupit, ale je možné je přeskočit).