Algorytmy Optymalizacji Dyskretnej 2022/23

Podstawowe informacje

Kurs ten jest przedmiotem wybieralnym przeznaczonym dla studentów 2 i 3 roku (4 i 6 semestru) studiów I stopnia na kierunku Informatyka Algorytmiczna. Obejmuje on wykład (30 h), ćwiczenia (15 h) oraz laboratorium (15 h).


Rozkład zajęć:

  • Wykład
    • Wtorek, 1515–1655, s. 0.32 bud. C-13
  • Ćwiczenia
    • Wtorek TN, 1115–1300, s. 311a bud. D-1
    • Czwartek TN/TP, 1115–1300, s. D2.2 bud. C-16
    • Czwartek TN/TP, 1515–1655, s. D2.2 bud. C-16
  • Laboratorium (dr Dominik Bojko)
    • Poniedziałek TN/TP, 730–900, s. 317.2 bud. D-1
    • Czwartek TN/TP, 1515–1655, s. 317.2 bud. D-1
    • Czwartek TN/TP, 1705–1845, s. 317.2 bud. D-1
    • Czwartek TN/TP, 1855–2035, s. 317.2 bud. D-1


Opis kursu (karta przedmiotu): INP002276Wcl.pdf

Listy zadań na ćwiczenia

  • Lista 0 – grafy – podstawowe pojęcia i algorytmy (przypomnienie)
  • Lista 1 – problemy optymalizacyjne, programowanie liniowe (cz. I)
  • Lista 2 – programowanie liniowe (cz. II) – Min Cost Flow, Max Flow, redukcje
  • Lista 3 – programowanie liniowe całkowitoliczbowe – algorytmy, redukcje, problem plecakowy
  • Lista 4 – problemy najkrótszych ścieżek – modelowanie, własności, algorytm Dijkstry
  • Lista 5 – problem maksymalnego przepływu, zadania uzupełniające

Listy zadań na laboratorium

  • Lista 1 – Podstawowe algorytmy grafowe
    • Punkty do zdobycia: 0–10 pkt
    • Termin realizacji: trzecie zajęcia (drugie pełne laboratorium)
    • Paczka z testami: aod_testy1.zip
  • Lista 2 – Programowanie liniowe i całkowitoliczbowe
    • Punkty do zdobycia: 0–15 pkt
    • Termin realizacji: czwarte zajęcia
  • Lista 3 – Porównanie implementacji algorytmu Dijkstry
    • Punkty do zdobycia: 0–20 pkt
    • Termin realizacji: szóste zajęcia
  • Lista 4 – Maksymalny przepływ (Max Flow) – algorytmy bazujące na ścieżkach powiększających
    • Punkty do zdobycia: 0–20 pkt (w tym 5 pkt dodatkowych)
    • Termin realizacji: ostatnie zajęcia w semestrze

Zasady zaliczenia kursu

Zaliczenie grupy kursów składa się z dwóch części: zaliczenia laboratorium i kolokwium końcowego.


Zaliczenie laboratorium

  1. Na laboratoriach studenci prezentują rozwiązania zadań z list przygotowanych do kursu. Rozwiązania obejmują implementację, otrzymane wyniki oraz – jeśli jest wymagane – sprawozdanie.
  2. Rozwiązania wszystkich zadań powinny być samodzielnie opracowane przez studenta.
  3. Dla każdej listy określone będą zadania, których realizacja jest warunkiem jej zaliczenia. Warunkiem zaliczenia laboratorium jest zaliczenie wszystkich list zadań.
  4. Dla każdego zadania określona będzie liczba punktów do zdobycia. Liczba punktów przyznana za rozwiązanie zadania zależeć będzie od jego jakości i kompletności.
  5. Prowadzący może zażądać modyfikacji oddawanych kodów źródłowych oraz zadawać pytania sprawdzające, czy student opanował zagadnienia związane z prezentowanym rozwiązaniem. Odpowiedź studenta na zadane pytania może mieć wpływ na liczbę punktów uzyskaną za rozwiązanie.
  6. Za rozwiązania zadań oddane w terminie uważa się rozwiązania oddane najpóźniej na zajęciach określonych jako termin realizacji danej listy.
  7. Liczbę punktów uzyskanych za rozwiązania oddane po terminie realizacji, ale nie później niż do końca kolejnych zajęć, mnoży się przez 0,5. Za rozwiązania oddane jeszcze później student otrzymuje 0 pkt.
  8. Terminy realizacji list zadań ulegają przedłużeniu o okres usprawiedliwionej nieobecności. Okres ten może ulec przesunięciu w trudnych przypadkach losowych (prowadzący ustala ze studentem indywidualny termin).
  9. Końcowa punktacja z laboratorium jest sumą punktów uzyskanych za rozwiązania zadań z list. Łącznie na laboratorium można uzyskać 60 punktów + 5 punktów dodatkowych.
  10. Punktacja z laboratorium nie podlega poprawianiu po zakończeniu zajęć.
  11. Kwestie tu nieustalone określa prowadzący laboratorium.

Zasady obowiązujące na ćwiczeniach

  1. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru.
  2. Wykładowca ogłasza z wyprzedzeniem listy zadań do samodzielnego rozwiązania. Na ćwiczeniach studenci prezentują rozwiązania zadań oraz wyjaśniane są wątpliwości dotyczące rozwiązań. Decyzję odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
  3. Za zaprezentowanie poprawnego rozwiązania zadania na ćwiczeniach student otrzymuje punkt z aktywności. Punkty z aktywności doliczane są do końcowej punktacji z kursu.

Kolokwium końcowe

  1. Kolokwium końcowe odbędzie się na ostatnim wykładzie.
  2. Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4 podpisana w taki sposób, aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek i innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.
  3. Z kolokwium można uzyskać maksymalnie 40 punktów.

Prawa autorskie

Odpowiedzi na kolowkium oraz rozwiązania zadań na laboratorium, których autorstwa prowadzący nie może ustalić (przypadek, gdy studenci porozumiewają się w trakcie kolokwium bądź przedkładają rozwiązania zadań o identycznej formie), nie mogą być punktowane i są traktowane jako „brak odpowiedzi” / „nieoddane zadanie”.


Ocena końcowa z kursu

  1. Końcowa liczba uzyskanych punktów \(P\) jest sumą punktów z laboratorium \(L\) i z kolokwium końcowego \(K\) powiększoną o liczbę punktów z aktywności na ćwiczeniach \(A\), zgodnie ze wzorem \(P = L + K + 2A\).
  2. Warunkiem koniecznym zaliczenia grupy kursów jest zaliczenie laboratorium. Wówczas końcowa ocena wyznaczana jest w następujący sposób: \[ ocena = \begin{cases} 2.0 & \texttt{if } \ P \lt 50 \\ 3.0 & \texttt{if } \ P \in [50,60) \\ 3.5 & \texttt{if } \ P \in [60,70) \\ 4.0 & \texttt{if } \ P \in [70,80) \\ 4.5 & \texttt{if } \ P \in [80,90) \\ 5.0 & \texttt{if } \ P \ge 90 \\ \end{cases} \]
  3. Ocena celująca jest przyznawana z inicjatywy prowadzących w przypadku wyjątkowych osiągnięć studenta.

Literatura

  • R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Pearson Education, 2014
  • M.M. Sysło, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, Wydanie trzecie, Wydawnictwo Naukowe PWN, Warszawa 1999
  • S. Dasgupta, Ch. Papadimitriou , U. Vazirani, Algorithms, 1st edition, McGraw-Hill Education, 2006
  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa 2012
  • W. Lipski, Kombinatoryka dla programistów, WNT, 2007
  • C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization. Algorithms and Complexity, Dover Publication, Inc, Mineola, 1998
  • B. Korte, J. Vygen, Combinatorial Optimization – Theory and Algorithms, Springer-Verlag, Berlin Heidelberg, 2006 (wersja cyfrowa dostępna z domeny PWr)
  • P. Brucker, Scheduling Algorithms, Springer-Verlag, Berlin Heidelberg 2007 (wersja cyfrowa dostępna z domeny PWr)
  • R.S. Garfinkel, G.L. Nemhauser, Programowanie całkowitoliczbowe, Wydawnictwo Naukowe PWN, Warszawa 1978
  • S. Bradley, A. Hax, T. Magnanti, Applied Mathematical Programming, Addison-Wesley, 1977 (available online at web.mit.edu)

Materiały do kursu, przydatne linki i narzędzia

Zagadnienia omówione na wykładach (w przybliżeniu)

