Diskrétna matematika

2013/14 -- Zimný semester

Prednášajúci

Konzultačné hodiny : len cez semester

Počas semestra poslucháči absolvujú jeden 30-bodový test. Zápočet získa len ten poslucháč, ktorého celkové bodové skóre (test + prípadné extra body) bude minimálne 15 bodov.

Účasť na teste je povinná. V prípade neúčasti je potrebné sa ospravedlniť (potvrdenie od lekára - PN odovzdané na dekanáte) do piatich dní odo dňa konania testu.

množiny, základné operácie na množinách, matematická indukcia
relácie (na množine), základné vlastnosti (reflexívnosť, symetričnosť, antisymetričnosť, tranzitívnosť),
zobrazenie (injektívne, surjektívne, bijektívne)
ekvivalencie a rozklady
(binárne) operácie na množine, asociatívnosť, komutatívnosť, jednotkový prvok, Cayleyho tabuľky
posety, diagramy posetov
zväzy, podzväzy, distributivita, modularita
morfizmy a kongruencie zväzov
grupy, podgrupy, kosety
morfizmy grúp, kongruencie grúp, normálne podgrupy, faktorové grupy
grupy permutácií
grafy, diagram grafu, izomorfizmus grafov
základné triedy grafov (stromy, lesy)
(uzavreté) sledy, ťahy, cesty
súvislosť grafov, komponenty grafu
Eulerovské grafy, algoritmus na nájdenie Eulerovského ťahu
rovinné grafy, Kuratowského veta, Eulerov vzorec
grafové algoritmy, prehľadávanie grafu do hĺbky a do šírky,
ohodnotené grafy, minimálna kostra, nájdenie najkratšej cesty

Iné materiály.

Úvod. Množiny, relácie, operácie na množinách, zobrazenia, matematická indukcia.
Relácie ekvivalencie a čiastočné usporiadania.
Pologrupy, grupy, podalgebry, homomorfizmy a ich vlastnosti.
Zväzy, podzväzy, distributívne a modulárne zväzy.
Kongruencie na zväzoch a faktorové zväzy.
Úvodné pojmy z teórie grafov a základné triedy grafov.
Stromy a kostry grafu. Algoritmy na nájdenie kostry a najlacnejšej kostry grafu.
Algoritmy na nájdenie najkratšej cesty v grafe a v ohodnotenom grafe.

Zlatoš, P.: Lineárna algebra a geometria. Marenčin PT, Bratislava 2011.
Kolář, J., Štěpánková, O., Chytil, M.: Logika algebry a grafy. SNTL, ALFA, Praha 1989.
Demel, J.: Grafy. SNTL, Praha 1989.
Galanová, J., Kaprálik, P. : Diskrétna matematika, skriptá, STU Bratislava, 1997 Časť o grafoch Časť o množinách
Johnsonbaugh, R.: Discrete Mathematics, Macmillan Publishing Company, New York,1992.