Diskrétní matematika je vědní obor, který se (velmi zjednodušeně řečeno) věnuje práci s množinami. Pro naše případy je důležitá především teorie dělitelnosti a kombinatorika.
Množina přirozených čísel, značí se N a většinou se uvádí jako {1,2,3,...} (tedy začíná od 1). Někteří autoři uvažují jako přirozené číslo i číslo nula.
Množina celých čísel, značí se Z, předstuje čísla {...,-2,-1,0,1,2,3,...}.
Množina racionálních čísel, značí se Q, předstuje čísla, která jdou vyjádřit zlomkem.
Řekneme, že číslo x dělí číslo y, pokud existuje celé číslo k takové, že y = kx. Značíme x ∣ y. Pokud takové číslo k neexistuje, píšeme x ∤ y.
Nejvyšší společný dělitel x a y, značí se NSD(x, y) je nejvyšší možné číslo k takové, že k ∣ x a zároveň k ∣ y. Pokud je NSD(x, y) rovné jedné, řekneme, že jsou čísla nesoudělná, jinak jsou čísla soudělná.
Představuje základní algoritmus na hledání největšího společného dělitele dvou čísel. Funguje tak, jak je zobrazeno níže, kde hledmáme NSD(493, 1411):
1411 = 2⋅493 + 425
493 = 1⋅425 + 68
425 = 6⋅68 + 17
68 = 4⋅17 + 0
Hledaný nejvyšší společný dělitel je číslo 17.
V první řádce vyjádříme větší z čísel ve tvaru podílu a zbytku při dělení menšího čísla. Zbytek je zřejmý, čísla stačí pouze správně opsat pod sebou, jak je barevně vyznačeno a dopočítat. Algoritmus končí, pokud je poslední zbytek 0.
Čísla (podíly) zobrazené v Eukleidově algoritmu kurzívou, mají své zvláštní uplatnění. S jejich pomocí lze sestrojit tzv. přibližné zlomky. Pro další označíme tyto podíly (to co je kurzívou) symboly q0 až qn, tedy:
q0 = 2
q1 = 1
q2 = 6
q3 = 4
Přibližný zlomek i-tého řádu δi má tvar δi = Pi / Qi. Představuje nejpřesnější odhad daného podílu čísel při určité velikosti jmenovatele.
Výpočet přibližného zlomku se provádí dosazováním do vztahu:
Pi = qiPi-1 + Pi-2
Qi = qiQi-1 + Qi-2
Přičemž uvažujeme počáteční podmínky:
P-1 = -1
P0 = q0
Q-1 = 0
Q0 = 1
Pro náš případ tedy:
| Pořadí: | -1 | 0 | 1 | 2 | 3 |
| qi | - | 2 | 1 | 6 | 4 |
| Pi | 1 | 2 | 3 | 20 | 83 |
| Qi | 0 | 1 | 1 | 7 | 29 |
Předposlední čitatel přibližného zlomku má zvláštní význam, jeho hodnota vynásobená (-1)n představuje multiplikativní inverzi menšího čísla v NSD(x,y) mod větším číslem ve výrazu, kde n je pořadí posledního řetězového zlomku.
Pro náš případ tedy můžeme říct, že multiplikativní inverze 29 mod 83 (což jsou po vydělení nejvyšším společným dělitelem čísla 493 a 1411) je rovna (-1)3⋅20 = (-20). Pokud vyjde záporné číslo, je hodnota stejná jako 83-20 = 63 (přičtením modulusu se nic nemění, modulus je naše číslo 83), hledaná multiplikativní inverze je tedy číslo 63.
def euclideanAlgorithm(a, n):
x = max(a,n);
y = min(a,n);
q = [];
while(y != 0):
q.append(int(x/y));
ri = x % y;
x = y;
y = ri;
return q;
def approximateFraction(q):
Pi = [1, q[0]];
Qi = [0, 1];
for i in range(1,len(q)):
Pi.append(q[i]*Pi[i] + Pi[i-1]);
Qi.append(q[i]*Qi[i] + Qi[i-1]);
return [Pi, Qi];
x = 493;
y = 1411;
print("q: " + str(euclideanAlgorithm(x,y)));
print("Qi, Pi: " + str(approximateFraction(euclideanAlgorithm(x,y))));
Definuje přeuspořádání množiny. Jedná se o vzájemně jednoznačné zobrazení z množiny X na X (kde X je konečná množina). Permutace se obvykle zapisují pomocí tzv. dvouřádkového zápisu (též nazývaný tabulkový zápis):
| π = |
|
V rámci tohoto zápisu jsou na prvním řádku uvedeny umístění ve výstupu a na druhém řádku jím odpovídající pořadí na vstupu. V ukázce to tedy znamená, že na 1. pozici výstupu jde 3. symbol vstupu, na 2. pozici výstupu 5. symbol vstupu atd. Existuje úmluva, že se permutace značí písmeny řecké abecedy.
Inverzní zobrazení (tedy pokud chceme z výstupu získat zpět vstup) získáme tak, že prohodíme v rámci zápisu řádky (na pořadí sloupečků v zápisu logicky nezáleží):
| π-1 = |
|
= |
|
Permutací na n prvkové množině existuje práve n! (n faktoriál).