Název:

Diskrétní matematika

Zkratka:IDA
Ak.rok:2017/2018
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-BC-3BIT1.povinný
Vyučovací jazyk:čeština
Aktuální informace:Rozpis cvičení pro skupinu doc. Hliněné

J. Dytrych, 2018-01-10: RNDr. Svoboda zaslal rozdělení do místností na 1. termín zkoušky:
BIA - rozpis na stránkách doc. Hliněné - Platí jenom pro studenty, kteří navštěvují cvičení doc. Hliněné a cvičení Mgr. Staňka. Řádný termín: čtvrtek 11.1.2018 od 9:00 v místnostech D105, D0206 a E112.  Rozdělení do místností je podle cvičení:
  • Studenti, kteří navštěvují cvičení doc. Hliněné (úterý od 13:00, pátek od 9:00 a od 11:00), budou psát v místnosti D105.
  • Studenti, kteří navštěvují cvičení ve středu od 11:00 (Mgr. Staněk), budou v místnosti E112.
  • Studenti, kteří navštěvují cvičení ve středu od 15:00 (Mgr. Staněk), budou v místnosti D0206.
  • Studenti, kteří navštěvují cvičení ve středu od 17:00 (Mgr. Staněk), budou rozděleni podle abecedy takto: Od Alexaj Adam po Kocurek Pavel (včetně), budou v místnosti E112. Od Koleček František po Ševčík Pavel (včetně), budou v místnosti D0206.
BIB (platí pro studenty, kteří nepatří do BIA dle rozpisu výše):
  • Technická 12 aula studenti jejichž příjmení začíná na A-O
  • Technická 8 - 010 studenti jejichž příjmení začíná na P-Š
  • Technická 8 - 030 studenti jejichž příjmení začíná na T-Ž.

J. Dytrych, 2018-01-18 22:08: RNDr. Svoboda zaslal rozdělení do místností na 2. termín zkoušky podle přednáškové skupiny:

  • Technická 8 posluchárna 30 přednášková skupina BIB doc. Kovár
  • Božetěchova posluchárna D105 přednášková skupina BIA doc. Hliněná.

Začátek je zítra tj. 19. 1. 2018 v 11.15 (do 11.00 je posluchárna na Technické 8 obsazena). Prosím o zveřejnění studentům. Děkuji a omlouvám se za pozdní mail.

J. Dytrych, 2018-01-28: RNDr. Svoboda zaslal rozdělení do místností na 3. termín zkoušky podle přednáškové skupiny:

  • Technická 8 posluchárna 10 přednášková skupina BIB doc. Kovár
  • Božetěchova posluchárna D105 přednášková skupina BIA doc. Hliněná.

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:52120410
 zkouškatestycvičenílaboratořeostatní
Body:60010030
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í: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
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. 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í. Skládání relací a zobrazení. Vlastnosti zobrazení. Indexované systémy množin a jejich zobrazení. Abstraktní prostory. Reálné funkce a jejich vlastnosti. Spojitost a nespojitost. Rekurzívně definované funkce.
  3. Další vlastnosti binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovské 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. Dualita a 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í:
 
  • 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.156.37.174
Přepnout na IPv6 spojení

DNSSEC [dnssec]