Algorytmy Optymalizacji Dyskretnej 2024/25

Podstawowe informacje

Kurs ten jest przedmiotem wybieralnym przeznaczonym dla studentów 3 roku (5 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
    • Środa, 1115–1300, s. 41 bud. C-4
  • Ćwiczenia
    • Wtorek TN/TP, 1315–1500, s. D3.1 bud. C-16
  • Laboratorium (mgr inż. Błażej Wróbel)
    • Wtorek TN/TP, 1515–1655, s. 317.4 bud. D-1
    • Wtorek TN/TP, 1705–1845, s. 317.4 bud. D-1

Opis kursu (karta przedmiotu): INP002276Wcl.pdf

Listy zadań na ćwiczenia

  • Lista 1 – problemy optymalizacyjne (wprowadzenie), programowanie liniowe (cz. I)
  • Lista 2 – programowanie liniowe (cz. II) – modele dla problemów przepływów w sieciach (Min Cost Flow, Max Flow i ich warianty), redukcje
  • Lista 3 – programowanie liniowe całkowitoliczbowe – modele, problem plecakowy, problem Bin Packing, redukcje
  • Lista 4 – problem najkrótszych ścieżek – modelowanie, zastosowania, własności, algorytmy label-setting i label-correcting

Listy zadań na laboratorium

  • Lista 1 – Podstawowe algorytmy grafowe
    • Punkty do zdobycia: 0–6 pkt
    • Termin realizacji: ostatnie zajęcia przed 30.10.2024.
    • Paczka z testami: aod_testy1.zip
  • Lista 2 – Programowanie liniowe i całkowitoliczbowe
  • Lista 3 – Porównanie implementacji algorytmu Dijkstry
    • Punkty do zdobycia: 0–20 pkt
    • Termin wysyłania (MS Teams): 09.12.2024. godz. 23:59
    • Termin oddawania: pierwsze zajęcia po terminie wysłania
    • Paczka z testami: ch9-1.1.tar.gz

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ń oraz sprawozdania 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 ma 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.
  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 1 lub 2 punkty z aktywności, w zależności od jakości rozwiązania lub trudności zadania. 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 kolokwium oraz rozwiązania zadań na laboratorium (w tym sprawozdania), których autorstwa prowadzący nie może ustalić (przypadek, gdy studenci porozumiewają się w trakcie kolokwium lub przedkładają rozwiązania zadań o identycznej formie), lub w których nie zostały wyraźnie oznaczone źródła pochodzenia wykorzystywanych fragmentów (brak odpowiednich cytowań lub informacji o wygenerowaniu przez dostępne narzędzia, w tym AI), 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 + A\).
  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, Introduction to Algorithms, 4th edition, MIT Press, 2022
  • 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 (Sr 11:15) Algorytmy Optymalizacji Dyskretnej - Wykład (Zima 24/25) na platformie MS Teams.


  1. wykład (02.10.2024; \(\rightarrow\) kontynuacja na ćw. 08.10.2024.)
    • informacje wstępne
      • organizacja pracy i zasady zaliczenia
      • literatura i materiały do kursu
    • omówienie listy 1 na laboratorium – podstawowe algorytmy grafowe
    • 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, sequencing with delays
      • przykład – programowanie liniowe (LP)
      • egzemplarz problemu MST jako przykład egzemplarza problemu LP
    • programowanie liniowe – podstawy
      • motywacje i przykład
      • postać ogólna, kanoniczna i standardowa problemu LP
      • geometryczna interpretacja problemu LP
      • podstawowe własności zbioru rozwiązań dopuszczalnych (bez dowodu)
  2. wykład (09.10.2024.)
    • programowanie liniowe – podstawy (kontynuacja)
      • istnienie optymalnego rozwiązania w wierzchołku (bez dowodu)
      • ogólna idea algorytmu Simplex
      • uwagi o złożoności obliczeniowej programowania liniowego
    • 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 (16.10.2024.)
    • omówienie listy 2 na laboratorium – programowanie liniowe i całkowitoliczbowe
    • 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 (23.10.2024.)
    • programowanie liniowe całkowitoliczbowe (ILP) – uzupełnienie
      • rozwiązywanie zagadnień ILP – intuicje, ogólna idea
      • rozwiązywanie zagadnień ILP – dodatkowe materiały dla zainteresowanych: [BHM77], Chapter 9
    • problem plecakowy (Knapsack Problem)
      • sformułowanie problemu – wersja dyskretna (0-1) i ciągła
      • modele LP/ILP dla problemu plecakowego
      • uwagi o złożoności problemu plecakowego
      • warianty problemu plecakowego
      • problem Subset-Sum jako szczególny przypadek
      • problem Bin Packing – model ILP, heurystyka first fit decreasing (bez analizy)
    • algorytmy dla problemu plecakowego (część 1. – wariant ciągły)
      • algorytm zachłanny dla wariantu ciągłego
      • analiza poprawności i złożoności algorytmu zachłannego
  5. wykład (30.10.2024.)
    • algorytmy dla problemu plecakowego (część 2. – wariant dyskretny)
      • algorytm oparty o programowanie dynamiczne dla wariantu dyskretnego
      • analiza poprawności i złożoności algorytmu
      • uwagi o schemacie aproksymacyjnym dla dyskretnego problemu plecakowego
    • 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
    • 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 acyklicznych grafach skierowanych (DAG-ach) – przypomnienie z kursu AiSD
  6. wykład (06.11.2024.)
    • najkrótsze ścieżki w sieciach z nieujemnymi wagami krawędzi – algorytm Dijkstry
      • idea algorytmu Dijkstry, kluczowe obserwacje
      • pseudokod generycznego algorytmu Dijkstry, przykład działania
      • poprawność i złożoność czasowa
      • 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
      • zakres tymczasowych distance labels w pojedynczej iteracji
      • zoptymalizowana implementacja Diala algorytmu Dijkstry
      • złożoność czasowa i pamięciowa algorytmu
  7. wykład (13.11.2024.)
    • 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 i realokacja węzłów
      • algorytm Radix Heap – omówienie implementacji i przykład działania
      • analiza złożoności algorytmu Radix Heap
    • omówienie listy 3 na laboratorium – implementacja i testowanie poznanych wariantów algorytmu Dijkstry
    • 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 (z dowodem)