Codice insegnamento

4S003197

Docente

Giuseppe Mazzuoccolo

Coordinatore

Giuseppe Mazzuoccolo

Crediti

6

Lingua di erogazione

Inglese

Settore Scientifico Disciplinare (SSD)

MAT/03 - GEOMETRIA

Periodo

II semestre dal 2 mar 2020 al 12 giu 2020.

Orario Lezioni Moodle Seminari 1

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. l 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à.

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.