Název: Úvod do lineární algebry a diskrétní matematiky Zkratka: ZDM Typ: povinný Rozsah: 14 týdnů, týdně 3 hodiny přednášek + 2 hodiny seminárních cvičení Kredity: 6 Způsob ukončení: zkouška Katedra: katedra aplikované matematiky FP TUL Přednášející: RNDr. Miroslav Koucký, CSc.
Stručná anotace předmětu:Předmět seznamuje studenty se základy lineární algebry a diskrétní matematiky. Lineární algebra zahrnuje úvod do problematiky vektorových prostorů, základy maticového počtu a jeho aplikace. Diskrétní matematika zahrnuje elementární úvod do teorie množin a relací, klasickou kombinatoriku, booleovské funkce, základy matematické logiky a základy teorie grafů.
Témata přednášek:Pojem množiny, množinové operace (sjednocení, průnik, rozdíl, kartézský součin). Binární relace, zejména ekvivalence a uspořádání. Zobrazení.
Kombinace, variace, permutace (bez opakování i s opakováním), subfaktoriály a jejich vlastnosti. Základní kombinatorická pravidla, princip inkluze a exkluze. Kombinatorika rozkladů. Kombinatorika na šachovnici. Lineární rekurentní vztahy (homogenní i nehomogenní) a jejich řešení. Vytvořující funkce a jejich aplikace v kombinatorice.
Pojem vektorový prostor, lineární (ne)závislost vektorů. Matice, základní operace. Soustavy lineárních algebraických rovnic, věta o řešitelnosti. Gaussova eliminační metoda. Inverzní matice, její souvislost s řešením soustavy. Determinanty a jejich aplikace při řešení soustav lineárních rovnic a v geometrii. Vlastní čísla a vlastní vektory matic. Formulace úlohy lineárního programování. Základní informace o simplexové metodě.
Základy výrokové logiky. Booleovy algebry a booleovské funkce. Disjunktivní a konjunktivní normální forma. Minimalizace booleovských funkcí (Karnaughovy mapy, Quine-McCluskeyův algoritmus). Základy predikátové logiky. Reléové sítě.
Pojem graf – orientovaný, neorientovaný. Reprezentace grafu a s tím související datové struktury. Sled, tah, cesta, kružnice. Vzdálenosti v grafu, poloměr a průměr grafu. Souvislost grafu, stromy, kostra grafu. Základní pojmy teorie orientovaných grafů. Čínský problém listonoše, toky v sítích, síťová analýza, Borůvkův problém minimální kostry. Rovinné grafy, Kuratowského věta.
Náplň cvičení:Procvičuje se látka vyložená na předchozích přednáškách. Důraz je kladen na schopnost samostatné aplikace získaných poznatků při řešení různých typů úloh.
Literatura:Vild J., Šedý J.: Matematika II (Algoritmy a logika). Liberec, VŠST 1978.
Kolář J., Štěpánková D., Chytil M.: Logika, algebra a grafy. Praha, SNTL 1959.
Kučera L.: Kombinatorické algoritmy. Praha, SNTL, 1989
Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky. Praha, Karolinum, 2000.
Prerekvizity: -Navazující: -
Datum poslední změny: 11.10.2001