Matematyka Dyskretna (studia niestacjonarne)
- 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
|