Matematyka dyskretna

obowiązkowe
ogólnouczelniane

zdalnie

Wykład przedstawia aparat matematyczny niezbędny do budowy i analizy algorytmów. Składa się z teorii liczb, zbiorów, elementów logiki i kombinatoryki uraz teorii grafów.

Matematyka dyskretna - zbiorcza nazwa wszystkich części matematyki, które zajmują się badaniem struktur dyskretnych, czyli zawierających skończone lub co najwyżej policzalne (tj. dyskretne) zbiory. Matematyka dyskretna stała się popularna w ostatnich latach dzięki zastosowaniom w informatyce, która zajmuje się tylko strukturami skończonymi.

Treść wykładu i ćwiczeń:

1. Elementy logiki, kwantyfikatory, rachunek zdań i reguły wnioskowania

2. Zbiory i działania na zbiorach, funkcje i ciągi, notacja

3. Relacje, grafy, grafy skierowane, macierze (macierz sąsiedztwa), relacje równoważności

4. Grafy Eulera i Hamiltona oraz algorytmy ich wyznaczania

5. Indukcja i rekurencja

6. Funkcje tworzące i wielomiany charakterystyczne

7. Algorytm Euklidesa (prosty i rozszerzony) do wyznaczania NWD(m, n)

8. Arytmetyka modularna (kongruencje i ich rozwiązywanie, odwrotność w

zbiorze Zn)

9. Metody zliczania: zasada włączeń i wyłączeń, zasada szufladkowa

Dirichleta, elementy kombinatoryki

Podstawowa: K. A. Ross, Ch. R.B. Wright, Matematyka Dyskretna PWN, 2012

Dodatkowa:

- R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka Konkretna, PWN 2011,

- J. Jaworski, Z. Palka, J. Szymański, Matematyka dyskretna dla informatyków: Część I: Elementy kombinatoryki

- W Kordecki, Matematyka dyskretna dla informatyków, Wrocław 2005,

- M. Żynel, Matematyka dyskretna, skrypt 2012 (dostępny w interniecie)

-J. Grytczuk, Matematyka dyskretna, skrypt dostępny w Internecie

Kształtowanie podstawowego rozumowania matematycznego niezbędnego do zapisu i analizy problemów spotykanych w informatyce.

Wykład:

1 końcowy egzamin zalicza gdy uzyska się >= 50% rozwiązanych zadań.

Egzamin końcowy pisemny w terminie sesji przeznaczony jest dla osób, które

zaliczyły ćwiczenia. Z egzaminu zwalnia ocena z ćwiczeń >= 4.

Egzamin w drugim terminie (poprawka) dotyczy osób, które poprawiły

ćwiczenia i uzyskały zaliczenie.

Ćwiczenia:

Podstawą zaliczenia jest wykonanie 1 testu oraz + 4 indywidualnych prac domowych. Ocena każdego z tych elementów liczona jest jako Wi = Si/S (i = 1, 2, ..5), a średnia z tych wskaźników W = (Suma Wi )/5 daje wskaźnik poprawności ich wykonania 0 <= W <= 1, a warunek zaliczenia, to W >= 0,5

O cena końcowa jest wystawiana w/g zasady: W < 0,5 ->2; 0,5 <= W < 0,6 – >3; 0,6 <= W < 0,7 –> 3,5; 0,7 <= W < 0,8 –> 3,5; 0,8 <= W < 0,9 –> 4,5; W >= 0,9 -> 5