Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wybrane zagadnienia geometrii obliczeniowej i topologii

Informacje ogólne

Kod przedmiotu: 1000-2M21GOT Kod Erasmus / ISCED: 11.303 / (0612) Database and network design and administration
Nazwa przedmiotu: Wybrane zagadnienia geometrii obliczeniowej i topologii
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
Język prowadzenia: angielski
Kierunek podstawowy MISMaP:

informatyka
matematyka

Rodzaj przedmiotu:

monograficzne

Założenia (opisowo):

(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.

Tryb prowadzenia:

w sali

Skrócony opis: (tylko po angielsku)

Beginning with a brief introduction to discrete geometry, we move on to algorithmic topics from computational geometry such as computation of Voronoi diagrams, Delaunay triangulations and convex hulls, bounded VC dimension and ε-nets, range reporting and point location problems, discrepancy theory, metric embeddings etc. Finally we shall discuss the basics of computational topology, like simplicial complexes, homology and cohomology, computing persistent homology and some Morse theory.

Pełny opis: (tylko po angielsku)

i. Convex sets: Radon’s lemma, Helly’s and Tverberg’s theorems (1 lecture).

ii. Incidence Bounds and Hyperplane Arrangements (1 lectures).

iii. Voronoi diagrams, Delaunay triangulations and Convex Hulls (2 lectures).

iv. The Clarkson-Shor method, Randomized Incremental Construction,

Backward Analysis (2 lectures).

v. Range spaces, VC dimension, ε-nets and related structures, (1 lecture).

vi. LP rounding (Bronnimann-Goodrich), Range search and point location algorithms. (1 lecture).

vii. Discrepancy theory (2 lecture).

viii. Metric embeddings and spanners (1 lectures).

ix. Graphs, Surfaces and Simplicial Complexes (1 lectures).

x. Homology, Persistent Homology and Co-homology (2 lectures).

xi. Morse Theory (1 lecture).

Literatura:

J. Matoušek - Lectures on Discrete Geometry.

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

Edelsbrunner and Harer - Computational Topology: An Introduction.

Selected recent papers.

Efekty uczenia się: (tylko po angielsku)

Knowledge:

Knowledge of basic and some advanced techniques in computational geometry and topology.

A reasonably wide exposure to classic and modern problems.

Understanding the importance of mathematical proofs.

Skills:

Ability to apply geometric and topological concepts to algorithmic problems.

Ability to select appropriate tools from Discrete Geometry, or to tweak existing tools if required, to solve algorithmic or combinatorial problems in Geometry.

Competence:

Awareness of own limitations and the need for further study.

Development of the ability to read scientific articles, if necessary in a foreign language, to expand their knowledge.

Ability to precisely formulate questions to deepen their own understanding or to find gaps in reasoning.

Metody i kryteria oceniania: (tylko po angielsku)

Homeworks and paper presentation (approximately 50 percent each). PhD students have the option to either (a) present a paper from a list of selected recent papers, OR (b) solve a challenging (starred) homework problem, preparing for research work.

Zajęcia w cyklu "Semestr zimowy 2021/22" (w trakcie)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Kunal Dutta
Prowadzący grup: Kunal Dutta
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.