02JSHMQ, 02JSHLP, 02JSHNG

A.A. 2019/20

Course Language

Inglese

Course degree

1st degree and Bachelor-level of the Bologna process in Matematica Per L'Ingegneria - Torino

1st degree and Bachelor-level of the Bologna process in Electronic And Communications Engineering (Ingegneria Elettronica E Delle Comunicazioni) - Torino

Master of science-level of the Bologna process in Ingegneria Matematica - Torino

Course structure

Teaching | Hours |
---|---|

Lezioni | 30 |

Esercitazioni in aula | 30 |

Teachers

Teacher | Status | SSD | h.Les | h.Ex | h.Lab | h.Tut | Years teaching |
---|---|---|---|---|---|---|---|

Chiado' Piat Valeria | Professore Ordinario | MAT/05 | 30 | 30 | 0 | 0 | 4 |

Teaching assistant

Context

SSD | CFU | Activities | Area context |
---|---|---|---|

MAT/05 | 6 | B - Caratterizzanti | Formazione teorica |

2019/20

The main goal of the course is to introduce some fundamental 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 fundamental 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.

Revisiion about 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

Revisiion about 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

Several exercises covering all the topics are discussed and solved during classes.

Several exercises covering all the topics are discussed and solved during classes.

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).

Gli studenti e le studentesse con disabilitą o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unitą Special Needs, al fine di permettere al/la docente la declinazione pił idonea in riferimento alla specifica tipologia di esame.

The exam consists of a written examination, which lasts 2 hours and includes exercises and questions on all the topics of the course.
As an alternative, the students may solve written exercises and questions during the last week of the course and conclude the exam with an oral interview during the first exam session after the end of the course.
Teaching material and calculator are not allowed during the exam.

In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY