Matematyka dyskretna II I-NI7O>MD-II
1. Elementy kombinatoryki
2. Funkcje i relacje
3. Podstawowe definicje i metody reprezentacji grafów
4. Dekompozycje grafów
5. Ścieżki w grafie
6. Arytmetyka modularna
7. Haszowanie uniwersalne
|
W cyklu 2021/2022-Z:
Celem zajęć w tym module jest wprowadzenie i ugruntowanie wśród studentów formalnej wiedzy dotyczącej zbiorów, ciągów i funkcji, elementów logiki matematycznej, relacji oraz indukcji i rekurencji w zakresie niezbędnym do przeprowadzenia i przedstawienia precyzyjnej analizy pod kątem matematycznym rozwiązań algorytmicznych i programistycznych realizowanych na przedmiotach kierunkowych. Student zostanie również zaznajomiony z wybranymi zagadnieniami teorii grafów, rachunku prawdopodobieństwa i struktur algebraicznych, niezbędnymi dla zrozumienia i samodzielnego projektowania metod rozwiązywania problemów informatycznych oraz oceny złożoności, sprawdzenia i uzasadnienia poprawności proponowanej metody. |
Koordynatorzy przedmiotu
<b>Ocena końcowa</b>
<b>Wymagania wstępne</b>
<b>Literatura podstawowa</b>
<b>Literatura uzupełniająca</b>
<b>Inne informacje</b>
Efekty kształcenia
Wiedza
Ma podstawową wiedzę z zakresu matematyki dyskretnej (podstawy teorii grafów i drzew, wybranych struktur algebraicznych).
Powiązane efekty kierunkowe:
IF1A_W01
Metody weryfikacji:
Kolokwium:Ma podstawową wiedzę z zakresu matematyki dyskretnej (podstawy teorii grafów i drzew, wybranych struktur algebraicznych).
Wiedza
Ma elementarną wiedzę w zakresie grafów Petri’ego.
Powiązane efekty kierunkowe:
IF1A_W03
Metody weryfikacji:
Kolokwium:Ma elementarną wiedzę w zakresie grafów Petri’ego.
Wiedza
Ma elementarną wiedzę z zakresu modelowania przekładni grafami.
Powiązane efekty kierunkowe:
IF1A_W10
Metody weryfikacji:
Kolokwium:Ma elementarną wiedzę z zakresu modelowania przekładni grafami.
Umiejętności
Potrafi wykorzystać wiedzę o grafach w modelowaniu problemów np. ścieżek, przydziału, kolorowania.
Powiązane efekty kierunkowe:
IF1A_U09
Metody weryfikacji:
Ocena aktywności na zajęciach:Potrafi wykorzystać wiedzę o grafach w modelowaniu problemów np. ścieżek, przydziału, kolorowania. Sprawdzian zaliczeniowy,
ćwiczenia realizowane podczas zajęć.
Umiejętności
Potrafi zbudować sieć Petri’ego dla wybranego prostego problemu oraz graf przekładni planetarnej
Powiązane efekty kierunkowe:
IF1A_U06
Metody weryfikacji:
Ocena aktywności na zajęciach:Potrafi zbudować sieć Petri’ego dla wybranego prostego problemu oraz graf przekładni planetarnej. Sprawdzian zaliczeniowy,
ćwiczenia realizowane podczas zajęć
Umiejętności
Potrafi samodzielnie zdobywać wiedzę oraz korzystać z literatury i Internetu celem uzupełnienia wiedzy.
Powiązane efekty kierunkowe:
IF1A_U01
Metody weryfikacji:
Ocena aktywności na zajęciach:Potrafi samodzielnie zdobywać wiedzę oraz korzystać z literatury i Internetu celem uzupełnienia wiedzy.
Kompetencje społeczne
Rozumie potrzebę ciągłego dokształcania się, potrafi myśleć analitycznie.
Powiązane efekty kierunkowe:
IF1A_K01
Metody weryfikacji:
Kolokwium:Rozumie potrzebę ciągłego dokształcania się, potrafi myśleć analitycznie.
Kryteria oceniania
Wykłady w formie prezentacji z wykorzystaniem rzutnika multimedialnego. Treść slajdów obejmuje zarówno aspekty teoretyczne matematyki dyskretnej, jaki i praktyczne przykłady rozwiązywania konkretnych zadań.
Wykłady kończą się zaliczeniem, który ma charakter testu jednokrotnego wyboru. Pytania dotyczą zagadnień teoretycznych oraz analizy rozwiązania przykładowych zadań. Za każde pytanie można uzyskać jeden punkt, a do zaliczenia wymagana jest poprawna odpowiedź na co najmniej 50% pytań plus jedno pytanie. Za 100% skuteczność student uzyskuje ocenę bardzo dobrą, a za mniejszą - proporcjonalnie mniej.
W ramach ćwiczeń tablicowych rozwiązywane są praktyczne zadania dotyczące poszczególnych metod przedstawianych na wykładzie. Każdy student dostaje inne zadanie, dla którego powinien przygotować rozwiązanie wykorzystujący daną metodę. za każde rozwiązane zadanie student uzyskuje ocenę (od dwóch do pięciu punktów). Dwa punkty za brak lub rozwiązanie nieprawidłowe, trzy lub więcej punktów w zależności od liczby punktów przypisanych do danego zadania. Aby zaliczyć laboratorium należy uzyskać średnią arytmetyczną ze wszystkich ocen nie mniejszą niż 3,0. Średnia ta zaokrąglona do najbliższej połówki stanowi ocenę zaliczającą ćwiczenia.
Ocena końcowa dla modułu to średnia arytmetyczna oceny z egzaminu oraz oceny zaliczającej laboratorium. Obydwie muszą być pozytywne.
Literatura
1. K.A. Ross, C.R.B. Wright, Matematyka dyskretna, PWN 1999.
2. E.A. Bender, S. Gill Williamson, Foundations of Combinatorics with Applications, Dover 2006.
3. W. Kordecki A. Łyczkowska-Hanćkowiak, Matematyka dyskretna dla informatyków, Helion 2018.
4. M. Kacprzak, G.Mirkowska, P. Rembelski, A. Sawicka, Elementy matematyki dyskretnej: Zbiór zadań, Wydawnictwo PJWSTK 2008.
5. O. Levin, Discrete Mathematics: An Open Introduction, 2019 (http://discrete.openmathbooks.org/).
6. S. Dasgupta i in.: Algorytmy, PWN 2010.