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.

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.

Sono richieste le nozioni di base su insiemi e funzioni, i fondamenti del calcolo in una variabile e dell’algebra lineare

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

Durante il corso vengono discussi e svolti dal docente numerosi esercizi, che coprono tutti gli argomenti trattati.

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)

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.