Scopo dell'insegnamento è quello di fornire una introduzione ad alcune nozioni e 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 modellizzare problemi concreti (ad esempio la pianificazione di eventi sotto determinati vincoli, l'ottimizzazione del percorso tra due località, l'analisi di strategie di gioco) mediante grafi con opportune proprietà. 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, funzioni, ed i fondamenti del calcolo in una variabile

Corrispondenze ed applicazioni. Relazioni di equivalenza ed ordine. Cardinalità. L'assioma del buon ordinamento, forma forte e debole del principio di induzione. 8 ore Primi problemi di conteggio. Alberi decisionali e processi ricorsivi. 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 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, problemi di colorazione ed applicazioni. Grafi bipartiti, problemi di matching e applicazioni. Matrice di adiacenza, cenni sulla teoria spettrale per i grafi, esempi di spettro. 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. 22 ore

Durante il corso vengono discussi e svolti dal docente numerosi esercizi, che coprono tutti gli argomenti trattati. Ai fini didattici e di valutazione, durante il corso, vengono proposte e monitorate dal docente attività in itinere quali, ad esempio, lo svolgimento di test di autovalutazione e la risoluzione di problemi, che richiedono la partecipazione attiva dello studente. Le modalità sono rese note dal docente all'inizio del corso.

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)

Slides; Dispense; Esercizi risolti; Video lezioni tratte da anni precedenti; Strumenti di auto-valutazione;

E' possibile sostenere l’esame in anticipo rispetto all’acquisizione della frequenza

Modalità di esame: Prova scritta (in aula); Prova orale facoltativa;

Exam: Written test; Optional oral exam;

... L’esame consiste di una prova scritta di 90 minuti con problemi e domande, che possono essere sia a risposta aperta che a risposta chiusa, su tutti gli argomenti del corso. I problemi consentono di verificare la capacità acquisita dello studente nell'utilizzo della teoria dei grafi e e dei metodi di conteggio e combinatori descritti nel corso. Le domande consentono di verificare la conoscenza della parte teorica della materia. Il voto massimo è 30 lode. Durante l'esame scritto non è consentito l'uso di materiale didattico, calcolatrice e dispositivi elettronici, ad eccezione di quelli esplicitamente autorizzati. La prova orale è facoltativa, si tiene nello stesso appello della prova scritta, verte su tutti gli argomenti del corso, può essere richiesta dallo studente per migliorare il risultato ottenuto nella prova scritta, o dal docente nel caso in cui sia opportuno un approfondimento. In caso di prova orale, il voto finale è composto dalla valutazione complessiva di prova scritta e prova orale (che può far variare il voto sia in positivo sia in negativo, rispetto a quello della prova scritta). La valutazione finale dell'esame può essere integrata fino ad un massimo di 3 trentesimi con la valutazione delle attività in itinere effettivamente svolte dallo studente. Esempi di problemi e domande di precedenti prove scritte sono disponibili sulla pagina web del corso.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.