Teoria dei grafi

Da WikiDsy.

Paper dati dal prof. a lezione il 13 gennaio

Disambigua compass.PNG
Questa è una pagina di introduzione al corso: contiene i turni, le modalità d'insegnamento, alcune informazioni generali ed eventuali giudizi sul corso in questione. Se sei giunto qui passando da un link, puoi tornare indietro e correggerlo in modo che punti direttamente alla voce appropriata.

Informazioni generali

Teoria dei grafi è un insegnamento complementare dei Corsi di Laurea del DSI/DICo.

Docente

Ottavio Mario D'Antona

Orari delle lezioni

  • Lunedì 17.30 - 19.30 (aula alfa)
  • Giovedì 17.30 - 19.30 (aula alfa)
  • Venerdì 16.30 - 18.30 (auletta 5)

Sito del corso

http://homes.dico.unimi.it/~dantona/tg/ (non aggiornato)

Materiale didattico

  • Ottavio Mario D'Antona - "Introduzione alla matematica discreta" (ed. Apogeo)

Diario del Corso

V 15 Ottobre

L 18 Ottobre

  • ( Dimostrazione che l' insieme dei numeri reali non è enumerabile )
  • Definizione di partizione di un insieme
  • Relazione tra funzioni suriettive e partizioni

G 21 Ottobre

  • Numeri di Stirling
    • Numeri di Stirling e triangolo di Tartaglia
    • Equazione S(n,k) = S(n-1,k-1) + kS(n-1,k)
  • Numeri di E.T. Bell
  • Concetto di "fattorizzazione" di una funzione tramite insieme ghost
  • come sommatoria di

V 22 Ottobre

  • Funzione Generatrice (esponenziale e ordinaria)
    • dei numeri di Bell
    • dei numeri di Fibonacci
  • Grafi e matrici come rappresentazione delle relazioni
  • Relazioni di equivalenza
    • Matrice a blocchi
  • Partial order relations
    • Nella teoria dei numeri: rel. di divisibilità
    • Nelle'algebra di Boole: rel. di raffinamento
  • Diagramma di Hasse
  • Greatest Lower Bound e Least Upper Bounds
  • Reticoli

L 25 Ottobre

  • come sommatoria di
  • Insieme parzialmento ordinato dotato di rango: rota-poset
  • Funzione di Möbius
  • Catene e prodotto di catene
  • La relazione "contiene tutti i punti di" tra le facce n-dimensionali di un solido
    • I complessi simpliciali, il triangolo di Tartaglia e l'algebra di Boole
  • Reticolo geometrico

G 28 Ottobre

  • Combinazioni tra n palline indistinguibili in x scatole distinguibili come numero di funzioni monotone tra due catene lunghe n e x
    • Definizione ricorsiva di questa f(n, x)
    • Valore della sommatoria degli interi da 1 a i (con dimostrazione di Gauss)
  • Definizione non ricorsiva di questa f(n, x) come
    • Definizione di "x crescente n" come

V 29 Ottobre

V 05 Novembre

L 08 Novembre

G 11 Novembre

L 15 Novembre

...

G 13 Gennaio

Esercizi assegnati

V 15 Ottobre

L 18 Ottobre

  • Trovare una procedura efficiente per il calcolo del coefficiente binomiale
  • Scrivere lo sviluppo di Mc-Laurin della funzione
  • Dimostrare che l' insieme delle parole binarie (compresa la parola vuota) è enumerabile

G 21 Ottobre

V 22 Ottobre

  • Calcolare la funzione generatrice ordinaria dei numeri di "Tribonacci"
  • Calcolare in quanti modi è possibile disporre dei rettangoli 1x2 per riempire un rettangolo 2xn
  • Determinare se la relazione "ha più blocchi?" applicata alle partizioni di un insieme forma un reticolo
  • Scrivere un algoritmo efficiente per determinare, data una matrice di adiacenza, se la corrispondente relazione è di equivalenza

L 25 Ottobre

  • Dimostrare che la funzione di Möbius in un'algebra di Boole vale sempre +1 o -1
  • Trovare per gli n-cubi il numero di facce k-dimensionali (come fatto per i simplessi e Tartaglia)
  • Dimostrare che presi m interi positivi consecutivi (n ... n+m-1) il loro prodotto sarà divisibile per m!

G 28 Ottobre

  • Dimostrare che
  • Calcolare quante sono le associazioni monotòne da una catena di n elementi a un albero binario completo di x elementi (era un esercizio o qualcosa che vedremo nelle prossime lezioni?)

V 29 Ottobre

Turni

A.A. passati

Informazioni

Giudizio sul corso

I giudizi di seguito espressi sono il parere personale degli studenti,
e potrebbero non rispecchiare il parere medio dei frequentanti.
Non vi è comunque alcun intento di mettere alla gogna i docenti del corso!
Interesse della materia (da 1 a 5 - aiuto)
____________________
Difficoltà del corso (da 1 a 5 - aiuto)
____________________
Difficoltà del corso per non frequentanti (da 1 a 5 - aiuto)
____________________
Ore di studio richieste (da 1 a 5 - aiuto)
____________________