Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Geometria obliczeniowa

Informacje ogólne

Kod przedmiotu: 1000-2M00GO
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: 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 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
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Mirosław Kowaluk
Prowadzący grup: Mirosław Kowaluk
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.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)