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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 2 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 19: Linia 19:
  
 
*Indukcja matematyczna i rekurencje
 
*Indukcja matematyczna i rekurencje
*Zliczanie zbiorów i funkcji
+
*Sumy skończone
*Permutacje
 
 
*Współczynniki dwumianowe  
 
*Współczynniki dwumianowe  
*Sumy skończone
+
*Permutacje i podziały
 
*Funkcje tworzące i ich zastosowania
 
*Funkcje tworzące i ich zastosowania
 +
*Metody zliczania
 +
**enumeratory
 +
**zasada włączania-wyłączania
 
*Asymptotyka:  
 
*Asymptotyka:  
**notacja asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>)  
+
**notacja asymptotyczna (<math>O,\Omega, \Theta, o, \omega</math>)  
** twierdzenie o rekursji uniwersalnej  
+
** twierdzenie o rekurencji uniwersalnej  
 
*Elementarna teoria liczb:  
 
*Elementarna teoria liczb:  
**podzielność, NWD, NWW, liczby pierwsze  
+
**podzielność, liczby pierwsze, rozkład na czynniki pierwsze
**algorytm Euklidesa  
+
**NWD i algorytm Euklidesa  
**rozkład na czynniki pierwsze
 
 
*Arytmetyka modularna:  
 
*Arytmetyka modularna:  
**twierdzenie Fermata  
+
**małe twierdzenie Fermata i twierdzenie Eulera  
**twierdzenie Eulera  
 
 
**chińskie twierdzenie o resztach  
 
**chińskie twierdzenie o resztach  
 
**rozwiązywanie równań modularnych
 
**rozwiązywanie równań modularnych
Linia 41: Linia 41:
 
**cykle Eulera i Hamiltona  
 
**cykle Eulera i Hamiltona  
 
**grafy dwudzielne, skojarzenia i twierdzenie Halla  
 
**grafy dwudzielne, skojarzenia i twierdzenie Halla  
**spójność i twierdzenie Mengera
+
**planarność
**sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona
 
**planarność i twierdzenie Kuratowskiego
 
 
**kolorowanie grafów
 
**kolorowanie grafów
  

Aktualna wersja na dzień 14:24, 6 lis 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
  • Sumy skończone
  • Współczynniki dwumianowe
  • Permutacje i podziały
  • Funkcje tworzące i ich zastosowania
  • Metody zliczania
    • enumeratory
    • zasada włączania-wyłączania
  • Asymptotyka:
    • notacja asymptotyczna ()
    • twierdzenie o rekurencji uniwersalnej
  • Elementarna teoria liczb:
    • podzielność, liczby pierwsze, rozkład na czynniki pierwsze
    • NWD i algorytm Euklidesa
  • Arytmetyka modularna:
    • małe twierdzenie Fermata i 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
    • planarność
    • 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.