Classe di Ingegneria dell'Informazione Corso di laurea in Ingegneria Informatica. Anno 2007-2008

Corso Integrato di Matematica Discreta (5 CFU)

• Parte A - Calcolo Combinatorio (2.5 CFU), Periodo: 21 gennaio 2008/21 marzo 2008, 2.5 CFU tenuto dal prof. Giuseppe Modica
• Parte B - Algebra (2.5 CFU), Periodo: 21 gennaio 2008/21 marzo 2008, 2.5 CFU tenuto dal prof. Umberto Tiberio

Parte A - Calcolo Combinatorio (2.5 CFU)

Libri consigliati

• 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.
• Note distribuite.

Lezioni svolte

Di norma il materiale delle lezioni e' contenuto nel volume di M. Cerasoli, F. Eugeni e M. Protasi.

• 24-01-2008 - 2 ore -
  • Introduzione. I modelli del conteggio: insiemi, mappe e parole con caratteri scelti in un alfabeto, estrazioni, collocazioni.
  • Richiami sulle matrici. Matrici triangolari.
  • Richiami sulle serie di potenze. Funzioni generatrici e generatrici esponenziali.
  • Coefficienti binomiali. Binomio di Newton.
  • Formula di inversione per i coefficienti binomiali.

• 30-01-2008 - 2 ore -
  • Sottoinsiemi. Mappe, mappe iniettive, mappe crescenti, mappe nondecrescenti.
  • Coefficienti binomiali generalizzati, la funzione $(1+z)^a$, $a\in R$.
  • Mappe surgettive e loro generatore esponenziale.

• 31-01-2008 - 2 ore -
  • Esercizi vari sul coefficienti binomiali. Numeri di Fibonacci e coefficienti binomiali.

• 07-02-2008 - 2 ore -
  • Estrazione simultanee da insiemi, Multiinsiemi. Estrazioni da multiinsiemi.
  • Estrazioni ordinate.
  • Proprieta' moltiplicativa delle funzioni generatrici di estrazioni.
  • Estrazioni vincolate e funzioni generatrici.

• 14-02-2008 - 2 ore -
  • Permutazioni senza punti fissi.
  • Numeri di Catalan: passeggiate crescenti sotto la diagonale,
  • Collocazioni in scatole distinte di oggetti distinti e indistinti, anche in presenza di vincoli.

• 20-02-2008 - 2 ore -
  • Collocazioni in scatole distinte di oggetti distinti e indistinti, anche in presenza di vincoli (segue)
  • Collocazioni di oggetti distinti in scatole indistinte. Numeri di Stirling di seconda specie. Partizioni di un insieme. Numeri di Bell e formula di Atkins.
  • Proprieta' moltiplicativa delle funzioni generatrici delle collocazioni.

• 21-02-2008 - 2 ore -
  • Collocazioni di oggetti distinti in scatole indistinte.
  • Partizioni di un intero anche in presenza di vincoli.
  • Esempi vari.

• 27-02-2008 - 2 ore -
  • Esercizi vari. Numeri di Catalan e alberi.

• 28-02-2008 - 2 ore -
  • La formula di inclusione-esclusione. Notazioni e formula.
  • Applicazione al calcolo del numero delle permutazioni senza punti fissi.
  • Il problema delle cene conviviali.

• 05-03-08 - 2 ore -
  • Valenza di un ricoprimento e formula di inclusione esclusione.
  • Insiemi parzialmente ordinati. Esempi. La funzione o matrice di incidenza: zeta di Riemann, sua invertibilita' e funzione o matrice di M\"obius.

• 12-03-08 - 2 ore -
  • Somme su un insieme parzialmente ordinato e formule di inversione. Il calcolo della funzione di Mobius degli interi con l''ordine standard, del prodotto cartesiano di due insiemi parzialmente ordinati, degli interi con l'ordine parziale dato dalla divisibilita' e dellinsieme delle parti di un insieme con l'ordine dato dall'inclusione.

• 13-03-08 - 2 ore -
  • La funzione di Eulero. Formula di M\"obius. Il prblema delle collane. Il numero di polinomi irriducibili a coefficienti in un campo finito.

• 14-030-8 - 2 ore -
  • Colorazioni di un grafo e la formula di Rota per il polinomio di Birkhoff.

Riepilogo

• Lezioni: 26h.