Cvičení NDMA005 DM, ve čtvrtek od 9:50 M3, kruh 52

Pro získání zápočtu je nutné získat dostatek bodů - alespoň 80 bodů. Body lze získat následujícími způsoby:

• Za aktivitu na cvičení a řešení příkladů u tabule.
• Za řešení domácích úkolů zadávaných na jednotlivých cvičeních.
• Napsání zápočtových písemek - budou obsahovat úlohy podobné příkladům ze cvičení a na zkoušce, mělo by jít získat až 100 bodů.

Domácí úkoly budou vždy zadávány po sériích na téma, které jsme probírali na cvičeních. Na jejich vypracování budou většinou dva týdny. Úkoly se odevzdávají písemně na cvičeních. Na daném cvičení si pak ukážeme i jejich řešení. Navíc některé obtížnější úkoly mají otevřený časový limit.

Konzultační hodiny nevypisuji, ale lze si je domluvit po mailu. Ideální doba je například na konci cvičení.

Pokud vám chybí body na zápočet, můžete vyřešit příklady z druhé písemky, za každý můžete dostat až pět bodů. Ke stažení: PDF PS.

Text o relacích - ke cvičení jsem sepsal desetistránkový textík o relacích, zejména o jejich skládání. Pokud relacím nerozumíte, doporučuji si ho přečíst. Pokud objevíte chybu nebo vám přijde nějaká část nesrozumitelná, napište mi prosím. Ke stažení zde: PDF.

Domácí úkoly

• Série 1: Logické úložky (termín odevzdání 14.10.2010) PDF PS, flashovou hru pro úlohu 1c naleznete ZDE. Protože nepředpokládám znalost japonštiny, hra se spustí modrým kruhovým tlačítkem, mezi břehem a vorem se lidé přesouvají kliknutím na ně, vor se přesune na druhou stranu pomocí červeného tlačítka na druhém břehu.
• Série 2: Množiny a matematická indukce (termín odevzdání 21.10.2010) PDF PS.
• Série 3: Kombinační čísla, relace a zobrazení (termín odevzdání 4.11.2010) PDF PS.
• Série 4: Zobrazení a ekvivalence (termín odevzdání 11.11.2010) PDF PS.
• Série 5: Kombinatorické počítání (termín odevzdání 25.11.2010) PDF PS.
• Série 6: Počítání a princip inkluze a exkluze (termín odevzdání 2.12.2010) PDF PS.
• Série 7: Částečná a lineární uspořádání (termín odevzdání 9.12.2010) PDF PS.

Co jsme dělali na cvičeních

• 30.09.2010 - úvodní cvičení; řešili jsme logické úlohy (PDF); dokazovali jsme, že šachovnice bez dvou protějších rohů nelze pokrýt dominovými kostičkami; ukazoval jsem podvodný důkaz matematickou indukcí, že všechny ženy mají stejnou barvu očí.
• 7.10.2010 - logická úloha o pirátech a dělení pokladu; deMorganovy vzorce pro průniky a sjednocení množin; počet podmnožin n-prvkové množiny, počet k-prvkových podmnožin, počet podmnožin sudé a liché velikosti; kombinační čísla a kombinatorický náhled; různé vztahy kombinačních číslech, např. Pascalův trojúhelník; počet cest v mřížce n krát m, které jdou pouze nahoru nebo doprava je n+m nad n; ekvivalence axiomu indukce s principem dobrého uspořádání - příště si ještě k tomu něco řekneme.
• 14.10.2010 - procházeli jsme některé z domácích úkolů první série; základní příklady na matematickou indukci: součet aritmetické řady; součet prvních n lichých čísel je n²; součet geometrické řady; rekurzivní vztah pro Fermatova čísla a proč dokazuje, že prvočísel je nekonecně mnoho; úvod do relaci - co je to, jak se dají reprezentovat (graf se šipkami, matice, šipky zleva doprava); základní vlastnosti relací - reflexivní, tranzitivní, symetrická; skládání relací; příště si na všechno uděláme spoustu příkladů.
• 21.10.2010 - bavili jsme se o skládání relací; jak vypadá ostré a neostré uspořádání přirozených čísel složené samo se sebou (v tom prvním případě dostaneme (a,b), pokud a + 1 < b, ve druhém dostaneme stejné uspořádání); pokud je relace R reflexivní, potom R je podmnožina R složeno s R, relace R je tranzitivni, právě když R složeno s R je podmnozina R -- tedy dohromady: Pokud je relace reflexivní a tranzitivní, potom R složeno s R je R; zadefinovali jsme si, jak vypadá inverzní relace R^-1.
• 26.10.2010 - ukazovali jsme si řešení některých domácích úkolů z druhé série; definice zobrazení, kdy je zobrazení prosté a na; pokud zobrazení f a g jsou prosté, potom i g o f je prosté; naopak, pokud g o f je prosté, potom f je prosté, ale g být nemusí; základní příklady ekvivalencí a co naopak ekvivalence nejsou; komplexní čísla v polárních souřadnicích jsou v relaci, pokud maji stejný úhel (to není ekvivalence kvůli počátku), za druhé pokud mají stejnou vzdálenost od počátku (to ekvivalence je).
• 04.11.2010 - kolik existuje zobrazení z A do B a kolik jich je prostých (někdy příště, kolik jich je na); počet permutací, které mají jenom jeden cyklus a které mají každý cyklus délky dva; binomická a multinomická věta, multinomické koeficienty a kolik existuje různých slov tvořených písmeny MISSISSIPPI; identity s kombinačními čísly a jejich kombinatorická interpretace.
• 11.11.2010 - pořádně jsme probírali úkoly o relacích, obzvlášť jsem zdůrazňoval, že v matematice je potřeba všechno zdůvodňovat, o samotné výsledky nám tolik nejde!!; Fibonacciho čísla jako řešení řady kombinatorických úloh; odvození vzorečku pro n-té Fibonacciho číslo jako kouzelnický trik pomocí lineární algebry (využívali jsme pěkné báze) - podobnou metodu lze použít i pro jiné lineární rekurzivní posloupnosti; Catalanova čísla a odvození pomocí metody zrcadla; příště budeme dělat inkluzi a exkluzi; písemka umluvena na 9.12.
• 18.11.2010 - princip inkluze a exkluze; ukazovali jsme si několik důkazů; motivační příklad s pohádkovými bytostmi (čarodejnice, vodníci a matfyzáci stojí ve frontě, kolika způsoby mohou stát, aby žádná skupina netvořila souvislý úsek); počet čísel od 1 do 1000 nedělitelných 4,5 a 6; počet zobrazení na pomocí inkluze a exkluze; proč je počet zobrazení na dělitelný n! a souvislost s počtem ekvivalencí s přesně k třídami na - stirlingovo číslo.
• 25.11.2010 - částečná a lineární uspořádání; příklady uspořádání a proč jsou to uspořádání, relace předchůdce a Hasseho diagramy, definice minimálního a nejmenšího prvku; příklady, kdy existují minimální prvky, ale neexistuje nejmenší; nejmenší prvek je určen jednoznačně, pokud existuje; nekonečné uspořádání může mít jediný minimální prvek, ale nemusí mít prvek nejmenší, pro konečné to už neplatí.
• zbytek - doplním brzy.