Classe di Ingegneria dell'Informazione
Corso di laurea in Ingegneria Informatica. Anno 2005-2006
Periodo: 16 gennaio 2006 - 17 marzo 2006, 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.
Di norma il materiale delle lezioni e' contenuto nel volume di M. Cerasoli,
F. Eugeni e M. Protasi.
- 01-02-06 -- 2 ore
- Il calcolo combinatorico: modelli: estrazioni, insiemi e mappe,
liste, collocazioni. Strumenti: calcolo in due modi distinti,
calcolo per inversione, funzioni generatrici.
- Sottoinsiemi di un insieme. Coefficienti binomiali. Formule varie.
Calcoli vari diretti e con l'uso delle funzioni generatrici.
Formula di Vandermonde.
- 02-02-05 --- 2ore -
- Numeri di Fibonacci e coefficienti binomiali. Esercizi vari
con l'uso della trasformata z, delle funzioni generatici e
l'induzione.
- Coefficienti binomiali modulo p: teorema di Lucas.
- 08-02-06 --- 2 ore -
- Mappe, mappe iniettive,, mappe crescenti mappe non decrescenti.
- Collocazioni in scatole distinte di oggetti distinti e indistinti.
Collocazioni di oggetti indistinti in scatole distinte con un munero
minimo assegnato per scatola. Composizioni ordinate di interi.
- La funzione $(1+z)^a$, $a\in R$.
- 15-02-06 --- 2 ore -
- Estrazioni da una popolazione di un sottoinsieme. Probabilità di
indovinare un terno al lotto. Estrazioni e loro funzioni
generatrici. Estrazioni dall'unione di popolazioni
distinte e funzioni generatrici. Estrazioni da un multiinsieme.
- 16-02-06 --- 2 ore -
- Numeri di Catalan: passeggiate crescenti sotto la diagonale,
Modi di dividere in triangoli un poligono tracciando diagonali.
Dimostrazione diretta e indiretta.
- Numeri di Fibonacci: pavimentazione di un corridoio 2xn con
mattonelle 2x1. Bytes di N bits con gli uni intervallati da almeno
uno zero.
- 22-02-06 --- 2 ore -
- Anagrammi. Distribuzione multinomiale. Funzioni generatrici
esponenziali e estrazioni ordinate.
- La formula di inversione per la matrice dei coeffienti binomiali.
- Permutazioni senza punti fissi. Calcolo diretto e indiretto.
- 27-02-06 --- 2 ore -
- Calcolo del numero di mappe surgettive. Calcolo indiretto. Calcolo
induttivo. Generatore esponenziale.
- Collocazioni in scatole indistinte tutte non vuote. Numeri di
Stirling. Numero delle partizioni in $n$ parti di
un insieme di $k$ elementi. Numero delle partizioni
possibili di un insieme di $k$ oggetti: numeri di Bell. Generatore
esponenziale e formula ricorsiva per i numeri di Bell.
- Composizioni di un intero. Generatore relativo.
- 01-03-06 --- 2 ore -
- La formula di inclusione-esclusione. La valenza di un punto rispetto
ad una famiglia di sottoinsiemi. Legame con la formula di inclusione
esclusione.
- Applicazione al calcolo del numero di funzioni surgettive e di
permutazioni senza punti fissi.
- Il problema delle cene conviviali.
- 02-03-06 --- 2 ore- Non tenuta.
- 07-03-06 --- 2 ore -
- La costruzione dei campi finiti. Estensione di un campo.
Caratteristica di un campo. Ogni campo finito ha ordine $p^n$, $p$ primo.
Campo di spezzamento di un polinomio. Per ogni $p$ primo e $n$ intero
esiste un campo di ordine $p^n$. Il polinomio $x^{p^n}-x$ e sue
proprieta'. Unicita' dei campi finiti (s.d.). Costruzione esplicita
di $F_4$, $F_8$, $F^9$.
- 08-03-06 --- 2 ore -
- Il problema delle cene conviviali.
- Insiemi semiordinati. Algebra di incidenza. Prodotto di funzioni
dell'algebra. Funzione di Riemann. Il caso finito: matrice
di adiacenza. Ordine topologico e matrici triangolari.
La funzione di Möbius e formula iterativa per il calcolo.
- 09-03-06 --- 2 ore -
- Ancora sul caso finito: matrice
di adiacenza. Ordine topologico e matrici triangolari.
La funzione di Möbius e formula iterativa per il suo calcolo.
- Formule di inversione di somme indicizzate da un insieme
semiordinato.
- Il calcolo della funzione di Möbius per l'insieme delle parti.
Interpretazione della formula di inclusione esclusione come
formula di inversione.
- Il caso di un insieme totalmente ordinato.
- Il caso dell'ordinamento lessicografico.
- 14-03-06 --- 2 ore -
- La funzione di Möbius e il semiordinamento per divisione.
- La funzione di Eulero.
- Il problema delle collane.
- Il polinomio cromatico di un grafico.
- 15-03-06 --- Non tenuta: Gita di istruzione
- 16-03-06 --- Non tenuta per partecipazione a convegno.
Riepilogo:
Lezioni: 24 h