|
|
Předmět X36PAA
ZS 2011/2012 |
|||
Rozvrh
předmětu - přednášky
|
Týden |
Datum |
Přednáška |
|
1. |
21.9. |
Kombinatorické
problémy, přehled úloh a metod řešení. Analýza složitosti algoritmů |
|
2. |
28.9. |
Státní svátek |
|
3. |
5.10. |
Metafora stavového prostoru a metody jeho
prohledávání, dynamické programování a aplikace |
|
4. |
12.10. |
Modely
výpočtu; rozhodovací problémy: třídy problémů
P a NP; optimalizační problémy: třídy PO a
NPO. Za hranice NP |
|
5. |
19.10. |
Karpova
redukce a třída problémů NP-úplný, Turingova
redukce a třída NP-těžký, Struktura NP a
NPO. |
|
6. |
26.10. |
Pseudopolynomiální a
aproximativní algoritmy, třídy APX, PTAS, FPTAS, úplnost |
|
7. |
2.11. |
Randomizované algoritmy,
experimentální vyhodnocení kvality heuristických algoritmů |
|
8. |
9.11. |
Lokální metody, typické
strategie pohybu stavovým prostorem, konstruktivní a iterativní metody.
Tabu prohledávání |
|
9. |
16.11. |
Simulované ochlazování |
|
10. |
23.11. |
Simulovaná evoluce I |
|
11. |
30.11. |
Simulovaná evoluce II |
|
12. |
7.12. |
|
|
13. |
14.12. |
Lineární
programování |
|
14. |
21.12. |
Rezerva |
Rozvrh cvičení
(pondělí)
|
Týden |
Datum |
Cvičení |
Domácí práce |
|
1. |
20.9. |
|
Úloha 1 |
|
2. |
27.9. |
Příklady problémů
|
|
|
3. |
4.10. |
Stavový prostor |
|
|
4. |
11.10. |
Konzultace domácí práce 2 |
Úloha 2 |
|
5. |
18.10. |
||
|
6. |
25.10. |
Konzultace domácí práce 3 |
Úloha 3 |
|
7. |
1.11. |
||
|
8. |
8.11. |
Třídy problémů NPC, NPH, redukce |
Úloha 4 |
|
9. |
15.11. |
||
|
10. |
22.11. |
Konzultace domácí
práce 5 |
Úloha 5 |
|
11. |
29.11. |
Aproximativní algoritmy |
|
|
12. |
6.12. |
Konzultace domácí práce 6 |
Úloha 6 Řešení problému vážené splnitelnosti
booleovské formule některou z následujících metod: · simulované ochlazování |
|
13. |
13.12. |
Opravný
TEST |
|
|
14. |
20.12. |
Čtvrtek |
Rozvrh cvičení
(čtvrtek)
|
Týden |
Datum |
Cvičení |
Domácí práce |
|
1. |
23.9. |
Příklady
problémů |
Úloha 1 |
|
2. |
30.10. |
Stavový prostor |
|
|
3. |
7.10. |
Konzultace domácí práce 1 |
|
|
4. |
14.10. |
Konzultace domácí práce 2 |
Úloha 2 |
|
5. |
21.10. |
||
|
6. |
28.10. |
Státní svátek |
Úloha 3 |
|
7. |
4.11. |
||
|
8. |
11.11. |
Třídy
problémů NPC, NPH,
redukce |
Úloha 4 |
|
9. |
18.11. |
||
|
10. |
25.11. |
Konzultace domácí práce 5 |
Úloha 5 |
|
11. |
2.12. |
|
|
|
12. |
9.12. |
Aproximativní algoritmy |
Úloha 6 Řešení problému vážené splnitelnosti
booleovské formule některou z následujících metod: · simulované ochlazování |
|
13. |
16. 12. |
Opravný
TEST |
|
|
14. |
20.12. |
Rezerva, zápočet |
Cvičení
Relevantní přednášky
předcházejí cvičením (včetně 2. týdne), znalost přednášené látky je
nutná pro práci na cvičeních.
Nerozumíte-li něčemu, ptejte se ihned. Vyžaduje se samostatná práce a
detailní
porozumění kódu domácích úloh.
Zelená políčka (s výjimkou svátků a ostatních volných dnů) označují prostor pro konzultaci domácích prací. Cvičení se nekoná v rozvrhované místnosti, není povinné, ovšem po dohodě se cvičícím můžete konzultovat Vaše problémy s úlohami. Obecně je tento prostor věnován práci na domácích úlohách.
Materiály
-
Ukázkové aplety použití pokročilých iterativních metod
Literatura
Klasika:
KUČERA, L.: Kombinatorické algoritmy. Praha, SNTL, 1983.
GAREY, M. R., JOHNSON, D. S.: Computers and Intractability. San
Francisco, W.
H. Freeman, 1979.
AUSIELO, G., et al: Complexity and Approximation. Berlin, Springer
1999.
Běžně dostupné knihy:
MAŘÍK, V., ŠTĚPÁNKOVÁ, O., LAŽANSKÝ, J. a kol.: Umělá inteligence 3.
Praha,
Academia, 2001.
DEMEL, J.: Grafy a jejich aplikace. Praha, Academia, 2002.
MATOUŠEK, J., NEŠETŘIL, J.: Kapitoly z diskrétní matematiky. Praha,
Nakladatelství Karolinum, 2002.
Podrobnější
seznam
Informace
na Webu
Uvedené
odkazy nejsou vyčerpávající. Budete-li chtít nějakou specifičtější
informaci,
použijte internetový vyhledávač (např. google).
Obecné
Handbook
of
Algorithms and Data Structures - přístupné jen vybrané partie
NETLIB - matematické rutiny
The
collection of
computer science bibliographies - databáze článků
ResearchIndex - databáze
článků
Dynamické
programování
Dynamic programming: an
introduction
Dynamic programming -
aplikované na vyhledávání řetězců
Dynamic
programming tutorial - další vyhledávání řetězců, rozkreslené
matice
Simulované
ochlazování
Simulated annealing
-
intro + odkazy
Adaptive simulated annealing -
popis,
zdrojáky
Tabu search
Tabu search -
intro +
odkazy
Evoluční algoritmy
Evolutionary
algorithms
- intro + odkazy
Illinois genetic
algorithms
laboratory - mj.
zdrojáky genetických algoritmů
Nové: Přednáška o evolučních algoritmech z CERN, část 1 a část 2
Domácí
úlohy
Písemná
zpráva ve formátu HTML se odevzdává do přiděleného adresáře spolu se
zdrojovými
soubory programu. Zpráva obsahuje:
- specifikaci úlohy
- rozbor možných variant
řešení
- rámcový popis postupu
řešení
- popis kostry algoritmu
- naměřené výsledky,
jsou-li žádány, v přehledné formě
- závěr: interpretace výsledků a zdůvodnění jejich kvality
Použité
programy jsou prostředkem, nikoliv cílem. Proto zprávu nelze
zredukovat
na jejich zdrojové programy.
Termíny odevzdání
domácích úloh
Normální
termín odevzdání je den prvního cvičení příslušného následujícímu
domácímu
úkolu (celý, až do 24:00) . Pozdní
odevzdávání
domácích úloh může být penalizováno! Odevzdávejte proto úlohy včas.
Ušetříte
tím práci i nervy nám i sobě. Naopak, včasné odevzdání úlohy bude odměněno plusem u
zkoušky.
K čemu jsou
dobré domácí úkoly
Jak s nimi
netrávit příliš mnoho času
Hodnocení
domácích úloh
Paralelka
Hodnocení
102
Zápočet
Podmínky
zápočtu:
- účast na cvičeních,
potřebná úroveň znalostí
- samostatné a správné
vypracování všech domácích úloh (1-5)
- absolvování testu (25 a
více bodů)
Zkouška
Zkouška
má písemnou a ústní část. Do hodnocení zkoušky se započítávají
- Body z testu (9. cvičení) -
0-40 bodů.
- Body z písemné části
zkoušky - 0-30 bodů.
- Hodnocení 6. úlohy -
0-30 bodů (detaily). 6. úlohu je nutné
odevzdat minimálně týden před zkouškou, poněvadž hodnocení nelze
stihnout na zkoušce, kromě výjimečných případů.
- Ostatní domácí úlohy a
práce na cvičeních, posoudí zkoušející podle hodnocení cvičících, 0-5
bodů, mají pomocný význam, nezapočítávají se přímo.
- Případná ústní
část, ponejvíce ve sporných a hraničních případech.
Body
se převádějí na známku podle závazné stupnice ECTS. Stupně A a B jsou
považovány za vynikající výsledek.
- 50 bodů a více, E (dostatečně)
- 60 bodů a více, D (uspokojivě)
- 70 bodů a více, C (dobře)
- 80 bodů a více, B (velmi dobře)
- 90 bodů a více, A (výborně)
Vyžadovanou
látku lze shrnout do následujících okruhů:
Základní pojmy
Problém,
kombinatorický problém, instance, konfigurace, řešení, optimální a
suboptimální
řešení. Rozhodovací, konstruktivní, enumerační, optimalizační problém.
Stavový
prostor, jeho vyjádření grafem, význam uzlů a hran tohoto grafu.
Složitost
Motivace
hodnocení složitosti algoritmů, nejhorší a průměrný případ, měření
velikosti
instance, praktický význam. Horní asymptotický odhad, vlastnosti.
Třídy P a NP
Modely
výpočtu, Turingův stroj, nedeterministický Turingův stroj. Třídy
problémů P a
NP, definice, souvislost se stavovým prostorem. Karpova redukce, třída
NP-úplných (NPC) úloh. Cookův teorém, princip důkazu příslušnosti
daného
problému do NPC. Turingova redukce, NP-těžké úlohy. NPI úlohy. Třída
co-NP,
polynomiální hierarchie (princip). Třídy PO a NPO.
Exaktní algoritmy
Úplné
a systematické metody. Metody průchodu stavovým prostorem do hloubky,
do šířky.
Dynamické programování, metoda větví a hranic.
Přibližné algoritmy
Aproximativní
a heuristické algoritmy, definice chyby. Polynomiální aproximační
schéma, plně
polynomiální aproximační schéma. Třídy APX, PTAS, FPTAS. Pojem úplnosti
v
těchto třídách. Randomizované algoritmy. Experimentální hodnocení
kvality
algoritmů.
Lokální metody
Okolí
bodu stavového prostoru, metody prohledávání okolí, závislost
složitosti a
kvality algoritmu na definici okolí. Lokální konstruktivní a iterativní
metody.
Problém výchozího stavu iterativních metod. Problém konvergence a
diversifikace
lokálních metod. Simulované ochlazování, teoretické vlastnosti, volba
rozvrhu
ochlazování. Evoluční algoritmy, přehled. Genetické algoritmy,
kódování,
základní operace, reprodukční plán, selekční tlak, metody jeho řízení
při
různých metodách výběru rodičů, varianty, schemata. Tabu prohledávání,
princip,
pojmy, varianty tvorby a užití historie, aspirační kriteria. Způsoby
práce s
omezujícími podmínkami v lokálních metodách.
Globální metody
Dekompozice,
redukce, rekompozice, charakter pro různé úlohy. Souvislost s
dynamickým
programováním.
Lineární programování
Definice, varianty LP. Simplexová metoda, vlastnosti. Relaxace.
Test
Na 9. cvičení se píše test. Tento test je nedílnou součástí hodnocení zkoušky, účast na tomto cvičení je povinná.
Otázky budou z látky přednášené do 8.
přednášky včetně, bez Tabu prohledávání.
Neúspěch v tomto testu (tj. méně než 25 bodů
z 40) znamená nemožnost absolvování zkoušky.
Je povolen jeden náhradní/opravný termín, konající se na 13.
cvičení.
Opravný / Náhradní
test
Opravný / náhradní test se bude psát na 13. cvičení.
Na tento test mají nárok:
- Ti, kdo ze závažných
důvodů první test nepsali
- Ti, kdo neuspěli v
prvním testu, tj. mají méně než 25 bodů
Látka i náročnost bude stejná, jako v předchozím testu. Tj. do 8. přednášky včetně.