Aritmetika a algoritmy

Logiky je třeba upozornit, že na této přednášce půjde jen občas o logiku, více o matematiku, také o počítání, a někdy bude užitečná dokonce kalkulačka. Někdy použijeme kalkulátor BNCalc.pdf. Nelogikové jsou vítáni, jediná podmínka je nemít averzi k matematice.

Atestace:

Program v LS 2011/12

23. února 2012

Pojem úlohy. časové nároky školního algoritmu pro Násobení a "přirozeného" algoritmu pro Prvočíselnost. Úloha Factoring. Polynomiální algoritmy a polynomiálně počitatelné (rozhodnutelné) úlohy.

1. března 2012

Vlastnosti relace dělitelnosti. Operace dělení se zbytkem. Úloha GCD a Eukleidův algoritmus pro ni.
D. cv.: Nalezněte největší společný dělitel čísel 65975193 a 265927, nebo čísel 180589 a 54737.

8. března 2012

Dělitelnost v oboru celých čísel. Bezoutova věta a Bezoutova rovnice. Zobecnění Eukleidova algoritmu, které je schopné najít i řešení Bezoutovy rovnice.
D. cv.: Nalezněte celočíselné řešení rovnice 829x+362y=1, pokud existuje.

15. března 2012

Modulární aritmetika. Definice komutativního okruhu a bezprostřední důsledky axiomů. Inverzní a invertibilní prvky. Okruhy Z, Z_m, Q a Q[x] a invertibilní prvky v nich. Použití Bezoutovy věty k identifikaci těch prvků v Z_m, které jsou invertibilní.
D. cv.: Dokažte, že v každém komutativním okruhu platí -(x+y)=(-x)+(-y).
V okruhu Z₆₅₅₃₆ vyřešte rovnici 7x=3.

22. března 2012

Obory integrity, tělesa, dělitelnost v oborech integrity, prvočísla a ireducibilní čísla, Bezoutova věta jako dodatečný axiom platný v některých oborech integrity.
D. cv.: Jsou-li prvky a a b libovolného oboru integrity, v němž platí Bezoutova věta, nesoudělné, pak splňují podmínku: pro každé z, když a dělí bz, pak a dělí z. Dokažte toto tvrzení.

29. března 2012

Modulární reprezentace a Čínská zbytková věta. Pseudoprvočísla.
D. cv. 1: Nalezněte číslo, jehož modulární reprezentace vůči modulům 7,8,9 je [4,6,5].
D. cv. 2: Dokažte pomocí modulárních reprezentací, že číslo 561 je pseudoprvočíslo.
Návod: kromě vědomostí známých z přednášky ověřte a využijte fakt, že v okruhu Z₁₇ platí rovnost 2⁸=1.

5. dubna 2012

Komutativní grupy, bezprostřední důsledky axiomů. Eulerova grupa a Eulerova funkce.
D. cv.: Stanovte počet prvků grupy Φ(175) a grupy Φ(341). Nalezněte prvek a grupy Φ(341), pro který v Z₃₄₁ platí a³⁴¹≠a.
Návod: z úvah o pseudoprvočíslech víme, že a=2 se nehodí. Ověřte a využijte skutečnosti, že v Z₃₁ platí 3³⁰=1, avšak 3¹⁰≠1 (což je ovšem totéž jako 3¹¹≠3).

12. dubna 2012

Polynomiální algoritmus pro umocňování modulo. Malá věta Fermatova. Kryptografická metoda RSA.
D. cv.: Pro šifrování metodou RSA byl zvolen šifrovací klíč r=1037 a jako limit pro šifrované číslo bylo zvoleno číslo m=2248240321; umocňování na 1037 mod 2248240321 je tedy šifrovací funkcí. S pomocí kalkulátoru BNCalc rozluštěte číslo 1579156340. Toto je cvičení 10 ze seznamu cvaralg.pdf. Relevantní je též (první část) cvičení 6 (druhou jsme na přednášce provedli).

19. dubna 2012

Řády prvků v grupách. Cyklické grupy. Úlohy ve třídě NP.
D. cv.: 9 a 10 v seznamu.

26. dubna 2012

Úlohy ve třídě NP ještě jednou. Úlohy Složená čísla, Sat a Problém batohu, jejich příslušnost do třídy NP. Šest lemmat týkajících se počtů prvků určitého řádu, směřujících k důkazu tvrzení, že Eulerova grupa Φ(m) je cyklická vždy, když m je prvočíslo.

3. května 2012

Dokončení důkazu věty, že když m je prvočíslo a k dělitel čísla m-1, pak ve Φ(m) je φ(k) prvků řádu k.
D. cv.: 16 a 17 v seznamu. Při rozkládání čísel na prvočísla využijte kalkulátor BNCalc. Práci se stránkou Factoring může usnadnit klávesová kombinace Shift-M, která funguje po stisknutí tlačítka Go, tj. je-li aktivní pole s nalezeným dělitelem (ve snímku obsahuje číslo 2). I v ostatních stránkách funguje kombinace Shift-M, a také kombinace Shift-B (je-li aktivní pole s výsledkem).

10. května 2012

Prattův kalkulus pro dokazování prvočísel. Prattova věta: Prvočíselnost je úloha ve třídě NP. Pojem probabilistického algoritmu.