Badania operacyjne

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. Arytmatyka 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. Filipowicz B.: Modele stochastyczne w badaniach operacyjnych. Analiza i synteza systemów obsługi i sieci kolejkowych”. Wydawnictwo Naukowo-Techniczne, Warszawa 1996
2. Filipowicz B.: Modelowanie i optymalizacja systemów kolejkowych. cz. 1. Systemy markowskie. Wyd. Poldex, Kraków 2006
3. Filipowicz B.: Modelowanie i optymalizacja systemów kolejkowych. cz. 2. Systemy niemarkowskie. Wyd. Poldex, Kraków 2000
4. Filipowicz B., Idzikowska K.: Systemy i sieci kolejkowe w przykładach 5 i zadaniach, Wydawnictwo ABART, Kraków 2008
5. Filipowicz B.: Matematyczne modelowanie zagadnie´n decyzyjnych . cz. 1, Wydawnictwa AGH, Kraków 1998,

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