Úvod do řešení problémů … (IPS)
IPS se v zimní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á.
Co jsme dělali
| datum | co jsme dělali |
|---|---|
| 30. 9. | Důkazy pravé a falešné. Záhadný trojúhelník a Fibonacciho čísla. |
| 7. 10. | Podivné číselné soustavy. |
| 14. 10. | Podivné číselné soustavy 2. |
| 21. 10. | Dlaždičkové programování. |
| 4. 11. | Dlaždičkové programování 2. |
| 11. 11. | Strom, na němž rostou zlomky. |
| 18. 11. | Které všechny zlomky rostou na stromě? |
| 25. 11. | Diskrétní kalkulus. |
| 2. 12. | Kombinatorické počítání 1. |
| 9. 12. | Kombinatorické počítání 2. |
| 16. 12. | Trocha Vánoc. Rozstříhaná a slepená :) |
| 6. 1. | Stroj s počítadly. |
Ú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ů:
- Dlaždičkové programování
- Vymyslete dlaždičkový program, který zjistí, zda posloupnost 0 a 1 na vstupu obsahuje stejně 0 jako 1. Dosáhněte logaritmické hloubky.
- Dlaždičkové programování podruhé
- Vymyslete dlaždičkový program, který zjistí, zda posloupnost 0 a 1 na vstupu je symetrická (je to palindrom). Dokažte, že to v asymptoticky lepší hloubce nejde.
- Zlomkovník
- Dokažte, že pro každé kladné reálné číslo existuje ve stromu zlomkovníku větev (nekonečná cesta začínající v kořeni), která k tomuto číslu konverguje.
- Kombinatorika
- Kolik existuje permutací na množině {1,…n} takových, že 1 a 2 leží na společném cyklu?
- Krychličky
- Kolik k-rozměrných stěn má d-rozměrná krychle?
- Stroj s počítadly
- Najděte co nejmenší K takové, že kterýkoliv program pro stroj s počítadly jde předělat na program používající nejvýše K registrů (nepočítáme registry pro vstup a výstup), který počítá totéž.
Ř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.