UIN1065 Kapitoly z diskrétní matematiky I

Filozoficko-přírodovědecká fakulta v Opavě
zima 2008
Rozsah
2/0/0. 3 kr. Ukončení: z.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
Garance
doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
MU10132 || MU10216 || MU10232
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Předmět nabízí seznámení s řadou elegantních metod diskrétní matematiky, které jsou užitečné mimo jiné při (a) stanovení časové a prostorové složitosti rekurzivních algoritmů, (b) analýze chování algoritmů počítajících s reálnými čísly, (c) analýze algoritmů umělé inteligence, (d) určování spolehlivosti algoritmů.
Osnova
  • 1. Rekurentní problémy: pojem rekurence, uzavřená forma, důkaz správnosti. Ukázkové problémy: problém Hanojských věží, problém přímek v rovině, Josefův problém a jeho zobecnění. Repertoárová metoda.
    2. Manipulace se sumami: zápisy a transformace indexů, povolené úpravy, Iversonova notace. Asociativní, komutativní a distributivní zákon.
    3. Vícenásobné sumy, vázané a volné indexy. Zjednodušování vícenásobných sum. Zobecněný asociativní, komutativní a distributivní zákon.
    4. Sumy a rekurence: vzájemné převody sum a rekurencí, metoda sumačního faktoru, perturbační metoda.
    5. Operace 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í.
Literatura
    doporučená literatura
  • MATOUŠEK, J., NEŠETŘIL, J. Kapitoly z diskrétní matematiky. Karolinum, Praha, 2000. info
  • GRAHAM, R., KNUTH, D., PATASHNIK, O. Concrete Mathematics. Addison-Wesley, New York, 1992. info
Metody hodnocení
Ústní zkouška
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2000, zima 2001, zima 2002, zima 2003, zima 2004, zima 2005, zima 2006, zima 2007, zima 2009, zima 2010, zima 2011, zima 2012, zima 2013, zima 2014.