Předmět Kapitoly z diskrétní matematiky (KMI / PGSD)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / PGSD - Kapitoly z diskrétní matematiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Předmět je určen studentům doktorského studia informatiky a matematiky. Studenti se seznámí s metodami diskrétní matematiky, které jsou užitečné zejména přia) stanovení časové a prostorové složitosti algoritmů,b) analýze chování algoritmů počítajících s reálnými čísly,c) analýze algoritmů umělé inteligence prohledávajících stavové prostory problémů s kombinatorickou explozí,d) tvorbě a analýze hašovacích algoritmů a řadě dalších příležitostí.1. Rekurentní problémy: rekurence a její uzavřená forma. Ukázkové problémy a jejich zobecnění. Repertoárová metoda řešení rekurencí.2. Sumy a pokročilé manipulace s nimi: transformace indexů, povolené úpravy, Iversonova notace. Vícenásobné sumy, vázané a volné indexy, jejich záměny a zjednodušování. Zobecněný asociativní, komutativní a distributivní zákon.3. Sumy a rekurence: vzájemné převody sum a rekurencí, metoda sumačního faktoru, perturbační metoda pro řešení sum a rekurencí.4. Operátory diference a sumace jako diskrétní paralela diferenciálního a integrálního počtu. Jejich aplikace při výpočtech sum a rekurencí.5. Výpočty se zaokrouhlováním. Odstraňování zaokrouhlovacích operátorů v nerovnicích. Rekurence a sumy se zaokrouhlováním, metody jejich řešení.Vybrané problémy teorie čísel: dělitelnost a (relativní) prvočíselnost, kongruence generovaná operací mod a její vlastnosti, nezávislá rezidua, aplikace teorie čísel v informatice.Asymptotiky a pokročilé manipulace s výrazy obsahujícími asymptotiky.Manipulace s výrazy obsahujícími binomické koeficienty, základní vztahy a možnosti úprav. Zobecnění na záporná čísla a na reálný obor. Sumy a rekurence s binomickými koeficienty.Vytvořující funkce a číselné posloupnosti jimi generované. Základní katalog vytvořujících funkcí. Složené vytvořující funkce - součty, násobení, sumace, diference, integrál, derivace, konvoluce.Manipulace s vytvořujícími funkcemi. Použití vytvořujících funkcí při výpočtech rekurencí a sum. Exponenciální a Dirichletovy generující funkce.
Získané způsobilosti
2. PorozuměníPopsat a důkladně pochopit principy a metody vybraných partií diskrétní matematiky.
Literatura
Graham R., Knuth D., Patashnik O. Concrete Mathematics. New York, Addison-Wesley, 1992. ISBN 0-201-14236-8.Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 1999. ISBN 0-07-289905-0.Matoušek J., Nešetřil J. Kapitoly z diskrétní matematiky. Praha, Karolinum, 2000. ISBN 80-246-0084-6.
Garant
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.
Vyučující
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.