Algorytmy najkrótszych ścieżek

monograficzne

Algorytmy i struktury danych 1000-213bASD

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

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

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.

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.

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

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.

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.