Matematyka Dyskretna
(ramowy program wykładu)
1.Wstęp:
elementarna algebra zbiorów;elementarne własności funkcji i ciągów:terminologia i notacja,;
relacje;zachowania asymptotyczne:notacje Ω,Ξ, o(-),O(-).
2.Logika (1).
elementarne reguły wnioskowania;reguły rachunku zdań;tautologie;równoważność logiczna zdań;model algebry Boola;wyrazenia i zmienne boolowskie;
3.Indukcja i rekurencja.
indukcja matematyczna i jej zastosowania;wzór dwumienny Newtona;procedury indukcyjne;definicje i procedury rekurencyjne;równania rekurencyjne, liniowe równania rekurencyjne i ich rozwiązywanie;
algorytm Euklidesa i analiza jego złożoności obliczeniowej,liczby Fibonacciego;algorytmy rekurencyjne i indukcyjne;
4.Zagadnienia kombinatoryczne.
elemenarne procedury zliczania;podziały ;algorytmy teoriomnogościowe;zasada szufladkowa Dirichleta;permutacje;kombinacje;wariacje;funkcje generujące;algorytmy kombinatoryczne i ich złożoność obliczeniowa;zastosowania do elementarnej teorii prawdopodobienstwa;
5.Zagadnienia teorii grafów.
relacje;grafy i grafy skierowane;zastosowania rachunku macierzy do analizy grafów;
algorytmy na grafach skierowanych;zagadnienia i algorytmy na grafach:przeszukiwania,sortowania,szukanie drzew rozpinających,szukanie optymalnych ścieżek;optymalne przepływy na grafach
6.Zagadnienia teorioliczbowe.
relacje podzielności, arytmetyka modularna;liniowe równania modularne;chińskie twierdzenie o resztach;rząd elementu:logarytm dyskretny; problem faktoryzacjitwierdzenie Eulera i twierdzenie (małe) Fermata;
protokół kryptograficzny RSA;testy pseudopierwszości;test Rabina-Millera;
7. Logika (2)
kwantyfikatory;elementarny rachunek predykatów;rachunek sekwentów;
zbiory nieskończone;
sieci boolowskie;tablice Karnaugha;
8. Uzupełnienia.
wiecej o relacjach;jezyki formalne;klasyczna teoria złożonosci obliczeniowej;problemy NP.,NP.-zupełne.
Literatura
1.K.A.Ross,CH. R. B. Wright, Matematyka Dyskretna, PWN, np 2000.
2.T.H.Cormen,Ch.E.Leiserson,R.L.Rivest;'Wprowadzenie do algorytmow',WNTWarszawa,1997
3.S.W.Jabloński,'Wstęp do Matematyki Dyskretnej',PWN Warszawa,1991
4.E.M.Reingold,J.Nievergelt,N.Deo;'Algorytmy Kombinatoryczne', PWN Warszawa 1985
5.J.Flachmeyer;'Kominatoryka';PWN Warszawa 1987.