Fakulta informačních technologií VUT v Brně

Detail předmětu

Diskrétní matematika

IDA Ak. rok 2006/2007 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

česky

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í

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í

  • 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.
  • Lipschutz, S., Lipson M. L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992. 
  • 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.
  • Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
  • Demlová, M., Nagy, J., Algebra, STNL, Praha 1982.
  • Havel, V., Holenda, J., Lineární algebra, STNL, Praha 1984.
  • Hrůza, B., Mrhačová, H., Cvičení z lineární algebry, PC-Dir, Brno 1984.

Literatura referenční

  • Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 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.
  • Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
  • Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983.
  • Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
  • 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.
  • Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
  • Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
  • Anton, H., Elementary Linear Algebra, John Wiley, New York, 1984.
  • Demlová, M., Nagy, J., Algebra, STNL, Praha, 1982.
  • 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

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

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