Projekt wykładu

Matematyka dyskretna z zastosowaniami

1. Podstawy teorii grafów, grafy skierowane i nieskierowane, przeszukiwanie grafu wszerz i wgłąb, przykłady problemów modelowanych za pomocą grafów.
2. Ścieżki Eulera, warunki istnienia ścieżki Eulera, konstrukcja ścieżki Eulera, problem chińskiego listonosza, zastosowania w kodowaniu i biologii.
3. Cykle Hamiltona, warunki istnienia cyklu i drogi Hamiltona, problem komiwojażera.
4. Kolorowania krawędzi i wierzchołków grafów, liczba i indeks chromatyczny, kolorowanie grafów płaskich, zastosowania kolorowań.
5. Systemy różnych reprezentantów, skojarzenia, pokrycia, twierdzenie Halla, zastosowania systemów różnych reprezentantów.
6. Złożoność obliczeniowa problemów decyzyjnych, redukcje wielomianowe, problemy wielomianowe, NP-zupełne, hipoteza P¹NP.
7. Zbiory uporządkowane, rozkłady na łańcuchy i antyłańcuchy, twierdzenie Dilwortha, zastosowania w planowaniu zadań.
8. Równania rekurencyjne, metoda pierwiastków charakterystycznych.
9. Funkcje tworzące i ich wykorzystanie do rozwiązywania równań rekurencyjnych.
10. Równania rekurencyjne z konwolucjami, równania typu "dziel i zdobywaj".
11. Ciała skończone, własności ciał skończonych, konstrukcje ciał skończonych.
12. Konfiguracje kombinatoryczne, kwadraty łacińskie, systemy trójek Steinera, nierówność Fishera, konfiguracje kwadratowe.
13. Geometrie skończone, zastosowania konfiguracji kombinatorycznych do planowania eksperymentów.
14. Matematyczne podstawy systemu kryptograficznego z kluczem jawnym RSA.

Bibliografia

1. F. S. Roberts, Applied Combinatorics, Prentice-Hall, Englewood Cliffs 1984.
2. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, WNT Warszawa 2002.

prof. dr hab. Zbigniew Lonc

Wydział Matematyki i Nauk Informacyjnych

Politechnika Warszawska

Warszawa, 26 maja 2003 r.