Náměty aktivit pro popularizaci matematiky

V jistém slova smyslu "si hrajeme" s pseudonáhodnými čísly. Zatímco v běžné loterii asi spíše či skoro určitě prohrajeme, v popisované metodě je náhoda naším spoluhráčem a můžeme se dostat rychle k výsledku.

Matematici hrají fair!

„Školní“ metoda pro nalezení rozkladu přirozeného čísla N  1 vyžaduje opakovat dělení čísly 2, 3, 4, 5, ... až do té doby, kdy nalezneme číslo dělící N. Pokud však žádné přirozené číslo x,  , nedělí N, pak je N prvočíslem. V tomto smyslu dává metoda opakovaného dělení vždy výsledek: buďto nalezne netriviální dělitel přirozeného čísla N, nebo poskytne důkaz, že N je prvočíslem. Je ale známo, že metoda opakovaného dělení je velice pomalá. Pro velká N není možné ji nechat v úplnosti proběhnout. Význam této metody pro faktorizaci velkých přirozených čísel je v tom, že ji lze užít jako první krok při faktorizaci, přičemž má odhalit malé prvočíselné faktory. (Lze vyslovit námitku, že efektivnost této metody by se zlepšila, kdybychom testovali jen dělitelnost prvočísly. To se ale opírá o fakt, že při školních výpočtech máme několik „malých“ prvočísel v paměti a stejně je tomu i při výpočtech počítačových). Závěr, že metoda opakovaného dělení je příliš pomalá, se nemění. Ještě horší je to, jak již víme, v obecném případě s efektivitou Fermatovy faktorizační metody.

Nepřekvapuje proto, že v posledních třiceti letech byly navrženy efektivnější faktorizační algoritmy. Patří mezi ně i faktorizační metoda, navržená J. M. Pollardem v r. 1975. Je vhodné se s touto metodou seznámit , je jednoduchá, elegantní a poskytne nám příležitost seznámit se s některými možnostmi grafických kalkulátorů. Snad tento text poskytne řadu návodů k experimentům, podnětů k napsání jednoduchých matematických programů atd.

Pollardova rho metoda má pravděpodobnostní charakter. Je v ní zapotřebí nalézt dvě pseudonáhodná čísla x_n, x_m, mající jistou vlastnost. Následující klasický příklad z teorie pravděpodobnosti dává naději, že na tato „vhodná“ čísla nebudeme čekat dlouho.

I. Příklad 1:

Sešla se skupina n osob, n je větší nebo rovno 2. Vypočtěte pravděpodobnost, že alespoň dva z nich budou mít narozeniny stejný den v roce. (Pro jednoduchost předpokládejme, že rok má 365 dní, tj. nebereme v úvahu přestupné roky).

Řešení:

Určeme pravděpodobnost komplementárního jevu A, že žádné dvě osoby z n zúčastněných nebudou mít narozeniny týž den v roce.

Spočtěme nejprve, kolik je všech možných případů pro data narození těchto n osob. Pro den narození první osoby je 365 možností, pro dvě osoby je tedy 365² možností, pro n osob 365ⁿ možností.

Vypočtěme dále, kolik z těchto případů je příznivých. První osoba se může narodit kterýkoli den v roce. Je-li ale již známo její datum narození a nemá -li druhá osoba mít narozeniny týž den, „zbývá“ pro její datum narození již jen 365 - 1 = 364 možností. Nemá-li datum narození žádných dvou osob z n zúčastněných připadnout na stejný den v roce, je 365.364. ... .(365 - n + 1) příznivých případů. Proto

     (1)     je pravděpodobnost jevu, že žádné dvě osoby z n zúčastněných nebudou mít narozeniny týž den v roce.

Jak si ale vypočítat a případě i znázornit hodnoty pravděpodobností P(A) z (1) pro různá n?

Bylo by jistě možné využít nějakého počítačového programu, ale příslušný software nebývá právě levný. Jak bylo řečeno výše, v posledních zhruba patnácti letech se zprvu v USA, pak v západní Evropě a nyní již i u nás rozšiřují tzv. grafické kalkulátory, které mají víceřádkový displej a umožňují „načrtnout“ grafy funkcí (posloupností). Tyto kalkulátory bývají programovatelné, nejlépe vybavené typy umožňují provádět i symbolické výpočty, resp. stáhnout si do kalkulátoru i programy z interenetu. Pro lepší představu o možnostech grafických kalkulátorů jsou dále zařazeny obrázky displeje kalkulátoru TI-83 Plus firmy Texas Instruments. Jednotlivé body znázorňují hodnoty posloupnosti (1) pro n = 1, 2, ..., 30.

Získány byly takto:

II. Grafické kalkulátory mívají k dispozici povel, kterým jsou generována tzv. pseudonáhodná celá čísla z intervalu . Vyzkoušejme povel, který by v závislosti na typu kalkulátoru mohl znít kupř. randInt(n, m) nebo nějak podobně. Kupř. na výše zmíněném kalkulátoru TI-83 Plus se po zadání randInt(1, 6) na displeji objeví jisté přirozené číslo k, pro které  čili kalkulačka vlastně simuluje házení kostkou s čísly 1, 2, ..., 6). Obdobně povel randInt(0, 1) poskytuje buď hodnotu 0 nebo 1 a tento výsledek lze interpretovat jako simulaci házení mincí, chápeme-li např. 0 jako líc, 1 - rub. Zmiňme se o metodách pro generování posloupností pseudonáhodných čísel.

Zřejmě nejvíce je využívána tzv. multiplikativní kongruenční metoda (multiplicative congruential method), pocházející od D. H. Lehmera (1948). Posloupnosti pseudonáhodných čísel se konstruují tak, že se

1. vypočítají po sobě jdoucí mocniny čísla 

2. získané mocniny se dělí nějakým modulem M, přičemž dostáváme zbytky, které (za určitých předpokladů) tvoří posloupnost pseudonáhodných čísel.