Revision 26 as of 2016-04-01 12:52:39
You are not allowed to revert this page!

Clear message

Rýchle algoritmy

2015/16 -- letný semester, rozsah 2-2

Vyučujúci

Písomka v pondelok 4.apríla 2016 od 9oo do 11oo. Rozdelenie do miestností:
  • DE 300 - poslucháči s priezviskom A - POD

  • B 704 - poslucháči s priezviskom PRI - Ž

Písomka trvá 120 minút.

Približné zloženie písomkových úloh:

  1. rozklad x^n-1 nad F_q
  2. Čínska zvyšková veta (pre polynómy)
  3. riešenie homogénnych lineárnych rekurentných rovníc + minimálne polynómy postupností
  4. pre daný charakteristický polynóm - stanovenie počtu postupností, ktoré majú rovnaký minimálny polynóm
  5. diskrétna Fourierova transformácia nad F_q

Počas písomky je možné používať k nahliadnutiu vlastnoručne písané poznámky z prednášok/cvičení.

Konzultácie v piatok 1.apríla ;) 2016 cca o 13:15 v AB 150. Majte pripravené konkrétne otázky. Môžem sa vám venovať cca 1 hodinu. Ak budem meškať, počkajte.

Rozvrh

Deň

Miestnosť

Krúžok

Od

Do

Prednáška

pondelok

b704

všetky

9:00

11:00

Nemoga

Cvičenie

pondelok

b701

1.

11:00

13:00

piatok

c802

2.

9:00

11:00

Čipková

piatok

c802

3.

11:00

13:00

Čipková

streda

c517

4.

9:00

11:00

Čipková

piatok

c802

5.

11:00

13:00

Čipková

Konzultácie

podľa dohody

Stručná osnova predmetu

1. Úvodné pojmy. Euklidov algoritmus. Overovanie prvočíselnosti. Konštrukcia prvočísel.

2. Základy algebry, grupy, okruhy, polia, polynómy, rozšírenia, cyklotomické polynómy.

3. Konečné polia, štruktúra a reprezentácia, norma, stopa.

4. Konštrukcia ireducibilných a primitívnych polynómov, faktorizácia, Berlekampov algoritmus.

5. Lineárne rekurentné rovnice, reprezentácia riešení, LFSR, Berlekampov Masseyov algoritmus.

6. Riešenie rovníc nad konečnými poľami, efektívne výpočty, CRT.

7. Efektívne metódy aritmetiky, (Montgomery, Karacuba, Cook, ...).

8. Diskrétna Fourierova transformácia a jej aplikácie, konvolúcie, Winogradov algoritmus.

9. Eliptické krivky, výpočty.

10. NTL, softvérové balíky pre výpočty.

11. Mrežové body, LLL algoritmus, aplikácie v kryptológii.

12. Riešenie veľkých sústav rovníc, Laczosova a Wiedemanova metóda.

Literatúra

  1. LIDL, R. -- NIEDERREITER, H.: Finite Fields. Cambridge: Cambridge University Press, 2nd Ed., 1997. 768 s. ISBN 0-521-39231-4.
  2. POMERANCE, C. -- CRANDALL, R." Prime Numbers. New York: Springer, 2001. 546 s. ISBN 0-387-94777-9.
  3. WILF, H.S.: Algorithms and Complexity.

Podmienky na absolvovanie predmetu

Z celkového počtu 100 bodov môže študent získať

Pre udelenie zápočtu je potrebné získať z písomky a zadania aspoň 30 bodov. Účasť na prednáškach a cvičeniach je nutná.

Prílohy, linky

Tabuľka hodnôt Eulerovej funkcie (pre n<100)

Interaktívny graf hodnôt Eulerovej funkcie (pre n<53)

Möbiova funkcia

Knižnica NTL (Number Theoretic Library)