1. Domácí úkol: Binomické koeficienty

Úvod

Cílem prvního úkolu je seznámit se se základy Julia (podmínky, cykly, metody, typový systém). Vypracování tohoto úkolu by vám nemělo zabrat příliš času.

Cvičnými objekty v tomto úkolu pro nás budou známé binomické koeficienty. V tomto prvním jednodušším úkolu se budeme zabývat jejich implementací v Julia. Na binomické koeficienty narazíte v mnoha kombinatorických, pravděpodobnostních ale i analytických úlohách. Jejich značení, které používáme i níže, pravděpodobně pochází od rakouského matematika Andrease von Ettingshausena z roku 1826.

Teoretický background

Středoškolská definice binomického čísla je jistě všem dobře známá. Pro nezáporné celé číslo $n$ a celé číslo $k$ splňující $0 \leq k \leq n$ klademe

\begin{pmatrix} n \\ k \end{pmatrix} := \frac{n!}{(n-k)! k!}.

Dále se používají tzv. zobecněná binomická čísla, která se značí stejným symbolem. Pro libovolné komplexní $z$ a nezáporné celé $k$ klademe

\begin{pmatrix} z \\ k \end{pmatrix} := \frac{z (z-1) (z-2) \cdots (z - k + 1)}{k!}.

Pro $k = 0$ součin v čitateli chápeme jako prázdný a tedy rovný $1$ . Pokud je $z = n$ nezáporné celé číslo, tak oba vzorce dávají stejnou hodnotu (zkrácení).

Implementační pokyny

Varování:

Julia samozřejmě binomické koeficienty implementuje. Pro účely tohoto úkolu ale tuto implementaci ignorujte, přijďte se svojí vlastní! V rámci finálního porovnání mezi studenty vezmu do úvahy i Julia implementaci.

V souboru main.jl doplňte implementaci funkce binom (resp. jejích metod, kterých může být více) počítajících (zobecněné) binomické koeficienty. Podrobněji:

Funkce bude přijímat dva poziční argumenty, označme nepřekvapivě první n a druhý k.
Pokud jsou n i k celočíselné stejného typu, tak funkce vrátí hodnotu příslušného binomického čísla. V případě, že nejsou z výše uvedeného rozsahu (záporné n, k větší než n, atp.), tak dojde k vyvolání výjimky ArgumentError.
Pokud je k nezáporné celočíselné a n neceločíselné (reálné, komplexní), tak funkce vrátí hodnotu příslušného zobecněného binomického čísla. V případě, že k je záporné, dojde k vyvolání výjimky ArgumentError.
Implementace bude detekovat přetečení při násobení celočíselných argumentů, například pomocí checked_mul metody z Base.Checked modulu a v takovém případě vyvolá výjimku OverflowError.

Ve všech případech bude funkce vracet hodnotu stejného typu jako je n. Například tedy:

julia> include("main.jl")
binom

julia> binom(12, 9)
220

julia> binom(0, 0)
1

julia> binom(12.3 + 4.0im, 7)
-1932.417921909584 + 380.25832630396883im

julia> binom(-999.0, 5)
-8.37504162495e12

julia> binom(5, -2)
ERROR: ArgumentError: Arguments are out of range!

Další ukázky lze nalézt v přiložených testech v adresáři test.

V případě nečíselného typu argumentů (např. pole nebo řetězec) dojde k vyvolání výjimky MethodError. Pokud je druhý argument záporný celočíselný nebo neceločíselný (reálný/komplexní), pak dostaneme výjimku ArgumentError.

Své metody opatřete dokumentačním docstringem stručně popisujícím její chování.

Svou implementaci můžete lokálně snadno otestovat příkazem julia test/runtests.jl (je potřeba mít nainstalovaný balíček Glob), výstup by měl vypadat přibližně takto:

$ julia test/runtests.jl
┌ Info:
│ Running tests in test_binom.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Errors: wrong types and values                               |    6      6  0.1s
Test Summary:                                                | Pass  Total  Time
Errors: integer overflow                                     |    1      1  0.0s
Test Summary:                                                | Pass  Total  Time
Types: integer arguments                                     |    4      4  0.1s
Test Summary:                                                | Pass  Total  Time
Types: complex/real arguments                                |    5      5  0.1s
Test Summary:                                                | Pass  Total  Time
Values: integer arguments                                    |    6      6  0.0s
Test Summary:                                                | Pass  Total  Time
Values: complex/real arguments                               |    5      5  0.2s

Tyto testy se spouští i automaticky na Gitlabu a na stránce Merge Requestu jejich výsledek uvidíte ve formě červené nebo zelené ikonky.

Součástí vyhodnocení řešení bude porovnání rychlosti i robustnosti vaší implementace vzhledem k ostatními řešením.

Řešení a odevzdání

Opět vytvořte větev odvozenou z větve assignment/01-binomial a nezvěte ji solution/01-binomial. Do solution/01-binomial vložte své řešení editací souboru main.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.