|
Matematyka Dyskretna (studia stacjonarne)
- Opis kursu
- Celem kursu jest:
- Przygotowanie do wysłuchania wykładów z: relacyjnej teorii baz danych, teorii algorytmów i teorii informacji oraz metod probabilistycznych.
- Nauczenie interpretowania pojęć z zakresu informatyki w terminach matematyki: zbioru, relacji, funkcji i ciągu, grafu i struktur algebraicznych.
- Pokazanie zastosowań aparatu: logiki matematycznej, teorii zliczania, teorii grafów, rekurencji i metod algebry Boole’a do rozwiązywania problemów o charakterze informatycznym.
- Zakres tematyczny kursu:
- Wprowadzenie do logiki matematycznej: pojęcie zdania, funktory i zdania złożone, rachunek predykatów, tautologie i ich metody dowodzenia.
- Elementy teorii zbiorów: pojęcie zbioru, zbiory skończone i nieskończone, rachunek zbiorów, zbiory liczbowe, rodziny zbiorów.
- Relacje: pojęcie relacji, działania na relacjach, metody reprezentowania relacji (przez grafy skierowane i macierze), klasyfikacja relacji, relacje równoważności (zasada abstrakcji), częściowe i dobre uporządkowanie.
- Odwzorowania i ich zastosowania: funkcje rzeczywiste, ciągi liczbowe, teoria rekurencji (metody rozwiązywania rekurencji), liczby Fibonacciego, Sterlinga i Catalana, metody zliczania (zasada włączania i wykluczania, zasada addytywności, zasada wielokrotnego wyboru, zasada szufladkowa Dirichleta), metody kombinatoryki, twierdzenie Halla.
- Teoria grafów i drzew: pojęcie grafu, drogi, cyklu Eulera i Hamiltona, grafy acykliczne. Grafy Eulera i ich własności (twierdzenia Eulera). Grafy Hamiltona i ich własności (twierdzenie Diraca), zastosowanie do kodów Graya. Grafy planarne i ich własności, grafy dwudzielne i twierdzenie o skojarzeniach. Drzewa jako grafy i ich zastosowania w informatyce (przeszukiwania binarne).
- Algebry Boole’a i ich zastosowania dla potrzeb optymalizacji wyrażeń boolowskich-metoda tablic Karanaugha.
- Zaliczenie kursu
- Wykład trwa semestr i kończy się egzaminem. Warunkiem koniecznym przystąpienia do egzaminu jest uzyskanie pozytywnego zaliczenia z ćwiczeń.
- Literatura
- LITERATURA PODSTAWOWA:
- Ryszard Rębowski, Matematyka Dyskretna dla Informatyków, seria wydawnicza PWSZ w Legnicy, Legnica 2008,
- Ryszard Rębowski i Janina Płaskonka, Zbiór zadań z matematyki dyskretnej dla informatyków, seria wydawnicza PWSZ w Legnicy, Legnica 2009,
- Kenneth A. Ross, Charles R.B. Wright, Matematyka Dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2003,
- R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2002.
- LITERATURA UZUPEŁNIAJĄCA:
- Victor Bryant, Aspekty kombinatoryki, WNT Warszawa 1997,
- Witold Lipski, Wiktor Marek, Analiza kombinatoryczna, PWN Warszawa 1986,
- Ian Anderson, A first cours in Discrete Mathematics, Springer 2000.
Metody zliczania
Lista 1 ze zbioru Lista 2 Lista 3 (wraz z przykładami) Lista4 (rozdział 6 ZZ)
Lista 2: 2.2.3-2.2.8, 2.2.10-2.2.12, 2.2.15, 2.2.17
Lista 3: 3.2.1-3.2.3, 3.2.5-3.2.7, 3.2.9-3.2.16, 3.2.18-3.2.21
Lista 4: 3.2.21, 3.2.22, 3.2.24, 4.2.2, 4.2.5, 4.2.11, 4.2.12, 4.2.13
Lista 5: 6.2.1, 6.2.2, 6.2.5, 6.2.6, 6.2.7, 6.2.8
Lista 6: 6.2.9, 6.2.12, 6.2.13, 6.2.15, 6.2.17, 6.2.19, 6.2.21
Lista 7: 6.2.20, 6.2.23, 6.2.24,
|
