Uniwersytet Jagielloński w Krakowie - Centralny System Uwierzytelniania
Strona główna

Algorytmy Geometryczne

Informacje ogólne

Kod przedmiotu: WMI.TCS.AGE.S
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy Geometryczne
Jednostka: Instytut Informatyki Analitycznej
Grupy:
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: polski

Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)

Okres: 2024-02-26 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Ślusarek
Prowadzący grup: Andrzej Pezarski, Maciej Ślusarek
Strona przedmiotu: http://satori.tcs.uj.edu.pl
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Efekty kształcenia:

E1 zna szerokie spektrum algorytmów i struktury danych specyficznych dla problemów geometrii obliczeniowej

E2 potrafi analizować problemy geometryczne pod kątem możliwości ich efektywnego rozwiązywania

E3 jest świadom wpływu architektury komputera, w szczególności błędów zaokrągleń, na wyniki obliczeń w geometrii i przewiduje skutki tego wpływu

E4 potrafi modelować problemy geometryczne przedstawione w języku naturalnym posługując się językiem matematyki i zaawansowanymi koncepcjami algorytmicznymi

E5 projektuje i implementuje efektywne rozwiązania dla problemów geometrycznych z wykorzystaniem wydajnych algorytmów i struktur danych
Wymagania wstępne:

Znajomość algorytmów i struktur danych na dobrym poziomie (np. przedmiotu Algorytmy i struktury danych 1 i 2: WMI.TCS.ASD1.OL, WMI.TCS.ASD2.OL).
Forma i warunki zaliczenia:

Zaliczenie ćwiczeń na podstawie programów uruchamianych na serwerze zadaniowym i zadań domowych.

Egzamin pisemny.

Wynik końcowy jest średnią ocen z ćwiczeń i egzaminu, z jednakową wagą.
Metody sprawdzania i kryteria oceny efektów kształcenia uzyskanych przez studentów:

Samodzielnie implementowane zadania programistyczne (E1 - E5)

Samodzielne rozwiązywanie zadań tablicowych (E1, E2, E4, E5)

Dyskusja podczas zajęć (E1 - E5)
Metody dydaktyczne:

1. Wykład.

2. Ćwiczenia w laboratorium komputerowym, połączone z dyskusją przy tablicy.

3. Samodzielna implementacja zadań programistycznych i automatyczne testowanie ich na serwerze zadaniowym
Bilans punktów ECTS:

6
Sylabus przedmiotu dla studentów rozpoczynających studia od roku akademickiego 19/20 lub później:

Informatyka analityczna, studia stacjonarne drugiego stopnia, rok 1
Informatyka analityczna, studia stacjonarne drugiego stopnia, rok 2
Skrócony opis:

Problemy algorytmiczne w geometrii i ich zastosowania. Techniki algorytmiczne i struktury danych specyficzne dla dziedziny. Algorytmy rozwiązujące problemy z geometrii, ich analiza i implementacja.
Pełny opis:

1. Podstawowe techniki algorytmiczne w geometrii, przykłady prostych zastosowań w algorytmach wypukłej otoczki na płaszczyźnie.

2. Algorytm Chana dla wypukłej otoczki i dolne oszacowanie złożoności problemu.

3. Przecinanie się odcinków na płaszczyźnie, zastosowania.

4. Reprezentacja podziału płaszczyzny - podwójnie wiązana lista krawędzi; nakładanie podziałów płaszczyzny.

5. Diagramy Voronoi: własności, algorytm zamiatania.

6. Problem galerii i triangulacja wielokąta, podział wielokąta na fragmenty monotoniczne.

7. Lokalizacja punktu: metoda łańcuchów, mapy trapezowe i algorytm przyrostowy, analiza probabilistyczna.

8. Otoczka wypukła w R^3, algorytm przyrostowy.

9. Dualność, układy prostych na płaszczyźnie, zastosowania.

10. Przeszukiwanie obszarów ortogonalnych, kd-drzewa, wielowymiarowe drzewa obszarów, kaskadowanie cząstkowe.

11. Wybrane struktury danych w geometrii obliczeniowej: drzewa przedziałów, drzewa wyszukiwania priorytetowego, drzewa odcinków.

12. Drzewa BSP, konstrukcja, algorytm malarza.
Literatura:

Obowiązuje przede wszystkim materiał wyłożony, literatura ma charakter pomocniczy. Do odpowiednich zagadnień literatura podawana jest na bieżąco w trakcie wykładu.

1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Geometria obliczeniowa, WNT, 2007.

2. F. Preparata, M. Shamos, Geometria obliczeniowa: wprowadzenie, Helion, 2003

3. D.Mount, Computational Geometry, Lecture Notes, U. Maryland, 2020.
Uwagi:

Do egzaminu można przystąpić z dowolną oceną z ćwiczeń różną od NZAL. Punktacja końcowa z przedmiotu jest średnią ważoną z zaliczenia i egzaminu, z jednakową wagą. Ocena dostateczna wymaga zdobycia 60% maksymalnej do osiągnięcia liczby punktów, ocena bardzo dobra - 90%, pozostałe proporcjonalnie.

Nie ma zaliczania ćwiczeń w sesji poprawkowej, za wyjątkiem sytuacji losowych za zgodą dziekana.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.
ul. Gołębia 24, 31-007 Kraków https://www.uj.edu.pl kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0 usosweb12c