Servizi per la didattica
PORTALE DELLA DIDATTICA

Matematica discreta

02GQNMQ

A.A. 2021/22

Lingua dell'insegnamento

Italiano

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 A - Di base Formazione matematica di base
2020/21
Presentazione Scopo del corso è quello di fornire una introduzione ad alcune nozioni e 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 aim of the course is to provide an introduction to some basic notions and techniques of combinatorial mathematics and of the theory of discrete structures such as graphs and trees. Emphasis is placed on several issues (such as tessellation and counting problems, decision trees, complexity estimates for recursive procedures) which allow for natural formulation in the context of discrete mathematics.
Risultati di apprendimento attesi 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 modellizzare problemi concreti (ad esempio la pianificazione di eventi sotto determinati vincoli, l'ottimizzazione del percorso tra due località, l'analisi di strategie di gioco) mediante grafi con opportune proprietà. 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 main combinatorial and counting tools. Ability to set up, formalize and solve some typical counting and combinatorial problems. Knowledge, use and explicit resolution of linear recursions. Knowledge of the basic elements of graph theory. Ability to model concrete problems (for example planning events under certain constraints, optimizing the path between two locations, analyzing game strategies) using graphs with appropriate properties. Ability to translate some instances of concrete problems (for example recursive procedures or simple problems of tessellation and enumerative combinatorics) into the equivalent mathematical / combinatorial object.
Sono richieste le nozioni di base su insiemi, funzioni, ed i fondamenti del calcolo in una variabile
The basic notions on sets, functions, and of calculus for functions in one variable are required
Corrispondenze ed applicazioni. Relazioni di equivalenza ed ordine. Cardinalità. L'assioma del buon ordinamento, forma forte e debole del principio di induzione. 8 ore Primi problemi di conteggio. Alberi decisionali e processi ricorsivi. 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 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, problemi di colorazione ed applicazioni. Grafi bipartiti, problemi di matching e applicazioni. Matrice di adiacenza, cenni sulla teoria spettrale per i grafi, esempi di spettro. 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. 22 ore
Correspondences and applications. Equivalence and order relations. Cardinality. The awell ordering axiom, strong and weak form of the induction principle. 8 hours First counting problems. Decision trees and recursive processes. Functions and counting, the pigeonhole principle, the product rule and the additive principle. Selections with or without order, with or without repetitions. Permutations, binomial and multinomial coefficients, binomial formula. Classic examples. The inclusion-exclusion principle and applications. 22 hours Linear recursions and applications. 8 hours Unoriented graphs, walks, paths and cycles. Eulerian walks and Hamiltonian cycles. Trees. Combinatorial graph. Planar graphs, the Euler formula and its corollaries, coloring problems and applications. Bipartite graphs, matching problems and applications. Adjacency matrix, outline on spectral theory for graphs, examples of spectrum. Lower estimates for complexity through decision trees and optimal strategies. Examples and applications, in particular to tessellation problems and sorting algorithms. Outline of direct and weight graphs. 22 hours
Durante il corso vengono discussi e svolti dal docente numerosi esercizi, che coprono tutti gli argomenti trattati. Ai fini didattici e di valutazione, durante il corso, vengono proposte e monitorate dal docente attività in itinere quali, ad esempio, lo svolgimento di test di autovalutazione e la risoluzione di problemi, che richiedono la partecipazione attiva dello studente. Le modalità sono rese note dal docente all'inizio del corso.
During the course many exercises are discussed and carried out by the teacher, covering all the topics of the course. For didactic and evaluation purposes, during the course, ongoing activities are proposed and monitored by the teacher such as, for example, the conduct of self-assessment tests and the resolution of problems, which require the active participation of the student. The modalities are made known by the teacher at the beginning of the course.
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 content is fully covered by lecture notes and other material (including examples and exercises carried out) prepared by the teacher and made available online to students enrolled in the course. For further information, any text entitled "Discrete Mathematics", "Graph Theory" or similar variants is suitable for the purpose. Some specific examples are as follows: 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)
Modalità di esame: Prova orale facoltativa; Prova scritta su carta con videosorveglianza dei docenti;
L’esame consiste di una prova scritta di 90 minuti con problemi e domande, che possono essere sia a risposta aperta che a risposta chiusa, su tutti gli argomenti del corso. I problemi consentono di verificare la capacità acquisita dello studente nell'utilizzo della teoria dei grafi e e dei metodi di conteggio e combinatori descritti nel corso. Le domande consentono di verificare la conoscenza della parte teorica della materia. Il voto massimo è 30 lode. Durante l'esame scritto non è consentito l'uso di materiale didattico, calcolatrice e dispositivi elettronici, ad eccezione di quelli esplicitamente autorizzati. La prova orale è facoltativa, si tiene nello stesso appello della prova scritta, verte su tutti gli argomenti del corso, può essere richiesta dallo studente per migliorare il risultato ottenuto nella prova scritta, o dal docente nel caso in cui sia opportuno un approfondimento. In caso di prova orale, il voto finale è composto dalla valutazione complessiva di prova scritta e prova orale (che può far variare il voto sia in positivo sia in negativo, rispetto a quello della prova scritta). La valutazione finale dell'esame può essere integrata fino ad un massimo di 3 trentesimi con la valutazione delle attività in itinere effettivamente svolte dallo studente. Esempi di problemi e domande di precedenti prove scritte sono disponibili sulla pagina web del corso.
Exam: Optional oral exam; Paper-based written test with video surveillance of the teaching staff;
The exam consists of a written closed book examination, which lasts 90 minutes and consists of problems and questions (either multiple choice test, or open text questions) on all the topics of the course. The 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 questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. The maximum grade is 30 lode. During the written examination, the use of teaching materials, calculator, and electronic devices is not allowed, except those explicitly authorized. The oral exam is optional, it is held in the same session as the written test, it covers all the topics of the course, it can be requested by the student to improve the result obtained in the written test, or by the teacher if an in-depth study is appropriate. In the case of an oral test, the final grade is made up of the overall assessment of the written test and the oral test (which may increase or decrease vary the grade of the written test). The final assessment of the exam can be integrated up to a maximum of 3 out of 30 with the evaluation of the ongoing activities actually carried out by the student. Examples of problems and questions of previous written examinations are available on the web page of the course.
Modalità di esame: Prova scritta (in aula); Prova orale facoltativa; Prova scritta su carta con videosorveglianza dei docenti;
L’esame consiste di una prova scritta di 90 minuti con problemi e domande, che possono essere sia a risposta aperta che a risposta chiusa, su tutti gli argomenti del corso. I problemi consentono di verificare la capacità acquisita dello studente nell'utilizzo della teoria dei grafi e e dei metodi di conteggio e combinatori descritti nel corso. Le domande consentono di verificare la conoscenza della parte teorica della materia. Il voto massimo è di 30 lode. Durante l'esame scritto non è consentito l'uso di materiale didattico, calcolatrice e dispositivi elettronici, ad eccezione di quelli esplicitamente autorizzati. La prova orale è facoltativa, si tiene nello stesso appello della prova scritta, verte su tutti gli argomenti del corso, può essere richiesta dallo studente per migliorare il risultato ottenuto nella prova scritta, o dal docente nel caso in cui sia opportuno un approfondimento. In caso di prova orale, il voto finale è composto dalla valutazione complessiva di prova scritta e prova orale (che può far variare il voto sia in positivo sia in negativo, rispetto a quello della prova scritta). La valutazione finale dell'esame può essere integrata fino ad un massimo di 3 trentesimi con la valutazione delle attività in itinere effettivamente svolte dallo studente.. Esempi di problemi e domande di precedenti prove scritte sono disponibili sulla pagina web del corso.
Exam: Written test; Optional oral exam; Paper-based written test with video surveillance of the teaching staff;
The exam consists of a written closed book examination, which lasts 90 minutes and consists of problems and questions (either multiple choice test, or open text questions) on all the topics of the course. The 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 questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. The maximum grade is 30 lode. During the written examination, the use of teaching materials, calculator, and electronic devices is not allowed, except those explicitly authorized. The oral exam is optional, it is held in the same session as the written test, it covers all the topics of the course, it can be requested by the student to improve the result obtained in the written test, or by the teacher if an in-depth study is appropriate. In the case of an oral test, the final grade is made up of the overall assessment of the written test and the oral test (which may increase or decrease vary the grade of the written test). The final assessment of the exam can be integrated up to a maximum of 3 out of 30 with the evaluation of the ongoing activities actually carried out by the student. Examples of problems and questions of previous written examinations are available on the web page of the course.


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