Scopo di questa parte 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.

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, dell’algebra lineare e della probabilità elementare.

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.

Durante il corso verranno discussi e svolti dai docenti numerosi esercizi, che copriranno tutti gli argomenti trattati.

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 della prima parte del corso, 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

L’esame consiste di una prova scritta con esercizi e domande teoriche. Alcune parti dell’esame potranno essere preventivamente superate durante il corso tramite lavori individuali di tipo homework ed in tal modo eliminate dalla prova scritta finale.