Wybrane zagadnienia matematyki dyskretnej w zastosowaniach informatycznych (przedmiot obieralny - K1) I24000a

Treści programowe:
Algorytmy operacji na wielkich liczbach całkowitych i ich złożoność.
Rozszerzony algorytm Euklidesa. Algorytmy rozkładu liczb na czynniki pierwsze i algorytmy testujące pierwszość liczb. Szybkie potęgowanie modularne. Problem logarytmu dyskretnego. Systemy kryptograficzne z kluczem publicznym, ich znaczenie i zastosowania.
Podstawowe pojęcia z teorii konfiguracji kombinatorycznych.
Porozumiewanie się bez błędów. Pojęcie kodu. Zastosowania teorii konfiguracji w teorii kodowania.
Twierdzenie Halla o kojarzeniu małżeństw, zastosowania w kwadratach łacińskich (sudoku).
Twierdzenia minimaxowe.
Zagadnienie skojarzeń dwustronnych. Algorytm Gale'a i Shapley'a i jego zastosowania.
Permutacje w kryptografii symetrycznej. Matematyka Enigmy. Szyfrowanie, deszyfrowanie.

Efekty kształcenia: wiedza z zakresu zastosowań wybranych zagadnień matematyki dyskretnej; umiejętności tłumaczenia zagadnień teoretycznych na konkretne zastosowania i implementacji algorytmów