COMBINATORIA
Corso di laurea in INFORMATICA
a.a. 2008/09

Programma del corso
Avvisi sugli esami e non solo
Testi consigliati
Appunti del corso
Siti utili
Esercizi proposti

 
 
Docente Num. Telefono E-mail Orario Ricevimento Stanza
Lezioni: Prof. János Körner 06 4991 8353 korner@di.uniroma1.it Mercoledì ore 10.30-12.30 340
Esercitazioni: D.ssa Blerina Sinaimeri 06 4991 8430 sinaimeri@di.uniroma1.it Per appuntamento email 333

Le lezioni si svolgono in Aula III Nuovo Edificio di Fisica

Orario lezioni: giovedì e venerdì dalle 14 alle 16

Durata: il corso prevede 56 ore di lezione

Programma

  • 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 funzioni f:[n]->[n].
    La decomposizione ciclica di permutazioni.
    Parità di permutazioni.

  • Colorazione e Teoria di Ramsey.

    Grafi bipartiti.
    Numero cromatico.
    Limitazioni per il numero cromatico e il numero di stabilità in termini del grado massimo.
    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.
    Teorema di Erdös-Ko-Rado.

  • Tecniche di conteggio.

    Il principio di inclusione-esclusione.
    Applicazione al numero di permutazioni senza punti fissi.
    Applicazione alla funzione di Euler.

    • Torna su

    Testi Consigliati

  • APPUNTI DEL CORSO (Ultima modifica: 7 aprile 2008)
  • J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (2001).
  • P.J.Cameron, Combinatorics. Topics, techniques, algorithms. Cambridge University Press (1994).
  • R.L.Graham, D.E.Knuth, O.Patashnik, Matematica Discreta. Hoepli (1992).
  • J.Matousek, J.Nesetril, Invitation to Discrete Mathematics. Clarendon Press (1998).
    •

    Torna su

    Siti utili

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

    Torna su

    Avvisi

    Appelli della sessione estiva:
    ore Aula ...
    ore Aula ...
    ore Aula ...

    Appello della sessione autunnale:
    ... settembre ore ... Aula ...

    Appelli della sessione invernale:
    ... gennaio ore ... Aula ...
    ... febbraio ore ... Aula ...

    In caso di insuccesso non è possibile presentarsi in un altro appello della stessa sessione.
    Per partecipare all'esame è necessario prenotarsi su un apposito foglio affisso sulla porta
    del Prof. Korner fino al giorno prima di ogni appello.

    Torna su

    Sito in costruzione, ultimo aggiornamento: 25/3/2009.
    Per commenti/correzioni al sito scrivere a B.Sinaimeri,
    indicando nel subject un riferimento al corso di combinatoria.