Geometria obliczeniowa 1000-2M00GO
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.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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).
Kryteria oceniania
Aktywność na zajęciach. Egzamin w formie testu.
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
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: