Název:

Diskrétní matematika

Zkratka:IDA
Ak.rok:2018/2019
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č.lab. cvič.poč. cvič.jiná
Rozsah:5220006
 zkouškatestycvičenílaboratořeostatní
Body:60250015
Garant:Kovár Martin, doc. RNDr., Ph.D. (UMAT)
Přednášející:Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Kovár Martin, doc. RNDr., Ph.D. (UMAT)
Cvičící:Čejka Rudolf, Ing. (CVT)
Demchenko Hanna, Mgr. (FEKT)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Kovár Martin, doc. RNDr., Ph.D. (UMAT)
Rebenda Josef, Mgr., Ph.D. (STI)
Staněk David, Mgr. (FEKT)
Svoboda Zdeněk, RNDr., CSc. (UMAT)
Vážanová Gabriela V., Mgr. (FEKT)
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
Rozvrh:
DenVýukaTýdenMístnostOdDoPSKSk-odSk-do
Popřednáška - KovárvýukyT12/2.17311:0012:501BIB
Popřednáška - KovárvýukyT12/2.17311:0012:502BIAxxxx
Popřednáška - KovárvýukyT12/2.17311:0012:502BIBxxxx
Popřednáška - HliněnávýukyD10511:0012:501BIA
Popřednáška - HliněnávýukyD10511:0012:502BIAxxxx
Popřednáška - HliněnávýukyD10511:0012:502BIBxxxx
Popřednáška - HliněnávýukyD020711:0012:501BIA
Popřednáška - HliněnávýukyD020711:0012:502BIAxxxx
Popřednáška - HliněnávýukyD020711:0012:502BIBxxxx
Pozkouška - 1. oprava2019-01-21T8/01012:0013:501BIB
Pozkouška - 1. oprava2019-01-21T8/01012:0013:502BIB
Pozkouška - 1. oprava2019-01-21D10512:0013:501BIA
Pozkouška - 1. oprava2019-01-21D10512:0013:502BIA
Pozkouška - 1. oprava2019-01-21D020612:0013:501BIA
Pozkouška - 1. oprava2019-01-21D020712:0013:501BIA
Pocvičení - KovárvýukyT8/31213:0014:501BIB3031
Pocvičení - KovárvýukyT8/31213:0014:502BIAxxxx
Pocvičení - KovárvýukyT8/31213:0014:502BIBxxxx
Útcvičení - StaněkvýukyT8/31209:0010:501BIB4041
Útcvičení - StaněkvýukyT8/31209:0010:502BIAxxxx
Útcvičení - StaněkvýukyT8/31209:0010:502BIBxxxx
Útpřednáška - KovárvýukyT12/2.17311:0012:501BIB
Útpřednáška - KovárvýukyT12/2.17311:0012:502BIAxxxx
Útpřednáška - KovárvýukyT12/2.17311:0012:502BIBxxxx
Útpřednáška - HliněnávýukyD10511:0012:501BIA
Útpřednáška - HliněnávýukyD10511:0012:502BIAxxxx
Útpřednáška - HliněnávýukyD10511:0012:502BIBxxxx
Útpřednáška - HliněnávýukyD020711:0012:501BIA
Útpřednáška - HliněnávýukyD020711:0012:502BIAxxxx
Útpřednáška - HliněnávýukyD020711:0012:502BIBxxxx
Útcvičení - KovárvýukyT8/31215:0016:501BIB3233
Útcvičení - KovárvýukyT8/31215:0016:502BIAxxxx
Útcvičení - KovárvýukyT8/31215:0016:502BIBxxxx
Útcvičení - KovárvýukyT8/31217:0018:501BIB3435
Útcvičení - KovárvýukyT8/31217:0018:502BIAxxxx
Útcvičení - KovárvýukyT8/31217:0018:502BIBxxxx
Stcvičení - ostatní aktivity, Hliněná KonzulvýukyA21808:0009:502BIAxxxx
Stcvičení - ostatní aktivity, Hliněná KonzulvýukyA21808:0009:502BIBxxxx
Stzkouška - předtermín2018-12-19D10509:0015:501BIA
Stzkouška - předtermín2018-12-19D10509:0015:502BIA
Stcvičení - HliněnávýukyA11312:0013:501BIA1415
Stcvičení - HliněnávýukyA11312:0013:502BIAxxxx
Stcvičení - HliněnávýukyA11312:0013:502BIBxxxx
Stzkouška - 2. oprava2019-01-30T8/01012:0013:501BIB
Stzkouška - 2. oprava2019-01-30T8/01012:0013:502BIB
Stzkouška - 2. oprava2019-01-30D10512:0013:501BIA
Stzkouška - 2. oprava2019-01-30D10512:0013:502BIA
Stcvičení - VážanovávýukyT8/31215:0016:501BIA1011
Stcvičení - VážanovávýukyT8/31215:0016:502BIAxxxx
Stcvičení - VážanovávýukyT8/31215:0016:502BIBxxxx
Stcvičení - VážanovávýukyT8/31217:0018:501BIA1213
Stcvičení - VážanovávýukyT8/31217:0018:502BIAxxxx
Stcvičení - VážanovávýukyT8/31217:0018:502BIBxxxx
Čtcvičení - HliněnávýukyA11309:0010:501BIA1617
Čtcvičení - HliněnávýukyA11309:0010:502BIAxxxx
Čtcvičení - HliněnávýukyA11309:0010:502BIBxxxx
Čtcvičení - HliněnávýukyA11312:0013:501BIA1819
Čtcvičení - HliněnávýukyA11312:0013:502BIAxxxx
Čtcvičení - HliněnávýukyA11312:0013:502BIBxxxx
Čtcvičení - HliněnávýukyA11314:0015:501BIA2021
Čtcvičení - HliněnávýukyA11314:0015:502BIAxxxx
Čtcvičení - HliněnávýukyA11314:0015:502BIBxxxx
Čtcvičení - KovárvýukyT8/31215:0016:501BIB3637
Čtcvičení - KovárvýukyT8/31215:0016:502BIAxxxx
Čtcvičení - KovárvýukyT8/31215:0016:502BIBxxxx
Čtcvičení - KovárvýukyT8/31217:0018:501BIB3839
Čtcvičení - KovárvýukyT8/31217:0018:502BIAxxxx
Čtcvičení - KovárvýukyT8/31217:0018:502BIBxxxx
zkouška - řádná2019-01-11T12/2.17309:0010:501BIB
zkouška - řádná2019-01-11T12/2.17309:0010:502BIB
zkouška - řádná2019-01-11D10509:0010:501BIA
zkouška - řádná2019-01-11D10509:0010:502BIA
zkouška - řádná2019-01-11D020609:0010:501BIA
zkouška - řádná2019-01-11D020709:0010:501BIA
zkouška - řádná2019-01-11E11209:0010:501BIA
 
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. Syntaxe a sémantika výrokové a predikátové logiky. Věty o úplnosti výrokové a predikátové logiky. Matice a determinanty. Soustavy lineárních rovnic. Vektorové prostory a podprostory. Kvadratické formy a kuželosečky. 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. 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ů a jejich ilustrace.
  2. Binární relace a zobrazení, jejich skládání a vlastnosti. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovské diagramy.
  3. Obecné algebry, algebry s jednou a dvěma operacemi, svazy jako algebry, Booleovy algebry.
  4. Výroková logika. Syntax a sémantika. Formální systém výrokové logiky, úplnost výrokové logiky.
  5. Predikátová logika. Syntax a sémantika. Formální systém predikátové logiky prvního řádu, úplnost predikátové logiky.
  6. Praktické užití výrokové a predikátové logiky v důkazech.
  7. Matice a maticové operace. Soustavy lineárních rovnic. Gaussova eliminace. Frobeniova věta. Determinant čtvercové matice. Inverzní a adjungovaná matice. Metody výpočtu determinantu. Cramerovo pravidlo.
  8. Vektorový prostor a jeho podprostory. Báze a dimenze. Vyjádření vektoru v bázi. Transformace souřadnic. Součet a průnik vektorových prostorů. Lineární zobrazení vektorových prostorů.
  9. Skalární součin. Ortonormální systémy vektorů. Ortogonální průmět vektoru do podprostoru. Aproximace ortogonálním průmětem. Problém vlastních hodnot. Vlastní vektory. Projekce na vlastní podprostory.
  10. Kvadratické formy, kuželosečky.
  11. Grafy a jejich různé reprezentace. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů. Podgrafy. Izomorfismus a homeomorfismus grafů.
  12. Eulerovské a hamiltonovské grafy. Problém rovinnosti. Základní grafové charakteristiky. Stromy, kostry a jejich vlastnosti a algoritmická konstrukce. 
  13. Orientované grafy, toky v sítích, hledání maximálního toku, aplikace.
