Opis
Wykład wprowadza aparat matematyczny niezbędny do konstruowania i analizy algorytmów. Składa się z elementów kombinatoryki, teorii grafów i teorii liczb.
Sylabus
Autorzy
- Paweł Idziak — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
- Bartłomiej Bosek — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
- Piotr Micek — Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
Wymagania wstępne
- Logika i teoria mnogości
- Algebra liniowa z geometrią analityczną
- Analiza matematyczna 1
Zawartość
- Indukcja matematyczna:
- zasada indukcji
- zasady minimum i maksimum
- liczby harmoniczne
- Rekurencja:
- definicje rekurencyjne
- zależności rekurencyjne
- liczby Fibonacciego
- rozwiązywanie równań rekurencyjnych
- Zliczanie zbiorów i funkcji:
- zliczanie podzbiorów
- zliczanie bijekcji
- zliczanie injekcji
- zliczanie funkcji
- zasada szufladkowa Dirichleta
- zasada włączania-wyłączania
- Sumy skończone i rachunek różnicowy:
- metody obliczania sum skończonych
- rachunek różnicowy
- dolna i górna silnia
- sumowanie przez części
- Współczynniki dwumianowe
- Permutacje i podziały:
- rozkład permutacji na cykle
- cyklowe liczby Stirlinga
- podziałowe liczby Stirlinga
- podziały liczby na sumy
- Funkcje tworzące:
- rozwijanie funkcji wymiernych w szereg
- funkcje tworzące w rozwiązywaniu zależności rekurencyjnych
- Funkcje tworzące w zliczaniu obiektów kombinatorycznych:
- liczby Catalana
- podziały liczby na sumy
- liczby Stirlinga
- liczby Bella
- Asymptotyka:
- notacja asymtotyczna \( O,\Omega, \Theta, o, \omega \)
- twierdzenie o rekursji uniwersalnej
- metoda przybliżeń
- Teoria liczb:
- podzielność, NWD, NWW, liczby pierwsze
- algorytm Euklidesa
- rozkład na czynniki pierwsze
- gęstość liczb pierwszych
- Arytmetyka modularna:
- twierdzenie Fermata
- twierdzenie Eulera
- chińskie twierdzenie o resztach
- rozwiązywanie równań modularnych
- funkcja Mobiusa
- Grafy:
- podstawowe pojęcia
- drzewa i cykle
- cykle Eulera i Hamiltona
- grafy dwudzielne, skojarzenia i twierdzenie Halla
- spójność, wielospójność i twierdzenie Mengera
- sieci, przepływy, przekroje i twierdzenie Forda-Fulkersona
- planarność i twierdzenie Kuratowskiego
- kolorowanie grafów (w tym planarnych)
- Metody algebraiczne w teorii grafów:
- macierz sąsiedztwa i domkniecie przechodnie grafu
- macierz incydencji
- permanent i skojarzenia
- wartości własne
Literatura
- V.Bryant, Aspekty kombinatoryki, Wydawnictwa Naukowo-Techniczne 1977.
- R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
- W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.
- W.Lipski, W.Marek, Analiza kombinatoryczna, Państwowe Wydawnictwo Naukowe, Warszawa 1986.
- K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
- Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
- R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985.
Moduły