Úvod do řešení problémů … (IPS) II
IPS se v letním semestru 2021/2022 koná ve čtvrtky od 19:19 v S3. Vedou ho Vašek Končický, Martin Medvěd Mareš a Eliška Vítková.
Budeme pokračovat v tradici náhodných procházek po grafech a po noční Praze.
Co jsme dělali
| datum | co jsme dělali |
|---|---|
| 17. 2. | Samoopravné kódy aneb obláčky nad prérií. |
| 24. 2. | Samoopravné kódy II: krajinou hranatých koulí. |
| 3. 3. | Náhodné procházky aneb bludičkou snadno a rychle. |
| 10. 3. | Náhodné procházky II: hledáme nejbloudivější bludiště. |
| 17. 3. | Klobouky a vězni: vězni na schodišti. |
| 24. 3. | Klobouky a vězni II: uvěznění filosofové. |
| 31. 3. | Temno poprvé: jak si pořídit množinu. |
| 7. 4. | Temno podruhé: trochu větší množiny. |
| 14. 4. | Temno potřetí: nekonečné množiny. |
| 21. 4. | Kreslení polynomy. |
| 28. 4. | Paralelní programování: spousta procesorů! |
| 5. 5. | Paralelní programování II: ještě víc procesorů! |
| 12. 5. | Stirlingova čísla. |
| 19. 5. | Kterak Herkules Hydru přelstil. |
Úkoly na zápočet
Pokud jste na IPS chodili, ale nestihli jste nic předvést u tabule, můžete si zápočet vysloužit vyřešením jednoho z těchto úkolů:
- Samoopravné kódy
- Ukažte, jak z libovolného (n,m,d)-kódu pro liché d vyrobit (n,m+1,d+1)-kód. (Připomínáme, že n je délka původní zprávy, m délka zakódované zprávy a d kódová vzdálenost.)
- Náhodné procházky
- Připomeňme větu: h(u,v) + h(v,u) = 2mR(u,v), kde h je hitting time, m počet hran a R(u,v) elektrický odpor (hrany považujeme za jednotkové rezistory). Z toho plyne, že je-li {u,v} hrana, pak h(u,v) + h(v,u) ≤ 2m. Dokažte, že pro libovolný graf platí, že střední hodnota doby, než náhodná procházka navštíví úplně všechny vrcholy, je O(n3). Hint: Obejděte kostru.
- Množiny
- Dokažte, že intervaly [0,1] a (0,1) jsou stejně mohutné.
- Paralelní programování
- Vymyslete program pro Common-CRCW PRAM, který pro graf zadaný maticí sousednosti zjistí, zda je to strom.
- Stirlingova čísla
- Jiný druh Stirlingových čísel: [n, k] je počet permutací na n-prvkové množině, které mají právě k cyklů. Prozokumejte, jaké mají vlastnosti. Inspirujte se tím, co jsme dokázali na semináři.
- Herkules a Hydra
- Odhadněte (stačí velmi zhruba), kolik seknutí stačí na zabití Hydry ve tvaru cesty s n hranami.
Řešení úkolů nám pošlete e-mailem. Řešení prosím nikde negooglete; kdybyste si nevěděli rady, řekněte si o nápovědu. Můžete pracovat ve svém IPSkovém týmu, ale řešení by měl sepsat každý sám za sebe.
Pokud by vás zaujal nějaký jiný problém, napište nám a dohodneme se.