PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Celočíselné programování - NOPT016
Anglický název: Integer Programming
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: https://kam.mff.cuni.cz/~hladik/CP
Garant: prof. Mgr. Milan Hladík, Ph.D.
Vyučující: Mgr. Elif Garajová, Ph.D.
prof. Mgr. Milan Hladík, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Optimalizace
Je neslučitelnost pro: NOPX016
Je prerekvizitou pro: NOPT020
Je záměnnost pro: NOPX016
Anotace -
Přednáška se zabývá optimalizačními problémy, kde některé proměnné mohou nabývat jen celočíselných hodnot. Úlohy celočíselného programování se často vyskytují v praktických problémech a mají silnou formulační schopnost. Díky vysoké výpočetní složitosti zároveň představují aktuální a důležitý směr výskumu. Poznámka: Předmět se obvykle koná jednou za dva roky.
Poslední úprava: T_KAM (26.04.2017)
Cíl předmětu -

Seznámení studentů s celočíselným programováním, a to nejen s klasickými výsledky, ale i s novými trendy. Absolventi by měli být schopni aplikovat metodologii v praxi stejně dobře jako navázat na aktuální výzkum v oboru.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)
Podmínky zakončení předmětu -

K získání zápočtu je potřeba alespoň 50% bodový zisk z každé série domácích úkolů zadaných v průběhu semestru.

Poslední úprava: Garajová Elif, Mgr., Ph.D. (13.02.2019)
Literatura -

Doprovodný text:

https://kam.mff.cuni.cz/~hladik/CP/text_cp.pdf

Další literatura:

[1] G.L. Nemhauser, L.A. Wolsey. Integer and combinatorial optimization. Wiley, New York, 1999.

[2] A. Schrijver. Theory of linear and integer programming. Repr. Wiley, Chichester, 1998.

[3] L.A. Wolsey. Integer programming. Wiley, Chichester, 1998.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (30.09.2021)
Požadavky ke zkoušce -

Zkouška je ústní a požadavky odpovídají sylabu předmětu v rozsahu, který byl presentován na přednášce.

Zkouška může mít kontaktní nebo distanční formu.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (24.09.2020)
Sylabus -
  • Formulace celočíselných úloh
  • Celočíselný polyedr, unimodulární matice, NP-úplnost
  • Metody sečných nadrovin a branch & bound
  • První a druhý Gomoryho algoritmus
  • Preprocessing. Heuristiky
  • Problém batohu
  • Set covering
  • Problém obchodního cestujícího

Předpokládají se základní znalosti lineárního programování.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (14.02.2023)
 
Univerzita Karlova | Informační systém UK