Název:

Diskrétní matematika

Zkratka:IDA
Ak.rok:2008/2009
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-BC-3BIT1.povinný
Vyučovací jazyk:čeština
Kredity:7 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:39120410
 zkouškatestycvičenílaboratořeostatní
Body:60010030
Garant:Kovár Martin, doc. RNDr., Ph.D., UMAT
Přednášející:Durnová Helena, Mgr., Ph.D., UMAT
Kovár Martin, doc. RNDr., Ph.D., UMAT
Cvičící:Durnová Helena, Mgr., Ph.D., UMAT
Fakulta:Fakulta elektrotechniky a komunikačních technologií VUT v Brně
Pracoviště:Ústav matematiky FEKT VUT v Brně
Navazující:
Algoritmy (IAL), UIFS
Formální jazyky a překladače (IFJ), UIFS
Matematická analýza (IMA), UMAT
Modelování a simulace (IMS), UITS
Numerická matematika a pravděpodobnost (INM), UMAT
Základy počítačové grafiky (IZG), UPGM
 
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.
Anotace:
  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.
Požadované prerekvizitní znalosti a dovednosti:
  Středoškolská matematika.
Získané dovednosti, znalosti a kompetence:
  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.
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í:
 
  1. 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í.
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.
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.
Kontrolovaná výuka:
  Absolvování cvičení ve stanoveném rozsahu.
Průběžná kontrola studia:
  Absolvování cvičení ve stanoveném rozsahu.