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

Detail předmětu

Diskrétní matematika

IDA Ak. rok 2018/2019 zimní semestr 7 kreditů

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.

Garant předmětu

Jazyk výuky

česky

Zakončení

zkouška (písemná)

Rozsah

52 hod. přednášky, 20 hod. cvičení, 6 hod. projekty

Bodové hodnocení

60 zkouška, 25 půlsemestrální test, 15 projekty

Zajišťuje ústav

Přednášející

Cvičící

Čejka Rudolf, Ing. (CVT FIT VUT)
Demchenko Hanna, Mgr. (FEKT VUT)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT FEKT VUT)
Kovár Martin, doc. RNDr., Ph.D. (UMAT FEKT VUT)
Rebenda Josef, Mgr., Ph.D. (STI VUT)
Staněk David, Mgr. (FEKT VUT)
Svoboda Zdeněk, RNDr., CSc. (UMAT FEKT VUT)
Vážanová Gabriela V., Mgr. (FEKT VUT)

Aktuální informace

Rozdělení studentů do místností na zkoušku z IDA 11. 1. 2019 od 9.00 do 11.00 je podle účasti na cvičeních:
  • cvičení v úterý - písemka v místnosti Technická 10 aula
  • cvičení  v pondělí a čtvrtek vedená doc. Kovárem Technická 8 - 030
  • cvičení  ve čtvrtek od 9.00, 12.00, 14.00 vedená doc. Hliněnou D105
  • cvičení  ve středu od 15.00 vedená Mgr. Vážanovou D0206
  • cvičení  ve středu od 12.00 vedená doc. Hliněnou a od 17.00 vedená Mgr. Vážanovou E112

P. Veigend, 2019-01-15 20:50: Rozdělení studentů na 1. opravný termín zkoušky IDA 21. 1. 2019 od 12:00 do 14:00. Rozdělení podle přenášejících:
  • Techncká T12 aula zkouší Doc. Kovár
  • D105 zkouší Doc. Hliněná

J. Dytrych, 2019-01-24: Rozdělení studentů na 3. termín z IDA, který se koná ve středu 30. 1. 2019 od 12.00 do 14.00, se řídí podle přednášejících a tedy zkoušejících. V místnostech:

  • Technická 8 T8 030 zkouší Doc. Kovár
  • D105 zkouší Doc. Hliněná.

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í

  • 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.

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.

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í.

Průběžná kontrola studia

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

Kontrolovaná výuka

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

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Popřednáškavýuky T12/2.173 11:0012:50 1BIB Kovár
Popřednáškavýuky D0207 D105 11:0012:50 1BIA 2BIA 2BIB xx Hliněná
Popřednáškavýuky T12/2.173 11:0012:50 2BIA xx Kovár
Popřednáškavýuky D105 11:0012:50 1BIA Hliněná
Popřednáškavýuky T12/2.173 11:0012:50 2BIB xx Kovár
Pozkouška2019-01-21 T12/2.173 12:0013:50 1BIB 1. oprava - Kovár
Pozkouška2019-01-21 D105 12:0013:50 1BIA 2BIA 1. oprava - Hliněná
Pozkouška2019-01-21 T12/2.173 12:0013:50 2BIB 1. oprava - Kovár
Pocvičenívýuky T8/312 13:0014:50 1BIB 2BIA 2BIB xx 30 - 31 Kovár
Útcvičenívýuky T8/312 09:0010:50 1BIB 2BIA 2BIB xx 40 - 41 Staněk
Útpřednáškavýuky T12/2.173 11:0012:50 1BIB 2BIA xx Kovár
Útpřednáškavýuky D105 11:0012:50 1BIA Hliněná
Útpřednáškavýuky T12/2.173 11:0012:50 2BIB xx Kovár
Útpřednáškavýuky D0207 D105 11:0012:50 1BIA 2BIA 2BIB xx Hliněná
Útcvičenívýuky T8/312 15:0016:50 1BIB 2BIA 2BIB xx 32 - 33 Kovár
Útcvičenívýuky T8/312 17:0018:50 1BIB 2BIA 2BIB xx 34 - 35 Kovár
Stcvičenívýuky A218 08:0009:50 2BIA 2BIB xx ostatní aktivity, Hliněná Konzul
Stzkouška2018-12-19 D105 09:0015:50 1BIA 2BIA předtermín
Stzkouška2019-01-30 D105 12:0014:50 1BIA 2BIA 2. oprava Doc. Hliněná
Stzkouška2019-01-30 T8/030 12:0013:50 1BIB 2BIB 2. oprava Doc. Kovár
Stcvičenívýuky A113 12:0013:50 1BIA 2BIA 2BIB xx 14 - 15 Hliněná
Stostatní2019-01-30 A113 14:0017:50hodnocení 2. opravy,doc. Hliněná
Stcvičenívýuky T8/312 15:0016:50 1BIA 2BIA 2BIB xx 10 - 11 Vážanová
Stcvičenívýuky T8/312 17:0018:50 1BIA 2BIA 2BIB xx 12 - 13 Vážanová
Čtcvičenívýuky A113 09:0010:50 1BIA 2BIA 2BIB xx 16 - 17 Hliněná
Čtcvičenívýuky A113 12:0013:50 1BIA 2BIA 2BIB xx 18 - 19 Hliněná
Čtcvičenívýuky A113 14:0015:50 1BIA 2BIA 2BIB xx 20 - 21 Hliněná
Čtcvičenívýuky T8/312 15:0016:50 1BIB 2BIA 2BIB xx 36 - 37 Kovár
Čtcvičenívýuky T8/312 17:0018:50 1BIB 2BIA 2BIB xx 38 - 39 Kovár
zkouška2019-01-11 E112 09:0010:50 1BIA řádná - Hli. st 12:00,Váž. st 17
zkouška2019-01-11 T8/030 09:0010:50 1BIB řádná - cv. po a čt Kovár
zkouška2019-01-11 D0206 09:0010:50 1BIA řádná - Vážanová, st., 15:00
zkouška2019-01-11 D105 09:0010:50 2BIA řádná - Hliněná čt. všechny sk.
zkouška2019-01-11 T10/1.36 09:0010:50 1BIB 2BIB řádná - cv. v úterý
zkouška2019-01-11 D105 09:0010:50 1BIA řádná - Hliněná čt. všechny sk.

Zařazení předmětu ve studijních plánech

  • Program IT-BC-3, obor BIT, 1. ročník, povinný
Nahoru