Počítačová algebra ZS 2026/2027

Kontakt

Pro případné dotazy a konzultace použijte můj mail: patak AT kam.mff DOT cuni.cz.

Domácí úkoly

Řešení domácích úkolů zasílejte na shora uvedený mail.
1.10.2026
  1. Napište program pro výpočet největšího společného dělitele v oboru Gaussovských celých čísel, a jeho běh ilustrujte na výpočtu největšího společného dělitele čísel 4 a 9+5i.
8.10.2026
  1. Napište vlastní programy na násobení (dlouhých) celých čísel: porovnejte metody školského násobení pod sebou, Karatsuby a Toom-3. Na základě experimentu určete, které metody jsou nejvhodnější pro dané délky čísel. To jest, určete, od jaké délky se vyplatí používat (vaší implementaci) Karatsuby, od jaké Toom-3..

Seznam probraných témat

1.10.2026
  1. Reprezentace čísel v počítači
  2. Délka čísla v soustavě o základu B
  3. Sčítání, odčítání, násobení a dělení pod sebou s časy O(n+m), O(n+m), O(mn), O(n(m-n+1)); převod do jiné báze
  4. Rozšířený Euklidův algoritmus a jeho použití pro řešení soustavy kongruencí (Čínská zbytková věta); Garnerův a Lagrangeův algoritmus - zatím bez odhadu časové a paměťové složitosti
  5. Reprezentace polynomu jedné proměnné (husté vs řídké reprezentace)
8.10.2026
  1. Složitost rozšířeného Euklidova algoritmu
  2. Složitost algoritmů pro Čínskou zbytkovou větu
  3. Interpolace polynomů jako speciální případ ČVZ
  4. Metoda rozděl a panuj:
    • Mistrovská metoda pro odhad časové složitosti
    • Karatsubův algoritmus pro násobení čísel
    • Algoritmy Toom-k pro násobení čísel

Literatura

Kurz následuje skripta Počítačová algebra od Davida Stanovského a Libora Barta; i když v poněkud volném pořadí témat. Scripta lze rovněž konzultovat pro rigorózní formulace všech důkazů. Buďte však obezřetní, skripta na mnoha místech obsahují drobné nepřesnosti.