Karol Gotfryd

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, 11¹⁰–12⁵⁰, s. 41 bud. C-4
• Ćwiczenia
  • Czwartek TN, 11¹⁵–13⁰⁰, s. 35 bud. C-4
  • Czwartek TP, 11¹⁵–13⁰⁰, s. 41 bud. C-4
• Laboratorium (mgr inż. Błażej Wróbel)
  • Wtorek TN/TP, 15¹⁵–16⁵⁵, s. 317.3 bud. D-1
  • Środa TN/TP, 9¹⁵–11⁰⁰, s. 317.2 bud. D-1

Opis kursu (karta przedmiotu): W04INA-SI0809G.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, szeregowanie zadań, problem plecakowy, problem Bin Packing, redukcje
• Lista 4 – problem najkrótszych ścieżek – modelowanie, zastosowania, własności, algorytmy
• Lista 5 – problem maksymalnego przepływu, skojarzenia w grafach dwudzielnych

Listy zadań na laboratorium

• Lista 1 – Podstawowe algorytmy grafowe
  • Waga listy: \(w_1 = 0,\!05\)
  • Termin realizacji: ostatnie zajęcia przed 31.10.2025.
  • Paczka z testami: aod_testy1.zip
• Lista 2 – Programowanie liniowe i całkowitoliczbowe
  • Waga listy: \(w_2 = 0,\!15\)
  • Termin realizacji: ostatnie zajęcia przed 20.11.2025.
  • Rysunek grafu do zadania 4(a): rcsp_graph_ex4.pdf
  • Przydatne linki: patrz sekcja Materiały do kursu...
• Lista 3 – Porównanie implementacji algorytmu Dijkstry
  • Waga listy: \(w_3 = 0,\!2\)
  • Termin realizacji: ostatnie zajęcia przed 18.12.2025.
  • Paczka z testami: ch9-1.1.tar.gz
• Lista 4 – Maksymalny przepływ (Max Flow) – algorytmy bazujące na ścieżkach powiększających
  • Waga listy: \(w_4 = 0,\!2\)
  • Termin realizacji: ostatnie zajęcia przed 29.01.2026.

Zasady zaliczenia kursu

Zaliczenie grupy kursów składa się z zaliczenia laboratorium i ćwiczeń oraz kolokwium końcowego.

Zaliczenie laboratorium

1. Na laboratoriach rozwiązania zadań z list przygotowanych do kursu prezentowane są prowadzącemu zajęcia. Rozwiązania obejmują implementację, otrzymane wyniki oraz – jeśli jest wymagane – sprawozdanie.
2. Rozwiązania wszystkich zadań oraz sprawozdania powinny być opracowane samodzielnie.
3. Dla każdej listy określone będą warunki jej zaliczenia. Warunkiem zaliczenia laboratorium jest zaliczenie wszystkich list zadań.
4. Z każdej listy można uzyskać od 0 do 5 punktów (plus ewentualne punkty dodatkowe). Dla każdej listy określona będzie również jej waga. Wagi sumują się do 0,6.
5. Końcowa punktacja z laboratorium \(L\) (w skali od 0 do 3 + dodatkowe 0,5 pkt) jest sumą ważoną punktów uzyskanych za rozwiązania zadań z list, tj. \(L = \sum_{i} \, p_i \cdot w_i\), gdzie \(p_i\) oraz \(w_i\) to, odpowiednio, liczba punktów uzyskanych za \(i\)-tą listę oraz jej waga.
6. Liczba punktów przyznana za rozwiązania zadań z list zależy od ich jakości i kompletności. Prowadzący może zażądać modyfikacji oddawanych kodów źródłowych oraz zadawać pytania sprawdzające, czy dana osoba opanowała zagadnienia związane z prezentowanym rozwiązaniem. Odpowiedzi na zadane pytania mają wpływ na liczbę uzyskanych punktów.
7. 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. 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. Rozwiązania oddane jeszcze później oceniane są na 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 (wówczas prowadzący ustala indywidualny termin).
9. Punktacja z laboratorium nie podlega poprawianiu po zakończeniu zajęć.
10. Kwestie tu nieustalone określa prowadzący laboratorium.

Zaliczenie ćwiczeń

