MATEMATYKA DYSKRETNA

PJWSTK, I rok, studia dzienne

Grażyna Mirkowska

Spis Treści

Organizacja roku

Kolokwia:
    1. na 5tych ćw. (10 punktów)
    2. na12tych ćw. (20 punktów)
Na zaliczenie cwiczeń z MAD trzeba zdobyć > 14 punktów.

Uwaga. Obecnosć na ćwiczeniach jest obowiązkowa!

Przy ocenie końcowej z ćwiczeń, poza kolokwiami, będzie brana pod uwagę aktywność studentów w czasie ćwiczeń i zadania domowe. Zaliczenie ćwiczeń jest niezbędnym warunkiem przystąpienia studenta do egzaminu końcowego.

Egzamin: w lutym ( 60 punktów)

Ocena. Zaliczenie roku wymaga zaliczenia ćwiczeń oraz uzyskania z egzaminu co najmniej 30 punktów.
Stopień w indeksie zależy od wyniku otrzymanego z ćwiczeń i egzaminu końcowego.
Maksymalna liczba punktów do zdobycia (cw+ex) =90 punktów.

< 45 -----> ndst
45-50 -----> dost
51-60 -----> dost+
61-70 -----> dobry
71-80 -----> dobry+
81-90 -----> bardzo dobry

Osoby, które zaliczą oba kolokwia oraz uzyskają co najmniej dobrą ocenę z ćwiczeń będą zwolnione z egzaminu końcowego i otrzymają, jako końcową, ocenę z ćwiczeń- 0.5.

SPIS TRESCI

Tematy Cwiczeń

No
Temat Cwiczeń
CW1 Działania na zbiorach. ................................................
CW2 Działania na zbiorach c.d. Algorytm sumowania zbiorów (3reprezentacje)CW3
CW3 Produkt kartezjanski. Badanie własności relacji. Składanie relacji. Reprezentacja relacji.
CW4 Funkcje. Badanie różnowartościowości. Obrazy i przeciwobrazy wyznaczone przez funkcje.
CW5 Sprawdzian 1 cd funkcje i ich własności
CW6 Relacje równowaznsci. Klasy abstrakcji. Podziały zbioru.
CW7 Zbiory częściowo uporządkowane. Elementy minimalne i maksymalne. Kresy.
CW8 Logika: rachunek zdań. Tautologie. Metoda zerojedynkowa i dowody 'nie wprost'.
CW9 Rachunek predykatów. Kwantyfikatory. Wyrażanie własności w języku logiki.
CW10 Indukcja i rekursja.Dowodzenie przez indukcję
CW11 Równolicznośc. Moce zbiorów
CW12 Sprawdzian 2 c.d. moc zbioru
CW13 Elementy kombinatoryki.
CW14 Rachunek prawdopodobieństwa.
CW15
 Rachunek prawdopodobieństwa.
SPIS TRESCI

Tematy Wykładow

No
Tematy
W1 Algebra zbiorów. Wprowadzenie podstawowych oznaczeń i pojęć. Przykłady. Własności operacji teoriomnogościowych.
W2 Produkt kartezjański. Algrbra relacji. Relacje zwrotne, symetryczne i przechodnie.Przykłady. Ilustracja graficzna i tablicowa (macierz incydencji). Relacje wieloczłonowe.
W3 Funkcje. Funkcje jako relacje, Odwzorowania różnowartościowe i 'na'. Odwracanie funkcji i
składanie funkcji. Wykresy funkcji. Ciagi jako szczególne przykłady funkcji. Notacja
asymptotyczna.
W4 Relacje równoważnści. Zasada abstrakcji i jej zastosowania
W5 Relacje porządku częściowego. Elementy minimalne i maksymalne, największe i najmniejsze.
 Kresy. Porządek liniowy i dobry porządek.
W6 Rachunek zdań. Zdania. Semantyka. Ważniejsze tautologie. Reguły wnioskowania. Dowody apagogiczne. Logika a informatyka.
W7 Rachunek funkcyjny. Kwantyfikatory. Semantyka. Prawa logiki predykatów.
W8 Indukcja i rekursja
W9 Moce zbiorów. Zbiory przeliczalne i nieprzeliczalne. Twierdzenie Cantora.
W10 Systemy algebraiczne. Struktury danych. Homomorfizm kongruencja. Algebra ilorazowa.
W11 Elementy kombinatoryki: wriacje bez powtórzeń, permutacje (sposoby ich generowania), kombinacje, symbol dwumianowy Newtona.
W12 Zliczanie relacji i funkcji. Podziały zbioru. Zasada włączeń i wyłączeń. Zasada szufladkowa Dirichleta
W13 Elementy rachunku prawdopodobieństwa. Definicja. Obliczanie prawdopodobieństw. Prawdopodobieństwo warunkowe. Niezależność zdarzeń.
W14 Wzór na prawdopodobieństwo całkowite. Wzór Bayesa. Zmienna losowa. Niezależność zmiennych losowych. Rozkład prawdopodobieństwa. Dystrybuanta. Wartość oczekiwana zmiennej losowej.
W15
cd Rachunek prawdopodobieństwa. Wartość oczekiwana. Wariancja. Odchylenie standardowe.Przykłady
SPIS TRESCI

Literatura

Literatura podstawowa

Rasiowa H.,Wstęp do matematyki współczesnej, PWN 1968
Ross K.A., Wright Ch., Matematyka Dyskretna, PWN 1999
Czechowski T., Elementarny wykład Rachunku Prawdopodobieństwa , PWN 1958
Lipski W., Kombinatoryka dla programistów, WNT

Literatura uzupełniająca

Arnold A., Guessarian I., Matematique Discrete, 1995
Cormen T., Leiserson Ch., Rivest R., Wprowadzenie do algorytmów , WNT
Baase S., Computer Algorithms Addison Wesley
Fisz M., Rachunek Prawdopodobieństwa, PWN 1958
Marek W., Onyszkiewicz ., Zbiór zadań z teorii mnogości
Barwise J., Etchemendy J., Tarski's world

SPIS TRESCI