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.

Le conoscenza acquisite in questo corso includeranno diverse tecniche di base della matematica combinatoria, con particolare attenzione alle possibili applicazioni. In particolare, alla fine del corso, ci si aspetta che lo studente sia in grado di impostare, formulare precisamente e risolvere alcuni tipici problemi della matematica combinatoria, con particolare riferimento a quelli che nascono dalle applicazioni.

Sono richieste le nozioni di base su insiemi e funzioni, oltre ai fondamenti del calcolo in una variabile.

L'assioma del buon ordinamento, forma forte e debole del principio di induzione (6 ore).
Primi problemi di conteggio. Alberi decisionali e processi ricorsivi (6 ore).
Funzioni e conteggio, il principio dei cassetti, il principio moltiplicativo e quello additivo (8 ore).
Selezioni con o senza ordine, con o senza ripetizioni. Permutazioni, coefficienti binomiali e multinomiali, formula del binomio. Il principio del crivello (8 ore).
Funzioni generatrici e ricorsioni lineari (8 ore).
Grafi orientati e 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 (12 ore).
Stime da sotto per la complessitą tramite gli alberi decisionali e strategie ottimali. Applicazioni ed esempi, in particolare ai problemi di tassellamento e agli algoritmi di ricerca e ordinamento (12 ore).

Durante le esercitazioni, gli esercizi copriranno il materiale discusso a lezione e saranno svolti dal docente.

Lecture Notes on "Discrete Mathematics" by L. Lovįsz and K. Vesztergombi.
Norman L. Biggs, Discrete Mathematics, Clarendon Press, Oxford, 1985.

Esame scritto.