1. Wykładowca ogłasza z wyprzedzeniem listy zadań do samodzielnego rozwiązania. Na ćwiczeniach prezentowane są 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.
2. Osoby prezentujące poprawne rozwiązania zadań na ćwiczeniach mogą otrzymać punkty z aktywności, w zależności od jakości rozwiązania i sposobu jego przedstawienia. Punkty te doliczane są do końcowej punktacji z ćwiczeń.
3. Na ćwiczeniach przeprowadzane będą krótkie sprawdziany polegające na rozwiązaniu jednego zadania i będą punktowane w skali od 0 do 5. Materiałem obowiązującym na sprawdzianie są tematy omawiane na trzech poprzednich ćwiczeniach. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi.
4. Nieusprawiedliwiona nieobecność na sprawdzianie lub nieoddanie rozwiązania skutkuje wynikiem 0. W przypadku usprawiedliwionej nieobecności prowadzący ustala indywidualny termin i sposób zaliczenia sprawdzianu.
5. Końcowa punktacja z ćwiczeń \(C\) jest średnią punktów ze sprawdzianów powiększoną o liczbę punktów z aktywności.
6. Punktacja z ćwiczeń nie podlega poprawianiu po zakończeniu zajęć.

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ć, do kogo należy. Oprócz tego nie można mieć żadnych innych kartek, książek lub innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.
3. Z kolokwium można uzyskać od 0 do 5 punktów.

Prawa autorskie i narzędzia AI

Odpowiedzi na sprawdzianach, kolokwium oraz rozwiązania zadań na laboratorium (w tym sprawozdania), których autorstwa prowadzący nie może ustalić (przypadek, gdy osoby porozumiewają się w trakcie sprawdzianu bądź 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 szczegółowej informacji o wygenerowaniu przez dostępne narzędzia, w tym AI), nie mogą być punktowane i są traktowane jako „brak odpowiedzi” / „nieoddane zadanie”.

W przypadku korzystania z narzędzi AI należy na prośbę prowadzącego umożliwić mu wgląd do wykorzystanych promptów i zwracanych odpowiedzi. Osoby używające narzędzi AI ponoszą odpowiedzialność za wszelkiego rodzaju błędy i nieakceptowalne treści zawarte w wykorzystanych odpowiedziach (np. błędy merytoryczne, wskazanie nieistniejących źródeł literaturowych, sformułowania nieakceptowalne etycznie, itp.) czy ewentualne naruszenie praw autorskich.

Ocena końcowa z kursu

1. Końcowa punktacja \(P\) z grupy kursów wyznaczana jest na podstawie punktów z laboratorium \(L\), ćwiczeń \(C\) i kolokwium końcowego \(K\) zgodnie ze wzorem \(P = L \, + \, 0,\!3 \cdot K \, + \, 0,\!1 \cdot C\).
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 2,\!75 \\ 3.0 & \texttt{if } \ P \in [2,\!75, \ 3,\!25) \\ 3.5 & \texttt{if } \ P \in [3,\!25, \ 3,\!75) \\ 4.0 & \texttt{if } \ P \in [3,\!75, \ 4,\!25) \\ 4.5 & \texttt{if } \ P \in [4,\!25, \ 4,\!75) \\ 5.0 & \texttt{if } \ P \ge 4,\!75 \end{cases} \]

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, 1^st edition, McGraw-Hill Education, 2006
• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 4^th 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

• Network Flows: Theory, Algorithms, and Applications - James Orlin's page
• Optimization Methods in Business Analytics – strona kursu na MIT (T. Magnanti, J. Orlin)
• Network Optimization – strona kursu na MIT OpenCourseware
• Introduction to Algorithms, 4^th edition by T.H. Cormen et al. – book website (The MIT Press)
• Decision Tree for Optimization Software – problemy optymalizacyjne: materiały, narzędzia, dane testowe
• OR-Library – dane testowe dla wielu problemów optymalizacyjnych
• OR-Notes – Operations research notes by prof. J.E. Beasley
• A compendium of NP optimization problems
• strona kursu Metody Optymalizacji – INA ALG, II stopień, prof. P. Zieliński
• JuMP – a modeling language and supporting packages for mathematical optimization in Julia
• HiGHS – High-performance parallel linear optimization software
• Cbc (COIN-OR Branch and cut) – an open-source MIP solver written in C++
• Optimization with PuLP – an LP/MIP modeler written in Python
• Google OR-Tools – a fast and portable software for combinatorial optimization
• GLPK (GNU Linear Programming Kit) – a package for solving large-scale linear programming (LP) and mixed integer programming (MIP) problems
• GUSEK (GLPK Under Scite Extended Kit) – GLPK + IDE for Windows
• lp_solve 5.5 – a Mixed Integer Linear Programming (MILP) solver
• lp_solve + IDE for Windows

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 (Śr 11:10) Algorytmy Optymalizacji Dyskretnej - Wykład (Zima 25/26) na platformie MS Teams.

0. wykład (02.10.2025. – pierwsze ćwiczenia „połówkowe”)
   • informacje wstępne
     • organizacja pracy i zasady zaliczenia
     • literatura i materiały do kursu
   • krótkie 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ć
1. wykład (08.10.2025.)
   • 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)
     • istnienie optymalnego rozwiązania w wierzchołku (bez dowodu)
     • ogólna idea algorytmu Simplex
     • uwagi o złożoności obliczeniowej programowania liniowego
2. wykład (15.10.2025.)
   • omówienie listy 2 na laboratorium – programowanie liniowe i całkowitoliczbowe
   • problem najtańszego przepływu w sieci (Minimum Cost Flow)
     • definicja problemu, model formalny, przykład
     • przepływy w sieciach – przykładowe obszary zastosowań
     • 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 (22.10.2025.)
   • problem maksymalnego przepływu w sieci (Maximum Flow)
     • definicja problemu, model formalny, przykład
     • 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
     • rozwiązywanie zagadnień ILP – intuicje, ogólna idea
     • rozwiązywanie zagadnień ILP – dodatkowe materiały dla zainteresowanych: [BHM77], Chapter 9
   • optymalizacja w warunkach niepewności – ogólna idea
     • problem niepewnych danych
     • przykład – wariant odporny zagadnienia LP
     • elementarne modele niepewności – dyskretna, przedziałowa, budżetowa (proste przykłady)
4. wykład (29.10.2025.)
   • 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 – wariant ciągły
     • algorytm zachłanny dla wariantu ciągłego
     • analiza poprawności i złożoności algorytmu zachłannego
   • algorytmy dla problemu plecakowego – wariant dyskretny
     • uwagi o strategii zachłannej dla wariantu dyskretnego
     • algorytm pseudowielomianowy oparty o programowanie dynamiczne o złożoności zależnej od wag przedmiotów
     • algorytm pseudowielomianowy oparty o programowanie dynamiczne o złożoności zależnej od wartości przedmiotów
     • analiza poprawności i złożoności algorytmów
     • algorytmy aproksymacyjne – wprowadzenie (podstawowe pojęcia)
5. wykład (05.11.2025.)
   • algorytmy dla dyskretnego problemu plecakowego – uzupełnienie
     • w pełni wielomianowy schemat aproksymacyjny (FPTAS) dla dyskretnego problemu plecakowego
     • analiza złożoności i wyznaczenie współczynnika aproksymacji
   • 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
6. wykład (12.11.2025.)
   • algorytm wyznaczania najkrótszych ścieżek w acyklicznych grafach skierowanych (DAG-ach) – przypomnienie z kursu AiSD
   • podejścia oparte o przeglądanie krawędzi wchodzących (pulling) oraz wychodzących (reaching)
   • analiza poprawności i złożoności czasowej
   • 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 (19.11.2025.)
   • 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
   • dodatkowe uwagi do listy 3 na laboratorium – implementacja i testowanie poznanych wariantów algorytmu Dijkstry (lista była wstępnie omówiona na 5. wykładzie)
   • 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)
   • 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 dla problemu najktórszych ścieżek
8. wykład (26.11.2025.)
   • zredukowane długości łuków – uzupełnienie
     • własności zredukowanych długości łuków – przypomnienie
     • zredukowane długości łuków i warunki optymalności a istnienie ujemnych cykli
   • generyczny algorytm label-correcting
     • idea algorytmu generycznego
     • złożoność obliczeniowa algorytmu generycznego
     • 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
9. wykład (03.12.2025.)
   • problem All-Pairs Shortest Path
     • definicja problemu
     • założenia modelu
   • algorytm Repeated Shortest Path (algorytm Johnsona)
     • 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 All-Pairs label-correcting – wykrywanie cykli o ujemnej długości
   • warunki dla algorytmów generycznego oraz Floyda-Warshalla
   • przeszukiwanie grafu poprzedników
10. wykład (10.12.2025.)
    • problem maksymalnego przepływu w sieci (Max Flow) – wprowadzenie
      • definicja problemu
      • ogólne założenia
      • model LP dla problemu Max Flow
      • główne podejścia algorytmiczne
    • sieci residualne
      • motywacje, konstrukcja, przykład
      • 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
11. wykład (17.12.2025.)
    • algorytmy dla problemu Max Flow oparte o ścieżki powiększające – wprowadzenie
      • ścieżki powiększające (augmenting paths) – definicja, własności, przykład
      • generyczny algorytm Forda-Fulkersona i jego bazowa implementacja
      • przykład działania
      • algorytmy dla problemu Max Flow – związki między sieciami a sieciami residualnymi
    • bazowa implementacja metody Forda-Fulkersona – algorytm Labeling
      • podstawowe własności i złożoność algorytmu Labeling
      • wyznaczanie minimalnego przekroju w sieci
      • twierdzenie o maksymalnym przepływie i minimalnym przekroju (Max-Flow Min-Cut theorem)
      • dualność w programowaniu liniowym – ogólna idea
    • implementacje metody Forda-Fulkersona o złożoności wielomianowej
      • wady algorytmu Labeling i pomysły na jego ulepszenie
      • ulepszenia generycznego algorytmu Forda-Fulkersona – motywacje, idee
      • algorytm wybierający ścieżkę o największej pojemności residualnej – idea, intuicje
      • algorytm Edmondsa-Karpa, jego złożoność i podstawowe własności