Úvod do řešení problémů … (IPS)

Příklady ze semináře 29. 10.

1. Počet posloupností N nul a jedniček, které neobsahují dvě jedničky za sebou.
2. Počet dláždění obdélníka 2xN kostkami 1x2 a 2x1.
3. Parkoviště s N místy, auto může parkovat buď normálně nebo kolmo (v druhém případě zabere dvě sousední místa).
   • Kolika způsoby mohou auta zaplnit celé parkoviště?
   • Kolika způsoby mohou auta parkovat?
4. Počet uzávorkování s N levými a N pravými závorkami.
5. Počet cest v mřížce z bodu (0,0) do bodu (M,N) skládajících se z kroků (1,0) a (0,1).
6. ... takových, že nikdy neprotnou úhlopříčku?
7. Suma pro K=0 až N z C(n,k)*k, kde C(n,k) je kombinační číslo "N nad K".
8. Na kolik nul končí desítkový zápis 1000!? Jaká je poslední nenulová číslice?
9. Součty úhlopříček Pascalova trojúhelníku.
10. Suma pro K=L až N z C(N,K)*C(K,L).
11. Suma pro K=0 až N z C(N,K)*2^K.
12. Suma pro K=0 až N z C(N,K)².
13. Počet K-rozměrných stěn N-rozměrné krychle.
14. Počet vyhrávajících linií v piškvorkách N^D.
15. Kolik pozic má Rubikova kostka? Typu N^D? Kolik je řešitelných?
16. Počet binárních stromů na N vrcholech.
17. Počet neklesajících funkcí z {1,…N} do {1,…,M}.
18. Počet permutací na {1,…,N} takových, že 1 a 2 jsou na společném cyklu.
19. Počet pěstovaných stromů na N vrcholech.
20. Nechť X je N-prvková množina. Počítejte dvojice množin (A,B) takových, že A je podmnožinou B a B podmnožinou X.

Příklad na zápočet

Pokud jste zápočet nezískali za aktivní účast, můžete si ho vysloužit za vyřešení některé z následujících úloh:

1. Dokažte, že každý dlaždicový program, který testuje, jestli je řetězec nul a jedniček palindromický, spotřebuje v nejhorším případě alespoň lineární hloubku.
2. Navrhněte paralelní algoritmus (v modelech PRAM CREW, Common CRCW a Priority CRCW) pro nalezení matice dosažitelnosti zadaného grafu (v této matici je na pozici (i,j) jednička právě tehdy, když existuje cesta z vrcholu i do vrcholu j).
3. Spočítejte, kolik je vydláždění obdélníka 3×N kostkami 1×2. (Kostky je možno otáčet.)