MATEMATICA DISCRETA
LAUREA MAGISTRALE IN MATEMATICA PER LE APPLICAZIONI
a.a. 2015/16


Programma del corso
Avvisi
Testi consigliati
Esami
Diario delle Lezioni
Esercizi proposti

 
 
Docente Num. Telefono E-mail Orario Ricevimento Stanza
Claudia Malvenuto 06 4969 4226 claudia@mat.uniroma1.it Su appuntamento per email 105

Le lezioni si svolgono in Aula C, Dip. di Matematica Guido Castelnuovo

Orario lezioni: martedì e giovedì dalle 11 alle 13

Inizio lezioni: giovedì 1 marzo 2016
Fine lezioni: lunedì 6 giugno 2016

Durata: il corso da 6 crediti prevede 48 ore di lezione


Avvisi

* Un articolo importante, tratto dal settimanale Internazionale, La fiducia delle donne: studiano, lavorano e fanno carriera, ma arrivano raramente ai vertici. Perché le donne restano indietro? Leggete la risposta provocatoria di due giornaliste al problema.

* Un esempio di combinatoria enumerativa da non seguire! (Da "Monty Python and the Holy Grail")

* Endre Szemerédi receives the 2012 Abel Prize "for his fundamental contributions to discrete mathematics and theoretical computer science and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory," to quote the Abel Committee.

* Terence Tao: blog category MathCO.

* Peter Cameron's blog

* Gil Kalai: Combinatorics and more.

* Una opinione di Doron Zeilberger sulla matematica pura, dai Notices AMS.

* La prefazione del libro Concrete Mathematics Ronald L. Graham (AT&T Bell Laboratories),
Donald E. Knuth (Stanford University) e Oren Patashnik (Center for Communications Research).

Torna su


Esami

* L'esame è scritto e orale. Per i frequentanti, sarà possibile sostituire allo scritto dei vari appelli due compiti scritti (prima e seconda prova in itinere), modalità fortemente incoraggiata.

* Gli appelli sono tutti aperti su InfoStud.

PRIMA PROVA IN ITINERE
La prova di esonero avrà luogo il 21 aprile 2016 alle ore 9,30 in aula I.
* Testo e soluzioni della prova.
* Risultati della prova, sotto pseudonimo, non ancora disponibili.

SESSIONE ESTIVA
Primo appello: Scritto: 14 giugno ore 14 aula I Orale: 16, 28 giugno ore Aula ...

* Testo e soluzioni parte 2 della prova di esame relativa alla seconda parte (secondo esonero).
* Testo e soluzioni parte 1 della prova di esame relativa alla prima parte (primo esonero).

Secondo appello: Scritto: 18 luglio ore 14.00 Aula II. Orale: ... luglio ore 9.00 Aula ...

SESSIONE AUTUNNALE
Primo appello: Scritto: 2 settembre ore 10.00 Aula ... Orale: ... settembre ore 10.00 Aula ... Secondo appello: Scritto: 15 settembre ore 10.00 Aula ... Orale: ... settembre ore 9.00 Aula ...

SESSIONE INVERNALE
Primo appello: Scritto: 17 gennaio 2017 ore 9.00 Aula ... Orale: ... gennaio 2016 ore ... Aula ...

Torna su


Programma di esame

* Fanno parte del programma di esame anche gli esercizi delle schede.
* Il programma completo e dettagliato del corso si ottiene solo consultando il
diario delle lezioni.

Programma di massima (provvisorio)

  • Teoria dei grafi: concetti fondamentali.
    Concetti fondamentali di grafi.
    Connessione, distanza.
    Esistenza di circuiti euleriani.
    Gradi e numero di archi: il metodo del doppio conteggio.
    Teorema di Bondy.
  • Alberi, foreste, permutazioni.
    Teorema di Cayley sul numero di alberi di copertura.
    Il codice di Prüfer.
    L'algoritmo di Kruskal per l'albero di copertura di costo minimo.
    Vertebrati e dimostrazione della formula di Cayley tramite
    la rappresentazione grafica di endofunzioni f:[n]->[n].
  • Combinatoria enumerativa
    Coefficienti multinomiali.
    La decomposizione ciclica di permutazioni.
    Parità di permutazioni.
    Numeri euleriani.
    Discese di una permutazione, enumerazione per discese.
    Inversioni di una permutazione, tavola di inversioni.
    Conteggio di permutazioni con determinati vincoli di precedenza.
    Funzioni generatrici.
    Tecniche di conteggio.
    Teoria dei reticoli, il principio di inclusione-esclusione.
    Applicazioni: numero di permutazioni senza punti fissi,
    la funzione di Eulero, numero di funzioni suriettive.
  • Colorazioni e Teoria di Ramsey.
    Grafi bipartiti.
    Numero cromatico.
    Limitazioni per il numero cromatico e il numero di stabilità in termini del grado massimo.
    Teoria di Ramsey per grafi.
    Il Teorema di esistenza di Erdös di grafi con "piccoli" numeri omega e alfa ma di "grande" numero cromatico.
  • Combinatoria estremale.
    Teorema di Mantel-Turán.
    Teorema di Sperner.
    Massima cardinalità di una famiglia intersecante.
    Teorema di Erdos-Ko-Rado
    Teoria di Ramsey e numeri di Ramsey. Generalizzazione del principio dei cassetti.
  • Torna su


    Testi Consigliati

  • Dispense del corso di Combinatoria di János Körner e Claudia Malvenuto.
  • J.Matousek, J.Nesetril, Invitation to Discrete Mathematics. Clarendon Press (1998).
  • R.P. Stanley, Enumerative Combinatorics Vol 1 (second edition), Cambridge University Press (2011). The manuscript of Enumerative Combinatorics Vol 1, published on R.P Stanley's website with the permission of Cambridge University Press, is not identical to the published version.
  • Altri testi consultabili

  • Dispense del corso di Combinatoria di Antonio Machì.
  • J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (1992).
  • P.J.Cameron, Combinatorics. Topics, techniques, algorithms. Cambridge University Press (1994).
  • R.L.Graham, D.E.Knuth, O.Patashnik, Matematica Discreta. Hoepli (1992).
  • Siti utili

  • http://mathworld.wolfram.com/topics/DiscreteMathematics.html
  • On-line encyclopedia of Integer Sequences.
  • Torna su


    Sito in costruzione, ultimo aggiornamento: 1 marzo 2016.
    Per commenti/correzioni al sito scrivere a C.Malvenuto, indicando nel subject un riferimento al sito del corso di Matematica Discreta.