Matematyka dyskretna 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 19: Linia 19:
 
=== Zawartość ===
 
=== Zawartość ===
  
−
*Indukcja matematyczna  
+
*Indukcja matematyczna:
 
**zasada indukcji  
 
**zasada indukcji  
 
**zasady minimum i maksimum  
 
**zasady minimum i maksimum  
 
**liczby harmoniczne
 
**liczby harmoniczne
−
*Rekurencja
+
*Rekurencja:
 
**definicje rekurencyjne
 
**definicje rekurencyjne
 
**zależności rekurencyjne
 
**zależności rekurencyjne
−
**liczby Fibonacci’ego
+
**liczby Fibonacciego
 
**rozwiązywanie równań rekurencyjnych
 
**rozwiązywanie równań rekurencyjnych
−
*Zliczanie zbiorów i funkcji  
+
*Zliczanie zbiorów i funkcji:
 
**zliczanie podzbiorów  
 
**zliczanie podzbiorów  
 
**zliczanie bijekcji  
 
**zliczanie bijekcji  
Linia 35: Linia 35:
 
**zasada szufladkowa Dirichleta  
 
**zasada szufladkowa Dirichleta  
 
**zasada włączania-wyłączania  
 
**zasada włączania-wyłączania  
−
*Sumy skończone i rachunek różnicowy
+
*Sumy skończone i rachunek różnicowy:
 
**metody obliczania sum skończonych
 
**metody obliczania sum skończonych
 
**rachunek różnicowy
 
**rachunek różnicowy
Linia 41: Linia 41:
 
**sumowanie przez części
 
**sumowanie przez części
 
*Współczynniki dwumianowe
 
*Współczynniki dwumianowe
−
*Permutacje i podziały
+
*Permutacje i podziały:
 
**rozkład permutacji na cykle
 
**rozkład permutacji na cykle
 
**cyklowe liczby Stirlinga  
 
**cyklowe liczby Stirlinga  
 
**podziałowe liczby Stirlinga
 
**podziałowe liczby Stirlinga
 
**podziały liczby na sumy
 
**podziały liczby na sumy
−
*Funkcje tworzące  
+
*Funkcje tworzące:
 
**rozwijanie funkcji wymiernych w szereg
 
**rozwijanie funkcji wymiernych w szereg
 
**funkcje tworzące w rozwiązywaniu zależności rekurencyjnych
 
**funkcje tworzące w rozwiązywaniu zależności rekurencyjnych
−
*Funkcje tworzace w zliczaniu obiektów kombinatorycznych  
+
*Funkcje tworzące w zliczaniu obiektów kombinatorycznych:
−
**liczby Catalana  
+
**liczby Catalana
 
**podziały liczby na sumy  
 
**podziały liczby na sumy  
 
**liczby Stirlinga
 
**liczby Stirlinga
 
**liczby Bella
 
**liczby Bella
−
*Asymptotyka  
+
*Asymptotyka:
 
**notacja asymtotyczna <math>O,\Omega, \Theta, o, \omega</math>  
 
**notacja asymtotyczna <math>O,\Omega, \Theta, o, \omega</math>  
 
**twierdzenie o rekursji uniwersalnej  
 
**twierdzenie o rekursji uniwersalnej  
 
**metoda przybliżeń
 
**metoda przybliżeń
−
*Teoria liczb  
+
*Teoria liczb:
 
**podzielność, NWD, NWW, liczby pierwsze  
 
**podzielność, NWD, NWW, liczby pierwsze  
 
**algorytm Euklidesa  
 
**algorytm Euklidesa  
 
**rozkład na czynniki pierwsze  
 
**rozkład na czynniki pierwsze  
 
**gęstość liczb pierwszych
 
**gęstość liczb pierwszych
−
*Arytmetyka modularna  
+
*Arytmetyka modularna:
 
**twierdzenie Fermata  
 
**twierdzenie Fermata  
 
**twierdzenie Eulera
 
**twierdzenie Eulera
Linia 69: Linia 69:
 
**rozwiązywanie równań modularnych
 
**rozwiązywanie równań modularnych
 
**funkcja Mobiusa
 
**funkcja Mobiusa
−
*Grafy  
+
*Grafy:
 
**podstawowe pojęcia  
 
**podstawowe pojęcia  
 
**drzewa i cykle  
 
**drzewa i cykle  
 
**cykle Eulera i Hamiltona  
 
**cykle Eulera i Hamiltona  
−
**grafy dwudzielne, skojarzenia i tw. Halla
+
**grafy dwudzielne, skojarzenia i twierdzenie Halla
−
**spójność, wielospójność i tw. Mengera
+
**spójność, wielospójność i twierdzenie Mengera
−
**sieci, przepływy, przekroje i tw. Forda-Fulkersona
+
**sieci, przepływy, przekroje i twierdzenie Forda-Fulkersona
−
**planarność i tw. Kuratowskiego
+
**planarność i twierdzenie Kuratowskiego
 
**kolorowanie grafów (w tym planarnych)  
 
**kolorowanie grafów (w tym planarnych)  
−
*Metody algebraiczne w teorii grafów  
+
*Metody algebraiczne w teorii grafów:
 
**macierz sąsiedztwa i domkniecie przechodnie grafu
 
**macierz sąsiedztwa i domkniecie przechodnie grafu
 
**macierz incydencji
 
**macierz incydencji
 
**permanent i skojarzenia
 
**permanent i skojarzenia
−
**wartosci własne
+
**wartości własne
  
 
=== Literatura ===
 
=== Literatura ===

Wersja z 19:18, 26 wrz 2006

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

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
    • 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

  1. V.Bryant, Aspekty kombinatoryki, WNT 1977
  2. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, PWN 1996
  3. W.Lipski, Kombinatoryka dla programistów, WMT 2004
  4. W.Lipski, W.Marek, Analiza kombinatoryczna, PWN 1986
  5. K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, PWN 1996
  6. Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, WNT 1998
  7. R.J.Wilson, Wprowadzenie do teorii grafów, PWN 1985

Moduły

  1. Indukcja (ćwiczenia) (test)
  2. Rekurencja (ćwiczenia) (test)
  3. Zliczanie zbiorów i funkcji (ćwiczenia) (test)
  4. Sumy skończone i rachunek różnicowy (ćwiczenia) (test)
  5. Współczynniki dwumianowe (ćwiczenia) (test)
  6. Permutacje i podziały (ćwiczenia) (test)
  7. Funkcje tworzące (ćwiczenia) (test)
  8. Funkcje tworzące w zliczaniu obiektów kombinatorycznych (ćwiczenia) (test)
  9. Asymptotyka (ćwiczenia) (test)
  10. Teoria liczb (ćwiczenia) (test)
  11. Teoria liczb II (ćwiczenia) (test)
  12. Grafy (ćwiczenia) (test)
  13. Grafy II (ćwiczenia) (test)
  14. Grafy III (ćwiczenia) (test)
  15. Metody algebraiczne w teorii grafów (ćwiczenia) (test)

Literatura uzupełniająca

  1. N.L.Biggs, Discrete Mathematics, Oxford University Press 1989
  2. B.Bollobas, Modern Graph Theory, Springer 1998
  3. Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein,Wprowadzenie do algorytmów, WNT, 2004.
  4. R.Diestel, Graph Theory, Springer 1997
  5. G.Polya, R.E.Tarjan, D.R.Woods, Notes on Introductory Combinatorics, Birkhauser 1983
  6. J.Riordan, An Introduction to Combinatorial Analysis, Princeton University Press 1978
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1&oldid=56903”