Diskrétna matematika 2. ročník, učitelia MI

riadny termín bol 8.1.2014 o 9:00

1. opravný termín bude 13.1.2014 o 10:00

Body

Počas semestra:

• 50% celkového hodnotenia bude tvoriť priebežné hodnotenie 9tri alebo štyri "rzocvičky". Ďalších 50% bude zo skúšky.

Tabuľka bodového ohodnotenia:

Preberané témy:

1. Riešenie rekurentných problémov, zostavenie a riešenie rekurentnej rovnice pre špeciálne typy úloh: odmena za vynájdenie šachu, Jozefova úloha, Hanojské veže, rezanie roviny. Zovšebecnená Jozefova úloha, metóda neurčitých koeficientov. PS-file a PDF-file
Príklady z cvičení: PS-file a PDF-file

2. Metódy riešenia rekurentných rovníc: Homogénne lineárne rekurentné rovnice s konštantnými koeficientami. PS-file a PDF-file
Domáca úloha č. 1 (do 23.10. 9:00): PDF-file
Príklady z cvičení: PS-file a PDF-file

3. Dolný a horný odhad, hierarchie funkcií podľa rýchlosti rastu. Asymptotické riešenie rekurentných rovníc z metódy rozdeľuj a panuj. Master Theorem. PS-file a PDF-file
Príklady z cvičení: PS-file a PDF-file
Domáca úloha č. 2: PDF-file

4. Sumy, značenie, význam. Vzťah sumy a rekurencie. PS-file a PDF-file
Príklady na sumy: PS-file a PDF-file

5. Základné sumačné zákony. Práca s viacnásobnými sumami, Čebyševove nerovnosti.
Domáca úloha č. 3: PDF-file

6. Metódy na počítanie súm. Metóda konečného kalkulu a jej aplikácie na počítanie súm. PS-file a PDF-file
Domáca úloha č. 4 PDF-file

7. Kombinatorika. Základné kombinatorické pojmy, kombinačné čísla a ich základné vlastnosti. Kombinácie, permutácie, variácie bez a s opakovaním.Polynomická veta a jej dôsledky, princíp zapojenia a vypojenia, aplikácia na príkladoch. Odhady faktoriálu.

8. Odhady kombinačných čísiel. Zovšeobecnené kombinačné čísla. Základné kombinatorické identity. Čiastočné a alternujúce súčty v zovšeobecnenom Pascalovom trojuholníku. PS-file alebo PDF-file.
Príklady z kombinatoriky: PS-file a PDF-file

9. Základné pojmy z teórie grafov. Skóre grafu. Havlova veta. Eulerovské grafy (charakterizácia). PS-file (teória grafov) alebo PDF verzia.
Príklady z teórie grafov: PS-file a PDF-file

10. Kreslenie grafu jedným ťahom. Hamiltonovské grafy. Niektoré postačujúce podmienky pre hamiltonovské grafy.

11. Vrcholová a hranová k-súvislosť grafu, vrcholový a hranový rez. Vzťah vrcholovej a hranovej súvislosti. Mengerova veta. 2-súvislé grafy. Kreslenie grafu, rovinné grafy. Eulerov vzorec a jeho dôsledky. Platónovské telesá. Kuratowského veta. Kreslenie grafu na iné plochy.

12. Farebnosť grafu, nezávislosť grafu. Vzťah farebnosti a nezávislosti grafu. Farebnosť rovinných grafov, problém štyroch farieb. Ramseyho čísla. Horné odhady na Ramseyho čísla.

13. Troška z teórie čísiel -- Nové! Faktorizácia faktoriálu, Legendrove sito, testovanie prvočíselnosti (Rabin-Millerov test), rýchle umocňovanie, šifrovanie RSA, niektoré vlastnosti kongruencií, ktoré treba k dôkazom. PDF verzia.
Príklady z teórie čísiel: PDF-file

Literatúra:

2. Š. Znám: Kombinatorika a teória grafov. Skriptá  dostupné v knižnici MFF UK v Bratislave.

3. J. Nešetřil: Teorie grafov. SNTL 1979.

4. J. Matoušek, J. Nešetřil: Kapitoly z diskrétnej matematiky. Matfyzpress 1996. Praha

5. N. J. Vilenkin: Kombinatorika, SNTL, 1977, Praha

6. Jozef Gruska: Foundation of Computing, International Thomson Press, 1997

7. Antonín Vrba: Kombinatorika, ŠMM 45, ÚV MO v Mladá fronta, Praha, 1980

8. Peter Giblin: Primes and Programming, Introduction to Number theory with Computing, Cambridge University Press, 1993

9. Juraj Hromkovič: Algorithmics for Hard Problems, Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristcs, Springer Verlag, 2001.