Introduzione all'uso della Matematica Discreta e della Combinatoria Enumerativa nell'Informatica. Serie formali e funzioni generatrici. Teoria delle specie di strutture. Funzioni generatrici razionali e algebriche. Cenni a metodi di analisi asintotica per la stima dei coefficienti di una funzione generatrice.
Generazione esaustiva di strutture combinatorie: algoritmi lessicografici e codici Gray..
Enumerative Combinatorics vol.I e II
CAMBRIDGE University Press.
E. Munarini, N. Zagaglia Salvi, Matematica Discreta, Città Studi Edizioni.
D.E. Knuth, The Art of Computer Programming, vol. 4, Addison-Wesley
Obiettivi Formativi
Conoscenze:
Utilizzo delle funzioni generatrici di enumerazione delle strutture combinatorie, anche in connessione con l’analisi degli algoritmi.
Tecniche per la generazione di strutture combinatorie.
Competenze acquisite:
Competenze nel campo della Combinatoria e delle sue applicazioni nei problemi informatici.
Capacità acquisite al termine del corso:
Al termine del corso gli studenti dovrebbero aver acquisito la capacità di affrontare e risolvere un elevato numero di problemi di enumerazione con lo strumento delle funzioni generatrici, anche in vista di applicazioni all’analisi degli algoritmi. Dovrebbero inoltre essere in grado di utilizzare e progettare algoritmi per la generazione di strutture combinatorie.
Prerequisiti
Corsi raccomandati:
Informatica
Algebra
Strutture Discrete
Linguaggi Formali e Codici
Logica e Calcolabilità
Metodi Didattici
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attività formative di tipo individuale: 153
Numero di ore relative alle attività in aula: 72
Numero di ore relative ad attività di laboratorio (lezioni in laboratorio): 0
Numero di ore relative ad attività di esercitazioni (in laboratorio e in campo): 0
Numero di ore relative ad attività seminariali: 0
Numero di ore relative ad attività di stage: 0
Numero di ore per prove in itinere: 0
Altre Informazioni
Frequenza delle lezioni ed esercitazioni:
Non obbligatoria
Strumenti a supporto della didattica:
Introduzione all’uso della Matematica Discreta e della Combinatoria Enumerativa in Informatica con esempi e applicazioni.
Introduzione del concetto di funzione generatrice ed esempi. Algebra delle serie formali di potenze. Teoria delle specie di strutture: concetti introduttivi di teoria delle categorie, nozione di specie combinatoria, principali operazioni combinatorie sulle specie, applicazioni. Funzioni generatrici razionali e classi di oggetti razionali (cammini nel piano, poliomini, alberi, permutazioni). Teorema di inversione di Lagrange. Funzioni generatrici algebriche e classi di oggetti algebriche (cammini nel piano, poliomini, alberi, permutazioni). Metodologia di Schutzenberger. Cenni a metodi di analisi asintotica per la stima dei coefficienti di una funzione generatrice; applicazioni all’analisi degli algoritmi.
Generazione di oggetti combinatori (tuple, permutazioni, partizioni, combinazioni, alberi). Algoritmi lessicografici. Codici Gray combinatori: aspetti algoritmici e graph-theoretic.