NDMI002 Diskrétní matematika
Středa, 15:40, S10
Výsledky druhé písemné práce ze dne 7.1.2009
Podmínky zápočtu
Postačující podmínkou pro udělení zápočtu je úspěšné napsání dvou písemek (první se bude psát 12.11., druhá 7.1.).
Za úspěšné se považuje dosažení 30 bodů z 50 možných.
V případě neúspěchu při písemce bude možný náhradní termín. Body do písemky lze také získat následovně:
- účastí na cvičeních (každé cvičení za 1 bod)
- vypracováním domácí úlohy (1-2 body za úlohu)
Probraná látka
1.10.2008
- Číselné množiny: přirozená, celá, racionální a reálná čísla. Důkaz, že sqrt(2) není racionální.
- Horní a dolní celá část čísla. Precizní důkaz, že horní celá část z x minus dolní celá část z x je buď 0 nebo 1.
Formule pro počet číslic celého čísla c v desítkové soustavě pomocí logaritmu.
- Matematická indukce. Princip matematické indukce. Důkaz, že
1+2+3+...+n = n*(n+1)/2.
- Sumy. Definice sumy a její hlavní vlastnosti
- Důkaz rovnosti:
\sum_{i=1}^n (-1)^{i+1} i^2 = \frac{(-1)^{n+1}n(n+1)}{2}
(zápis rovnice v TeXu)
- Ekvivalence principu indukce a principu dobrého uspořádání. Ukázána byla pouze jedna implikace. Druhá zůstává
jako rozmyšlení na doma.
Domácí úloha (1 bod): Indukcí dokázat následující tvrzení: Nechť x1, x2, ..., xn jsou reálná čísla. Potom platí:
|\sum_{i=1}^n x_i | \leq \sum_{i=1}^n |x_i|
8.10.2008
- Opakování matematické indukce, několik 'standardních' příkladů na matematickou indukci.
- Příklad na nebezpečná zákoutí matematické indukce: důkaz, že všechny krávy na světě mají stejnou barvu.
- Množiny a operace s nimi: sjednocení, průnik, rozdíl, kartézský součin, kartézská mocnina
- Relace na množině, příklady relací.
Domácí úloha (2 body): Indukcí dokázat Moivreovu větu:
(cos x + i*sin x)^n = cos (nx) + i*sin(nx)
15.10.2008
Cvičení odpadlo z důvodu imatrikulace - také mi o tom mohl někdo (nemám na mysli studenty) říct:-)
22.10.2008
- Opakování relací, skládání relací, mocnění relací
- Příklady na skládání relací.
- Důkaz, že je-li R relace na konečné množině X, existují kladná různá přirozená čísla r,s tak, že R^r = R^s.
- Zobrazení. Definiční obor, obor hodnot zobrazení. Souvislost s relacemi. Skládání zobrazení a relací.
- Zobrazení prostá a na.
29.10.2008
- Vlastnosti relací (reflexivita, symetrie, tranzitivita, slabá antisymetrie).
- Uspořádání a ekvivalence.
- Zobrazení prostá a na.
- Na konečné množině platí f:X -> X je prostá právě když je na.
- Na nekonečné množině předchozí tvrzení neplatí. Neplatí ani jedna implikace.
- Jsou-li f,g prostá zobrazení (zobrazení na) je i f o g prosté (na).
- Je-li f o g prosté (na), je i g (f) prosté (na)
Domácí úloha (1 bod): Vyjádřit vlastnosti relací (reflexivita, symetrie, tranzitivita, slabá antisymetrie) pouze pomocí
symbolů Id (identita), ^-1 (inverzní relace), o (skládání relací), množinových operací a \subseteq (býti podmnožinou).
5.11.2008
- Grafy.
- Podgraf, indukovaný podgraf
- Speciální druhy grafů: úplný graf, cesta, kružnice.
- Bipartitní grafy.
- Izomorfizmus grafů.
12.11.2008
Psala se písemná práce.
19.11.2008
- Izomorfizmus grafů, dolní odhad počtu neizomorfních grafů.
- Cesta, kružnice, sled v grafu.
- Tvrzení: Mezi dvěma vrcholy existuje sled právě když mezi nimi existuje cesta.
- Souvislost grafu.
- Eulerovské tahy, věta o uzavřeném eulerovském tahu (podrobně udělána pouze neorientovaná verze).
Domácí úloha (1 bod): Formulovat a dokázat tvrzení o ne nutně uzavřeném eulerovském tahu.
26.11.2008
- De Bruijnovy grafy.
- Stromy, různé definice stromů, důkaz jejich ekvivalence.
- Úvod do rovinných grafů.
3.12.2008
- Rovinné grafy.
- Eulerův vzorec.
- Důsledek: každý rovinný graf má vrchol stupně 5.
- Barevnost grafů.
- Degenerovanost grafů.
- Věta o pěti barvách s důkazem, věta o čtyřech barvách bez důkazu.
10.12.2008
- Základy teorie pravděpodobnosti.
- Pravděpodobnostní prostor.
- Jevy a elementární jevy v pravděpodobnostním prostoru.
- Diskrétní a indiskrétní pravděpodobnostní prostory, význam sigma-algebry v definici pravděpodobnostního prostoru.
- Popis pravděpodobnostního prostoru G(n,p).
- Narozeninový paradox.
17.12.2008
- Podmíněná pravděpodobnost, nezávislost jevů.
- Náhodná veličina.
- Střední hodnota náhodné veličiny.
- Linearita střední hodnoty.
- Příklad na linearitu střední hodnoty: Počet přeživších zajíců.
