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 (verze 22.10.), který jsem zkompiloval z přípravované učebnice obecné algebry pro matematiky. Text bude průběžně upravován.
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.

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. Základní pojmy dělitelnosti (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 zbytek sekce 4
sekce 5
screenshot tabulí
Q3 do 28.10. 14:00
28.10.--- přednáška není ---
Cv.: jedno doběhne časový rozvrh, druhé není
sekce 6
4.11.Polynomy: rozklady, NSD (nad tělesem i obecně).
Cv.: invertibilní prvky, ireducibilní prvky, rozklady (polynomy, kvadratická rozšíření)
sekce 6
11.11.Abstraktní teorie dělitelnosti: gaussovské a eukleidovské okruhy
Cv.: NSD a rozklady polynomů, vícenásobné kořeny polynomů (?)
sekce 7
18.11.Polynomy: počítání modulo polynom, čínská věta o zbytcích a interpolace, konstrukce konečných těles
Cv.: dělitelnost v oborech Z[sqrt s]
sekce 8
25.11.Aplikace konečných těles v informatice - AES, sdílení tajemství, samoopravné kódy.
Cv.: ČVZ pro polynomy, počítání v konečných tělesech
sekce 9
2.12.Grupy: příklady, podrupy, generátory.
Cv.: opakování permutací, automorfismy grafů, symetrie geometrických objektů
sekce 10, 11.1
9.12.Grupy: Lagrangeova věta, působení grupy na množině.
Cv.: podgrupy, generátory
sekce 11.2, 12.1
16.12.Grupy: Burnsideova věta a kombinatorické počítání až na symetrie. Struktura cyklických grup (úvod).
Cv.: rozklady podle podgrupy; příklady působení grup, grupy symetrií
sekce 12.2, 13.1
6.1.Grupy: Cyklické grupy, diskrétní logaritmus a aplikace v kryptografii (Diffie-Hellmanův a El Gamalův protokol).
Cv.: Burnsideova věta
sekce 13

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. Přesný způsob specifikuji podle toho, jak dlouho bude probíhat distanční výuka. Počítejte s tím, že to bude cca 5-10% zkouškových bodů.

body z kvízů

Zkouška: Celkem lze získat 100 bodů, z toho max. ??? za kvízy a ??? za písemný test - přesná čísla a formát testu budou specifikovány později.