Problémy a algoritmy

Předmět je náhradou za:

Problémy a algoritmy (X36PAA)

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

Mnohé na první pohled jednoduché úlohy nelze na počítači prakticky řešit, protože by výpočet trval déle než je jeho životnost. Jak lze rozpoznat takové úlohy a jak lze navrhnout v praxi použitelné algoritmy - o tom je tento kurz. Použitý matematický aparát je minimalizován. Důraz je kladen na poznatky použitelné v inženýrské praxi a na souvislosti mezi jednotlivými metodami.

Požadavky:

Osnova přednášek:

1. Kombinatorické problémy: přehled úloh a metod řešení

2. Analýza složitosti algoritmů

3. Metafora stavového prostoru, úplné prohledávání

4. Systematické metody prohledávání

5. Modely výpočtu: třídy problémů P a NP

6. Třídy problémů NP-úplný a NP-těžký, polynomiální redukce

7. Měření kvality aproximativních metod

8. Lokální konstruktivní metody

9. Princip lokálních iterativních metod

10. Simulované ochlazování

11. Simulovaná evoluce

12. Tabu prohledávání

13. Globální metody: princip a typické strategie

14. Lineární programování: celočíselné a 0-1 programování, relaxace

Osnova cvičení:

1. Ukázky problémů, úvod do algoritmů

2. Složitost

3. Stavový prostor

4. Domácí práce 2.

5. Třídy problémů P a NP, transformace, důkazy

6. Domácí práce 3.

7. Lokální konstruktivní metody

8. Pondělí velikonoční

9. Jednoduché iterativní metody

10. Pokročilé iterativní metody

11. Domácí práce 4.

12. Domácí práce 4.

13. Prezentace řešení problému obchodního cestujícího

14. Prezentace řešení problému obchodního cestujícího, zápočet

Cíle studia:

Studijní materiály:

[1] Kučera, L.: Kombinatorické algoritmy. SNTL, Praha 1983

[2] Plesnik, J.: Grafové algoritmy. Veda, Bratislava 1983

[3] Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.Freeman, San Francisco 1979

Poznámka:

Rozsah výuky v kombinované formě studia: 19+4

Typ cvičení: s, p

Tento předmět je nabízen také v anglické verzi

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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