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

Matematica Discreta (5 CFU)

• Corso integrato
  • Periodo: 19 gennaio 2009 - 20 marzo 2009, 2.5 CFU
  • Parte A - Calcolo combinatorio, tenuta dal prof. G. Modica
  • Parte B - Algebra, tenuta dalla prof.ssa Fiammetta Battaglia

Parte A - Calcolo Combinatorio (2.5 CFU)

Libri consigliati

• Note distribuite.
• M. Aigner, A Course in Enumeration, 2007, Springer-Verlag, Berlin
• M. Cerasoli, F. Eugeni, M. Protasi, Elementi di matematica discreta, Zanichelli, 1988.
• L. Anderson, A First Course in Discrete Mathematics, Springer, 2000.

Lezioni svolte

Di norma il materiale delle lezioni e' contenuto nelle note al corso.

• 21-01-2009 - 2 ore -
  • Introduzione.
  • Richiami sulle matrici. Matrici triangolari.
  • Richiami sulle serie di potenze.
  • Numeri di Fibonacci.

• 22-01-2009 - 2 ore -
  • Coefficienti binomiali. Formula di inversione per i coefficienti binomiali. Binomio di Newton. Coefficienti binomiali generalizzati e serie binomiale generalizzata.
  • Esercizi vari sui coefficienti binomiali con l'uso delle serie di potenze e del prodotto di convoluzione. Numeri di Fibonacci e coefficienti binomiali.

• 29-01-2009 - 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.

• 04-02-2009 - 2 ore -
  • Permutazioni. Decomposizione ciclica. Segnatura. Permutazioni senza punti fissi. Permutazioni decomponibili in $k$ cicli. Numeri di Stirling di prima e seconda specie.

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

• 11-02-2009 - 2 ore -
  • Collocazioni di oggetti distinti in scatole distinte.
  • Collocazioni di oggetti distinti in scatole indistinte. Partizioni. Numeri di Stirling di seconda specie. Numeri di Bell e formula di Atkins.
  • Proprieta' moltiplicativa delle funzioni generatrici delle collocazioni di oggetti distinti.

• 12-02-2009 - 2 ore -
  • Collocazioni di oggetti indistinti in scatole distinte.
  • Collocazioni di oggetti indistinti in scatole indistinte. Partizioni di un intero, anche in presenza di vincoli. Funzioni generatrici relative.

• 19-02-2009 - 2 ore -
  • Cammini crescenti e Numeri di Catalan. Cammini di Dyck. Numeri e cammini di Schroder.

• 26-02-2009 - 2 ore -
  • Il problema di Ippocrate. Numeri di Schroder. Alberi con nodi distinti. Teorema di Cayley. Alberi ordinati o piani con nodi indistinti e radice fissata. Alberi piani completi con nodi indistinti e radice fissata.
  • Composizione di strutture.

• 02-03-2009 - 2 ore -
  • Composizione di strutture.
  • La formula di inclusione-esclusione. Notazioni e formula.
  • Valenza di un ricoprimento e formula di inclusione esclusione.
  • Applicazione al calcolo del numero delle permutazioni senza punti fissi.

• 05-03-2009 - 2 ore -
  • Il problema delle cene conviviali.
  • Insiemi parzialmente ordinati. Esempi. La funzione o matrice di incidenza: zeta di Riemann, sua invertibilita' e funzione o matrice di M\"obius.
  • Il calcolo della funzione di Mobius: per gli interi naturali, le parti di un insieme. Legame con l'inversione di matrici nel caso finito.

• 12-03-2009 - 2 ore -
  • Funzione di M\"obius per gli interi parzialmente ordinati dalla divisione.
  • Formule di inversione.
  • Formula di M\"obius per la funzione di Eulero. Il problema delle collane. Il numero di polinomi irriducibili a coefficienti in un campo finito.

• 18-03-2009 --- 2 ore --
  • Il polinomio cromatico di un grafo. Il metodo di Zykov. La formula di Rota.
  • Azione di un gruppo finito su un insieme finito. Formula di Burnside-Frobenius per il calcolo del numero di orbite.

• 19-03-2009 --- 2 ore --
  • Mappe modulo l'azione di gruppi sul dominio e sul codominio. Formula di de Bruijn.
  • Formula di Polya-Redfeld. Applicazioni (s.d.)) al problema delle collane, al problema della collocazione delle torri modulo il gruppo diedrale $D_4$ e alle colorazioni delle facce, degli spigoli e dei vertici di un cubo modulo il gruppo delle simmetrie del cubo.

Riepilogo

• Lezioni: 28 ore.