Diskrétní matematika

• 39 hod. přednášky
• 13 hod. cvičení
• 13 hod. pc laboratoře
• 10 hod. projekty

Studenti získají elementární znalosti z diskrétní matematiky a lineární algebry, a schopnost orientace v souvisejících matematických strukturách.

Předmět poskytuje základní znalosti z matematiky potřebné pro řadu navazujících předmětů. Studenti se seznámí s elementárními poznatky z algebry a diskrétní matematiky, s důrazem na matematické struktury, které jsou potřebné pro pozdější aplikace v informatice.

Středoškolská matematika.

• Demlová M., Nagy J., Algebra, SNTL, Praha 1982.
• Havel, V., Holenda, J., Lineární algebra, STNL, Praha 1984.
• Jablonskij, S.V., Úvod do diskrétnej matematiky, Alfa, Bratislava, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
• Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
• Peregrin J., Logika a logiky, Academia, Praha 2004.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.

• Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
• Acharjya D. P., Sreekumar, Fundamental Approach to Discrete Mathematics, New Age International Publishers, New Delhi, 2005.
• Faure R., Heurgon E., Uspořádání a Booloeovy algebry, Academia, Praha 1984.
• Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
• Garnier R.,  Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002.
• Gratzer G., General Lattice Theory, Birkhauser Verlag, Berlin 2003.
• Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
• Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
• Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
• Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
• Kolman B., Elementary Linear Algebra, Macmillan Publ. Comp., New York 1986.
• Kolman B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1993.
• Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
• Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
• Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983.
• Lipschutz, S., Lipson, M.L., Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997.
• Lovász L., Pelikán J., Vesztergombi, Discrete Mathematics, Springer-Verlag, New York 2003.
• Mannucci M. A., Yanofsky N. S., Quantum Computing For Computer Scientists, Cambridge University Press, Cambridge 2008.
• Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
• Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
• Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
• Nahara M., Ohmi T., Qauntum Computing: From Linear Algebra to Physical Realizations, CRC Press, Boca Raton 2008.
• O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
• Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
• Rosen, K. H. et al., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton 2000.
• Ross, S. M. Topics in Finite and Discrete Mathematics, Cambridge University Press, Cambridge 2000.
• Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
• Švejdar, V., Logika, neúplnost, složitost a nutnost, Academia, Praha 2002.
• Vickers S., Topology via Logic, Cambridge University Press, Cambridge 1990.

• Intuitivní pojem množiny. Základní množinové operace. Potenční množina. Číselné množiny Binární relace na množině. Zobrazení jako binární relace. Obor a ko-obor. Funkce a posloupnosti jako zobrazení číselných množin. Kompozice relací a zobrazení.
• Zobrazení injektivní, surjektivní a bijektivní. Inverzní zobrazení. Obraz a inverzní obraz množiny. Význačné systémy podmnožin a jejich užití. Topologická definice spojitosti s příklady.
• Operace na množině. Základní klasifikace struktur s jednou a dvěma operacemi. Grupa permutací konečné množiny. Kombinatorické vlastnosti konečných množin. Princip inkluze a exkluze.
• Reflexivita, symetrie, antisymetrie, tranzitivnost binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Grupy zbytkových tříd.
• Uspořádání, zvláště svazové. Jako příklady Khalimského digitální přímka a uspořádání množiny reálných čísel. Hasseovy diagramy. Svaz jako množina se dvěma operacemi. Booleova algebra.
• Hlavní vlastnosti a zákony Booleových algeber. Dualita a množinová reprezentace konečné Booleovy algebry.
• Výroky, kvantifikátory a základní logické spojky. Predikátový počet a jeho syntaxe. Klasifikace formulí. Výrokový počet a počet rovnosti jako vlastní podtřídy predikátového počtu.
• Interpretace formulí. Tautologie, nesplnitelné formule a logická ekvivalence formulí. Struktura algebry neekvivalentních formulí.
• Prenexní normální formy formulí. Pravdivost a rozhodnutelnost.
• Dedukční systémy. Systém přirozené dedukce a jeho pravidla. Důkaz v systému přirozené dedukce. Techniky důkazů.
• Grafy. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů. Podgraf.
• Izomorfismus a homeomorfismus grafů. Problém rovinnosti .
• Stromy, kostry a jejich vlastnosti. Prohledávání binárního stromu. Vybrané třídící algoritmy.

• Procvičování a modelování vlastností množin, množinových operací, binárních relací a zobrazení. Modelování kompozice relací a zobrazení.
• Procvičování a modelování vlastností zobrazení injektivních, surjektivních a bijektivních. Inverzní zobrazení. Zkoumání jednoduchých topologií na množinách.
• Procvičování a modelování struktur s jednou a dvěma operacemi. Procvičování kombinatorických vlastností konečných množin a Principu inkluze a exkluze.
• Rozhodování o reflexivitě, symetrii, antisymetrii, tranzitivnosti binárních relací. Hledání uzávěrů, ekvivalencí a rozkladů. Zkoumání vlastností grup zbytkových tříd.
• Příklady různých uspořádání. Khalimského digitální přímka a reálná přímka. Hasseovy diagramy. Booleova algebra.
• Procvičování vlastností konečných Booleových algeber. Jejich dualita a množinová reprezentace.
• Procvičování základů výrokového a predikátového počtu.
• Zkoumání a procvičování vlastností formulí.
• Hledání prenexních normální forem formulí.
• Formalizace, příklady a procvičování důkazových technik.
• Konstrukce algoritmu nalezení nejkratší cesty. Zjišťování souvislosti grafů.
• Zjišťování rovinnosti grafů.Zkoumání a modelování stromů a koster grafů.
• Hledání minimální kostry.Prohledávání binárního stromu. Třídění.

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Absolvování cvičení ve stanoveném rozsahu.