Servizi per la didattica
PORTALE DELLA DIDATTICA

Discrete Mathematics

03JSHLP

A.A. 2018/19

Course Language

English

Course degree

1st degree and Bachelor-level of the Bologna process in Electronic And Communications Engineering - Torino

Borrow

01OUJNG

Course structure
Teaching Hours
Lezioni 48
Esercitazioni in aula 12
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Chiado' Piat Valeria Professore Ordinario MAT/05 48 12 0 0 4
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
ING-INF/04
MAT/05
2
4
C - Affini o integrative
A - Di base
Attività formative affini o integrative
Matematica, informatica e statistica
2018/19
The main goal of the course is to introduce some basic techniques of combinatorial mathematics and discrete structures such as graphs and trees. Emphasis is laid on several questions (such as tiling and counting problems, decision trees, complexity estimates for recursive procedures) that can be formulated in a natural way within the framework of discrete mathematics.
The main goal of the course is to introduce some basic techniques of combinatorial mathematics and discrete structures such as graphs and trees. Emphasis is laid on several questions (such as tiling and counting problems, decision trees, complexity estimates for recursive procedures) that can be formulated in a natural way within the framework of discrete mathematics.
Knowledge of the induction principle and its use in theory and applications. Knowledge of the basic tools of combinatorics and counting. Ability to set up, formalize and solve some typical problems of counting and combinatorics. Knowledge, usage and solution of linear recurrences. Knowledge of basic graph theory. Ability to find connections between certain qualitative/quantitative properties of a graph and partial information on its spectrum. Ability to translate some concrete problems and situations (e.g. recursive procedures or simple questions concerning tilings or enumerative combinatorics) into the equivalent mathematical/combinatorial object.
Knowledge of the induction principle and its use in theory and applications. Knowledge of the basic tools of combinatorics and counting. Ability to set up, formalize and solve some typical problems of counting and combinatorics. Knowledge, usage and solution of linear recurrences. Knowledge of basic graph theory. Ability to find connections between certain qualitative/quantitative properties of a graph and partial information on its spectrum. Ability to translate some concrete problems and situations (e.g. recursive procedures or simple questions concerning tilings or enumerative combinatorics) into the equivalent mathematical/combinatorial object.
Basic knowledge of sets and functions. Basic notions of calculus and linear algebra
Basic knowledge of sets and functions. Basic notions of calculus and linear algebra
First counting problems. Decision trees and recursive processes. Invariants. Functions and counting, the Pigeonhole Principle, the multiplicative and the additive principles. Selections with or without ordering, with or without repetitions. Permutations, binomial and multinomial coefficients, binomial expansion. Classical examples. The inclusion-exclusion principle and applications. 22 hours Generating functions and linear recurrences. 8 hours The Well Ordering Axiom. Weak and strong form of the Induction Principle. 4 hours Undirected graphs, walks, paths and cycles. Eulerian and Hamiltonian cycles. Trees. Combinatorial graph theory. Planar graphs, the Euler formula and its consequences. Adjacency matrix and spectral graph theory. Examples of spectra. Complexity estimates through decision trees and optimal strategies. Examples and applications, in particular to tiling problems and sorting algorithms. Directed and weighted graphs. Basic notions on directed and weighted graphs. 26 hours
First counting problems. Decision trees and recursive processes. Invariants. Functions and counting, the Pigeonhole Principle, the multiplicative and the additive principles. Selections with or without ordering, with or without repetitions. Permutations, binomial and multinomial coefficients, binomial expansion. Classical examples. The inclusion-exclusion principle and applications. 22 hours Generating functions and linear recurrences. 8 hours The Well Ordering Axiom. Weak and strong form of the Induction Principle. 4 hours Undirected graphs, walks, paths and cycles. Eulerian and Hamiltonian cycles. Trees. Combinatorial graph theory. Planar graphs, the Euler formula and its consequences. Adjacency matrix and spectral graph theory. Examples of spectra. Complexity estimates through decision trees and optimal strategies. Examples and applications, in particular to tiling problems and sorting algorithms. Directed and weighted graphs. Basic notions on directed and weighted graphs. 26 hours
Lectures and practice classes are used to obtain the expected learning outcomes in terms of knowledge and abilities. During practice classes several exercises covering all the topics are discussed and solved.
Lectures and practice classes are used to obtain the expected learning outcomes in terms of knowledge and abilities. During practice classes several exercises covering all the topics are discussed and solved.
The course is fully covered by Lecture Notes and other material (including examples and exercises with solutions) provided by the teacher and available online for the students attending the course. For possible deepening, any book entitled Discrete Mathematics, Graph Theory or similar will be fit for the purpose. Some specific examples are the following: L. Lovász and K. Vesztergombi , Lecture Notes on Discrete Mathematics" (available online). N. L. Biggs, Discrete Mathematics. Clarendon Press, Oxford, 1985. A. E. Brower and W. H. Haemers, Spectra of graphs. Springer, New York, 2012 K. H. Rosen. Discrete Mathematics and its applications, 7th edition (available online).
The course is fully covered by Lecture Notes and other material (including examples and exercises with solutions) provided by the teacher and available online for the students attending the course. For possible deepening, any book entitled Discrete Mathematics, Graph Theory or similar will be fit for the purpose. Some specific examples are the following: L. Lovász and K. Vesztergombi , Lecture Notes on Discrete Mathematics" (available online). N. L. Biggs, Discrete Mathematics. Clarendon Press, Oxford, 1985. A. E. Brower and W. H. Haemers, Spectra of graphs. Springer, New York, 2012 K. H. Rosen. Discrete Mathematics and its applications, 7th edition (available online).
Modalità di esame: prova scritta;
The exam consists of a written closed book examination, which lasts 2 hours and consists of 4 exercises containing both numerical problems and open text questions on all the topics of the course. The numerical problems allow to check the ability of the student to solve problems using graph theory and the counting and combinatorics methods described in the course. The open text questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. Examples of problems and questions of previous exams are available on the web page of the course. The maximum grade is 30 lode.
Exam: written test;
The exam consists of a written closed book examination, which lasts 2 hours and consists of 4 exercises containing both numerical problems and open text questions on all the topics of the course. The numerical problems allow to check the ability of the student to solve problems using graph theory and the counting and combinatorics methods described in the course. The open text questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. Examples of problems and questions of previous exams are available on the web page of the course. The maximum grade is 30 lode.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il