Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Algorytmy najkrótszych ścieżek

Informacje ogólne

Kod przedmiotu: 1000-2M24ANS
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy najkrótszych ścieżek
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty dla doktorantów
Przedmioty obieralne dla informatyki
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: (brak danych)
Rodzaj przedmiotu:

monograficzne

Założenia (lista przedmiotów):

Algorytmy i struktury danych 1000-213bASD

Założenia (opisowo):

W niektórych częściach materiału pomocna będzie podstawowa wiedza z algebry

liniowej, rachunku prawdopodobieństwa i przedmiotu Algorytmika (1000-2N00ALG).

Skrócony opis:

Przedmiot poświęcony jest teoretycznym aspektom obliczania najkrótszych ścieżek w grafach, wykraczającym poza zakres podstawowych przedmiotów algorytmicznych. Omówimy niektóre z najważniejszych teoretycznych osiągnięć ostatnich dekad w tym zakresie: algorytmy skalujące w przypadku ujemnych wag, wyrocznie odległości, algorytmy dynamiczne i równoległe, ograniczenia dolne. Spojrzymy również na zastosowania tychże i związki z innymi fundamentalnymi problemami algorytmicznymi na grafach.

Pełny opis:

1. Warianty problemu i modele obliczeń. Podstawowe algorytmy: Dijkstra, Bellman-Ford, ich uogólnienia, skalowanie wag.

2. Klasyczne skalowanie dla SSSP z ujemnymi wagami: Goldberg, Gabow-Tarjan.

3. Ograniczenia dolne: równoważność APSP, znajdowania ujemnego trójkąta i powiązanych problemów.

4. Dynamiczne struktury danych utrzymujące najkrótsze ścieżki (wybór).

5. Algorytmy algebraiczne: APSP w grafach skierowanych, nieskierowanych; wyrocznie odległości.

6. Spannery. Aproksymacyjne wyrocznie odległości w grafach nieskierowanych.

7. Low-diameter decomposition (LDD) w grafach nieskierowanych i skierowanych i zastosowania.

8. SSSP z ujemnymi wagami w czasie prawie liniowym.

9. Algorytmy równoległe: klasyczne, redukcja dokładnego całkowitoliczbowego SSSP do wariantu przybliżonego, równoległe LDD.

10. Podstawowe techniki dla grafów planarnych i minor-free.

11. Najkrótsze ścieżki w “życiowych” grafach: highway dimension.

Literatura:

Notatki i artykuły badawcze wskazane przez wykładowcę.

Efekty uczenia się:

Wiedza: student:

1. zna i potrafi umotywować najważniejsze warianty, w których rozważa się fundamentalne problemy ścieżkowe w grafach,

2. rozumie znaczenie wyboru modelu obliczeń dla określania złożoności obliczeniowej problemów algorytmicznych,

3. ma zaawansowaną wiedzę z zakresu projektowania algorytmów rozwiązujących (wielomianowe) problemy grafowe i dowodzenia ich ograniczeń dolnych.

Umiejętności: student:

1. potrafi zastosować poznane techniki do konstruowania wydajnych algorytmów dla problemów grafowych bądź dowodzenia ich trudności,

2. potrafi w formalny sposób dowieść poprawności i określić złożoność czasową algorytmów w omawianych wydaniach: statycznym, dynamicznym, i równoległym.

Kompetencje: student:

1. zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej.

2. rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy.

Metody i kryteria oceniania:

Ocena końcowa będzie zależała od wyników prac domowych (teoretycznych; ok. 70%) i egzaminu ustnego (ok. 30%).

Egzamin ustny będzie miał jedną z dwóch form (do wyboru studenta):

1. sprawdzianu znajomości materiału z wykładu, albo

2. rozmowy nt. jednego powiązanego artykułu naukowego nieomawianego na zajęciach, do samodzielnego zapoznania się przez studenta. Zostanie podana lista możliwych artykułów. Będzie można zaproponować artykuł spoza listy, ale będzie on musiał być wcześniej zaakceptowany przez wykładowcę.

W przypadku zaliczania przedmiotu przez doktoranta, tylko druga forma egzaminu ustnego jest dozwolona.

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

Okres: 2024-02-19 - 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: Adam Karczmarz
Prowadzący grup: Adam Karczmarz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)

Okres: 2025-02-17 - 2025-06-08

Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Adam Karczmarz
Prowadzący grup: Adam Karczmarz
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 mapa serwisu USOSweb 7.0.4.0-7ba4b2847 (2024-06-12)