Matematyka dyskretna

* 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

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).