Advanced geometry (2016/2017)

Codice insegnamento
4S003197
Docente
Giuseppe Mazzuoccolo
Coordinatore
Giuseppe Mazzuoccolo
crediti
6
Settore disciplinare
MAT/03 - GEOMETRIA
Lingua di erogazione
Inglese
Periodo
II sem. dal 1-mar-2017 al 9-giu-2017.

Orario lezioni

II sem.
Giorno Ora Tipo Luogo Note
lunedì 9.30 - 11.30 lezione Aula M  
mercoledì 11.30 - 13.30 lezione Aula M  

Obiettivi formativi

L'insegnamento si propone di fornire allo studente i concetti fondamentali della teoria dei grafi e le basi della geometria discreta e computazionale.
Al termine dell'insegnamento lo studente conoscerà alcuni teoremi classici della teoria dei grafi, in particolare riguardo teoremi di struttura, colorazioni, matching theory, immersioni nel piano, problemi di flusso.
Inoltre conoscerà i temi fondamentali della geometria discreta e alcuni algoritmi classici della geometria computazionale, e avrà la percezione dei collegamenti con problemi in ambito non prettamente matematico.
Sarà in grado di produrre argomentazioni e dimostrazioni rigorose su questi temi e sarà in grado di leggere articoli e testi (anche avanzati) di Teoria dei Grafi e Geometria discreta.

Programma

L'insegnamento prevede lezioni frontali di teoria ed esercitazioni.

A seguire un programma dettagliato del corso:

TEORIA DEI GRAFI:
-Definizioni e proprietà di base
-Matching in grafi bipartiti: Teorema di Konig, Teorema di Hall. Matching in grafi arbitrari: Teorema di Tutte e Teorema di Petersen.
-Connessione: teoremi di Menger.
-Grafi planari: Formula di Eulero e sue conseguenze, Teorema di Kuratowski.
-Colorazioni: Teorema dei Quattro Colori, Teorema dei Cinque Colori, Teorema di Brooks e di Vizing.

GEOMETRIA DISCRETA:
-Convessità, insiemi convessi, separazione, Lemma di Radon e Teorema di Helly.
-Reticoli, Teorema di Minkowski. Teorema di Erdos-Szekeres.
-Intersezione di insiemi convessi, versione frazionaria del teorema di Helly.
-Problema dell'immersione di spazi metrici finiti in spazi normati, Johnson-Lindenstrauss Flattening Lemma
-Superfici discrete e curvature discrete.

GEOMETRIA COMPUTAZIONALE:
-Introduzione generale, reporting vs counting, problema “fixed-radius near neighbourhood” .
-Problema della chiusura convessa: Graham's scan e altri algoritmi.
-Poligonali e problema della Galleria d'Arte. Teorema della Galleria d'Arta, triangolazione di poligoni.
- Diagramma di Voronoi e algoritmo di Fortune.
- Triangolazione di Delaunay e sue proprietà.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Diestel Graph Theory (Edizione 5) Springer 2016
Matousek Lectures on Discrete Geometry (Edizione 1) Springer 2002

Modalità d'esame

Per superare l'esame gli studenti devono dimostrare di:
- conoscere e aver compreso i concetti fondamentali della Teoria dei Grafi
- conoscere e aver compreso i concetti fondamentali della Geometria Discreta e Computazionale
- avere un'adeguata capacità di analisi e sintesi e di astrazione
- sapere applicare queste conoscenze per risolvere problemi ed esercizi, sapendo argomentare i loro ragionamenti con rigore matematico.
- conoscere alcuni possibili sviluppi avanzati della Teoria dei Grafi

Prova scritta (2 ore).
L'esame scritto sulla parte di Teoria dei Grafi, consiste nella risoluzione di 3 o 4 esercizi più due domande di teoria (1 su definizioni/concetti generali e 1 con dimostrazione di un teorema presentato a lezione).

Prova orale (obbligatorio)
Prevede una discussione con il docente sulle definizioni e dimostrazioni discusse durante le lezioni sulla parte di programma di Geometria Discreta e Combinatoria.

Opinione studenti frequentanti - 2015/2016


Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2016/2017 non sono ancora disponibili