Matematyka dyskretna (ćwiczenia)

Opis przedmiotu
Informacje ogólne
Organizator:Wydział Matematyki, Informatyki i Architektury Krajobrazu - Instytut Matematyki i Informatyki
Kod ECTS:11100-XXXX-1001CWI0194
Kierunek studiów: Informatyka (stacjonarne I stopnia)
Lokalizacja w planach rocznych:
Etap:Rok I - Semestr 2
Punkty ECTS: 0
Forma zaliczenia: Zaliczenie na ocenę
Rozkład zajeć
Lokalizacja w programie modułowym:
Moduł programowy:Przedmioty kształcenia podstawowego » Matematyka dyskretna
Kierunek studiów: Matematyka (stacjonarne I stopnia)
Lokalizacja w planach rocznych:
Etap:Rok I - Semestr 2
Punkty ECTS: 0
Forma zaliczenia: Zaliczenie na ocenę
Rozkład zajeć
Cele przedmiotu
C1 - Poznanie podstawowych metod matematycznych. 
C2 - Nauczenie twórczego rozwiązywania problemów z zakresu teorii zbiorów i relacji, algorytmiki , indukcji i rekurencji, kombinatoryki, teorii grafów, algebry i funkcji Boole’ai. 
C3 - Przygotowanie do dalszych studiów informatycznych.
Wymagania wstępne
W1 – znajomość podstawowych pojęć matematycznych
znajomość zagadnień z przedmiotu: logika dla informatyków, 
W2 - znajomość zagadnień z przedmiotu: Algebra liniowa z geometrią analityczną, 
W3 - znajomość zagadnień z przedmiotu: Wstęp do informatyki.
W3 - Algebra liniowa
Efekty kształcenia dla przedmiotu
WIEDZA 
1. student zna wymagane pojęcia - K_W02 
2. student zna omawiane techniki i narzędzia występujące w matematyce dyskretnej - K_W02 
UMIEJĘTNOŚCI 
1. student rozwiązuje zagadnienia z zakresu teorii zbiorów i relacji, algorytmiki , indukcji i rekurencji, kombinatoryki, teorii grafów, algebry i funkcji Boole’a - K_U21 
2. student potrafi zastosować omawiane pojęcia, techniki i narzędzia występujące w matematyce dyskretnej - K_U22 
KOMPETENCJE SPOŁECZNE (POSTAWY) 
1. student zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia - K_K01
Metody dydaktyczne
Ćwiczenia praktyczne
Treści programowe przedmiotu
1. Podstawy teorii zbiorów. 
2. Relacje: podstawowe własności, relacja równoważności, funkcje, relacje porządku. 
3. Algorytmy: podstawowe własności, porównywanie algorytmów, złożoność obliczeniowa, problemy P-zupełne a NP-zupełne. 
4. Zasada indukcji matematycznej, dowody indukcyjne. 
5. Rekurencja: definicje rekurencyjne, zależności i równania rekurencyjne, algorytmy rekurencyjne.
6. Modele kombinatoryczne. Kombinacje bez powtórzeń i z powtórzeniami. Wariacje bez powtórzeń i z powtórzeniami. Permutacje. Algorytmy generowania kombinacji, wariacji, permutacji. Zasada włączania-wyłączania. Zasada szufladowa Dirichleta.
7. Analiza kombinatoryczna: podstawowe twierdzenia, trójkąt Pascala, dwumian Newtona i inne ważne formuły.
8. Grafy. Sposoby zapisywania grafów. Grafy a relacje. Izomorfizm a homomorfizm grafów. Twierdzenia o stopniach wierzchołków grafu. Regularność, pełność, dwudzielne grafy. Spójność, składowe grafu.
9. Drogi i cykli w grafie. Tw. o cyklach i drodze Eulera. Algorytm Fleury’ego konstruowania drogi Eulera. Tw. o grafach hamiltonowskich. Algorytm konstruowania drogi Hamiltona. Przykłady zagadnień znalezienia cyklów Eulera i Hamiltona. Prymitywny algorytm do rozwiązania problemu komiwojażera (travelling salesman problem).
10. Planarność grafów. Kolorowanie grafów. Tw. Eulera o płanarnych grafach (z dowodem). Tw. Kuratowskiego-Pontrjagina (bez dowodu). Mapa i graf oporny. Problem kolorowania mapy z minimalną liczbą kolorów. Tw. o czterech barwach. Kolorowanie wierzchołków i krawędzi grafu. Algorytm kolorowania wierzchołków grafu.
11. Grafy skierowane. Najkrótsze drogi w grafach skierowanych o krawędziach z wagami. Znajdowanie najmniejszej odległości między wierzchołkami. Algorytm Forda-Bellmana. Algorytm Dijkstry. Grafy z etykietkami. Hiperkostka. Zastosowania grafów z etykietkami.
12. Drzewa i lasy. Oszacowania liczby grafów. Drzewo spinające. Oszacowania liczby drzew (Tw. Keli). Drzewa ukorzenione. Algorytmy przeszukiwania wierzchołków drzewa w głąb i wszerz. Oszacowania liczby drzew z korzeniem, lasów, zwykłych grafów.
13. Algebry i funkcje Boole’a. Wyrażenia boolowskie. Prawa algebry zdań. Wartościowanie. Układy funkcji Boole’a jako modeli sieci logicznych z bramek ({NOT, OR, AND}, {NOR} i tp). Przykłady sieci logicznych (sumator, komparator). Analityczna reprezentacja BF. Normalne formy (DNF, CNF).
14. Minimalizacja funkcji Boole’a. Formułowanie problemu. Kryterium optymalności. Konstytuanty i implikanty. Tw. Quine’a. Problem optymalnego pokrycia macierzy Boole’a. Budowanie minimalnej DNF. Zastosowania metod algebry Boole’a do projektowania sieci logicznych.
Kryteria oceny i sposoby weryfikacji zakładanych efektów kształcenia
Wiedza i umiejętności studentów sprawdzane będą na kolokwium (egzamin połówkowy w semestrze) oraz na egzaminie pisemnym w sesji egzaminacyjnej.
Ocena niedostateczna (2) 
(W) - Student nie zna pojęć, technik i narzędzi występujących w matematyce dyskretnej 
(U) - Student nie potrafi zastosować podstawowych pojęć, technik i narzędzi występujących w matematyce dyskretnej 
(K) - Student nie rozumie potrzeby dalszego kształcenia 

Ocena dostateczna (3) 
(W) - Student zna wybrane pojęcia, techniki i narzędzia występujące w matematyce dyskretnej 
(U) - Student potrafi zastosować niektóre pojęcia, techniki i narzędzia występujące w matematyce dyskretnej 
(K) - Student rozumie potrzebę dalszego kształcenia ale nie robi tego 

Ocena dobra (4) 
(W)- Student zna większość pojęć, technik i narzędzi występujących w matematyce dyskretnej 
(U)- Student potrafi zastosować pojęcia, techniki i narzędzia występujące w matematyce dyskretnej 
(K)- Student rozumie potrzebę dalszego kształcenia, robi to, ale nie wszystko umie 

Ocena bardzo dobra (5) 
(W)- Student zna wszystkie wymagane pojęcia, techniki i narzędzia występujące w matematyce dyskretnej 
(U)- Student potrafi zastosować wszystkie wymagane pojęcia, techniki i narzędzia występujące w matematyce dyskretnej 
(K)- Student rozumie potrzebę dalszego kształcenia, robi to i wszystko umie
Literatura podstawowa i uzupełniająca
Literatura podstawowa: 
1. K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2000. 
Literatura uzupełniająca: 
1. R. J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa 2000. 
2. V. Bryant, Aspekty kombinatoryki, Wydawnictwa - Naukowo Techniczne, Warszawa 2007. 
3. Andrzej Szepietowski: Matematyka dyskretna. W-wo GU. Gdańsk, 2004.