Ú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é číselne soustavy 1.
31. 10. Podivné číselne 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.
Stránku spravuje Martin Mareš