Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wybrane zagadnienia geometrii obliczeniowej i topologii

Informacje ogólne

Kod przedmiotu: 1000-2M21GOT
Kod Erasmus / ISCED: 11.303 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Wybrane zagadnienia geometrii obliczeniowej i topologii
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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:

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.

Pełny opis:

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

Literatura:

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.

Efekty uczenia się:

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.

Metody i kryteria oceniania:

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

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)