Detail předmětu

Diskrétní matematika

IDA Ak. rok 2005/2006 zimní semestr 7 kreditů

Aktuální akademický rok

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy 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

český

Zakončení

zkouška (písemná)

Rozsah

39 hod. přednášky, 12 hod. cvičení, 4 hod. pc laboratoře, 10 hod. projekty

Bodové hodnocení

60 zkouška, 10 cvičení, 30 projekty

Zajišťuje ústav

Přednášející

Cvičící

Fuchs Petr, RNDr., Ph.D. (UMAT FEKT VUT)

Získané dovednosti, znalosti a kompetence z předmětu

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.

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

Středoškolská matematika.

Literatura studijní

  1. Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
  2. Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
  3. Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
  4. Lipschutz, S., Lipson M. L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992. 
  5. Preparata, F. P., Yeh R. T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
  6. Rosen, K. H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
  7. Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
  8. Demlová, M., Nagy, J., Algebra, STNL, Praha 1982.
  9. Havel, V., Holenda, J., Lineární algebra, STNL, Praha 1984.
  10. Hrůza, B., Mrhačová, H., Cvičení z lineární algebry, PC-Dir, Brno 1984.

Literatura referenční

  1. Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
  2. Jablonskij, S. V., Úvod do diskrétnej matematiky, Alfa, Bratislava, 1984.
  3. Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
  4. Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
  5. Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983.
  6. Lipschutz, S., Lipson, M. L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
  7. Preparata, F. P., Yeh, R. T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
  8. Rosen, K. H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
  9. Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
  10. Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
  11. Anton, H., Elementary Linear Algebra, John Wiley, New York, 1984.
  12. Demlová, M., Nagy, J., Algebra, STNL, Praha, 1982.
  13. Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.

Osnova přednášek

  1. 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.
  2. 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.
  3. Vlastnosti binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hassovy diagramy.
  4. Algebry s jednou a dvěma operacemi a jejich morfismy. Grupy a tělesa. Svaz jako množina se dvěma operacemi. Booleova algebra.
  5. Hlavní vlastnosti a zákony Boolových algeber. Množinová reprezentace konečných Boolových algeber.
  6. Formule a sémantika výrokového počtu. Interpretace a klasifikace formulí. Boolova algebra neekvivalentních formulí. Syntaxe výrokového počtu. Věta o kompaktnosti. Normální tvary formulí.
  7. Matice a maticové operace. Determinant čtvercové matice. Inverzní a adjungovaná matice. Metody výpočtu determinantu.
  8. 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ů.
  9. Soustavy lineárních rovnic. Gaussova eliminace. Frobeniova věta. Cramerovo pravidlo.
  10. 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.
  11. Grafy a jejich různé reprezentace. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů.
  12. Podgrafy. Izomorfismus a homeomorfismus grafů. Eulerovské a hamiltonovské grafy. Problém rovinnosti.
  13. 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.

Osnova ostatní - projekty, práce

Pět samostatných domácích úloh - bližší informace sdělí vyučující.

Průběžná kontrola studia

Účast na cvičeních. Odevzdání domácích úloh.

Kontrolovaná výuka

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

Zařazení předmětu ve studijních plánech

  • Program IT-BC-3, obor BIT, 1. ročník, povinný
Nahoru