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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Gracja (dyskusja | edycje)
4759 edycji
Gracja (dyskusja | edycje)
4759 edycji
Linia 66: Linia 66:
== Moduły ==
== Moduły ==


# [[MD Moduł 1|tytuł]] ([[MD Ćwiczenia 1|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 1:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 1:|ćwiczenia]])
# [[MD Moduł 2|tytuł]] ([[MD Ćwiczenia 2|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 2:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 2:|ćwiczenia]])
# [[MD Moduł 3|tytuł]] ([[MD Ćwiczenia 3|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 3:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 3:|ćwiczenia]])
# [[MD Moduł 4|tytuł]] ([[MD Ćwiczenia 4|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 4:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 4:|ćwiczenia]])
# [[MD Moduł 5|tytuł]] ([[MD Ćwiczenia 5|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 5:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 5:|ćwiczenia]])
# [[MD Moduł 6|tytuł]] ([[MD Ćwiczenia 6|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 6:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 6:|ćwiczenia]])
# [[MD Moduł 7|tytuł]] ([[MD Ćwiczenia 7|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 7:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 7:|ćwiczenia]])
# [[MD Moduł 8|tytuł]] ([[MD Ćwiczenia 8|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 8:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 8:|ćwiczenia]])
# [[MD Moduł 9|tytuł]] ([[MD Ćwiczenia 9|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 9:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 9:|ćwiczenia]])
# [[MD Moduł 10|tytuł]] ([[MD Ćwiczenia 10|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 10:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 10:|ćwiczenia]])
# [[MD Moduł 11|tytuł]] ([[MD Ćwiczenia 11|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 11:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 11:|ćwiczenia]])
# [[MD Moduł 12|tytuł]] ([[MD Ćwiczenia 12|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 12:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 12:|ćwiczenia]])
# [[MD Moduł 13|tytuł]] ([[MD Ćwiczenia 13|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 13:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 13:|ćwiczenia]])
# [[MD Moduł 14|tytuł]] ([[MD Ćwiczenia 14|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 14:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 14:|ćwiczenia]])
# [[MD Moduł 15|tytuł]] ([[MD Ćwiczenia 15|ćwiczenia]])
# [[Matematyka dyskretna/Wykład 15:|tytuł]] ([[Matematyka dyskretna/Ćwiczenia 15:|ćwiczenia]])


== Literatura uzupełniająca ==
== Literatura uzupełniająca ==

Wersja z 13:36, 6 sie 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
  • Bartłomiej Bosek
  • Piotr Micek

Wymagania wstępne

  • Logika i teoria mnogości

Zawartość

  • Indukcja matematyczna
    • zasada indukcji
    • zasady minimum i maksimum
    • zależności rekurencujne
  • Sumy skończone
  • Zliczanie zbiorów i funkcji
    • zliczanie podzbiorów
    • zliczanie bijekcji
    • zliczanie injekcji
    • zliczanie funkcji
    • współczynniki dwumianowe
  • Permutacje i liczby Stirlinga
  • Funkcje tworzące
  • Zliczanie obiektów kombinatorycznych
    • zasada szufladkowa Dirichleta
    • zasada włączania-wyłączania
    • liczby Catalana
    • podziały liczby na sumy
  • Asymptotyka
    • notacja O,Ω,Θ,o,ω
    • twierdzenie o rekursji uniwersalnej
  • Grafy
    • podstawowe pojęcia
    • drzewa i cykle
    • cykle Eulera i Hamiltona
    • spójność (i tw. Mengera)
    • dwudzielność (i tw. Halla)
    • planarność (i tw. Kuratowskiego)
    • sieci i przepływy
  • Kolorowania grafów (w tym planarnych)
  • Metody algebraiczne w teorii grafów
  • Teoria liczb
    • NWD, NWW, liczby pierwsze
    • algorytm Euklidesa
    • rozkład na czynniki pierwsze
  • Arytmetyka modularna
    • twierdzenie Fermata
    • chińskie twierdzenie o resztach

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. tytuł (ćwiczenia)
  2. tytuł (ćwiczenia)
  3. tytuł (ćwiczenia)
  4. tytuł (ćwiczenia)
  5. tytuł (ćwiczenia)
  6. tytuł (ćwiczenia)
  7. tytuł (ćwiczenia)
  8. tytuł (ćwiczenia)
  9. tytuł (ćwiczenia)
  10. tytuł (ćwiczenia)
  11. tytuł (ćwiczenia)
  12. tytuł (ćwiczenia)
  13. tytuł (ćwiczenia)
  14. tytuł (ćwiczenia)
  15. tytuł (ćwiczenia)

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=9944”