Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2016/17
02JSHMQ
Discrete Mathematics
Corso di Laurea in Matematica Per L'Ingegneria - 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. L'accento verrà posto 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
L'assioma del buon ordinamento, forma forte e debole del principio di induzione.
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.
Funzioni generatrici e ricorsioni lineari.
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 da sotto per la complessità tramite gli alberi decisionali e strategie ottimali. Esempi e applicazioni, in particolare ai problemi di tassellamento e agli algoritmi di ordinamento.
Organizzazione dell'insegnamento
Durante il corso verranno discussi e svolti dai docenti numerosi esercizi, che copriranno tutti gli argomenti trattati.
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
Il corso sarà coperto per intero da dispense e altro materiale (comprendente esempi ed esercizi svolti) preparato dai docenti e reso disponibile online agli studenti iscritti al corso.
Per possibili approfondimenti, sarà 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
Criteri, regole e procedure per l'esame
L’esame consiste di una prova scritta con esercizi e domande .
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2016/17
Indietro



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