Wydział Informatyki - Informatyka (S1)
Sylabus przedmiotu Matematyka dyskretna:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | pierwszego stopnia |
| Tytuł zawodowy absolwenta | inżynier | ||
| Obszary studiów | charakterystyki PRK, kompetencje inżynierskie PRK | ||
| Profil | ogólnoakademicki | ||
| Moduł | — | ||
| Przedmiot | Matematyka dyskretna | ||
| Specjalność | przedmiot wspólny | ||
| Jednostka prowadząca | Katedra Metod Sztucznej Inteligencji i Matematyki Stosowanej | ||
| Nauczyciel odpowiedzialny | Andrzej Banachowicz <Andrzej.Banachowicz@zut.edu.pl> | ||
| Inni nauczyciele | Andrzej Banachowicz <Andrzej.Banachowicz@zut.edu.pl>, Joanna Banaś <Joanna.Banas@zut.edu.pl>, Larisa Dobryakova <Larisa.Dobryakova@zut.edu.pl>, Leszek Drobiazgiewicz <Leszek.Drobiazgiewicz@zut.edu.pl>, Marcin Korzeń <Marcin.Korzen@zut.edu.pl>, Małgorzata Machowska-Szewczyk <Malgorzata.Machowska.Szewczyk@zut.edu.pl> | ||
| ECTS (planowane) | 5,0 | ECTS (formy) | 5,0 |
| Forma zaliczenia | egzamin | Język | polski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Algebra liniowa |
| W-2 | Matematyka stosowana ze statystyką 1 |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Zapoznanie studenów z podstawowymi pojęciami logiki matematycznej i teorii mnogości. |
| C-2 | Nabycie umiejętności stosowania aparatu pojęciowego matematycznych struktur skończonych i przeliczalnych w modelowaniu zagadnień informatycznych. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| T-A-1 | Przykłady zastosowań matematyki dyskretnej w informatyce. Definiowanie. Pojęcia logiczne, poprawne formułowanie zdań, wartości logiczne zdań, rachunek zdań, rachunek predykatów, dowodzenie twierdzeń, indukcja zupełna. | 5 |
| T-A-2 | Przykłady zbiorów i ich elementów, sposoby określania zbiorów, działania na zbiorach, zbiory uporządkowane, funkcje zdaniowe, iloczyn kartezjański zbiorów, relacje, własności relacji, funkcje, zbiory uporządkowane, obcięcie i rozszerzenie funkcji, funkcja odwrotna, permutacje, superpozycja funkcji, grupy przekształceń, równoliczność i moc zbioru. | 7 |
| T-A-3 | Kolokwium zaliczające 1 | 2 |
| T-A-4 | Zliczanie, rozmieszczenia, zasada włączania i wyłączania, konfiguracje kombinatoryczne. Ciągi, równania rekurencyjne, funkcje tworzące, algorytmy rekurencje. | 4 |
| T-A-5 | Struktury algebraiczne, grupa, pierścień, ciało, ciała skończone, homomorfizm struktur. Podzielność, dzielenie z resztą, największy wspólny dzielnik, najmniejsza wspólna wielokrotność, liczby pierwsze, faktoryzacja, kongruencje, klasy reszt, elementy odwracalne, Chińskie twierdzenie o resztach, arytmetyka modularna. | 6 |
| T-A-6 | Grafy skierowane i nieskierowane, wierzchołki, krawędzie, macierz sąsiedztwa, macierz incydencji, graf Hamiltonowski, graf planarny, cykle, drzewa, mosty, działania na grafach, kolorowanie grafów. | 4 |
| T-A-7 | Kolokwium zaliczające 2 | 2 |
| 30 | ||
| wykłady | ||
| T-W-1 | Pojęcia wstępne – zakres tematyczny matematyki dyskretnej, definiowanie, dowodzenie, oznaczenia, teorie aksjomatyczne, systemy logiczne, przykłady zastosowań matematyki dyskretnej w informatyce. | 2 |
| T-W-2 | Logika. Wprowadzenie, systemy logiczne, operatory logiczne, rachunek zdań, podstawowe prawa rachunku zdań, rachunek predykatów, metody dowodzenia twierdzeń, zasada indukcji zupełnej, reguły dowodzenia. | 4 |
| T-W-3 | Teoria mnogości. Podstawowe pojęcia, zbiór, element zbioru, działania na zbiorach, twierdzenie, przestrzeń, dopełnienie zbioru, aksjomaty teorii mnogości, produkty kartezjańskie, relacje, własności relacji, zasada abstrakcji, funkcje zdaniowe. Odwzorowania i funkcje – pojęcie funkcji, funkcje jako relacje, rodzaje odwzorowań, obcięcie i rozszerzenie funkcji, funkcja odwrotna, superpozycja funkcji, równoliczność i moc zbioru, zbiór przeliczalny, zbiory uporządkowane. | 6 |
| T-W-4 | Zliczanie. Kombinatoryka – zliczanie, rozmieszczenia, zasada włączania i wyłączania. | 2 |
| T-W-5 | Teoria liczb. Arytmetyka i algebra, struktury algebraiczne, grupa, pierścień, ciało, morfizmy, ciała skończone, podzielność, dzielenie z resztą, największy wspólny dzielnik, najmniejsza wspólna wielokrotność, liczby pierwsze, faktoryzacja, kongruencje, elementy odwracalne, Chińskie twierdzenie o resztach, funkcje Eulera. | 6 |
| T-W-6 | Grafy. Grafy skierowane i nieskierowane, wierzchołki, krawędzie, macierz sąsiedztwa, macierz incydencji, graf Hamiltonowski, graf planarny, cykle, drzewa, liście, mosty, kolorowanie grafów, działania na grafach. | 4 |
| T-W-7 | Teoria automatów komórkowych – definicja automatu komórkowego, sąsiedztwa komórek, warunki brzegowe, ewolucja automatu komórkowego, klasyfikacja automatów komórkowych, deterministyczne i niedeterministyczne automaty komórkowe. | 4 |
| T-W-8 | Repetytorium | 2 |
| 30 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| A-A-1 | uczestnictwo w zajęciach | 30 |
| A-A-2 | Przygotowanie do zajęć audytoryjnych - praca własna studenta. | 10 |
| A-A-3 | Pisanie sprawozdań z ćwiczeń - praca własna studenta. | 4 |
| A-A-4 | Przygotowanie do kolokwium - praca własna studenta. | 4 |
| A-A-5 | Udział w zaliczeniu formy zajęć i konsultacje | 2 |
| 50 | ||
| wykłady | ||
| A-W-1 | Uczestnictwo w zajęciach. | 30 |
| A-W-2 | Studiowanie wskazanej literatury - praca własna studenta. | 10 |
| A-W-3 | Konsultacje do wykładu. | 8 |
| A-W-4 | Rozwiązywanie postawionych problemów - praca własna studenta. | 12 |
| A-W-5 | Przygotowanie się do egzaminu - praca własna studenta. | 12 |
| A-W-6 | Egzamin. | 2 |
| 74 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykład: informacyjny, problemowy, konwersatoryjny. |
| M-2 | Ćwiczenia audytoryjne: metoda przypadków, ćwiczenia przedmiotowe, metody programowane z użyciem komputera. |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena formująca: Wykład: na podstawie rozwiązywania problemów i dyskusji. Ćwiczenia audytoryjne: na podstawie indywidualnego rozwiązywania zadań i problemów; |
| S-2 | Ocena podsumowująca: Wykład: egzamin pisemny (zestaw zadań i problemów). Ćwiczenia audytoryjne: kolokwium (zestaw zadań i problemów). |
Zamierzone efekty uczenia się - wiedza
| Zamierzone efekty uczenia się | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_B03_W01 Posiada wiedzę w zakresie wykorzystania logiki, teorii mnogości i struktur dyskretnych w projektowaniu, analizie i implementacji algorytmów oraz konstrukcji programistycznych. | I_1A_W02 | — | — | C-1, C-2 | T-W-6, T-W-1, T-W-2, T-W-4, T-W-5, T-W-3 | M-1, M-2 | S-2, S-1 |
Zamierzone efekty uczenia się - umiejętności
| Zamierzone efekty uczenia się | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_B03_U01 Potrafi wykorzystywać wnioskowanie logiczne, pojęcia teoriomnogościowe i struktury dyskretne do rozwiązywania zadań i problemów informatycznych. | I_1A_U05 | — | — | C-1, C-2 | T-A-1, T-A-2, T-A-4, T-A-6, T-A-5 | M-1, M-2 | S-2, S-1 |
Kryterium oceny - wiedza
| Efekt uczenia się | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_B03_W01 Posiada wiedzę w zakresie wykorzystania logiki, teorii mnogości i struktur dyskretnych w projektowaniu, analizie i implementacji algorytmów oraz konstrukcji programistycznych. | 2,0 | Student nie zna podstawowych pojęć teorii mnogości, logiki matematycznej, kombinatoryki, algebry, teorii liczb i teorii grafów. |
| 3,0 | Student zna podstawowe pojęcia teorii mnogości, logiki matematycznej, kombinatoryki, algebry, teorii liczb i teorii grafów. | |
| 3,5 | Student zna podstawowe pojęcia teorii mnogości oraz działania na zbiorach przeliczalnych, podstawowe prawa logiki matematycznej, kombinatoryki, algebry, teorii liczb i teorii grafów. | |
| 4,0 | Student zna pojęcia teorii mnogości oraz działania na zbiorach przeliczalnych, podstawowe prawa logiki matematycznej, analizę kombinatoryczną, struktury algebraiczne, systemy liczbowe i teorię grafów. | |
| 4,5 | Student zna pojęcia teorii mnogości, działania na zbiorach przeliczalnych, podstawowe prawa logiki matematycznej i ich zastosowania w informatyce, analizę kombinatoryczną, struktury algebraiczne, systemy liczbowe i ich zastosowania w algebrze komputerów, teorię grafów i jej wykorzystanie w analizach. | |
| 5,0 | Student zna pojęcia teorii mnogości, działania na zbiorach przeliczalnych, podstawowe prawa logiki matematycznej i ich zastosowania w informatyce, systemy aksjomatyczne, analizę kombinatoryczną, struktury algebraiczne, systemy liczbowe i ich zastosowania w algebrze komputerów oraz kryptografii, teorię grafów i jej wykorzystanie w analizach. |
Kryterium oceny - umiejętności
| Efekt uczenia się | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_B03_U01 Potrafi wykorzystywać wnioskowanie logiczne, pojęcia teoriomnogościowe i struktury dyskretne do rozwiązywania zadań i problemów informatycznych. | 2,0 | Student nie potrafi stosować podstawowych zagadnień logiki, teorii mnogości, algebry i teorii grafów. |
| 3,0 | Student potrafi budować proste modele informatyczne rozpatrywanych zagadnień z wykorzystaniem struktur teoriomnogościowych, praw logiki matematycznej, kombinatoryki, struktur algebraicznych i prostych grafów. | |
| 3,5 | Student potrafi budować złożone modele informatyczne rozpatrywanych zagadnień z wykorzystaniem struktur teoriomnogościowych, praw logiki matematycznej, kombinatoryki, struktur algebraicznych, teorii liczb i prostych grafów. | |
| 4,0 | Student potrafi budować bardziej złożone modele informatyczne rozpatrywanych zagadnień z wykorzystaniem struktur teoriomnogościowych, praw logiki matematycznej, kombinatoryki, struktur algebraicznych i prostych grafów. | |
| 4,5 | Student potrafi w sposób kreatywny dobrać adekwatny dyskretny model matematyczny rozpatrywanego zagadnienia, posługując się nabytą wiedzą. | |
| 5,0 | Student potrafi w sposób kreatywny dobrać adekwatny dyskretny model matematyczny rozpatrywanego zagadnienia oraz dokonać jego analizy i weryfikacji, posługując się nabytą wiedzą. Potrafi dowodzić twierdzenia oraz poprawność wnioskowania. |
Literatura podstawowa
- Ben-Ari M., Logika matematyczna w informatyce., Wydawnictwo Nukowo-Techniczne., Warszawa, 2005
- Dobryakova L., Matematyka dyskretna, Lulu Publishing, Raleigh North Company, USA, 2012
- Guzicki W., Zakrzewski P., Wykłady ze wstępu do matematyki., Wydawnictwo Naukowe PWN., Warszawa, 2007
- Homeda W., Elementy lingwistyki matematycznej i teorii automatów, Wydawnictwo Politechniki Warszawskiej, Warszawa, 2005
- Kacprzak M., Mirkowska G., Rembalski P., Sawicka A., Elementy matematyki dyskretnej. Zbiór zadań., Wydawnictwo PJWSTK., Warszawa, 2008
- Lipski W., Kombinatoryka dla pogramistów., Wydawnictwo Naukowo-Techniczne., Warszawa, 2004
- Ławrow I.A., Łarisa L., Maksimowa Ł.L., Zadania z teorii mnogości, logiki matematycznej i teorii algorytmów., Wydawnictwo Naukowe PWN., Warszawa, 2004
- Mirkowska G., Elementy matematyki dyskretnej., Wydawnictwo PJWSTK., Warszawa, 2003
- Ross K.R., Wright C.R.B., Matematyka dyskretna., Wydawnictwo Naukowe PWN., Warszawa, 2005
- Szepietowski A., Matematyka dyskretna., Wydawnictwo Uniwersytetu Gdańskiego., Gdańsk, 2004
- Lipski W., Wiktor M., Analiza kombinatoryczna., Państwowe Wydawnictwo Naukowe., Warszawa, 1986
- Yan S.Y., Teoria liczb w informatyce, Wydawnictwo Naukowe PWN, 2006
Literatura dodatkowa
- Bronsztejn I.N., Siemiendiajew K.A., Musiol G., Muhling H., Nowoczesne kompendium matematyki., Wydawnictwo Naukowe PWN, Warszawa, 2004
- Bryant V., Aspekty kombinatoryki., Wydawnictwo Naukowo-Tehniczne., Warszawa, 1997
- Graham R.L., Knuth D.E., Patashnik O., Matematyka konkretna., Wydawnictwo Naukowe PWN., Warszawa, 1996
- Grell B., Wstęp do matematyki., Wydawnictwo Uniwersytetu Jagiellońskiego., Kraków, 2006
- Grzegorczyk A., Logika popularna., Wydawnictwo Naukowe PWN., Warszawa, 2010
- Marek W., Onyszkiewicz J., Elementy logiki i teorii mnogości e zadaniach., Wydawnictwo Naukowe PWN, 2004
- Wilson R.J., Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2000
- Wolfram S., A New Kind of Science, Wolfram Media, Inc., 2005
- Rosen K.H., Discrete Mathematics and its Applications., McGraw – Hill, New York, 2012