1. Domácí úkol: Dělení polynomů

Úvod

Prvním domácím úkolem se vrátíme k studentům velmi dobře známému algebraickému algoritmu, k dělení polynomu polynomem. Obsahem tohoto úkolu cílíme zejména na následující body procvičení základů Julia (podmínky, cykly, typy, metody, práce s poli),

Algoritmus dělení polynomu polynomem se používá například v konstrukci konečných těles majících $p^n$ prvků (zde $p$ je prvočíslo a $n$ nějaké přirozené číslo větší než 1).

Teoretický background

Implementační cíle úkolu jsou tři:

typ Polynomial{T} modelující polynom s koeficienty typu T,
algebrické operace sčítání + a násobení * mezi instancemi dříve uvedného typu,
metoda pdiv provádějící dělení polynomu polynomem.

Svůj kód vložte do souboru poly.jl, kde je i předpřipravena nekompletní šablona. Nedokončená místa jsou označena pomocí koentářů # TODO. V tomto souboru můžete (a je to velmi vhodné) definovat i další pomocné metody. Případně můžete přidat i další testy do adresáře test, viz sekci Lokální spouštění testů.

Než se pustíme do formálního popisu zadání, rychle připomeneme/představíme matematické pozadí problému.

Dělení polynomu polynomem

Mějme dva polynomy $p(x) = \sum_{k=0}^n a_k x^k$ a $q(x) = \sum_{k=0}^m b_k x^k$ . Nechť $p$ má stupeň $n$ a $q$ je nenulový polynom stupně $m$ .

Cílem algoritmu dělení polynomu polynomem je nalézt polynomy $Q$ (násobek) a $R$ (zbytek) takové, že $p = Q \cdot q + R$ a stupeň polynomu $R$ je ostře menší než stupeň polynomu $q$ . Tato úloha má jednoznačné řešení.

Pokud $n < m$ , pak máme triviální řešení $p = 0 \cdot q + p$ .

V opačném případě hledané polynomy určíme iterativně pomocí následujícího postupu (znáte ze svého studia jako tzv. "dlouhé" dělení):

nastav $Q = 0$ a $R = p$ .
poděl vedoucí člen (člen s nejvyšší mocninnou) polynomu $R$ vedoucím členem polynomu $q$ , tento podíl přičti k polynomu $Q$ a dále od $R$ odečti součin $q$ a tohoto podílu.
tento proces opakuj tak dlouho dokud není stupeň polynomu $R$ menší než stupeň polynomu $q$ .

Na konec vrátíme dvojici $(Q, R)$ .

Implementační pokyny

Část kódu je pro vás již předpřipravena, můžete ho ale případně upravovat či zkrášlovat. Existující testy byste ale modifikovat neměli, určitě ovšem můžete přidávat vlastní.

Ke splnění úkolu je potřeba doplnit implementace následujících metod:

sčítání + a násobení * polynomů,
vyhodnocování funkčního hodnot polynomů,
dělení polynomu polynomem pdiv, které vrátí násobek a zbytek po dělení jako dvojici (tuple).

Lokální spouštění testů

Toto zadání je úmyslně vytvořeno lehce "na koleni" a nevyužívá například moduly nebo Julia projekty ke správě závislostí (látka, ke které se dostaneme později během semestru).

Zadání je doplněno sadou jednoduchých testů. V kořenovém adresáři tohoto zadání stačí z příkazové řádky spustit

$ julia test/runtests.jl

Tímto příkazem spustíte všechny test v souborech test/test_*.jl. Případně tak do adresáře test můžete snadno přidat i další pomocné vlastní testy vlastních pomocných metod, jen je musíte pojmenovat ve tvaru test_*.jl.

Pokud vše dopadne dobře, měli byste vidět na standardním výstup výpis podobný tomuto:

$ julia test/runtests.jl
┌ Info: Running tests in test_Polynomial.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Polynomial: constructor                                      |    2      2  0.1s
Test Summary:                                                | Pass  Total  Time
Polynomial: degree                                           |    5      5  0.0s
Test Summary:                                                | Pass  Total  Time
Polynomial: takes care of zero leading coefficient           |    3      3  0.0s
┌ Info: Running tests in test_algebra.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Multiplication: simple examples                              |    6      6  0.1s
Test Summary:                                                | Pass  Total  Time
Addition: simple examples                                    |    4      4  0.0s
┌ Info: Running tests in test_other.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
subtract!                                                    |    4      4  0.1s
┌ Info: Running tests in test_pdiv.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
pdiv: simple examples                                        |    5      5  0.1s
Test Summary:                                                | Pass  Total  Time
pdiv: more involved examples                                 |    2      2  1.0s
┌ Info: Running tests in test_peval.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Evaluation: simple examples                                  |    7      7  0.1s

V opačném případě dostanete od Julia vynadáno!

Řešení a odevzdání

Opět vytvořte větev odvozenou z větve assignment/01-poly a nezvěte ji například solution/01-poly. Do solution/01-poly vložte své řešení editací souboru poly.jl případně přidáním testů do složky test. Až budete se svým řešením spokojeni, vytvořte MR (to můžete i dříve, aspoň uvidíte výsledek testů, pokud je nespouštíte lokálně) a přiřaďte mě k němu jako assignee. Tímto aktem úkol odevzdáte.