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
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: