David Stanovský    //   

ALGEBRA I pro informatiky 2020/21

Stručný obsah:

  1. Čísla: prvočíselné rozklady, kongruence, Eulerova věta a RSA, čínská věta o zbytcích
  2. Polynomy: abstraktní obory integrity, obory polynomů, ireducibilní rozlady, NSD, čínská věta o zbytcích a interpolace, konstrukce konečných těles a jejich aplikace (samoopravné kódy, sdílení tajemství, ...)
  3. Grupy: permutační grupy, podgrupy, Lagrangeova věta, působení grupy na množině a Burnsideova věta, cyklické grupy a diskrétní logaritmus a jeho aplikace v kryptografii

Základním studijním materiálem je studijní text (finální verze), který jsem zkompiloval z přípravované učebnice obecné algebry pro matematiky.
On-line přednáška bude komentářem tohoto textu, hlavní část studia však spočívá v četbě tohoto textu.

Cvičení: viz Moodle.

!!NEW!! Zde je podrobný popis zkoušky, včetně vzorového textu. !!NEW!!

Předběžný plán / Průběžně aktualizovaný program přednášky:

téma četba video kvíz
30.9.Quo vadis mathematica.
Elementární teorie čísel: rozklady, NSD
Cv.: elementární teorie čísel, kongruence (včetně teorie)
sekce 1
$1M problems
motivace
sekce 1
--
7.10.Elementární teorie čísel: Eulerova věta a kryptosystém RSA, čínská věta o zbytcích
Cv.: Eukleidův algoritmus (čísla, polynomy)
sekce 2 sekce 2 Q1 do 14.10. 14:00
výsledky
14.10.Abstraktní teorie dělitelnosti: základní vlastnosti oborů integrity, podílové těleso, obory polynomů.
Cv.: Eulerova věta, ČVZ
sekce 3, 4.1 sekce 3.1,3.2
sekce 3.3
sekce 4.1
Q2 do 21.10. 14:00
výsledky
21.10.Polynomy: dělení se zbytkem, kořeny a dělitelnost.
Abstraktní teorie dělitelnosti: základní pojmy - invertibilní prvky, NSD, ireducibilní prvky a prvočinitelé, ired. rozklady
Cv.: příklady oborů integrity (včetně kvadratických rozšíření), podílové těleso (důkaz správnosti konstrukce a příklady)
sekce 4, 5.1-5.3 zbytek sekce 4
sekce 5.1-5.3
screenshot tabulí
Q3 do 28.10. 14:00
výsledky
28.10.--- přednáška není ---
Cv.: jedno doběhne časový rozvrh, druhé není
4.11.Abstraktní teorie dělitelnosti: důsledky existence a jednoznačnosti rozkladů
Polynomy: dělitelnost v polynomiálních oborech (rozklady, NSD), kritérium existence racionálního kořene.
Cv.: rozklady a kořeny polynomů
sekce 5.4, 6 sekce 5.4
sekce 6.1
sekce 6.2
sekce 6.3
Q4 do 11.11. 14:00
výsledky
11.11.Abstraktní teorie dělitelnosti: zobecněná základní věta aritmetiky, abstraktní Eukleidův algoritmus
Polynomy: čínská věta o zbytcích a interpolace
Cv.: invertibilní prvky; kvadratická rozšíření celých čísel
sekce 7, 8.1 sekce 7.1
sekce 7.2
sekce 8.1
Q5 do 18.11. 14:00
výsledky
18.11.Polynomy: počítání modulo polynom, konstrukce konečných těles. Reprezentace dat pomocí F_2^k, aplikace: šifra AES
Cv.: dělitelnost v Gaussových celých číslech
sekce 8.2, 9.1
eliptické křivky
sekce 8.2
sekce 9.1
screenshot tabulí
Q6 do 25.11. 14:00
výsledky
25.11.Aplikace konečných těles v informatice - sdílení tajemství, samoopravné kódy, vzájmně ortogonální latinské čtverce.
Cv.: ČVZ pro polynomy; počítání v konečných tělesech
sekce 9.2-9.4 sekce 9.2
sekce 9.3
sekce 9.4
Q7 do 2.12. 14:00
výsledky
2.12.Grupy: příklady, podrupy, generátory.
Cv.: opakování permutací, automorfismy grafů, symetrie geometrických objektů
sekce 10, 11.1 sekce 10, 11.1 Q8 do 9.12.
výsledky
9.12.Grupy: Lagrangeova věta, působení grupy na množině.
Cv.: podgrupy, generátory
sekce 11.2, 12.1 sekce 11.2
sekce 12.1
Q9 do 16.12.
výsledky
16.12.Grupy: Burnsideova věta a kombinatorické počítání až na symetrie. Struktura cyklických grup (úvod, podgrupy).
Cv.: rozklady podle podgrupy; příklady působení grup, grupy symetrií
sekce 12.2, 13.1 (po příklady o Zn, Zp*) sekce 12.2
sekce 13.1 úvod
tabule
Q10 do 6.1.
výsledky
6.1.Grupy: Cyklické grupy, grupy Zp* jsou cyklické, diskrétní logaritmus a aplikace v kryptografii (Diffie-Hellmanův a El Gamalův protokol).
Cv.: Burnsideova věta
sekce 13 sekce 13.1,2
sekce 12.3
---

Literatura:

  • učební text připravený pro tento kurz - primární zdroj, obsahuje naprostou většinu materiálu
  • sbírka úloh (kurzu se týkají kapitoly II, III, IV.2); jde o mírně zastaralý materiál a neobsahuje zdaleka všechny typy úloh, které se vyskytnou na cvičeních či u zkoušky
  • pokud se vám můj styl nelíbí, existuje řada pěkných učebnic v angličtině, doporučuji například:
    • J. Rotman, A First Course in Abstract Algebra (2ks v knihovně)
    • L. Rowen, Algebra: Groups, Rings, and Fields (zdarma online)
    • víceméně jakákoliv kniha obsahující "abstract algebra" v názvu a "undergraduate level" v popisu bude pokrývat větší část látky přístupnou formou
  • podnětné články obsahuje anglická wikipedia, ideální na dohledání širšího kontextu probíraných pojmů
  • moje stará skripta Základy algebry (Matfyzpress 2009) jsou víceméně překonaná tím novým textem

zdroj: xkcd.com

Konzultace: Pokud něčemu nerozumíte, nebojte se zeptat! Kdykoliv osobně či on-line, po předchozí domluvě emailem. K dotazům můžete využít i kvízy.

Zápočet bude udělován za zápočet za aktivní přípravu spočívající v odevzdání alespoň 9 poctivých příprav, přičemž "poctivá příprava" znamená, že jste se seriózně pokusili o aspoň polovinu úloh a aspoň jednu úlohu jste vyřešili správně. Udělení zápočtu je v kompetenci cvičících.

Kvízy budou zadávány on-line každý týden po dobu distanční výuky. Jejich účelem je kontrolovat, zda studujete materiály průběžně. Termín vyplnění najdete v tabulce (typicky do další přednášky). Kvízy se počítají se jako extra body ke zkoušce, jeden kvíz = maximálně jeden bod, celkem maximálně 10 bodů.

body z kvízů

Zde je podrobný popis zkoušky, včetně vzorového textu. !!NEW!!