en
Politecnico di Torino
Anno Accademico 2013/14
02JSHOT
Discrete Mathematics
Corso di Laurea Magistrale in Ingegneria Delle Telecomunicazioni (Telecommunications Engineering) - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Tilli Paolo ORARIO RICEVIMENTO PO MATH-03/A 40 20 0 0 6
SSD CFU Attivita' formative Ambiti disciplinari
MAT/05 6 C - Affini o integrative A11
Esclusioni:
02KRR
Presentazione
The course is taught in English.

Il principale obiettivo 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, oltre ai fondamenti del calcolo in una variabile.
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 dal docente 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 dal docente 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 in una prova scritta ed una eventuale prova orale facoltativa. La prova scritta si compone tipicamente di quattro esercizi, ciascuno frazionato in più punti per facilitarne lo svolgimento e la relativa correzione, modellati sulla tipologia degli esercizi discussi a lezione e atti ad accertare l’apprendimento delle tecniche insegnate nel corso. Esempi di vecchie prove di esame, con le relative soluzioni, sono resi disponibili online. L’eventuale prova orale potrà avvenire su richiesta dello studente, dopo il superamento della prova scritta con un voto non inferiore a 18/30, e sarà incentrata sulla teoria presentata a lezione. Essa comporterà nel voto finale una variazione da un minimo di -3 ad un massimo di +3 punti rispetto al punteggio conseguito nella prova scritta.
Orario delle lezioni
Statistiche superamento esami
Programma definitivo per l'A.A.2013/14
Indietro