Matematyka dyskretna

obowiązkowe

Analiza matematyczna inf. I 1000-211bAM1
Geometria z algebrą liniową 1000-211bGAL
Podstawy matematyki 1000-211bPM

Aparat matematyczny niezbędny do układania i analizy algorytmów: elementy kombinatoryki, teorii grafów i teorii liczb.

* 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

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.

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

Dopuszczenie do egzaminu w 1 terminie na podstawie wyników kolokwiów, quizów i punktów za aktywność.

Ocena w 1 terminie na podstawie średniej ważonej wyników egzaminu, kolokwiów, quizów 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.