Matematyka dyskretna 1000-212bMD
* Indukcja matematyczna i rekurencje
* Sumy skończone
* Współczynniki dwumianowe
* Permutacje i podziały
* Funkcje tworzące i ich zastosowania
* Metody zliczania
- enumeratory
- zasada włączania-wyłączania
* Asymptotyka:
- notacja asymptotyczna (O,Omega, Theta, o, omega)
- twierdzenie o rekurencji uniwersalnej
* Elementarna teoria liczb:
- podzielność, liczby pierwsze, rozkład na czynniki pierwsze
- NWD i algorytm Euklidesa
* Arytmetyka modularna:
- małe twierdzenie Fermata i twierdzenie Eulera
- chińskie twierdzenie o resztach
- rozwiązywanie równań modularnych
* Elementy kryptografii: test Millera-Rabina i system RSA
* Grafy:
- ścieżki, drzewa i cykle
- cykle Eulera i Hamiltona
- grafy dwudzielne, skojarzenia i twierdzenie Halla
- planarność
- kolorowanie grafów
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza
1. Ma wiedzę w zaawansowanym stopniu w zakresie kombinatoryki, teorii grafów i elementarnej teorii liczb dającą matematyczne podstawy projektowania algorytmów (K_W01).
2. Rozumie i potrafi stosować notację asymptotyczną (K_W01).
3. Rozumie rolę i znaczenie konstrukcji rozumowań matematycznych (K_W01, K_W02).
Umiejętności
1. Potrafi analizować i rozwiązywać proste problemy z zakresu matematyki dyskretnej (K_U01).
2. Potrafi zrozumieć i stosować formalny opis obiektów matematycznych (K_U01, K_U03).
Kompetencje
1. Jest przygotowany do krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01).
2. Uznaje znaczenie wiedzy w rozwiązywaniu problemów poznawczych i praktycznych, potrafi wyszukiwać informacje w literaturze (K_K03).
Kryteria oceniania
Dopuszczenie do egzaminu w 1 terminie na podstawie wyników kolokwiów, kartkówek i punktów za aktywność.
Ocena w 1 terminie na podstawie średniej ważonej wyników egzaminu, kolokwiów, kartkówek i punktów za aktywność.
Do egzaminu w terminie poprawkowym dopuszczeni są wszyscy.
Ocena w terminie poprawkowym wyłącznie na podstawie wyniku egzaminu poprawkowego.
Szczegóły na kursie na moodlu.
Literatura
1. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 2013.
2. W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.
3. Z.Palka, A.Ruciński, Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne 2009
4. R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 2012.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: