Strona główna

Matematyka dyskretna


Pobieranie 6.09 Kb.
Data18.06.2016
Rozmiar6.09 Kb.

MATEMATYKA DYSKRETNA

Kod: Symbol:

ECTS: 4 punkty.

Wymagania: Wiedza z zakresu szkoły średniej

Czas trwania: jeden semestr, 30 w. + 30 konw.
Program wykładu


  1. Liczby naturalne, indukcja

  2. Definicje i równania rekurencyjne

  3. Liczby pierwsze, postać kanoniczna liczby naturalnej, funkcja Eulera, małe twierdzenie Fermata, twierdzenie chińskie o resztach

  4. Twierdzenie o dzieleniu z resztą, algorytm Euklidesa, relacja podzielności, NWD, NWW

  5. Asymptotyka funkcji liczbowych

  6. Zliczanie i generowanie obiektów kombinatorycznych

  7. Tożsamości dla współczynników dwumianowych, zasada włączania i wyłączania

  8. Zliczanie i podziały, zasada szufladkowa Dirichleta

  9. Grafy – pojęcia wstępne

  10. Drzewa, drzewa z korzeniem, drzewa binarne

  11. Metody przeszukiwania grafów

  12. Drzewa rozpinające, algorytmy Kruskala i Prima

  13. Tranzytywne domknięcie grafu, najkrótsze ścieżki w grafie ważonym, algorytmy Dijkstry i Warshalla

  14. Informacje na temat grafów Eulera, Hamiltona, planarności i kolorowania grafów

LITERATURA


[1] W.Narkiewicz, Teoria liczb, PWN, 2003.

[2] K.A.Ross, Ch.R.B.Wright, Matematyka dyskretna, PWN, 1996.

[3] R.J.Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1985.
Literatura uzupełniająca
[4] N.Deo, Teoria grafów i jej zastoswania w technice i informatyce, PWN, Warszawa, 1980.

[5] R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka konkretna, PWN, Warszawa, 1998.



[6] W.Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 1989.


©snauka.pl 2016
wyślij wiadomość