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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
następna edycja →
WizualnieWikikod
Diks (dyskusja | edycje)
538 edycji
Nie podano opisu zmian
 
Diks (dyskusja | edycje)
538 edycji
Linia 24: Linia 24:
*Sumy skończone
*Sumy skończone
*Funkcje tworzące i ich zastosowania
*Funkcje tworzące i ich zastosowania
*Asymptotyka: notacja asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>), twierdzenie o rekursji uniwersalnej  
*Asymptotyka:  
*Elementarna teoria liczb: podzielność, NWD, NWW, liczby pierwsze, algorytm Euklidesa, rozkład na czynniki pierwsze  
**notacja asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>)  
*Arytmetyka modularna: twierdzenie Fermata, twierdzenie Eulera, chińskie twierdzenie o resztach, rozwiązywanie równań modularnych
** twierdzenie o rekursji uniwersalnej  
*Elementarna teoria liczb:  
**podzielność, NWD, NWW, liczby pierwsze  
**algorytm Euklidesa  
**rozkład na czynniki pierwsze  
*Arytmetyka modularna:  
**twierdzenie Fermata  
**twierdzenie Eulera  
**chińskie twierdzenie o resztach  
**rozwiązywanie równań modularnych
*Elementy kryptografii: test Millera-Rabina i system RSA
*Elementy kryptografii: test Millera-Rabina i system RSA
*Grafy: ścieżki, drzewa i cykle; cykle Eulera i Hamiltona; grafy dwudzielne, skojarzenia i twierdzenie Halla; spójność, wielospójność i twierdzenie Mengera;
*Grafy:  
sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona; planarność i twierdzenie Kuratowskiego; kolorowanie grafów (w tym planarnych)
**ścieżki, drzewa i cykle  
 
**cykle Eulera i Hamiltona  
**grafy dwudzielne, skojarzenia i twierdzenie Halla  
**spójność i twierdzenie Mengera  
**sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona  
**planarność i twierdzenie Kuratowskiego  
**kolorowanie grafów


=== Literatura ===
=== Literatura ===

Wersja z 08:52, 17 paź 2006

Forma zajęć

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

Opis

Aparat matematyczny niezbędny do układania i analizy algorytmów: elementy kombinatoryki, teorii grafów i teorii liczb.

Sylabus

Autorzy

  • Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki
  • Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

Wymagania wstępne

  • Podstawy matematyki
  • Geometria z algebrą liniową
  • Analiza matematyczna 1

Zawartość

  • Indukcja matematyczna i rekurencje
  • Zliczanie zbiorów i funkcji
  • Permutacje
  • Współczynniki dwumianowe
  • Sumy skończone
  • Funkcje tworzące i ich zastosowania
  • Asymptotyka:
    • notacja asymtotyczna (O,Ω,Θ,o,ω)
    • twierdzenie o rekursji uniwersalnej
  • Elementarna teoria liczb:
    • podzielność, NWD, NWW, liczby pierwsze
    • algorytm Euklidesa
    • rozkład na czynniki pierwsze
  • Arytmetyka modularna:
    • twierdzenie Fermata
    • twierdzenie Eulera
    • chińskie twierdzenie o resztach
    • rozwiązywanie równań modularnych
  • Elementy kryptografii: test Millera-Rabina i system RSA
  • Grafy:
    • ścieżki, drzewa i cykle
    • cykle Eulera i Hamiltona
    • grafy dwudzielne, skojarzenia i twierdzenie Halla
    • spójność i twierdzenie Mengera
    • sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona
    • planarność i twierdzenie Kuratowskiego
    • kolorowanie grafów

Literatura

  1. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
  2. W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.
  3. R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=MIMINF:Matematyka_dyskretna&oldid=63841”