Servizi per la didattica
PORTALE DELLA DIDATTICA

Discrete Mathematics

02JSHMQ

A.A. 2020/21

Lingua dell'insegnamento

Inglese

Corsi di studio

Corso di Laurea in Matematica Per L'Ingegneria - Torino

Organizzazione dell'insegnamento
Didattica Ore
Docenti
Docente Qualifica Settore h.Lez h.Es h.Lab h.Tut Anni incarico
Collaboratori
Espandi

Didattica
SSD CFU Attivita' formative Ambiti disciplinari
MAT/05 6 B - Caratterizzanti Formazione teorica
2019/20
The course is taught in English. Scopo del corso è quello di fornire una introduzione ad alcune tecniche di base della matematica combinatoria e della teoria delle strutture discrete quali grafi ed alberi. Viene posto l'accento su diverse questioni (quali ad esempio problemi di tassellamento e di conteggio, alberi decisionali, stime di complessità per le procedure ricorsive) che ammettono una formulazione naturale nel contesto della matematica discreta.
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.
Conoscenza del principio di induzione e suo utilizzo nella teoria e nella applicazioni. Conoscenza dei principali strumenti combinatori e di conteggio. Capacità di impostare, formalizzare e risolvere alcuni tipici problemi di conteggio e combinatoria. Conoscenza, utilizzo e risoluzione esplicita delle ricorsioni lineari. Conoscenza degli elementi di base di teoria dei grafi. Capacità di mettere in relazione proprietà qualitative e quantitative di un grafo con informazioni parziali sul suo spettro. Capacità di tradurre alcune istanze di problemi concreti (ad esempio procedure ricorsive o semplici problemi di tassellamento e di combinatoria enumerativa) nell’equivalente oggetto matematico/combinatorio.
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.
Sono richieste le nozioni di base su insiemi e funzioni, i fondamenti del calcolo in una variabile e dell’algebra lineare
Basic knowledge of sets and functions. Basic notions of calculus and linear algebra.
Primi problemi di conteggio. Alberi decisionali e processi ricorsivi. Invarianti. Funzioni e conteggio, il principio dei cassetti, il principio moltiplicativo e quello additivo. Selezioni con o senza ordine, con o senza ripetizioni. Permutazioni, coefficienti binomiali e multinomiali, formula del binomio. Esempi classici. Il principio di inclusione-esclusione ed applicazioni. 22 ore Ricorsioni lineari ed applicazioni. 8 ore L'assioma del buon ordinamento, forma forte e debole del principio di induzione. 4 ore Grafi non orientati, passeggiate, cammini e cicli. Passeggiate Euleriane e cicli Hamiltoniani. Alberi. Combinatoria dei grafi. Grafi planari, la formula di Eulero e i suoi corollari. Matrice di adiacenza e teoria spettrale dei grafi. Esempi di spettri. Stime inferiori per la complessità tramite gli alberi decisionali e strategie ottimali. Esempi e applicazioni, in particolare ai problemi di tassellamento e agli algoritmi di ordinamento. Cenno ai grafi diretti e con peso. 26 ore
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
Durante il corso vengono discussi e svolti dal docente numerosi esercizi, che coprono tutti gli argomenti trattati.
Several exercises covering all the topics are discussed and solved during classes.
Il contenuto del corso è coperto per intero da dispense e altro materiale (comprendente esempi ed esercizi svolti) preparato dal docente e reso disponibile online agli studenti iscritti al corso. Per possibili approfondimenti, è adatto allo scopo qualsiasi testo dal titolo "Discrete Mathematics", "Graph Theory" o analoghe varianti. Alcuni esempi specifici sono i seguenti: L. Lovász e K. Vesztergombi , "Lecture Notes on Discrete Mathematics" (disponibile online). N. L. Biggs, "Discrete Mathematics". Clarendon Press, Oxford, 1985. A. E. Brower e W. H. Haemers, "Spectra of graphs". Springer, New York, 2012 K.H. Rosen. Discrete mathematics and its applications (7th edition) (disponibile 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;
L’esame consiste di norma di una prova scritta di due ore, con esercizi e domande. In alternativa, lo studente può sostenere una prova scritta durante l’ultima settimana del corso e completare l’esame con un colloquio orale durante la prima sessione successiva al termine del corso. Durante l’esame non è consentito l’uso di materiali didattici e calcolatrice.
Exam: written test;
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.


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