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 informatyczne dla doktorantów Przedmioty obieralne dla informatyki |
Punkty ECTS i inne: |
6.00
|
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 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-17 - 2025-06-08 |
Przejdź do planu
PN WYK
CW
WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Adam Karczmarz | |
Prowadzący grup: | Adam Karczmarz | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.