Corso di Laurea in Matematica Per L'Ingegneria - Torino Corso di Laurea in Electronic And Communications Engineering (Ingegneria Elettronica E Delle Comunicazioni) - Torino
Presentazione
Scopo dell'insegnamento è 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)
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)
Slides; Dispense; Esercizi risolti; Video lezioni tratte da anni precedenti; Strumenti di auto-valutazione;
Lecture slides; Lecture notes; Exercise with solutions ; Video lectures (previous years); Self-assessment tools;
E' possibile sostenere l’esame in anticipo rispetto all’acquisizione della frequenza
You can take this exam before attending the course
Modalità di esame: Prova scritta (in aula); Prova orale facoltativa;
Exam: Written test; Optional oral exam;
...
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.
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.
Exam: Written test; Optional oral exam;
L’esame consiste di una prova scritta 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.
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.