Discrete mathematics 1000-212bMD
* Mathematical induction and recursion
* Finite sums
* Binomial Coefficients
* Permutations and partitions
* Generating functions with application
* Counting methods:
- enumerators
- inclusion-exclusion principle
* Asymptotics:
- asymptotic notation
- Master theorem
* Elementary number theory:
- divisibility, primes, factorization
- gcd and Euclid's algorithm
* modular arithmetic:
- Fermat's little theorem and Euler's theorem
- Chinese remainder theorem
- solving modular equations
* Elements of the cryptography: Miller-Rabin primality and the RSA system
* Graphs:
- paths, trees and cycles
- Euler and Hamilton cycles
- bipartite graphs, transversals and Hall theorem
- planarity
- coloring
Type of course
Requirements
Course coordinators
Learning outcomes
Knowledge
1. Knowledge of combinatorics, graph theory and elementary number theory giving mathematical foundations for algorithm design. (K_W01).
2. Understanding and ability to apply the asymptotic notation (K_W01).
3. Understanding the role and importance of the construction of mathematical reasonings (K_W01, K_W02).
Skills
1. Ability to analyze and solve simple problems in discrete mathematics (K_U01).
2. Ability to understand and apply a formal description of mathematical objects (K_U01, K_U03).
Competence
1. Student is prepared to critically evaluate his or her knowledge and content received. (K_K01).
2. Student recognizes the importance of knowledge in solving cognitive and practical problems and searches
for information in literature (K_K03).
Assessment criteria
Written tests during the course, written exam.
Bibliography
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.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: