Geometria obliczeniowa
Informacje ogólne
Kod przedmiotu: | 1000-2M00GO |
Kod Erasmus / ISCED: |
11.303
|
Nazwa przedmiotu: | Geometria obliczeniowa |
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
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Skrócony opis: |
Analiza wybranych problemów geometrii obliczeniowej i metod, które je rozwiązują (zamiatanie, dziel i rządź, prune and search, dualizacja itp..). Teoria i zastosowania. |
Pełny opis: |
1. Podstawowe fakty geometryczne. 2. Wielokąty, ich podziały i triangulacje. 3. Problem galerii, graf widzialności. 4. Geometryczne struktury danych. 5. Diagramy Voronoi i szkielety. 6. Lokalizacja punktów na płaszczyźnie. 7. Przestrzeń dualna, sortowanie biegunowe w R^2. 8. Proste przecinające w R^2 i R^3, ciągi Davenporta-Schinzela. 9. Programowanie liniowe w R^2. 10. Planowanie ruchu robota, suma Minkowskiego. 11. Algorytmy równoległe. 12. Algorytmy randomizacyjne. 13. Algorytmy aproksymacyjne. |
Literatura: |
1. F.P.Preparata, M.I.Shamos, "Geometria obliczeniowa. Wprowadzenie." 2. J.O'Rourke, "Computational geometry in C" 3. M.de Berg, M. van Kreveld, M.Overmars, O.Schwarzkopf, "Geometria obliczeniowa. Algorytmy I zastosowania." 4. Materiały na stronie: http://www.mimuw.edu.pl/~kowaluk |
Efekty uczenia się: |
Wiedza 1. Ma wiedzę z działów matematyki (geometria, kombinatoryka, teoria grafów) niezbędnych do studiowania omawianych zagadnień informatcznych (K_W01). 2. Dobrze rozumie rolę i znaczenie struktur danych wykorzystywanych w rozwiązaniach problemów (K_W02). 3. Zna problemy, techniki i narzędzia występujące w rozważaniach teoretycznych i praktycznych (K_W03). Umiejętności 1. Posiada umiejętność konstruowania rozumowań matematycznych (K_U01). 2. Potrafi wyrażać problemy obliczeniowe w języku matematyki (K_U02). 3. Projektuje algorytmy z wykorzystaniem poznanych technik. (K_U04). Kompetencje 1. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01). 2. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu (w szczególności w kontaktach z nieinformatykiem) lub odnalezieniu brakujących elementów rozumowania (K_K02). 3. Rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08). |
Metody i kryteria oceniania: |
Aktywność na zajęciach. Egzamin w formie testu. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT WYK
CW
ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mirosław Kowaluk | |
Prowadzący grup: | Mirosław Kowaluk | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mirosław Kowaluk | |
Prowadzący grup: | Mirosław Kowaluk | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.