Úvod do řešení problémů … (IPS)
IPS se v zimním semestru 2019/2020 koná ve čtvrtky od 19:19 v S3. Vedou ho Meggy Calábková, Martin Medvěd Mareš a Viki Němeček.
Co jsme dělali
| datum | co jsme dělali |
|---|---|
| 3. 10. | Důkazy pravé a falešné. Záhadný trojúhelník a Fibonacciho čísla. |
| 10. 10. | Dlaždičkové programy 1. |
| 17. 10. | Dlaždičkové programy 2. |
| 24. 10. | Podivné číselné soustavy 1. |
| 31. 10. | Podivné číselné soustavy 2. |
| 7. 11. | Kreslení pomocí polynomů. |
| 14. 11. | Simulace kostek. |
| 21. 11. | Strom, na němž rostou zlomky. |
| 28. 11. | Které všechny zlomky rostou na stromě? |
| 5. 12. | Stroj s počítadly. |
| 12. 12. | Různé stroje s počítadly. |
| 19. 12. | Trocha Vánoc. Rozstříhaná a slepená :) |
| 9. 1. | Stirlingova čísla. |
Ú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ů:
- 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.
- 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éž.
- Stirlingova čísla
- Připomeňme definici Stirlingových čísel: S{n,k} = počet rozkladů n-prvkové množiny na k tříd; S[n,k] = počet permutací na n-prvkové množině s k cykly. Dále zavedeme klesající mocninu: xn = x*(x-1)*…*(x-n+1). To je nějaký polynom v proměnné x. Jaké jsou jeho koeficienty? A jak bude naopak vypadat zápis xn jako lineární kombinace klesajících mocnin? Obojí hezky souvisí se Stirlingovými čísly.