Module also offered within study programmes:
General information:
Name:
Discrete Programming
Course of study:
2019/2020
Code:
AMAT-1-512-s
Faculty of:
Applied Mathematics
Study level:
First-cycle studies
Specialty:
-
Field of study:
Mathematics
Semester:
5
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Żak Andrzej (zakandrz@agh.edu.pl)
Module summary

Problemy programowania dyskretnego (załadunku, przydziału, komiwojażera, lokalizacyjno-transportowy, pokrycia zbioru itd.) oraz ich modele matematyczne w postaci problemów progr. całkowitoliczbowego.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania Activity during classes,
Examination,
Test,
Oral answer
Skills: he can
M_U001 potrafi samodzielnie zbudować model matematyczny (model problemu programowania całkowitoliczbowego) dla różnorodnych zagadnień praktycznych oraz znaleźć jego rozwiązanie za pomocą dostępnych programów komputerowych. Activity during classes,
Examination,
Test,
Oral answer
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z programowania dyskretnego Activity during classes,
Examination,
Test,
Oral answer
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, matematyka dyskretna, programowanie liniowe, teoria grafów) w programowaniu dyskretnym Activity during classes,
Examination,
Test,
Oral answer
Knowledge: he knows and understands
M_W001 zna podstawowe problemy programowania dyskretnego (załadunku, przydziału, komiwojażera, lokalizacyjno-transportowy, pokrycia zbioru itd.) oraz ich modele matematyczne w postaci problemów programowania całkowitoliczbowego. Activity during classes,
Examination,
Test,
Oral answer
M_W002 zna podstawowe metody rozwiązywania problemów programowania całkowitoliczbowego i binarnego. Activity during classes,
Examination,
Test,
Oral answer
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 0 30 0 0 0 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + - + - - - - - - - -
Skills
M_U001 potrafi samodzielnie zbudować model matematyczny (model problemu programowania całkowitoliczbowego) dla różnorodnych zagadnień praktycznych oraz znaleźć jego rozwiązanie za pomocą dostępnych programów komputerowych. + - + - - - - - - - -
M_U002 potrafi samodzielnie przeprowadzić proste dowody wykorzystując poznaną wiedzę z programowania dyskretnego + - + - - - - - - - -
M_U003 potrafi wykorzystać wiedzę z innych działów matematyki (algebra, matematyka dyskretna, programowanie liniowe, teoria grafów) w programowaniu dyskretnym + - + - - - - - - - -
Knowledge
M_W001 zna podstawowe problemy programowania dyskretnego (załadunku, przydziału, komiwojażera, lokalizacyjno-transportowy, pokrycia zbioru itd.) oraz ich modele matematyczne w postaci problemów programowania całkowitoliczbowego. + - + - - - - - - - -
M_W002 zna podstawowe metody rozwiązywania problemów programowania całkowitoliczbowego i binarnego. + - + - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 150 h
Module ECTS credits 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 37 h
Realization of independently performed tasks 51 h
Examination or Final test 2 h
Module content
Lectures (30h):

1. Programowanie dyskretne, programowanie całkowitoliczbowe, programowanie binarne, optymalizacja kombinatoryczna. Zastosowania – układanie rozkładów jazdy pociągów, planów lotów samolotów, sporządzanie harmonogramów prac dużych przedsięwzięć inwestycyjnych, planowanie produkcji, podejmowanie optymalnych decyzji.

2. Modele matematyczne wybranych problemów. Przegląd metod stosowanych do rozwiązywania zadań PC, klasyfikacja: modeli matematycznych, zagadnień praktycznych, metod numerycznych.

3. Ograniczenia w zadaniach PC. Liniowe układy diofantyczne, macierze unimodularne, postać Smitha i Hermita macierzy. Kraty ze skończonym zbiorem generatorów.

4. Twierdzenia o istnieniu rozwiązań liniowych układów diofantycznych. Macierze pseudoodwrotne. Metody rozwiązywania układów diofantycznych.

5. Wielościany wymierne, ściany wielościanów, wielościany całkowite. Macierze totalnie unimodularne, przedziałowe, zbalansowane. Twierdzenie Veinotta – Dantziga o związkach tych macierzy z wielościanami całkowitymi.

6. Twierdzenia Hoffmana—Kruskala o związkach macierzy wielościanami i grafami. Zadanie transportowe i przydziału.

7. Równanie dualne programowania liniowego. Totalna dualna całkowitość (TDC) (Edmonds, Giles). Bazy Hilberta. Twierdzenia o układach TDC i wielościanach całkowitych.

8. Wielomianowy algorytm testowania TDC. Grafy doskonałe i układy TDC. Twierdzenie Lovasza (bd).

9. Metoda podziału i ograniczeń Dakina dla PC i programowania zero—jedynkowego, przegląd pośredni, algorytm Balasa.

10. Zadanie plecakowe i załadunku. Problemy pokrycia, rozbicia i upakowania zbiorów.

11. Twierdzenia Gomory’ego—Chvatala o płaszczyznach odcinających, rząd Chvatala. Algorytmy płaszczyzn odcinających.

12. Zastosowania metody płaszczyzn odcinających, problem komiwojażera.

13. Metody geometrii algebraicznej. Pierścień wielomianów. Ideał. Twierdzenie Hilberta o zerach.

14. Bazy Groebnera. Algorytm Buchbergera. Zastosowania i kierunki rozwoju optymalizacji dyskretnej, problemy i nowe możliwości.

Laboratory classes (30h):
Program laboratoriów pokrywa się z programem wykładów

Rozwiązywanie problemów (głównie związanych z zagadnieniami praktycznymi) ilustrujących treści przekazywanych na kolejnych wykładach.

Additional information
Teaching methods and techniques:
  • Lectures: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Laboratory classes: W trakcie zajęć laboratoryjnych studenci samodzielnie rozwiązują zadany problem praktyczny, dobierając odpowiednie narzędzia. Prowadzący stymuluje grupę do refleksji nad problemem, tak by otrzymane wyniki miały wysoką wartość merytoryczną.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
Dwa terminy zaliczeń poprawkowych są skorelowane czasowo z egzaminami poprawkowymi

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: No
    – Participation rules in classes: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Laboratory classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci wykonują ćwiczenia laboratoryjne zgodnie z materiałami udostępnionymi przez prowadzącego. Student jest zobowiązany do przygotowania się w przedmiocie wykonywanego ćwiczenia, co może zostać zweryfikowane kolokwium w formie ustnej lub pisemnej. Zaliczenie zajęć odbywa się na podstawie zaprezentowania rozwiązania postawionego problemu. Zaliczenie modułu jest możliwe po zaliczeniu wszystkich zajęć laboratoryjnych.
Method of calculating the final grade:
  1. Warunkiem koniecznym dopuszczenia do egzaminu jest posiadanie oceny pozytywnej z ćwiczeń.
  2. Ocenę końcową OK wyznacza się na podstawie średniej ważonej SW obliczonej według wzoru
    SW = 1/2 OL + 1/2 OE,
    gdzie OL jest oceną uzyskaną z ćwiczeń laboratoryjnych,
    a OE jest oceną uzyskaną z egzaminu.
    3. Ocena końcowa OK. jest obliczana według algorytmu:
    Jeżeli SW ≥ 4.75, to OK = 5.0 (bdb),
    jeżeli 4.75 > SW ≥ 4.25, to OK = 4.5 (db),
    jeżeli 4.25 > SW ≥ 3.75, to OK = 4.0 (db),
    jeżeli 3.75 > SW ≥ 3.25, to OK = 3.5 (dst),
    jeżeli 3.25 > SW ≥ 3.00, to OK = 3.0 (dst).
Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia sposobu nadrobienia zaległości.

Prerequisites and additional requirements:

Znajomość podstawowych faktów programowania liniowego (algorytm sympleks, dualność)

Recommended literature and teaching resources:
  1. R. S. Garfinkel, G. L. Nemhauser, Programowanie całkowitoliczbowe, PWN Warszawa, 1978.
  2. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1987.
  3. M. M. Sysło, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN Warszawa, 1999.
  4. S. Walukiewicz, Programowanie dyskretne, PWN Warszawa, 1986.
  5. L.A. Wolsey, Integer Programming, Wiley, 1998.
Scientific publications of module course instructors related to the topic of the module:

1. Żak, Andrzej; General lower bound on the size of (H;k)-stable graphs; J. Comb. Optim. 29, No. 2, 367-372 (2015).

2. Żak, Andrzej; On packing two graphs with bounded sum of sizes and maximum degree;
SIAM J. Discrete Math. 28, No. 4, 1686-1698 (2014).

3. Żak, Andrzej; A generalization of an independent set with application to (K q ;k)-stable graphs; Discrete Appl. Math. 162, Part 1, 421-427 (2014).

4. Żak, Andrzej; On embedding graphs with bounded sum of size and maximum degree; Discrete Math. 329, 12-18 (2014).

5. Żak, Andrzej; On (K q ;k)-stable graphs; J. Graph Theory 74, No. 2, 216-221 (2013).

6. Zak, Andrzej; Near packings of graphs; Electron. J. Comb. 20, No. 2, Research Paper P36, 8 p., electronic only (2013).

7. Ruciński, Andrzej; Ẓak, Andrzej; Hamilton saturated hypergraphs of essentially minimum size; Electron. J. Comb. 20, No. 2, Research Paper P25, 16 p., electronic only (2013).

8. Żak, Andrzej; Growth order for the size of smallest Hamiltonian chain saturated uniform hypergraphs;
Eur. J. Comb. 34, No. 4, 724-735 (2013).

9. Zak, Andrzej; Dudek, Aneta; On Hamilton-chain saturated uniform hypergraphs; Discrete Math. Theor. Comput. Sci. 14, No. 1, 21-28, electronic only (2012).

10. Görlich, Agnieszka; Ẓak, Andrzej; Sparse graphs of girth at least five are packable; Discrete Math. 312, No. 24, 3606-3613 (2012).

11. Cichacz, Sylwia; Görlich, Agnieszka; Nikodem, Mateusz; Żak, Andrzej; A lower bound on the size of (H;1)-vertex stable graphs; Discrete Math. 312, No. 20, 3026-3029 (2012).

Additional information:

None