Název:

Diskrétní matematika

Zkratka:IDA
Ak.rok:2004/2005
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-BC-3BIT1.povinný
Vyučovací jazyk:čeština, anglič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:39100412
 zkouškatestycvičenílaboratořeostatní
Body:60010030
Garant:Krupková Vlasta, RNDr., CSc., UMAT
Přednášející:Havel Václav, prof. RNDr., DrSc., UMAT
Krupková Vlasta, RNDr., CSc., UMAT
Švarc Svatopluk, RNDr., CSc., 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 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.
Získané dovednosti, znalosti a kompetence:
  Studenti získají elementární znalosti z diskrétní matematiky 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é. Hasseovy 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 Booleových algeber. Množinová reprezentace konečných Booleových algeber.
  6. 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í.
  7. Algebra komplexních čísel. 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:
 Bližší informace sdělí vyučující numerických cvičení.

Literatura referenční:
 
  • Faure, R., Heurgon, E., Stuctures ordonnées et algebres de Boole, Gauthier-Villars, Paris, 1971.
  • Gantmacher, F.R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
  • Havel, V., Holenda, J., Lineární algebra, STNL, Praha, 1984.
  • Hellerstein, N.S., Diamond, A., Paradox Logic, World Scientific, Singapore, 1996.
  • 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., 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 1991.
  • Kučera,  L., Kombinatorické algoritmy, SNTL, Praha 1983.
  • Lipschutz, S., 3000 Solved Problems in Linear Algebra, McGraw-Hill, New York, 1989.
  • Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGraw-Hill, New York, 1992.
  • Manna, Z., Matematická teorie programů, SNTL, Praha 1981.
  • Novák, V., Fuzzy množiny a jejich aplikace, SNTL, Praha 1986.
  • 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.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
  • Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum).
  • Vickers, S., Topology Via Logic, Cambridge University Press, Cambridge, 1989.
Literatura studijní:
 
  • 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.
  • 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., 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, 1991.
  • Lipschutz, S., 3000 Solved Problems in Linear Algebra, McGraw-Hill, New York, 1989.
  • 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).
Kontrolovaná výuka:
  Absolvování počítačových cvičení ve stanoveném rozsahu a odevzdání domácích úloh/projektů.
Průběžná kontrola studia:
  Aktivní účast na počítačových cvičeních a vypracování a odevzdání domácích úloh/projektů ve stanoveném rozsahu a ve stanovených termínech.