MIMINF:Matematyka dyskretna: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania| Linia 19: | Linia 19: | ||
*Indukcja matematyczna i rekurencje | *Indukcja matematyczna i rekurencje | ||
| − | |||
*Permutacje | *Permutacje | ||
*Współczynniki dwumianowe | *Współczynniki dwumianowe | ||
*Sumy skończone | *Sumy skończone | ||
*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 asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>) | ||
| − | ** twierdzenie o | + | ** twierdzenie o rekurencji uniwersalnej |
*Elementarna teoria liczb: | *Elementarna teoria liczb: | ||
| − | **podzielność, | + | **podzielność, liczby pierwsze, rozkład na czynniki pierwsze |
| − | **algorytm Euklidesa | + | **NWD i algorytm Euklidesa |
| − | |||
*Arytmetyka modularna: | *Arytmetyka modularna: | ||
| − | **twierdzenie Fermata | + | **małe twierdzenie Fermata i 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 | ||
| − | + | **planarność | |
| − | |||
| − | **planarność | ||
**kolorowanie grafów | **kolorowanie grafów | ||
Wersja z 13:34, 19 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
- Permutacje
- Współczynniki dwumianowe
- Sumy skończone
- Funkcje tworzące i ich zastosowania
- Metody zliczania
- enumeratory
- zasada włączania-wyłączania
- Asymptotyka:
- notacja asymtotyczna ()
- 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
- 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.
- R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985.
