Algorytmy najkrótszych ścieżek 1000-2M24ANS
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.
Rodzaj przedmiotu
Założenia (lista przedmiotów)
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
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.
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.
Literatura
Notatki i artykuły badawcze wskazane przez wykładowcę.
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: