Detail předmětu
Diskrétní matematika
IDA Ak. rok 2004/2005 zimní semestr 7 kreditů
Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Booleovy algebry. Sémantika a syntaxe výrokového počtu. Normální tvary formulí. Matice a determinanty. Vektorové prostory a podprostory. Soustavy lineárních rovnic. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Jednoduché grafové algoritmy.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 10 hod. cvičení
- 4 hod. pc laboratoře
- 12 hod. projekty
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Studenti získají elementární znalosti z diskrétní matematiky a schopnost orientace v souvisejících matematických strukturách.
Cíle předmětu
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.
Požadované prerekvizitní znalosti a dovednosti
Nejsou žádné prerekvizity.
Literatura studijní
- 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.
Literatura referenční
- 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.
Osnova přednášek
- Formální jazyk matematiky a intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Kombinatorické vlastnosti množin. Princip inkluze a exkluze. Techniky důkazů - důkazy přímé, indukcí, sporem a jejich ilustrace.
- Binární relace a zobrazení. Skládání relací a zobrazení. Vlastnosti zobrazení. Algebry a indexované systémy množin a jejich zobrazení. Reálné funkce a jejich vlastnosti. Rekurzívně definované funkce.
- Vlastnosti binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovy diagramy.
- Algebry s jednou a dvěma operacemi a jejich morfismy. Grupy a tělesa. Svaz jako množina se dvěma operacemi. Booleova algebra.
- Hlavní vlastnosti a zákony Booleových algeber. Množinová reprezentace konečných Booleových algeber.
- Formule a sémantika výrokového počtu. Interpretace a klasifikace formulí. Booleova algebra neekvivalentních formulí. Syntaxe výrokového počtu. Věta o kompaktnosti. Normální tvary formulí.
- Algebra komplexních čísel. Matice a maticové operace. Determinant čtvercové matice. Inverzní a adjungovaná matice. Metody výpočtu determinantu.
- Vektorový prostor a jeho podprostory. Báze a dimenze. Vyjádření vektoru v bázi. Transformace souřadnic. Lineární zobrazení vektorových prostorů.
- Soustavy lineárních rovnic. Gaussova eliminace. Frobeniova věta. Cramerovo pravidlo.
- Skalární a unitární součin. Ortonormální systémy vektorů. Ortogonální průmět vektoru do podprostoru. Vektorový a smíšený součin.
- Grafy a jejich různé reprezentace. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů.
- Podgrafy. Izomorfismus a homeomorfismus grafů. Eulerovské a hamiltonovské grafy. Problém rovinnosti.
- Stromy, kostry a jejich vlastnosti. Binární stromy a jejich prohledávání. Tok v orientovaném grafu.
Osnova numerických cvičení
Budou procvičena témata z přednášek ve vhodném rozsahu.
Osnova počítačových cvičení
Dvě dvouhodinová cvičení k tématům přednášek číslo 8, 9 a 10.
Průběžná kontrola studia
Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.
Podmínkou pro udělení zápočtu je absolvování počítačových cvičení a vypracování domácích úloh/projektů v rozsahu, který stanoví cvičící.
Kontrolovaná výuka
Absolvování počítačových cvičení ve stanoveném rozsahu a odevzdání domácích úloh/projektů.