ARCHIV 09/10 zimni semestr
[Zpet]
LINEARNI ALGEBRA A GEOMETRIE I (NALG001) - CVICENI
Streda 11:30 M2, Streda 14:00 K9
ZAPOCET
Na kazde hodine piseme kratky test, za ktery lze ziskat 4 body. V pripade, ze dostanete mene bodu, vam zadam priklad(y) za domaci ukol,
typove podobne, ale casove narocnejsi. Ty lze odevzdat pred dalsi hodinou (ne pozdeji) a lze za ne ziskat 4 body. Pocita se lepsi z vysledku.
K ziskani zapoctu je treba mit aspon 70% bodu. V pripade, ze potrebny pocet bodu mit nebudete, bude mozne nekolik chybejicich bodu
doplnit spocitanim MNOHA (!!!) prikladu (durazne nedoporucuji).
Studenti kombinovaneho studia mohou ziskat zapocet vyresenim domacich ukolu (u kazdeho ukolu staci resit mene pracnou variantu).
Ukoly mi muzete odevzdavat kdykoliv behem semestru.
ODKAZY
KAFKA (ALG080)
Streda 15:40 seminarni mistnost KA
UVOD DO SLOZITOSTI CSP (NALG117)
Pondeli 10:40 seminarni mistnost KA
- Priklady CSP, strucny uvod do slozitosti - polynomialni prevoditelnost a ekvivalence, P, NP, NP-c, strucne zminena logspace-prevoditelnost, L, NL. SAT je NP-c (Cook, Levin). Cviceni: 3-SAT, 3-COL, NOT-ALL-EQUAL-SAT jsou NP-c.
Pokud P \neq NP, pak NP modulo polynomialni ekvivalence je nekonecny poset (Ladner).
- Ruzne formulace CSP, priklady. Relacni struktury (indexovane a neindexonavane), CSP s pevnou sablonou, dichotomicka hypoteza (Feder, Vardi). Zmineny nektere castecne vysledky.
- Pp-definovatelnost, relacni klony, cviceni. Redukce na relacni klony (Jeavons).
- Algebry (indexovane a neindexovane), algebraicke klony. Operatory Pol a Inv - Galoisova korespondence mezi relacnimi a algebraickymi klony. Uzavrene prvky na relacni (resp. algebraicke) strane jsou relacni (resp. algebraicke) klony (Geiger; Bodnarchuk, Kaluznin, Kotov, Romov).
Dusledky pro CSP.
- Redukce na obraz unarniho polymorfismu (Jeavons). Core struktury, veta o pridani konstant (Bulatov, Jeavons, Krokhin). Dusledky (zejmena to, ze mame-li rozhodovaci problem v P, pak existuje polynomialni algoritmus na hledani reseni).
- CSP na dvojprvkove mnozine - prehled. Netrivialni idempotentni klony na dvojprvkove mnozine obsahuji polosvazovou operaci nebo majoritni operaci nebo operaci x+y+z (mod 2).
Polynomialni algoritmus v pripade x+y+z (mod 2).
- Relacni sirka - motivace, obrazek instance. (k,l)-minimalni instance, priklady. Prevod instance na ekvivalentni (k,l)-minimalni.
Konecna relacni sirka.
- Struktury s polosvazovym polymorfismem maji konecnou sirku (FV), relace kompatibilni s NU jsou urceny malymi projekcemi (Baker, Pixley), struktury s NU polymorfismem maji konecnou sirku.
- Priklady na (ne)konecnou sirku. Definice interpretace mezi (algebraickymi) klony. Zneni interpretacni vety (Bulatov, Jeavons, Krokhin).
- H,S,P a I-interpretace. Birkhoffova HSP-veta (naznak dukazu). Dukaz interpretacni vety.
- Algebraicka dichotomicka hypoteza, ekvivalentni formulace. Charakterizace problemu konecne sirky.
ODKAZY
- Prezentace A. Krokhina z SSAOS'08
[1. dil],
[2. dil],
[3. dil].
- Zapisky A. Kazdy z prednasky M. Marotiho o CSP jsou
[Zde].
- Prezentace B. Larose z SSAOS'09
[1. dil],
[2. dil],
[3. dil].
- Uvod do slozitosti - prezentace R. Willarda z SSAOS'08
[1. dil],
[2. dil],
[3. dil].
- A. Bulatov, M. Valeriote, Results on the algebraic approach to the CSP
[PDF]
SEMINAR Z TEORIE KROTKYCH KONGRUENCI (NALG123)
Utery 14:30 laborator KA
ODKAZY
- D. Hobby, R. McKenzie, The Structure of Finite Algebras [download]
- M. Clasen, M. Valeriote, Tame Congruence Theory [PS]
- A course in TCT
RUZNE
Text Petara Markovice z prednasky o konecne bazovanosti rovnicovych teorii jsou
[Zde] (verze z 28.4.2008).
ARCHIV
[Archiv 2008/09 letni semestr]
[Archiv 2008/09 zimni semestr]
[Archiv 2007/08 letni semestr]
[Archiv 2007/08 zimni semestr]
[Archiv 2006/07 letni semestr]
[Archiv 2006/07 zimni semestr]
[Archiv 2005/06 letni semestr]
|