Algoritmy na mrizich, ZS 2022/2023

Kdy a kde

Streda 12:20 - 13:50 v K5

Zkouska

Bude ustni, dve otazky z probrane latky.

Prezentace a zaznam prednasek ze ZS 2020/2021

Jsou k dispozici na studentskem ulozisti .

Deni na prednasce

5. 10. 2022 Definice mrize, mrize a diskretni podgrupy, nejkratsi vektor v mrizi, varianty problemu SVP.

12. 10. 2022 Problem CVP a jeho varianty, neformalni dukaz NP uplnosti rozhodovaciho CVP. Algoritmus pro promise SVP pomoci orakula pro promise CVP. Problemy SIVP a SIS (nedokonceno).
Prednaska O. Regeva, ze ktere jsem vychazel zde

19. 10. 2022 Redukce nejtezsiho SIVP na prumerny SIS (pokus o neformalni priblizeni, v zadnem pripade nebude predmetem zkousky). Celociselna linearni algebra - konecne generovane volne grupy a jejich homomorfismy, uchopeni pojmu pomoci souradnic.

26. 10. 2022 Hermiteuv normalni tvar ctercove matice (algoritmus pro prevedeni matice do HNF), HNF obecne matice (bez dukazu) podgrupy volne komutativni grupy, jak najit volnou bazi podgrupy Z^n zadane pomoci konecne mnoziny generatoru.

2. 11. 2022 Gram-Schmidtova ortogonalizace - opakovani + zavedeni znaceni, Gramova matice a jeji determinant. Determinant uplne mrize, fundamentalni bunka mrize vzhledem k nejake jeji bazi, zneni Minkowskeho vety o mrizovem bode.
Vysvetleni dukazu Minkowskeho vety lze nalezt zde.

16. 11. 2022 Dukaz vety o mrizivem bode a Minkowskeho mez pro prvni postupne minimum uplne mrize. Kazda diskretni podgrupa R^n je mriz - trochu krkolomna aplikace Minkowskeho meze.

23. 11. 2022 Gaussova redukce dvourozmerne mrize.

30. 11. 2022 LLL-redukovana baze uplne mrize a jeji vlastnosti. Algoritmus LLL.

7. 12. 2022 Koreknost + (nedodelana) slozitost algoritmu LLL.

14. 12. 2022 Dokonceni slozitosti LLL, kombinacni faze Berlekampova - Henselova algoritmu.

21. 12. 2022 Dokonceni aplikace LLL pro faktorizaci polynomu. The Nearest Plane Algorithm - uvod.
Poznamky k Nearest Plane Algorithm zde. Poznamky k vykladu jeste doplnim.

4. 1. 2023 Dukaz koreknosti N.P.A. Pravdepodobnostni algoritmus pro reseni SVP v case 2^O(n)*poly (vpodstate jen zformulovani algoritmu, tento algoritmus jiz nebude predmetem zkousky.)
Dalsi informace k algoritmu pro SVP jsou zde.

Info ke zkouskam: Terminy zkousky nejsou vypsany v SISu - termin zkousky dohodneme individualne po mailu. Ke zkousce neni potreba zapocet a bude-li treba, lze ji slozit i v prubehu letniho semestru.