Politecnico di Torino
Politecnico di Torino
Politecnico di Torino
Academic Year 2010/11
Discrete Mathematics
Master of science-level of the Bologna process in Telecommunications Engineering - Torino
Master of science-level of the Bologna process in Mathematical Engineering - Torino
Teacher Status SSD Les Ex Lab Tut Years teaching
Tilli Paolo ORARIO RICEVIMENTO PO MAT/05 60 0 0 0 6
SSD CFU Activities Area context
MAT/05 6 C - Affini o integrative Attivitŕ formative affini o integrative
Subject fundamentals
The course is taught in English.
The main aim of the course is to provide a basic introduction to some standard techniques of combinatorial mathematics and discrete structures such as graphs and trees. Emphasis will be given to several problems (such as questions concerning tiling and counting, decision trees, estimates on the complexity for recursive procedures, etc.) which admit a natural formulation within the framework of discrete mathematics.
Expected learning outcomes
The knowledge obtained from this course will include several standard techniques of combinatorial mathematics, with emphasis on possible applications. In particular, by the end of the course, it is expected that students will be able to set out, formulate precisely and solve typical problems in combinatorial mathematics, especially those arising in applications.
Prerequisites / Assumed knowledge
Basic notions on sets and functions, and some basic calculus are required.
The well-ordering axiom, strong and weak form of the induction principle (6 hours).
Basic counting problems. Decision trees and recursive processes (6 hours).
Functions and counting, the pigeon-hole principle, the multiplicative principle, the additive principle (8 hours).
Ordered and unordered selections with and without repetition. Permutations, binomial and multinomial coefficients, the binomial formula. The sieve principle (8 hours).
Generating functions and linear recurrences (8 hours).
Ordered and unordered graphs, walks, paths, cycles. Eulerian walks and Hamiltonian cycles. Trees. Combinatorics of graphs. Planar graphs, Euler formula and its corollaries (12 hours).
Complexity lower bounds via decision trees and optimal strategies. Applications and examples, in particular to tiling problems, searching and sorting algorithms (12 hours).
Delivery modes
Exercises during tutorials will cover the subjects discussed during the lectures, and will be carried out by the teacher.
Texts, readings, handouts and other learning resources
Lecture Notes on "Discrete Mathematics" by L. Lovász and K. Vesztergombi.
Norman L. Biggs, Discrete Mathematics, Clarendon Press, Oxford, 1985.
Assessment and grading criteria
Written examination.

Programma definitivo per l'A.A.2010/11

© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)