University of Warsaw - Central Authentication System

Discrete mathematics

General data

Course ID:	1000-212bMD
Erasmus code / ISCED:	11.001 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0540) Mathematics and statistics, not further defined The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Discrete mathematics
Name in Polish:	Matematyka dyskretna
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	Obligatory courses for 1st year Computer Science Obligatory courses for 2nd grade JSIM (3I+4M) Obligatory courses for 2nd grade JSIM (3M+4I)
ECTS credit allocation (and other scores):	7.00 Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	Polish
Type of course:	obligatory courses
Requirements:	Foundations of mathematics 1000-211bPM Geometry with linear algebra 1000-211bGAL Mathematical analysis for computer science I 1000-211bAM1
Short description:	Mathematical concepts essential for design and analysis of algorithms: combinatorics, graph theory and number theory.
Full description:	* 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
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.
Learning outcomes:	(in Polish) 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).
Assessment methods and assessment criteria:	Written tests during the course, written exam.

Classes in period "Summer semester 2023/24" (in progress)

Time span:	2024-02-19 - 2024-06-16	Selected timetable range: weekly course term Navigate to timetable MO WYK CW CW CW CW CW CW CW CW CW TU W TH WYK FR CW CW CW CW CW CW CW CW CW
Type of class:	Classes, 60 hours more information Lecture, 45 hours more information
Coordinators:	Adam Malinowski
Group instructors:	Łukasz Bożyk, Kunal Dutta, Soumik Dutta, Paweł Górecki, Mirosław Kowaluk, Adam Malinowski, Tomáš Masařík, Marcin Smulewicz
Students list:	(inaccessible to you)
Examination:	Examination

Classes in period "Summer semester 2024/25" (future)

Time span:	2025-02-17 - 2025-06-08	Selected timetable range: weekly course term Navigate to timetable
Type of class:	Classes, 60 hours more information Lecture, 45 hours more information
Coordinators:	Adam Malinowski
Group instructors:	Łukasz Bożyk, Kunal Dutta, Soumik Dutta, Paweł Górecki, Mirosław Kowaluk, Adam Malinowski, Oskar Skibski
Students list:	(inaccessible to you)
Examination:	Examination

Course descriptions are protected by copyright.
Copyright by University of Warsaw.