Matematyka dyskretna

1. Znajomość indukcji matematycznej

2. Umiejętność obliczania pochodnych

3. Podstawy algebry

4. Podstawy logika

5. Podstawy teorii mnogości

1. Godziny kontaktowe z nauczycielem akademickim

-wykład 30,

-konwersatorium 30,

-konsultacje 2,

-egzamin 3.

Razem 65.

2. Samodzielna praca studenta

- samodzielne rozwiązywanie zadań 25,

- przygotowanie się do konwersatorium 15,

- przygotowanie się do egzaminu 15.

Razem 55.

Samodzielna praca studenta + godziny kontaktowe = 120

Liczba punktów ECTS - 4 w tym 2,17 za godziny kontaktowe oraz 1,83 za samodzielną pracę studentów.

Kolokwia - W01 W02, W04,

Egzamin - W01, W02, W04,

Zadania wykonywane na konwersatorium - U01, U02, W01, W02, W03, W04,

Matematyka dyskretna - to zbiorcza nazwa różnych działów matematyki, zajmujących się badaniem struktur nieciągłych czyli skończonych lub co najwyżej przeliczalnych. Stała się popularna w ostatnich latach dzięki zastosowaniom w informatyce, która w sposób naturalny zajmuje się jedynie strukturami skończonymi (skończona reprezentacja liczb, skończona ilość operacji w jednostkach czasu komputera - taktowanie zegara). Moduł ten obejmuje takie zagadnienia jak - rekurencje i równania różnicowe - sumy i metody różnicowe, - funkcje całkowitoliczbowe - wybrane zagadnienia teorii liczb - kombinatorykę - podstawy algebry - funkcje tworzące - podstawy teorii grafów. Również wprowadzam, w dość okrojonym stopniu, treści związane z analizą algorytmów (m. in. sortowania) i haszowania. W efekcie kształcenia student powinien potrafić przeanalizować złożoność obliczeniową algorytmów, umieć zastosować niektóre algorytmy szyfrowania czy potrafić zaimplementować grafy. Dodatkowo student poznaje różne, nawet mało znane, metody implementacji w komputerze liczb wymiernych, rzeczywistych i całkowitych.

Literatura podstawowa:

1. Krajka A., Matematyka dyskretna, Lublin 2011.UMCS

2. Krajka A., Zbiór zadań z matematyki dyskretnej, Lublin 2012 Skrypt Akademiski Informatyka UMCS.

3. Knuth D., E., Sztuka programowania, Wydawnictwo Naukowo-Techniczne, Warszawa 2002, T. I-III.

4. Graham R., L., Knuth D., E., Patashnik, O., Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996

5. Wirth, N., Algorytmy + struktury danych = programy, Wydawnictwo Naukowo-Techniczne, Warszawa 2004 Wyd. 7.

6. Materiały z wykładów Uniwersytetu Warszawskiego zamieszczone na stronie http://wazniak.mimuw.edu.pl/

Literatura Uzupełniająca:

1. Biggs N., L., Discrete Mathematics, Oxford University Press 1989

2. Bollobas B., Modern Graph Theory, Springer 1998

3. Bryant V., Aspekty kombinatoryki, Wydawnictwa Naukowo-Techniczne 1977.

4. Cormen Th., H., Leiserson Ch., E., Rivest, R., L., Stein, C., Wprowadzenie do algorytmów, WNT, 2004.

5. Grossman P., Discrete Mathematics for Computing, Second Edition, 2002, Palgrave Macmillan Houndmills, Basingstoke, Hampshire and New York.

6. Krantz F., G., Discrete Mathematics Demystified, 2009 McGraw-Hill Companies, Inc., New York, Chicago, San Francisco.

7. Lipski, W., Kombinatoryka dla programistów, Wydawnictwo Naukowo- Techniczne 2004.

8. Pałka, Z., Ruciński, A., Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.

9. Ross, K., A., Wright, Ch., R., B., Matematyka Dyskretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996

W01 - algorytmy Euklidesa, hash table, sortowania, faktoryzacji, algorytm Fleurego, algorytm Roberta-Floresa, algorytm Kruskala, algorytm Prima, algorytm Huffmana algorytm RSA - kierunkowy K_W05

W02 - metody analizy algorytmów, poszukiwanie błędów K_W08

W03 - rozwiązywanie rekurencji,kombinatoryka, teoria liczb, algebra wielomianów, funkcje tworzące, rachunek różnicowy - kierunkowy K_W09

W04 - analiza rekurencji (jak rekurencyjnie opisać badane zjawisko), badania grafowe, znajdywanie drogi, problem komiwojażera - kierunkowy K_W10

U01 - poszukiwanie optymalnych algorytmów, analiza kosztów algorytmu - kierunkowy K_U03

U02 - programowanie z wykorzystaniem grafów i rekurencji - kierunkowy K_U05

K01 -nierozwiązane problemy teorii grafów, rekurencje czy też problemy teorii liczb - kierunkowy K_K01