Libor Barto

DOMU VYZKUM PRO STUDENTY

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

  1. 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).
  2. Ruzne formulace CSP, priklady. Relacni struktury (indexovane a neindexonavane), CSP s pevnou sablonou, dichotomicka hypoteza (Feder, Vardi). Zmineny nektere castecne vysledky.
  3. Pp-definovatelnost, relacni klony, cviceni. Redukce na relacni klony (Jeavons).
  4. 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.
  5. 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).
  6. 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).
  7. Relacni sirka - motivace, obrazek instance. (k,l)-minimalni instance, priklady. Prevod instance na ekvivalentni (k,l)-minimalni. Konecna relacni sirka.
  8. 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.
  9. Priklady na (ne)konecnou sirku. Definice interpretace mezi (algebraickymi) klony. Zneni interpretacni vety (Bulatov, Jeavons, Krokhin).
  10. H,S,P a I-interpretace. Birkhoffova HSP-veta (naznak dukazu). Dukaz interpretacni vety.
  11. 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]