Summer Semester 2009/10
Summer Semester 2010/11
Winter Semester 2010/11
Summer Semester 2011/12
Summer Semester 2013/14
Selected Topics of Discrete Mathematics and Their Applications in Computer Science (elective) I24000a
Course content: Aithmetic operations on big integers.
The extended Euclid algorithm. The algorithms of decomposition of integers and primary tests.
Fast algorithm for powers in modular arithmetic. The discrete logarithm problem. Public key cryptografic systems.
Basic notions of combinatorial configurations.
Codeing. Applications of combinatorial configurations in coding theory.
Hall's mariage theorem and its applications in latin squares (sudoku).
Mini-max theorems.
Matching theory with two sided preferences. Algorithm of Gale and Shapley and its applications.
Permutations in symmetric cryptography. The mathematics of Enigma.
Learning outcomes: Knowledge on applications of selected topics of discrete mathematics; skills of transformation of theoretical ideas into practical applications.
(in Polish) Rodzaj przedmiotu
Course coordinators
Bibliography
a) basic references:
1. D. Knuth, The Art of Computer Programming, Wydawnictwo Naukowo-Techniczne, Warszawa 2003.
2. Victor Bryant, Aspects of combinatorics, Cambridge University Press.
3. Robin J. Wilson, Introduction to graph theoy, Wydawnictwo Naukowe PWN, Warszawa 1998.
b) supplementary references:
1. Witold Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 1982.
2. Yan Song, Number theory in computer science, PWN, Warszawa 2006.
3. Martin Aigner, Gunter M. Ziegler, The Proofs from the Book, Wydawnictwo Naukowe PWN, Warszawa 2004.