Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Algebraické struktury v teoretické informatice

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01ALTI ZK 3 1+1 česky
Garant předmětu:
Edita Pelantová, Severin Pošta
Přednášející:
Severin Pošta, Milena Svobodová
Cvičící:
Severin Pošta, Milena Svobodová
Předmět zajišťuje:
katedra matematiky
Anotace:

Předmět je věnován některým algebraickým strukturám. Zaměřuje se na Gröbnerovy báze ideálů okruhů polynomů a na jejich použití při řešení soustav algebraických rovnic a jejich další praktické aplikace a na celočíselné okruhy v algebraických tělesech, které se využívají k různým reprezentacím čísel s cílem návrhu efektivních algoritmů pro aritmetické operace a evaluaci elementárních funkcí.

Požadavky:

Znalosti základů obecné algebry (01ALGE) a algebraické teorie čísel (01TC).

Osnova přednášek:

1) Gröbnerovy báze v okruzích polynomů více proměnných

2) Ideály v okruzích polynomů více proměnných, báze ideálu

3) Uspořádání monomů, přepisování

4) Buchbergerův algoritmus

5) Řešení soustav polynomiálních rovnic, barvení grafů, automatické dokazování

6) Jednoznačné poziční reprezentace s celočíselnými bázemi v okruhu celých čísel Z a v okruhu gaussovských celých čísel, NAF reprezentace, aritmetické operace v těchto soustavách a konečné automaty.

7) Redundantní reprezentace v reálném a komplexním oboru, paralelní algoritmy pro sčítání a odčítání a vztah k míře redundance, on-line algoritmy pro násobení a dělení.

8) Reprezentace čísel pro „posuň a sečti“ algoritmy k výpočtu hodnot elementárních funkcí.

Osnova cvičení:

V oblasti okruhů polynomů je cvičení zaměřeno na konstrukci Gröbnerových bází konkrétně zadaných ideálů.

V oblasti číslených soustav je cvičení zaměřeno zejména na hledání reprezentace čísel v různých soustavách, algorimty pro aritmetické operace v redundantní soustavě a na optimalizaci parametrů pro zadanou bázi. Studenti také prezentují řešení teoretických i praktických úloh, které jim byly zadány individuálně.

Cíle studia:

Naučit se manipulovat s ideály okruhů polynomů několika proměnných, konstruovat Gröbnerovy báze těchto ideálů. Naučit se pracovat s různými číselnými reprezentacemi a využívat je ke konstrukci algoritmů pro rychlé počítání aritmetických operací a vyčíslování elementárních funkcí.

Studijní materiály:

[1] Jean-Michel Muller, Elementary Functions: Algorithms and Implementation, 3rd ed., Birkhauser 2016

[2] Michel Rigo, Formal languages, Automata and Numeration systems, Wiley, 2014

[3] David Stanovský, Libor Barto: Počítačová algebra, Matfyzpress 2017

Poznámka:
Rozvrh na zimní semestr 2024/2025:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost TR:112
Svobodová M.
16:00–17:50
(přednášková par. 1)
Trojanova 13
zasedací místnost KM
St
Čt

Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 2. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet3947206.html