Classe di Ingegneria dell'Informazione
Corso di laurea in Ingegneria Informatica. Anno 2004-2005
Corso Integrato di Matematica Discreta
Parte 1 - Calcolo Combinatorio
Periodo: 22 novembre 2004 - 22 Gennaio 2005, 2.5 CFU
Tenuto da: prof. Giuseppe Modica modica@dma.unifi.it
- M. Cerasoli, F. Eugeni, M. Protasi, Elementi di matematica discreta,
Zanichelli, 1988.
- L. Anderson, A First Course in Discrete Mathematics, Springer, 2000.
- C. Liu, Introduction to combinatorial mathematics, Mc-Graw-Hill, New York.
Di norma il materiale delle lezioni e' contenuto nel volume di M. Cerasoli,
F. Eugeni e M. Protasi.
- 25-11-04 --- 2 ore -
- Modelli di dati: Mappe e parole, Mappe iniettive, mappe crescenti,
mappe non decrescenti. Estrazioni.
- Strumenti analitici: le funzioni generatrici e l'induzione.
La formula del binomio e applicazioni ai coefficienti binomiali.
- vedi Cerasoli-Eugeini-Protasi, Capitolo 1.
- 26-11-04 --- 2 ore -
- Modelli di dati: Collocazioni. Statistiche di Boltzmann,
Bose--Einstein e Fermi--Dirac.
- Insiemi. Multiinsiemi.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 1.
- 30-11-04 --- 2 ore -
- Esercizi vari su coefficienti binomiali, insiemi e multiinsiemi.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 1. e Liu, Capitolo~1.
- 02-12-04 -- 2 ore -
- Esercizi vari su composizioni di interi, distribuzione multinomiale.
- Distanza di Hamming e distanza $L_1$. Codici binari.
Codici $r$-correttori. Stima di Hamming.
- 07-12-04 -- 2 ore -
- Codici $r$-correttori: stima di Gilbert.
- Passeggiate crescenti e Numeri di Catalan. Derivazione induttiva
e diretta. Problema di Eulero. Alberi binari piantati con
$2n+1$ vertici.
- 09-12-04 -- 2 ore - Non tenuta
- 14-12-04 -- 2 ore -
- Cardinalit\`a delle mappe surgettive: conteggio per inversione. Collocazioni
di oggetti distinti in scatole distinte con almeno uno per scatola.
Collocazioni di oggetti distinti in scatole indistinte: numeri di
Stirling di prima e seconda specie e numeri di Bell.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 3.
- 16-12-04 -- 2 ore -
- Formula di inclusione-esclusione: dimostrazione con le funzioni
caratteristiche. Valenza di un punto . Punti di valenza $k$.
Applicazione al calcolo della cardinalit\`a delle mappe surgettive.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 3.
- 11-01-05 -- 2 ore -
- Permutazioni senza punti fissi: calcolo per induzione, per
inversione e con la formula di inclusione--esclusione.
- Il problema delle cene conviviali.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 3.
- 13-01-05 -- 2 ore -
- Colorazioni di un grafo: Il polinomio di Birkhoff.
- Numero di alberi con $n$ nodi distinti. Algoritmo di Pr\'ufer.
- Insiemi semiordinati: esempi e definizioni. L'algebra di incidenza.
Relazione con le matrici triangolari.
- 18-01-05 -- 2 ore -
- Prodotto di funzioni dell'algebra di incidenza.
Propriet\`a associativa del prodotto.
- Inversa destra e sinistra di una funzione dell'algebra di incidenza.
La zeta di Riemann e la sua inversa: la
funzione di M\"obius: formula iterativa.
La formula di inversione generale su insiemi semiordinati.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 6.
- 20-01-05 -- 2 ore -
- Funzione di M\"obius dell'insieme semiordinato delle parti e
formula di inclusione-esclusione.
- Funzione di M\"obius dei naturali semiordinato dalla divisibilit\`a.
Calcolo della funzione di Eulero. Il problema delle collane.
- vedi Cerasoli-Eugeni-Protasi, Capitolo 6.
Lezioni: 22h.