Matematyka dyskretna I I-NI7O>MD-I
- Elementy logiki oraz metody dowodzenia twierdzeń
- Powtórka z wielomianów i liczb zespolonych
- Obliczanie sum skończonych
a) podstawowe wzory i proste metody
b) rachunek różnicowy
- Rozwiązywanie równań rekurencyjnych
a) równania liniowe o współczynnikach stałych i zmiennych
b) notacja asymptotyczna
c) twierdzenie o rekurencji uniwersalnej
|
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 (relacje i funkcje na zbiorach skończonych, zliczanie-kombinatoryka, definicje i równania rekurencyjne, podstawy teorii grafów)
Powiązane efekty kierunkowe:
IF1A_W01
Metody weryfikacji:
Egzamin:Ma podstawową wiedzę z zakresu matematyki dyskretnej (relacje i funkcje na zbiorach skończonych, zliczanie-kombinatoryka, definicje i równania rekurencyjne, podstawy teorii grafów)
Wiedza
Ma elementarną wiedzę w zakresie algorytmów rekurencyjnych.
Powiązane efekty kierunkowe:
IF1A_W03
Metody weryfikacji:
Egzamin:Ma rozszerzoną wiedzę w zakresie matematycznych podstaw teorii informacji, teorii algorytmów i kryptografii oraz ich praktycznych zastosowań
Umiejętności
Potrafi zliczać elementy zbiorów skończonych. Umie rozwiązywać niektóre równania rekurencyjne.
Powiązane efekty kierunkowe:
IF1A_U06
Metody weryfikacji:
Ocena aktywności na zajęciach:Potrafi zliczać elementy zbiorów skończonych. Umie rozwiązywać niektóre równania rekurencyjne. Sprawdzian zaliczeniowy,
ćwiczenia realizowane podczas zajęć
Umiejętności
Potrafi stosować indukcję matematyczną, rekurencje w algorytmach rekurencyjnych. Potrafi wykorzystać wiedzę o grafach w zadaniach.
Powiązane efekty kierunkowe:
IF1A_U09
Metody weryfikacji:
Ocena aktywności na zajęciach:Potrafi stosować indukcję matematyczną, rekurencje w algorytmach rekurencyjnych. Potrafi wykorzystać wiedzę o grafach w zadaniach. Sprawdzian zaliczeniowy,
ćwiczenia realizowane podczas zajęć
Kompetencje społeczne
Rozumie potrzebę ciągłego dokształcania się, potrafi myśleć analitycznie.
Powiązane efekty kierunkowe:
IF1A_K01
Metody weryfikacji:
Egzamin:Rozumie potrzebę ciągłego dokształcania się, potrafi myśleć analitycznie. wykład Sprawdzian zaliczeniowy
Objaśnienia:
„Odniesienie do form zajęć” – wskazać która/które z form zajęć pozwalają na uzyskanie efektów uczenia się dla modułu zajęć.
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ę egzaminem, który ma charakter testu jednokrotnego wyboru. Pytania dotyczą zagadnień teoretycznych, analizy przykładowych modeli logicznych oraz rozwiązywania sum i równań rekurencyjnych. 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. Warunkiem dopuszczenia do egzaminu jest zdobycie pozytywnej oceny z laboratorium.
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ące daną metodę omówioną na wykładzie. 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
- K. A. Ross i in.: Matematyka dyskretna, PWN 1999.
- I. Koźniewska: Równania rekurencyjne, PWN 1972.
- R. L. Graham i in.: Matematyka konkretna, PWN 1998.
- M. Ben-Ari: Logika matematyczna w informatyce, WNT 2005.
- T. Biegańska i in.: Matematyka dyskretna zbiór zadań, AJD 2008.
- W. Sierpiński: Zasady algebry wyższej, PAN 1946.
- J. L. Hein: Distcrete Structures, Logic, and Computability, Jones and Barlett 2010.