Osnova numerických cvičení:
 
  • Budou procvičena témata z přednášek ve vhodném rozsahu.
Osnova ostatní - projekty, práce:
 Tři samostatné, strukturované domácí úlohy - bližší informace sdělí vyučující.
Literatura referenční:
 
  • Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
  • Acharjya D. P., Sreekumar, Fundamental Approach to Discrete Mathematics, New Age International Publishers, New Delhi, 2005.
  • Faure R., Heurgon E., Uspořádání a Booloeovy algebry, Academia, Praha 1984.
  • Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
  • Garnier R.,  Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002.
  • Gratzer G., General Lattice Theory, Birkhauser Verlag, Berlin 2003.
  • Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
  • Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
  • 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.
  • Kolman B., Elementary Linear Algebra, Macmillan Publ. Comp., New York 1986.
  • Kolman B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1993.
  • Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
  • Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
  • Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983.
  • Lipschutz, S., Lipson, M.L., Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997.
  • Lovász L., Pelikán J., Vesztergombi, Discrete Mathematics, Springer-Verlag, New York 2003.
  • Mannucci M. A., Yanofsky N. S., Quantum Computing For Computer Scientists, Cambridge University Press, Cambridge 2008.
  • Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • Nahara M., Ohmi T., Qauntum Computing: From Linear Algebra to Physical Realizations, CRC Press, Boca Raton 2008.
  • O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
  • 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.
  • Rosen, K. H. et al., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton 2000.
  • Ross, S. M. Topics in Finite and Discrete Mathematics, Cambridge University Press, Cambridge 2000.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
  • Švejdar, V., Logika, neúplnost, složitost a nutnost, Academia, Praha 2002.
  • Vickers S., Topology via Logic, Cambridge University Press, Cambridge 1990.
Literatura studijní:
 
  • Demlová M., Nagy J., Algebra, SNTL, Praha 1982.
  • Havel, V., Holenda, J., Lineární algebra, STNL, Praha 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.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
  • Peregrin J., Logika a logiky, Academia, Praha 2004.
  • Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
Kontrolovaná výuka:
  Absolvování cvičení ve stanoveném rozsahu.
Průběžná kontrola studia:
  Absolvování cvičení ve stanoveném rozsahu.
 

Vaše IPv4 adresa: 54.196.161.252
Přepnout na IPv6 spojení

DNSSEC [dnssec]