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 - absolwent zna i rozumie:
- ma wiedzę w zaawansowanym stopniu w zakresie kombinatoryki, teorii grafów i elementarnej teorii liczb dającą matematyczne podstawy projektowania algorytmów (K_W01),
- rozumie i potrafi stosować notację asymptotyczną (K_W01),
- rozumie rolę i znaczenie konstrukcji rozumowań matematycznych (K_W01).
Umiejętności - absolwent potrafi:
- zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01),
- samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09).
Kompetencje społeczne - absolwent jest gotów do:
- uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (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: