Optimalizace datových toků

Přednášející:

Marcel Jiřina (gar.)

Cvičící:

Marcel Jiřina (gar.), Petr Hošek

Předmět zajišťuje:

katedra biomedicínské informatiky

Anotace:

Úvod do problematiky datových toků a jejich definice. Sítě a grafy. Optimalizace, optimální a pseudoptimální řešení, heuristiky. Hledání nejkratší cesty v časově proměnných sítích - formulace problému, NP-úplnost, otázka času potřebného k nalezení řešení. Minimální časově proměnné stromové grafy - paralelní sítě, pseudopolynomiální algoritmus. Problém hledání maximálního toku v časově proměnné síti - max-flow min-cut algoritmus. Optimalizace toku cen v sítích - (k,c)-flow problém. Hledání cesty v síti, která má maximální kapacitu. Hledání cesty v síti, která je nejrychlejší. Hledání nejlepší cesty v síti pokud je stanoveno více kritérií - MinSum-MinSum a MinSum-MinMax problém. Dynamické programování.

Požadavky:

Studenti by měli mít základní znalosti z oblasti vysokoškolské matematiky, zejména pak znalosti práce s maticemi a základy diferenciálního a integrálního počtu.

Osnova přednášek:

1. Úvod do problematiky datových toků a jejich definice. Sítě a grafy.

2. Optimalizace, optimální a pseudoptimální řešení, heuristiky.

3. Hledání nejkratší cesty v časově proměnných sítích - formulace problému, NP-úplnost, otázka času potřebného k nalezení řešení.

4. Minimální časově proměnné stromové grafy - paralelní sítě, pseudopolynomiální algoritmus.

5. Problém hledání maximálního toku v časově proměnné síti - max-flow min-cut algoritmus.

6. Optimalizace toku cen v sítích - (k,c)-flow problém.

7. Hledání cesty v síti, která má maximální kapacitu.

8. Hledání cesty v síti, která je nejrychlejší

9. Hledání nejlepší cesty v síti pokud je stanoveno více kritérií - MinSum-MinSum a MinSum-MinMax problém.

10. Dynamické programování.

Osnova cvičení:

1. Úvod do Matlabu. Reprezentace grafu v počítači. Základní úlohy z teorie grafů.

2. Optimalizace, optimální a pseudoptimální řešení, heuristiky.

3. Hledání nejkratší cesty v časově proměnných sítích - formulace problému, NP-úplnost, otázka času potřebného k nalezení řešení.

4. Minimální časově proměnné stromové grafy - paralelní sítě, pseudopolynomiální algoritmus.

5. Problém hledání maximálního toku v časově proměnné síti - max-flow min-cut algoritmus.

6. Optimalizace toku cen v sítích - (k,c)-flow problém.

7. Hledání cesty v síti, která má maximální kapacitu.

8. Hledání cesty v síti, která je nejrychlejší

9. Hledání nejlepší cesty v síti pokud je stanoveno více kritérií - MinSum-MinSum a MinSum-MinMax problém.

10. Dynamické programování.

Cíle studia:

Cílem studia je seznámit studenty se základními pojmy a zejména pak s algoritmy z oblasti teorie grafů. Studenti by měli získat znalosti ohledně hledání nejkratších (nejlevnějších, nejrychlejších) cest v síti (grafu) a umět implementovat příslušné algoritmy.

Studijní materiály:

[1] Žambochová M.: Teorie grafů v příkladech, FSE, UJEP, Ústí nad Labem, 2007, ISBN: 978-80-7044-962-2

[2] Šeda M.: Teorie grafů, UAI, FSV, VUT, Brno, 2003

[3] Hliněný P.: Základy teorie grafů pro (nejen) informatiky, FI, Masarykova Univerzita, 2010

[4] Demel J.: Grafy a jejich aplikace, 1. vyd., Praha, Academia, 2002

[5] Daněk J.: Logistické systémy, Vysoká škola báňská - Technická univerzita, 2006, ISBN: 80-248-1017-4

[6] Stehlík, Kapoun: Logistika pro manažery

[7] Bagley B. a kol.: Physician Quality Reporting Guide: Essentials of Data Collection, Work Flow Optimization and Physician Engagement for Practices, Healthcare Intelligence Network, 2008, ISBN: 1934647225

[8] Pardo R.: Design, Testing, and Optimization of Trading Systems, 1992, ISBN: 0471554464

[9] Manacapilli T.: Air Education and Training Command Cost and Capacity System: Implications for Organizational and Data Flow Changes, RAND Corporation, 2004, ISBN: 0833035037

Poznámka:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Bakalářský studijní obor Plánování a řízení krizových situací - prezenční (povinně volitelný předmět)
• Bakalářský stud. obor Plánování a řízení krizových situací,zaměření Bezp. a krizový management (povinně volitelný předmět)