Wybrane zagadnienia geometrii obliczeniowej i topologii

informatyka
matematyka

monograficzne

(tylko po angielsku) The main prerequisites are mathematical maturity and familiarity with algorithms. A working knowledge of basic Discrete Mathematics, and Algorithms and Data Structures is recommended. A course on

Probability and Statistics would be helpful but is not mandatory.

w sali

Rozpoczynając od krótkiego wprowadzenia do geometrii dyskretnej, przechodzimy do zagadnień algorytmicznych z geometrii obliczeniowej, takich jak obliczanie diagramów Woronoja, triangulacje Delaunaya i wypukłe kadłuby, ograniczony wymiar VC i sieci ε, raportowanie zasięgu i problemy z lokalizacją punktów, teoria rozbieżności, metryka osadzania itp. Na koniec omówimy podstawy topologii obliczeniowej, takie jak kompleksy uproszczone, homologia i kohomologia, obliczanie trwałej homologii i trochę teorii Morse'a.

i. Zbiory wypukłe: lemat Radona, twierdzenia Helly'ego i Tverberga (2 wykłady).

ii. Diagramy Woronoja, triangulacje Delaunaya i łuski wypukłe (1 wykład).

iii. Metoda Clarksona-Shora, Randomizowana konstrukcja przyrostowa,

Analiza wsteczna (2 wykłady).

iv. Przestrzenie zasięgowe, wymiar VC, sieci ε i struktury pokrewne, (2 wykłady).

v. Zaokrąglanie LP (Bronnimann-Goodrich), algorytmy wyszukiwania zasięgu i lokalizacji punktów. (1 wykład).

vi. Teoria rozbieżności (2 wykłady).

vii. Osadzenia i klucze metryczne (1 wykład).

viii. Grafy, powierzchnie i kompleksy uproszczone (1 wykład).

ix. Homologia, trwała homologia i kohomologia (2 wykłady).

X. Teoria Morse'a (1 wykład).

J. Matoušek - Lectures on Discrete Geometry.

J. Matoušek - Geometric Discrepancy.

J-D. Boissonnat and M. Yvinec - Algorithmic Geometry.

Edelsbrunner and Harer - Computational Topology: An Introduction.

Selected recent papers.

Wiedza:

Znajomość podstawowych i niektórych zaawansowanych technik geometrii obliczeniowej i topologii.

Dość szeroka ekspozycja na problemy klasyczne i współczesne.

Zrozumienie znaczenia dowodów matematycznych.

Umiejętności:

Umiejętność zastosowania pojęć geometrycznych i topologicznych do problemów algorytmicznych.

Umiejętność wyboru odpowiednich narzędzi z geometrii dyskretnej lub dostosowania istniejących narzędzi w razie potrzeby w celu rozwiązania problemów algorytmicznych lub kombinatorycznych w geometrii.

Kompetencja:

Świadomość własnych ograniczeń i potrzeby dalszej nauki.

Wykształcenie umiejętności czytania artykułów naukowych, w razie potrzeby w języku obcym, w celu poszerzenia wiedzy.

Umiejętność precyzyjnego formułowania pytań w celu pogłębienia własnego zrozumienia lub znalezienia luk w rozumowaniu.

2 prace domowe i końcowa prezentacja referatu (około 25+25+50 procent).