Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2017/18
02JSHMQ, 02JSHNG
Discrete Mathematics
Corso di Laurea in Matematica Per L'Ingegneria - Torino
Corso di Laurea Magistrale in Ingegneria Matematica - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Chiado' Piat Valeria ORARIO RICEVIMENTO O2 MAT/05 40 20 0 0 4
SSD CFU Attivita' formative Ambiti disciplinari
MAT/05 6 B - Caratterizzanti Formazione teorica
Presentazione
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.
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 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.
Prerequisiti / Conoscenze pregresse
Sono richieste le nozioni di base su insiemi e funzioni, i fondamenti del calcolo in una variabile e dell’algebra lineare
Programma
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
Organizzazione dell'insegnamento
Durante il corso vengono discussi e svolti dal docente numerosi esercizi, che coprono tutti gli argomenti trattati.
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
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)
Criteri, regole e procedure per l'esame
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.
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2017/18
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti