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

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...

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. 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) 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)