16. 10. 2019  21:39 Vladimíra
Akademický informační systém

Sylabus předmětu B-RAL - Rýchle algoritmy (FEI - LS 2018/2019)


     Informačný list          ECTS          Sylabus          


     Slovenština          Angličtina          


Vysoká škola: Slovenská technická univerzita v Bratislave
Fakulta: Fakulta elektrotechniky a informatiky
Kód predmetu: B-RAL
Názov predmetu: Rýchle algoritmy
Druh, rozsah a metóda vzdelávacích činností:
prednáška2 hod. týždenne (prezenčná metóda)
cvičenie2 hod. týždenne (prezenčná metóda)

 
Počet kreditov: 5
 
Odporúčaný semester/trimester: aplikovaná informatika - bakalársky (povinne voliteľný), 6. semester
Stupeň štúdia: 1.
Podmieňujúce predmety: žiadne
 
Podmienky na absolvovanie predmetu:
V priebehu semestra študenti vypracujú zadanie zamerané na výpočty v končných poliach, zadaný výpočet implementujú do podoby vykonávateľných modulov s interfejsom na overenie správnosti výpočtu. Zadanie sa hodnotí 30 bodmi, kontrolny test v priebehu semestra 30 bodmi a záverečná písomná skúška sa hodnotí 40 bodmi.
 
Výsledky vzdelávania:
Získať základné znalosti z algebraickej teórie štruktúr, hlavne z teórie konečných polí a postupností nad konečnými poľami. Ďalej znalosti z efektívnych a rýchlych výpočtov nad konečnými poľami. Študent získa znalosti o matematickom aparáte a programovacích technikách, ktoré sa využívajú v najrozmanitejších krypto API. Po absolvovaní predmetu pochopí princípy konštrukcie algoritmov tvoriacich jadro najrozmanitejších aplikácii na prenos a uchovávanie utajovaných skutočností.
 
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.
 
Odporúčaná literatúra:
Základné:
LIDL, R. -- NIEDERREITER, H. Finite Fields. Cambridge: Cambridge University Press, 2nd Ed., 1997. 768 s. ISBN 0-521-39231-4.
POMERANCE, C. -- CRANDALL, R. Prime Numbers. New York: Springer, 2001. 546 s. ISBN 0-387-94777-9.

 
Jazyk, ktorého znalosť je potrebná na absolvovanie predmetu: slovenský jazyk alebo anglický jazyk
 
Poznámky:
 
Hodnotenie predmetov:
Celkový počet hodnotených študentov: 246

ABCDEFX
21,1 %22,0 %18,7 %17,9 %17,1 %3,2 %
Vyučujúci: RNDr. Karla Čipková, PhD. (cvičiaci, prednášajúci, skúšajúci, tútor) - slovenský jazyk, anglický jazyk
doc. RNDr. Karol Nemoga, CSc. (prednášajúci, zodpovedný za predmet) - slovenský jazyk, anglický jazyk
 
Dátum poslednej zmeny: 9. 4. 2018
Schválil: doc. RNDr. Karol Nemoga, CSc. a garant príslušného študijného programu


Poslednú zmenu urobil RNDr. Marian Puškár dňa 09. 04. 2018.

Typ výstupu: