Matematyka Dyskretna

RSS

Cel przedmiotu

Nabycie umiejętności wykorzystywania niektórych działów matematyki do rozwiązywania zagadnień informatycznych. Zaznajomienie z metodami dowodzenia twierdzeń. Zapoznanie z metodami algebry, kombinatoryki, teorii grafów i teorii liczb do rozwiązywania problemów o charakterze informatycznych.

Program wykładu

Ciągi rekurencyjne (metoda rozwiązywania dla ciągów liniowych o stałych współczynnikach, ciąg Fibonacciego). Kombinatoryka: podstawowe metody zliczania (metoda podwójnego zliczania, metody algebraiczne), liczby Stirlnga, Zasada Sita, Zasada Gołębnika, tw. Cantora. Arytmetyka modularna. Algorytm Euklidesa znajdowania NWD. Grupy. Grupy Z i Z *. Grupa permutacji. Twierdzenie Cayleya. Działanie grupy na zbiorze – Lemat Burnside’a. Chińskie twierdzenie o resztach. Twierdzenia Lagrange’a, Małe Fermata i Eulera. Zastosowanie w szyfrowaniu z kodem publicznym (metody Rabina i RSA).Teoria grafów. Grafy Eulera, algorytm Fleury’ego. Bryły platońskie. Twierdzenie Kuratowskiego. Kolorowanie grafów - twierdzenia Brooksa, Heawood, o 4 kolorach (informacyjnie) i Vizinga. Drzewa. Odległość w grafie. Tw. Koeniga. Drzewa binarne – zastosowanie w opisie i optymalizacji algorytmów. Przeszukiwania w grafach. Dendryty. Dendryty minimalne – algorytmy Kruskala i Prima. Turnieje. Przepływy w sieciach.

Charakterystyka pozostałych zajęć

Podczas ćwiczeń rozwiązywane są zadania ilustrujące i uzupełniające wykłady. Celem ćwiczeń jest ułatwienie zrozumienia i opanowania materiału zrealizowanego podczas wykładów.

Bibliografia

1. W.J Gilbert, W.K. Nicholson, Algebra współczesna z zastosowaniami, WNT, Warszawa 2008.
2. N. Koblitz, Algebraiczne aspekty kryptografii, WNT, Warszawa 2000
3. Zb. Palka i A. Ruciński, Wykłady z kombinatoryki, WNT 2004.
4. K.A Ross i Ch.R.B. Wright, Matematyka dyskretna, PWN 2000.
5. R.J. Wilson, Wprowadzenie do teorii grafów, PWN 1998.

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards