Libor Barto

DOMU VYZKUM PRO STUDENTY

ARCHIV 14/15 letni semestr

[Zpet]

KAFKA (NMMB551)

streda 15:40 seminarni mistnost KA

POCITACOVA ALGEBRA (NMMB204)

Prednaska: streda 9:00 - 10:40 K11 lichy tyden semestru, ctvrtek 14:00-15:30 L12
Cviceni: streda 9:00 - 10:40 K11 sudy tyden semetru (vede Marcel Sebek).

Informace ke cviceni a rada odkazu je na strankach Marcela Sebka.
Informace k prednasce jsou na strankach Davida Stanovskeho.

  • 19.2. Asymptoticka casova slozitost, "Big-O" notace. Reprezentace celych cisel, racionalnich cisel, polynomu (husta/ridka, distributivni/rekurzivni), prvku konecnych teles a algebraickych rozsireni Q.
  • 25.2. Skolske algoritmy pro operace s celymi cisly (+, -, x, div, mod, prevod mezi bazemi). Metoda rozdel a panuj, Karacubuv algoritmus.
  • 26.3. Algoritmus Toom-k (pro nasobeni). Mocneni - naivni algoritmus, binarni mocneni, vypocet a^b mod m.
  • 4.3. Eukleiduv algoritmus (na hledani NSD a Bezoutovych koeficentu v N), odhad poctu kroku, velikosti Bezoutovych koeficientu a slozitosti.
  • 5.3. Binarni NSD algoritmus. Operace v Q, Z_p. Operace s polynomy (+, x, pseudodeleni). Operace v Z_q.
  • 12.3. Modularni reprezentace - celych cisel, polynomu nad T, obecne. Zobecnena cinska veta o zbytcich, dukaz pro OIHI.
  • 18.3. Langraneuv a Garneruv algoritmus na prevod z modularni reprezentace (zejmena okruhu Z, T[x]).
  • 19.3. Shamirovo (k,n)-schema na sdileni tajemstvi. Primitivni n-ta odmocnina z 1, diskretni Fourierova transformace (DFT), inverzni DFT pomoci DFT, rychla Fourierova transformace (FFT).
  • 26.3. Slozitost FFT. Primitivni odmocniny v Z_p. Strategie nad Z_p, Q, pokud primitivni odmocnina neni. Rychle nasobeni polynomu. Rychle nasobeni celociselnych polynomu uzitim modularni metody na koeficienty + FFT.
  • 1.4. Vylepseni algoritmu na nasobeni v Z[x] - CVZ na koeficienty, Schonhage-Strassenuv trik. FFT bez rekurze.
  • 2.4. Formalni mocnine rady, existence inverzni mocnine rady (<=> nenulovy konstantni koeficient). “Otoceni polynomu”, rychle deleni polynomu. Rychle invertovani polynomu.
  • 9.4. Invertovani celych cisel. Iteracni metody na hledani korene, rad konvergence. Metody zuzovani intervalu - puleni, regula falsi. Metoda tecen.
  • 15.4. NSD polynomu. Gaussova veta. NSD = NSD obsahu x NSD primitivnich casti.
  • 16.4. Posloupnost polynomialnich zbytku (PRS) - eukleidovska, primitivni, redukovana a subrezultantova. Heuristicke odhady rustu koeficientu pro eukleidovskou a redukovanou PRS (+reseni linearnich rekurentnich rovnic).
  • 23.4. Eukleiduv algoritmus pomoci radkovych uprav. Sylvesterova matice, rezultant. Kritera na soudelnost (nad podilovym telesem). Veta: res(f,g)=uf+vg pro nejake u,v, deg(u) < deg(g), deg(v) < deg(f).
  • 29.4. Modularni algoritmus pro NSD v Z[x]. Pouzitelna, stastna s smolna prvocisla (je jich jen konecne). Landau-Mignottova mez. Reseni problemu vedouciho koeficientu.
  • 30.4. Modularni algoritmus pro polynomy vice promennych, pouzitelne, stastne a smolne hodnoty (opet jich je jen konecne).
  • 7.5. (neni pozadovano ke zkousce) Dukaz Landu-Mignottovy meze. Vypocet determinantu celociselne matice.
  • 14.5. Opakovani
  • 21.5. ---

UNIVERSAL ALGEBRA 2 (NMAG450)

Lecture: Wed 14:00 - 15:30 seminar room of KA
Tutorial: Wed 13:10 - 13:55 laboratory of KA

LECTURES

  • 25.2. Congruence permutability (CP). Characterization of CP using Maltsev term. Congruence distributivity (CD), charakterization using Jonsson terms (without a proof).
  • 4.3. Proof of CD <=> Jonsson terms. Interpretation - two definitions. The lattice of interpretability.
  • 11.3. Thm: Idempotent V is not the least element of the interpretability lattice <=> V has a Taylor term.
  • 18.3. Thm: Set of identities closed under semantic consequence = equational theory (fully invariant congruence of the absolutely free algebra on countable generator set). Immediate consequence of an identity, syntactic consequence. Thm: semantic consequence = syntactic consequence.
  • 25.3. Rewriting systems, digraph terminology (finitely terminating/ normal/ convergent digraph, terminal vertex). Reduction order, compatibility with reduction order. Thm: E is compatible with a reduction order => D(E) is finitely terminating.
  • 1.4. Confluent, locally confluent digraph. Thm: confluent => normal. Thm: locally confluent + finitely terminating => convergent. Unifier, the most general unifier. Critical pair. Thm: D(E) finitely terminating + has confluent critical pairs => convergent. The Knuth-Bendix algorithm.
  • 8.4. The Knuth-Bendix order.
  • 15.4. Finitely based varieties and algebras. Thm: finitely based variety = finitely axiomatizable variety. Thm: finite A is finitely based <=> there is n such that A has a base consisting of identities over n variables. Park's 4-element example of a non-finitely based algebra.
  • 22.4. Thm: If V has definable principal congruences and SI(V) is a finite set of finite algebras (up to iso), then V is finitely based.
  • 29.4. Affine algebra, central Maltsev polynomial, Abelian algebra. Thm: Affine <=> Maltsev + Abelian (in fact Maltsev => (central Maltsev <=> Abelian <=> affine).
  • 6.5. ---
  • 20.5. Classification of minimal algebras. Restricting algebra to a set, minimal set, neighborhood. Thm: A simple => (1) minimal set => neighborhood (2) Restrictions to minimal sets are isomorphic (3) minimal sets are dense (proof of (1)).

TUTORIALS

Homework (for credits) is here

  • 4.3. few subpowers <=> small generating sets (few subpowers means that log(#poduniverz A^n) is less than a polynomial in n; small generating sets means that each subuniverse of A^n has a generating set of size at most g(n), where g(n) is a polynomial in n)
  • 11.3. Maltsev => small generating sets (as a generating set one can take witnesses of forks)
  • 18.3. NU(n) => relations are determined by (n-1)-ary projections => few subpowers
  • 25.3. CD (and thus CM) does not imply few subpowers
  • 1.4. ditto
  • 9.4.
  • 15.4. Knuth-Bendix algorithm applied to E = {(xy)(yz)=y}
  • 22.4. Knuth-Bendix algorithm applied to group axioms
  • 29.4.
  • 6.5.
  • 20.5. Abelian semilattices (trivial), groups (commutative) and rings (zero multiplication).

SEMINAR K PROBLEMU CSP (NMAG573)

pondeli 14:50 - 16:20 laborator KA

Zadani problemu: sada 1 sada 2 sada 3 sada 4

ARCHIV

[Archiv 2014/15 zimni semestr]
[Archiv 2013/14 letni semestr]
[Archiv 2013/14 zimni semestr]
[Archiv 2012/13 letni semestr]
[Archiv 2012/13 zimni semestr]
[Archiv McMaster (anglicky)]
[Archiv 2009/10 letni semestr]
[Archiv 2009/10 zimni semestr]
[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]