Classe di Ingegneria dell'Informazione
Corso di laurea in Ingegneria Informatica. Anno 2006-2007
Periodo: 22 gennaio 2007 - 25 marzo 2007, 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.
- G. Rota, Introduzione alla probabilita', Unione Matematica Italiana,
1984, Bologna.
Di norma il materiale delle lezioni e' contenuto nel volume di M. Cerasoli,
F. Eugeni e M. Protasi.
- 24-01-07 -- 2 ore
- I modelli: estrazioni, insiemi e mappe,
liste e parole di simboli scelti in un alfabeto, collocazioni.
Gli strumenti: calcolo in due modi distinti, calcolo per induzione,
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 inversione per i coefficienti binomiali.
- 31-01-07 --- 2 ore -
- Calcoli vari diretti e con l'uso delle funzioni generatrici.
Formula di Vandermonde.
- Mappe e parole con simboli scelti in un alfabeto.
- Mappe, mappe iniettive,, mappe crescenti, mappe non decrescenti.
- La funzione $(1+z)^a$, $a\in R$.
- 01-02-06 --- 2 ore -
- Mappe surgettive. La funzione $(1+z)^a$, $a\in R$.
- Estrazione simultanea da una popolazione e sua funzione
generatrice. Probabilità di indovinare un terno al lotto.
Estrazione da un multiinsieme e sua funzione generatrice.
- Estrazioni e loro funzioni generatrici. Estrazioni dall'unione
di popolazioni distinte e funzioni generatrici.
- 07-02-07 --- 2 ore -
- Esercizi vari.
- Permutazioni senza punti fissi.
- Numeri di Catalan: passeggiate crescenti sotto la diagonale,
Modi di dividere in triangoli un poligono tracciando diagonali.
Calcolo diretto e indiretto.
- 14-02-07 --- 2 ore -
- Numeri di Fibonacci: pavimentazione di un corridoio 2xn con
mattonelle 2x1.
- Bytes di N bits con gli uni intervallati da almeno
uno zero.
- k-parole da un alfabeto di $n$ che non contengono due simboli
successivi nei due casi dell'alfabeto lineare e circolare.
- Collocazioni di oggetti distinti in scatole ditinte. Il caso libero,
con almeno uno per scatola, con al piu' uno per scatola. Legami con
le classi di funzioni.
- Collocazioni di oggetti indistinti in scatole distinte con vari tipi
di vincoli.
- 15-02-07 --- 2 ore -
- Collocazioni di oggetti distinti in scatole distinte cn almeno
uno per scatola e mappe surgettive. Collocazioni di oggetti distinti
in scatle indistinte con almeno uno per scatola. Numeri di Stirling
di seconda specie. Collocazione in scatole indistinte. Numeri di
Bell. Partizioni di un insieme. Funzione generatrici esponenziali
relative.
- 21-02-07 --- 2 ore -
- Collocazione di oggetti indistinti in scatole distinite. Collegamento
con le estrazioni. Funzione generatrice relativa.
- Statistiche di Maxwell-Bolztmann, Bose-Einstein e Fermi-Dirac.
- Partizione di un intero e collocazione di uni. Funzione generatrice
associata.
- Collocazioni di oggetti indistinti in scatole indistinte.
- 28-02-07 --- 2 ore -
- La formula di inclusione-esclusione. Notzioni e formula.
- Applicazione al calcolo del numero delle permutazioni senza punti fissi.
- Il problema delle cene conviviali.
- 01-03-07 --- 2 ore -
- La valenza di un punto rispetto ad una famiglia di sottoinsiemi.
Legami con la formula di inclusione esclusione.
- Formula di inversione dei coefficienti binomiali.
- Insiemi parzialmente ordinati. Minimo di un poset. Ordinament
topologico. Funzione zeta di Riemann. Inversa di Mobius.
Matrici associate alla zeta e alla mobius nel caso di poset
finito.
- 07-03-07 --- 2 ore -
- Calcolo della funzione di Mobius associata ad un insieme semiordinato:
interi naturali, parti di un insieme finito, naturali semiordinati
dalla relazione di divisibilita'.
- 14-03-07 --- 2 ora -
- Formula di inversione. Il caso degli interi natirali. Formula
di inclusione-esclusione. La funzione di Eulero, formula di Mobius.
- 15-03-07 --- 1 ora -
- Il problema delle collane.