Slajdy do wykładów będą udostępniane w zakładce 'Pliki' na kanale zespołu (Wt 15:15) Algorytmy Optymalizacji Dyskretnej - Wykład (K00-08a / Lato 22/23) na platformie MS Teams.


  1. wykład (28.02.2023.)
    • informacje wstępne
      • organizacja pracy i zasady zaliczenia
      • literatura i materiały do kursu
    • wprowadzenie do kursu
      • metody optymalizacji – przykłady zastosowań
      • główne zagadnienia, czyli czym będziemy się zajmować
    • problemy optymalizacyjne – wprowadzenie
      • egzemplarz problemu optymalizacyjnego, problem optymalizacyjny
      • przykłady – minimum spanning tree (MST), shortest path
      • przykład – programowanie liniowe (LP)
      • egzemplarz problemu MST jako przykład egzemplarza problemu LP
    • programowanie liniowe – podstawy (cz. I)
      • motywacje i przykład
      • postać ogólna, kanoniczna i standardowa problemu LP
  2. wykład (07.03.2023.)
    • programowanie liniowe – podstawy (cz. II)
      • geometryczna interpretacja problemu LP
      • podstawowe własności zbioru rozwiązań dopuszczalnych (bez dowodu)
      • istnienie optymalnego rozwiązania w wierzchołku (bez dowodu)
      • ogólna idea algorytmu Simplex
    • problem najtańszego przepływu w sieci (Minimum Cost Flow)
      • definicja problemu, model formalny, przykład
      • problem Minimum Cost Flow jako zagadnienie LP
      • macierz incydencji jako macierz ograniczeń
      • założenie o całkowitoliczbowości, istnienie optymalnego rozwiązania całkowitoliczbowego (bez dowodu)
    • szczególne przypadki problemu Minimum Cost Flow
      • problem transportowy (transportation problem)
      • problem przydziału (assignment problem / bipartite weighted matching problem)
      • problem cyrkulacji (circulation problem)
      • problem najkrótszej ścieżki (shortest path problem)
  3. wykład (14.03.2023.)
    • problem maksymalnego przepływu w sieci (Maximum Flow)
      • definicja problemu, model formalny
      • problem Max Flow jako zagadnienie LP
      • związki maksymalnych przepływów z najtańszymi przepływami
    • redukcje
      • przykład – redukcja problemu Max Flow do problemu Min Cost Flow
      • ogólna idea redukcji dla problemów obliczeniowych
      • przykład – eliminacja niezerowych ograniczeń dolnych na przepustowość łuków w problemie Min Cost Flow
    • programowanie liniowe całkowitoliczbowe (ILP) – wprowadzenie
      • motywacje, ogólna idea
      • LP a ILP – złożoność obliczeniowa, dodatkowe uwagi
      • przykłady – capital-budgeting problem, warehouse location
  4. wykład (21.03.2023.)
    • rozwiązywanie zagadnień ILP – wprowadzenie
    • metoda podziału i ograniczeń dla ILP (branch and bound)
      • ogólna idea metody
      • przykład zastosowania do zagadnienia z dwoma zmiennymi decyzyjnymi
      • ogólne własności metody branch and bound
    • metoda przeglądu dla zmiennych decyzyjnych 0-1 (implicit enumeration)
      • ogólna idea metody
      • przykład zastosowania
      • najważniejsze własności
    • więcej informacji o omówionych metodach rozwiązywania zagadnień ILP: [BHM77] – Chapter 9
  5. wykład (21.03.2023.)
    • problem plecakowy (Knapsack Problem)
      • sformułowanie problemu – wersja dyskretna (0-1) i ciągła
      • model LP dla problemu plecakowego
      • algorytm zachłanny dla wariantu ciągłego – dowód poprawności, złożoność
      • własność rozwiązania optymalnego dla wariantu dyskretnego
      • algorytm dla dyskretnego problemu plecakowego (programowanie dynamiczne)
      • odtwarzanie optymalnego wyboru, złożoność algorytmu dla wariantu dyskretnego
    • złożoność obliczeniowa problemów dla sieci
      • reprezentacja sieci, rozmiar instancji problemów
      • uwagi dotyczące złożoności obliczeniowej
      • algorytmy silnie i słabo wielomianowe, algorytmy pseudowielomianowe
  6. wykład (04.04.2023.)
    • problemy wyznaczania najkrótszych ścieżek w sieciach – wprowadzenie
      • podstawowe pojęcia (trasa, ścieżka), definicja problemu i założenia
      • model LP dla problemu Shortest Path
      • podział na algorytmy typu label-setting i label-correcting
      • własności najkrótszych ścieżek
      • istnienie drzewa najkrótszych ścieżek
    • algorytm wyznaczania najkrótszych ścieżek w w grafach skierowanych (DAG-ach)
    • najkrótsze ścieżki w sieciach z nieujemnymi wagami krawędzi – algorytm Dijkstry
      • idea algorytmu Dijkstry, kluczowe obserwacje
      • pseudokod algorytmu Dijkstry, przykład działania
      • poprawność i złożoność czasowa
  7. wykład (18.04.2023.)
    • najkrótsze ścieżki w sieciach z nieujemnymi wagami krawędzi – algorytm Dijkstry (cd.)
      • generyczny algorytm Dijkstry – podsumowanie
      • kopiec jako przykład implementacji kolejki priorytetowej (ogólna idea)
      • implementacje algorytmu Dijkstry wykorzystujące kopce
    • implementacja Diala algorytmu Dijkstry
      • algorytm Dijkstry – własności distance labels
      • główna idea algorytmu Diala
      • wariant algorytmu Diala bez optymalizacji wykorzystania pamięci
      • złożoność czasowa i pamięciowa algorytmu
      • uwagi implementacyjne
    • implementacja Diala – optymalizacja użycia pamięci
      • zoptymalizowana implementacja Diala algorytmu Dijkstry
      • złożoność czasowa i pamięciowa algorytmu
  8. wykład (25.04.2023.)
    • implementacja Radix Heap algorytmu Dijkstry
      • idea użycia kubełków różnej szerokości
      • struktura Radix Heap
      • dynamiczna zmiana szerokości kubełków
      • algorytm Radix Heap i jego złożoność
      • przykład działania algorytmu
    • najkrótsze ścieżki w sieciach z dowolnymi wagami krawędzi
      • założenia modelu
      • algorytmy typu label-correcting
    • projektowanie algorytmów w oparciu o warunki optymalności
      • warunki optymalności (ang. optimality conditions)
      • warunki optymalności dla problemu najktórszych ścieżek
    • zredukowane koszty (ang. reduced costs)
      • pojęcie zredukowanych kosztów
      • zredukowane długości łuków
      • własności zredukowanych długości łuków
      • zredukowane długości łuków a warunki optymalności
      • warunki optymalności a istnienie ujemnych cykli
    • generyczny algorytm label-correcting
      • idea algorytmu generycznego
      • złożoność obliczeniowa algorytmu generycznego
  9. wykład (09.05.2023.)
    • generyczny algorytm label-correcting dla problemu najkrótszych ścieżek (cd.)
      • przykład działania
      • graf poprzedników i jego własności
      • poprawność algorytmu
    • zmodyfikowany algorytm label-correcting
      • procedura modified label-correcting
      • poprawność i złożoność algorytmu
      • poznane algorytmy wyznaczania najkrótszych ścieżek jako warianty algorytmu modified label-correcting
    • szczególne implementacje algorytmu modified label-correcting
      • algorytm Bellmana-Forda
      • algorytm FIFO label-correcting
      • algorytm DEQUE label-correcting
      • poprawność, złożoność i najważniejsze własności poszczególnych implementacji
    • metody wykrywania cykli o ujemnej długości w grafie sieci
      • przeszukiwanie grafu poprzedników
      • dedykowane techniki dla poznanych algorytmów
  10. wykład (16.05.2023.)
    • problem All-Pairs Shortest Path
      • definicja problemu
      • założenia modelu
    • algorytm Repeated Shortest Path
      • przypadek sieci z nieujemnymi długościami łuków
      • uogólnienie – dowolne długości łuków
      • najkrótsze ścieżki w sieci ze zredukowanymi kosztami
      • przejście do optymalnego rozwiązania w oryginalnej sieci
      • złożoność algorytmu
    • algorytmy All-Pairs label-correcting
      • warunki optymalności dla problemu All-Pairs Shortest Path
      • generyczny algorytm label-correcting i jego własności
      • algorytm Floyda-Warshalla
      • własności i złożoność algorytmu Floyda-Warshalla
    • algorytmy label-correcting – wykrywanie cykli o ujemnej długości
      • warunki dla algorytmów generycznego oraz Floyda-Warshalla
      • przeszukiwanie grafu poprzedników
  11. wykład (23.05.2023.)
    • problem maksymalnego przepływu w sieci (Max Flow) – wprowadzenie
      • definicja problemu
      • ogólne założenia
      • model LP dla problemu Max Flow
    • zredukowane koszty – ciąg dalszy
      • zredukowane koszty w kontekście problemu Min-Cost Flow
      • zredukowene koszty a najtańszy przepływ w sieci
    • sieci residualne
      • motywacje oraz konstrukcja
      • związek przepływów z przepływami w sieciach residualnych
      • sieci residualne dla problemu Max Flow
    • przepływy i przekroje (cuts)
      • przekrój, \(s\)–\(t\) przekrój – definicje, przykłady
      • pojemność przekroju, przekrój minimalny (minimum cut)
      • związki wielkości przepływów z pojemnościami przekrojów
      • pojemność residualna przekroju, związki z przepływami
    • przepływ po ścieżkach i cyklach (path-and-cycle flow)
      • oznaczenia i definicje
      • rozkład przepływu po ścieżkach i cyklach na przepływ po łukach
      • rozkład przepływu po łukach na przepływ po ścieżkach i cyklach
      • Flow Decomposition Algorithm i jego własności
  12. wykład (30.05.2023.) – zastępstwo (dr M. Gębala, prof. uczelni)
    • algorytmy dla problemu Max Flow oparte o ścieżki powiększające
      • ścieżki powiększające (augmenting paths) – definicja, własności, przykład
      • generyczny algorytm Forda-Fulkersona i jego bazowa implementacja
      • własności i złożoność bazowej implementacji algorytmu Forda-Fulkersona
      • ulepszenia generycznego algorytmu Forda-Fulkersona – motywacje, idee
      • algorytm Edmondsa-Karpa, jego złożoność i jego własności
      • wyznaczanie minimalnego przekroju w sieci
    • przykłady redukcji do problemów przepływów w sieciach
  13. wykład (06.06.2023.)
    • algorytmy dla problemu Max Flow wykorzystujące ścieżki powiększające – uzupełnienie
      • algorytmy dla problemu Max Flow – związki między sieciami a sieciami residualnymi
      • bazowa implementacja metody Forda-Fulkersona – algorytm Labeling
      • własności i złożoność algorytmu Labeling
      • twierdzenie o maksymalnym przepływie i minimalnym przekroju (Max-Flow Min-Cut theorem)
      • dualność w programowaniu liniowym – ogólna idea
      • wady algorytmu Labeling i pomysły na jego ulepszenie
    • funkcje odległości oraz etykiety (distance labels) w sieciach residualnych
      • funkcja odległości, prawidłowa funkcja odległości, prawidłowe etykiety
      • własności prawidłowych funkcji odległości
      • dokładne etykiety i ich wyznaczanie
      • dopuszczalne łuki i ścieżki – definicja i własności
    • algorytmy dla problemu Max Flow oparte o najkrótsze ścieżki powiększające
      • ograniczenia i możliwości ulepszenia algorytmu Edmondsa-Karpa
      • algorytm Shortest Augmenting Path
      • własności wyznaczanych etykiet i poprawność algorytmu
      • efektywny wybór dopuszczalnych łuków – struktura current-arc
  14. wykład (13.06.2023.)
    • złożoność obliczeniowa algorytmu Shortest Augmenting Path
      • algorytm Shortest Augmenting Path – przypomnienie
      • ograniczenie liczby wyznaczanych ścieżek powiększających
      • analiza złożoności obliczeniowej
    • praktyczne ulepszenie algorytmu Shortest Augmenting Path
      • usprawnienie algortmu – motywacje
      • wcześniejsze wykrywanie momentu zakończenia – idea i implementacja
      • poprawność "nowego" warunku zakończenia – wyznaczenie minimalnego przekroju
    • ograniczenia algorytmów opartych o ścieżki powiększające
    • algorytmy preflow-push dla problemu Max Flow
      • wprowadzenie – motywacje, podstawowe pojęcia i fakty
      • preflows (przedprzepływy / przepływy nadmiarowe)
      • idea algorytmów preflow-push (push-relabel)
      • generyczny algorytm Preflow-Push
      • własności i poprawność algorytmu Preflow-Push
      • uwagi o złożoności algorytmu generycznego
    • szczególne implementacje generycznego algorytmu Preflow-Push – ogólna idea
      • algorytm FIFO Preflow-Push
      • algorytm Highest-Label Preflow-Push
      • algorytm Excess Scaling
  15. wykład (20.06.2023.)
    • Kolokwium końcowe – szczegóły zostały podane na wykładzie 14.