Codice insegnamento

4S003197

Docente

Coordinatore

Crediti

6

Lingua di erogazione

Inglese

Settore Scientifico Disciplinare (SSD)

MAT/03 - GEOMETRIA

Periodo

Secondo semestre dal 6 mar 2023 al 16 giu 2023.

Orario Lezioni Moodle Seminari 0

Obiettivi di apprendimento

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.

Prerequisiti e nozioni di base

Fondamenti di geometria affine ed euclidea e di topologia generale.

Programma

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.
-Superfici discrete e curvature discrete.

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

Bibliografia

Modalità didattiche

L'insegnamento prevede lezioni frontali di teoria ed esercitazioni.

Modalità di verifica dell'apprendimento

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 (obbligatoria)
Prevede una discussione con il docente sulle definizioni e dimostrazioni discusse durante le lezioni sulla parte di programma di Geometria Discreta e Combinatoria.

Criteri di valutazione

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

Criteri di composizione del voto finale

Prova scritta massimo 30/30. Prova orale, se superata, aggiunge al più 5 punti.

Lingua dell'esame

English