Název:

Diskrétní matematika

Zkratka:IDA
Ak.rok:2005/2006
Semestr:zimní
Studijní plán:
ProgramObor/
specializace
Roč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č.lab. cvič.poč. cvič.jiná
Rozsah:39120410
 zkouškatestycvičenílaboratořeostatní
Body:60010030
Garant:Kovár Martin, doc. RNDr., Ph.D. (UMAT)
Přednášející:Kovár Martin, doc. RNDr., Ph.D. (UMAT)
Švarc Svatopluk, RNDr., CSc. (UMAT)
Cvičící:Fuchs Petr, RNDr., 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í:
 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í:
 
  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.
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.
Kontrolovaná výuka:
  Absolvování cvičení ve stanoveném rozsahu.
Průběžná kontrola studia:
  Účast na cvičeních. Odevzdání domácích úloh.
 

Vaše IPv4 adresa: 54.172.234.236