PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Celočíselné programování - NOPT016
Anglický název: Integer Programming
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019 do 2019
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Milan Hladík, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Optimalizace
Anotace -
Poslední úprava: T_KAM (26.04.2017)
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.
Cíl předmětu -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)

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.

Podmínky zakončení předmětu -
Poslední úprava: Mgr. Elif Garajová (13.02.2019)

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.

Literatura -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)

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

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

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

Sylabus -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)
  • 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

 
Univerzita Karlova | Informační systém UK