David Stanovský    //   

ALGEBRA pro informatiky 2010/11

Obsah přednášky Algebra I (NMAI062):
Cílem kurzu je seznámení se základními algebraickými strukturami a koncepty, které jsou užitečné v teoretické informatice, logice a kombinatorice.
  • 30.9.-21.10. Algebry - základní strukturní pojmy (podalgebry, homo- a izomorfismy, faktoralgebry), termy a absolutně volné algebry
    [Skripta sekce 12,24, event. Žemlička sekce 3,11]
  • 4.11.-11.11. Uspořádání, svazy, Booleovy algebry
    [Skripta sekce 2, Žemlička sekce 4]
  • 18.11.-6.1. Grupy - cyklické grupy a modulární aritmetika, permutační grupy a symetrie objektů
    [Skripta sekce 3,14,15,17,18,19,22]
  • 13.1. algebra a constraint solving
Obsah přednášky Algebra II (NMAI063):
Tématem kurzu je algebra polynomů a její aplikace: řešení polynomiálních rovnic, řešení diferenčních rovnic, samoopravné kódy atd. Pozornost bude věnována také konečným tělesům a jejich využití v informatice.
  • 24.2.-17.3. Teorie dělitelnosti - základní věta aritmetiky, gaussovské a eukleidovské obory, hlavní ideály, rozšíření celých čísel
    [Skripta sekce 3,4,5,6,7,8, event. Žemlička sekce 7,8]
  • 24.3.-31.3. Obory polynomů - Gaussova věta, kořeny polynomů a jejich výpočet, interpolace
    [Skripta sekce 9,10]
  • 7.4.-14.4. Čínská věta o zbytcích - faktorokruhy, zobecněná ČVZ a algoritmy na její řešení, modulární metoda návrhu rychlých algoritmů: rychlé násobení polynomů, efektivní NSD v Z[x]
    [Skripta sekce 23.1, Počítačová algebra sekce 5,6,8,14]
  • 21.4.-5.5. Lineární diferenční rovnice - vícenásobné kořeny polynomů, řešení diferenčních rovnic nad algebraicky uzavřenými tělesy, periody řešení diferenčních rovnic nad konečnými tělesy (LFSR)
    [Skripta sekce 11, k LFSR žádný dobrý materiál nemám... připraveno volně podle textu Sequence Analysis, sekce 3.1-3.4, který je ale napsán příšerně]
  • 12.5. Samoopravné kódy - lineární kódy a jejich konstrukce pomocí polynomů
    [žádný dobrý materiál nemám, připraveno na motivy str. 361-366 ze skript Panák-Slovák, kde je ale dost chyb, takže se nenechte zmást]
  • 17.5. Kořenová a rozkladová rozšíření, konstrukce konečných těles
    [Skripta sekce 23.2,25,27,28 (vybrané části), event. Žemlička sekce 5,9,10 (vybrané části)]
  • 26.5. Řešení soustav polynomiálních rovnic více proměnných
    [Počítačová algebra kapitola VI, nezkouší se]
Základní literatura:

  • moje skripta Základy algebry [errata], která právě vyšla v Matfyzpressu - zimní semestr bude založen na kapitolách 0,II,III, letní na kapitolách I,VI
  • Sbírka úloh (v přípravě) - k zimnímu semestru doporučuji cvičení z kapitol I,II, k letnímu především z kapitoly IV
  • skripta Jana Žemličky díl I, díl II
  • k látce druhého semestru též vybrané kapitoly skript Počítačová algebra (Stanovský, Barto), která právě vyšla v Matfyzpressu.

Další užitečné prameny:

Konzultace: kdykoliv mě zastihnete, doporučuji se ohlásit emailem. Sídlím na Katedře algebry, místnost 306, tel. 22191 3359.

Zkouška z Algebry I bude písemná, v případě nesouhlasu s hodnocením může následovat ústní část. Zápočet je nutnou podmínkou přihlášení ke zkoušce.

Test bude obsahovat jednoduché otázky na znění definic a vět (6x 1 bod), znalost základních příkladů a aplikaci definic a vět (6x 1 bod), početní úlohy (4x 2 body) a dále dva důkazy z přednášky (2x 6 bodů). Minimální počet bodů na trojku je 19 bodů (z celkových 32), výsledná známka bude určena podle celkového dojmu z testu. V případě nesouhlasu s hodnocením může následovat ústní část. Časový limit na test je 120 minut.
Zde je předběžná verze kompletní sady úloh 1-13 a seznam důkazů pro úlohy 17-18. Z těchto seznamů se budou losovat písemky. Početní úlohy 14-16 vymyslím pro každý termín zvlášť, půjde o dva typové a jeden netypový početní příklad.
Zde je ukázka testu, který dostanete na zkoušce.

Požadavky ke zkoušce jsou dány tím, co jsem odpřednášel, viz výše uvedené sekce ze skript mojich i Jana Žemličky. Doporučuji se učit ze zápisků z přednášky i ze skript, styl výkladu se může mírně lišit. Doporučuji propočítat reprezentativní část příkladů ze sbírky, sekce I.1,2, II.1,2,3,5,7.

Termíny zkoušek: Budou v SISu. Tamtéž se na ně přihlašujte.
Ještě budou dva termíny, jeden v červnu, jeden v srpnu. V září budu mimo ČR.

Zkouška z Algebry II bude písemná, trochu jiného typu než v zimě.

Test bude obsahovat jednoduché otázky na znění a přímou aplikaci definic a vět, dva důkazy z přednášky a dvě početní úlohy. Podívejte se na vzorový test a první zkouškový test. Limit 90 minut, minimální počet bodů 30 z 60. Výsledná známka bude určena podle celkového dojmu z testu, v případě nesouhlasu s hodnocením může následovat ústní část.

Požadavky ke zkoušce jsou dány tím, co jsem odpřednášel, viz výše uvedené materiály. Doporučuji se učit ze zápisků z přednášky i ze skript, styl výkladu se může mírně lišit. Doporučuji propočítat reprezentativní část následujících příkladů ze sbírky:

  • faktorokruhy: 469-485, 630-641 (konečná tělesa)
  • čínská věta o zbytcích: 507-513
  • kořeny polynomů: 553-561, 582-600
  • dělitelnost v oborech integrity: 562-581 (polynomy), 601-618 (rozšíření celých čísel)
  • teorie těles: 646-649 (minimální polynomy), 699-710 (kořenová a rozkladová nadtělesa)
Přínosná mohou být i cvičení ve skriptech Počítačová algebra.

Termíny zkoušek: Budou v SISu. Tamtéž se na ně přihlašujte.
Budou čtyři termíny v červnu a jeden v srpnu. V září budu mimo ČR.