COMBINATORIA
Corso di laurea in TECNOLOGIE INFORMATICHE
a.a. 2003/04

Programma del corso
Avvisi sugli esami e non solo
Testi consigliati
Appunti del corso
Diario delle Lezioni
Esercizi proposti

 
 
Docente Num. Telefono E-mail Orario Ricevimento Stanza
Lezioni: Prof. Claudia Malvenuto 06 4991 8540 claudia@di.uniroma1.it Su appuntamento per email 344
Esercitazioni: Dott. Daniele A. Gewurz
/
 gewurz@mat.uniroma1.it Su appuntamento per email sans toit ni loi

Le lezioni si svolgono in Aula 1, Dip. di Fisica, Istituto Fermi

Orario lezioni: lunedì dalle 14 alle 16 e martedì dalle 14 alle 15
Orario esercitazioni: venerdì dalle 14 alle 16

Durata: il corso prevede 60 ore di lezione

Avvisi

Sono state apportate delle correzioni agli appunti, alle pagine 14, 23 e 57-60 (27 maggio 2004).

L'esame è solo orale. Ci saranno due appelli nella sessione estiva, uno nella sessione autunnale e due nella sessione invernale.

SESSIONE ESTIVA
Primo appello: lunedì 7 giugno, ore 9:00 Aula Alfa (via Salaria 113).
Secondo appello: venerdì 23 luglio, ore 9:00 Aula Alfa (via Salaria 113).

SESSIONE AUTUNNALE
Primo appello: venerdì 24 settembre, ore 9:00 in aula da destinarsi (via Salaria 113).

SESSIONE INVERNALE
Primo appello: 12 gennaio, ore 9.30 Aula Alfa (Via Salaria, 113).

Per partecipare al primo appello è necessario iscriversi, inviando un messaggio email
contenente il proprio nome e cognome a Claudia Malvenuto specificando
nel subject: "Prenotazione appello di Combinatoria del 12 gennaio".

Secondo appello: 16 febbraio, ore 9.30 Aula Alfa (Via Salaria, 113).

Per partecipare al secondo appello è necessario iscriversi, inviando un messaggio email
contenente il proprio nome e cognome a Claudia Malvenuto specificando
nel subject: "Prenotazione appello di Combinatoria del 16 febbraio".

Torna su

Programma (provvisorio!)

* Fanno parte del programma di esame anche gli tutti gli esercizi delle schede di esercizi.
* Consultando il diario delle lezioni si può avere un programma più dettagliato.

  • Grafi
    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.
    Coefficienti multinomiali.
    Vertebrati e dimostrazione della formula di Cayley tramite
    la rappresentazione grafica di endofunzioni f:[n]->[n].
    La decomposizione ciclica di permutazioni.
    Parità di permutazioni.
    Conteggio di permutazioni con determinati vincoli di precedenza.
    L'algoritmo di Kruskal per l'albero di copertura di costo minimo.
  • 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.
  • Tecniche di conteggio.
    Il principio di inclusione-esclusione.
    Applicazioni: numero di permutazioni senza punti fissi,
    la funzione di Eulero, numero di funzioni suriettive.

    • Torna su

    Testi Consigliati

  • APPUNTI DEL CORSO in formato dvi ps pdf
    N.B. È stata apportata qualche piccola correzione il 21 settembre 2004 agli appunti che erano già in rete a:
    * pag.19
    * pag.27 Prop. 2.9
    * pag.29 riga 3
    * pag.40 riga 5
    * pag.63 riga 19 e seguenti
    Per chi volesse confrontare i cambiamenti fatti, ecco la VECCHIA versione: dvi ps pdf

  • J.Matousek, J.Nesetril, Invitation to Discrete Mathematics. Clarendon Press (1998).

    • Altri testi consultabili

  • 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).
  • Dispense del corso di Combinatoria del Prof. Machì, tenuto nell'a.a. 2002/03.
  • Dispense di Discrete Mathematics, di Lovasz e Vesztergombi, in formato .ps

    • Siti utili

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

    Torna su

    Sito in costruzione, ultimo aggiornamento: 27 maggio 2004.
    Per commenti/correzioni al sito scrivere a C.Malvenuto, indicando nel subject un riferimento al sito del corso di combinatoria.