Čtvrtá série devátého ročníku KSP

Vzorová řešení


9-4-1 Cor Sair strikes back (Zadání)


Začneme úvahami o nutném počtu vážení: Určitě potřebujeme aspoň 3 vážení (protože ve 2 váženích může nastat pouze 9 různých výsledků a koulí je 12). 3 vážení nám ovšem stačí (dokážeme příkladem).

Nejprve si označíme balíky písmenky. (Můžeme použít 12 státních agentů, každý si bude pamatovat jeden balík a písmeno k němu přiřazené, nebo je nahradíme propisovací tužkou a napíšeme číslo přímo na balík – ale pozor na Agentskou odborovou organizaci.) [Michal Šída]

Tučnými písmeny budeme označovat balíky, o kterých víme, že mohou být normální nebo těžší (zbyla-li jediná taková, je jistě těžší), kurzívou pak normální či lehčí, monospacem zaručeně normální balíky a latinkou pak balíky dosud zahalené tajemstvím.

Při prvním vážení použijeme abcd – efgh [ijkl] (levá miska – pravá miska [zbytek]). V případě, že je levá miska těžší, víme, že situace vypadá takto: abcdefghijkl, pro pravou těžší analogicky abcdefghijkl, pro obě stejné abcdefghijkl.

Nyní pro první (analogicky i pro druhý) případ: vážíme aefbgh [cdijkl]. Levá miska těžší dostaneme abcdefghijkl, pravá těžší abcdefghijkl, obě stejné abcdefghijkl.

A pro případ třetí: vážíme ij – ak [bcdefghl]. Levá těžší abcdefghijkl, pravá abcdefghijkl, obě stejné abcdefghijkl.

Všechny zbývající situace jsou vždy typu abc, abc či ab, případně a, které je všechny možno triviálně rozhodnout jediným vážením (v posledním případě doplníme na druhou misku zaručeně normální kouli). Tudíž třetím vážením se vždy dozvíme, který balík je jiný a dokonce i jak je jiný.

Pokud jste dodrželi postup a nevyskytly se určité nevhodné okolnosti (např. váhy všechny zásilky proměnily v dýně, nebo vysoká hustota tajných agentů květinářské společnosti Brambořík Ibišek Slunečnice), tak jste provedli zakázku za použití 3 vážení, takže si toho všimlo minimální množství lidí (jen cca 99.99%) a vy jste se stal nejslavnějším a nejbohatším važičem všech dob a žil jste šťastně až do smrti. (Což bylo ostatně asi 2 dny, protože tajná služba nerada nechává informace o své samozřejmě legální činnosti.) [opět Michal Šída]

Martin Mareš & Pavel Machek


9-4-2 Green Bit Problem (Zadání)


Ve světle vzorového řešení předchozí ufounské úlohy (9-2-3 – Překla-datel) jest ten pravý trik na "rozlousknutí" tohoto problému téměř zřejmý: opět budeme něco řešit pro postupně se zvětšující skupiny velikosti 2i.

Konkrétně se budeme snažit pro všechny části velikosti 2i vždy spočíst, kolik je ve které části jedničkových bitů, známe-li to již pro obě její poloviny a budeme podle zneužívat toho, že počet jedniček v k-bitovém čísle se vždy do k-bitového čísla vejde (jelikož k < 2k pro každé k>1, kteroužto úvahu mnozí z vás opomněli učiniti).

Pro dvojbitové skupiny to lze provést triviálně a dokonce pro všechny najednou: stačí si označit a původní číslo, v němž jsou na lichých místech samé nuly a na sudých místech původní číslice, b číslo, v němž jsou na lichých místech opět nuly a na sudých místech číslice z oněch lichých míst a pak tato dvě čísla sečíst. Jelikož 2 < 22, k přenosu mezi jednotlivými 2-bitovými skupinami nedojde a dostaneme přesně to, co jsme chtěli.

Nyní již máme 128-bitové číslo z rozdělené na 27-k skupin velikosti 2k, každá z nich již obsahuje počet bitů na počátku v této skupině se nacházejících. Opět zavedeme a obsahující jen skupiny na sudých místech a b původní skupiny z lichých míst přesunuté na sudá místa. A a+b je rozděleno na 26-k skupin velikosti 2k+1. Takto pokračujeme tak dlouho, až získáme jednu skupinu velikosti 27=128, což je hledaný výsledek.

Program bude vypadat takto (ij značí zopakovat j-kráte posloupnost číslic i):

a ←x > 1a ←a & (01)64b ←x & (01)64y ←a+b
a ←y > 2a ←a & (0212)32b ←y & (0212)32y ←a+b
a ←y > 4a ←a & (0414)16b ←y & (0414)16y ←a+b
a ←y > 8a ←a & (0818)8b ←y & (0818)8y ←a+b
a ←y > 16a ←a & (016116)4b ←y & (016116)4y ←a+b
a ←y > 32a ←a & (032132)2b ←y & (032132)2y ←a+b
a ←y > 64b ←y & 064164y ←a+b.

Získáváme tak řešení v 27 krocích…

Martin Mareš


9-4-3 Hellish Clocks (Zadání)


Označme si pi původní nastavení i-tých hodin, ri jejich požadované nové nastavení, aij posunutí i-tých hodin při zmáčknutí j-tého tlačítka a xj počet zmáčknutí j-tého tlačítka.

Posunutí stejných hodin po zmáčknutí různých tlačítek se sčítají a protože je sčítání komutativní, nezáleží na pořadí stisků jednotlivých tlačítek, ale pouze na jejich počtu. Bude platit následující soustava rovnic (je to pouhé rozepsání pohybu hodin):

(a11x1 +a12x2 +… +a1nxn +p1 -r1) mod 37 =0
(a21x1 +a22x2 +… +a2nxn +p2 -r2) mod 37 =0
. . . . . .
. . . . . .
. . . . . .
(an1x1 +an2x2 +… +annxn +pn -rn) mod 37 =0

aneb pokud operace `+', `-' a `*' budeme provádět modulo 37, můžeme soustavu napsat v maticovém tvaru:

a11 a12 a1n
a21 a22 a2n
. . .
. . .
. . .
an1 an2 ann
·
x1
x2
.
.
.
xn
r1-p1
r2-p2
.
.
.
rn-pn

Mnozí z vás vědí, že podobnou soustavu lze v reálných (resp. racionálních) číslech řešit Gaussovou eliminační metodou. Málokdo si však uvědomil, že tato metoda nepožaduje práci přímo s reálnými (resp. racionálními) čísly. Pro zdárný průběh tohoto algoritmu je nutno, aby daný číselný obor byl tělesem, tj. aby splňoval některá základní pravidla (komutativita, asociativita, distributivita, jednotkový a nulový prvek) a aby ke každému nenulovému číslu existovalo číslo inversní.

Lze snadno ukázat, že množina Zp zbytkových tříd po dělení prvočíslem p je tělesem. Základní vlastnosti, jako je např. komutativita, lze dokázat snadno, takže jediným problémem je existence inversního prvku. Jak již bylo v některé z předchozích sérií KSP ukázáno, plyne z Malé Fermatovy věty, že jsou-li čísla a a p nesoudělná, pak ap-1≡ 1 mod p, tedy a·ap-2≡ 1 mod 37. Poněvadž a může být pouze z množiny {0,1,2,…,p-1}, je nenulové a vždy s p nesoudělné. Pro každé nenulové a tedy můžeme nadefinovat a-1=ap-2 mod p.

Závěr je ten, že můžeme Gaussovu eliminační metodu použít stejným způsobem, jako kdybychom pracovali např. s racionálními čísly. Pouze musíme zaměnit původní aritmetické operace za nové.

Gaussova eliminační metoda se snaží upravit matici na trojúhelníkový tvar, tj. tvar, ve kterém jsou všechny koeficienty pod hlavní diagonálou nulové. Toho dosáhne řádkovými úpravami matice (násobení rovnic nenulovým číslem, výměna rovnic, sečtení rovnic). Snadno ověříme, že tyto úpravy nemění prostor všech řešení této soustavy.

Popišme po krocích tento důležitý algoritmus:

  1. Provedeme druhý krok postupně pro všechny sloupce i=1,2,…,n.
  2. Nyní jsou sloupce 1,2,…,i-1 v požadovaném tvaru, cheme upravit také i-tý sloupec.
    1. Je-li aii≠ 0, pak můžeme tuto rovnici podělit aii. Dále pro všechna j=i+1,i+2,…,n odečteme aji násobek této rovnice od j. rovnice. Tím vynulujeme všechna čísla v sloupci pod aii.
    2. Pokud je aii=0, zkusíme nalézt takové j∈{i+1,i+2,…,n}, že aji≠ 0. Pokud takové j existuje, můžeme prohodit i. a j. rovnici, bude splněna podmínka nenulovosti a můžeme postupovat podle bodu (a).
    3. Pokud žádné takové j nenalezneme, je celý sloupec včetne aii nulový. Pak žádné úpravy dělat nebudeme a skočíme rovnou na další sloupec. Při zpětném dosazování mohou nastanou dvě možnosti:
      • vyjde nám rovnice typu 0x=0, pak je řešením jakékoliv x, např. x=0 (ať nemusejí čerti zbytečně mačkat tlačítka),
      • nebo nám vyjde 0x=1, pak nemá soustava rovnic řešení.
  3. Soustava je v diagonálním tvaru, tedy v poslední rovnici se vyskytne maximálně jedna neznámá, v předposlední dvě… Rovnice budeme odzadu řešit. Pokud bude existovat více řešení, zvolíme např. nulu, pokud nebude existovat žádné, ohlásíme, že řešení neexistuje.

Program je přímou implementací uvedeného algoritmu. Jsou k němu připojeny komentáře, takže jeho pochopení by nemělo činit potíže. Nezbývá než ještě poznamenat, že tabulka inversních čísel je předpočítaná, aby se urychlil výpočet.

Program

Robert Špalek


9-4-4 Whatsit? (Zadání)


Cílem této úlohy bylo, abyste zjistili nejenom co onen záhadný program dělá, ale také proč to vlastně dělá. Řešení bez důkazu tedy nebyla odměněna příliš štědře. Rovněž pak důkaz typu "zkoušel jsem to pro 10000 hodnot a fungovalo to" nemá žádnou váhu (to, že program funguje pro N různých vstupů, ještě nevypovídá příliš o tom, co dělá pro ty ostatní, leda že by již žádné ostatní neexistovaly [ale v tomto příkladu bylo ≈ 109 možností, takže probrání všech v rozumném čase nehrozilo]).

A co že vlastně program dělal? Inu, byl to interpreter jednoduchého programovacího jazyka. Text interpretovaného programu byl uložen v řetězci s, jazyk pracoval se sedmiprvkovým polem, jehož prvky si označíme k0k6. Prvek k0 ukazoval do pole s na právě prováděný příkaz (pokud "vyjel" pryč, program se zastavil), k1 fungoval jako "data pointer" (označíme si jej δ) – tedy obsahoval číslo prvku ki, se kterým se prováděly některé operace a k2 sloužil k uchování cílové adresy skoku. Jazyk se skládal z následujících příkazů:

< Posunutí k1 o jedno pole doleva s případným podtečením (0 →6).
> Posunutí k1 o dvě pole doprava s případným přetečením (5→0, 6→1).
# Není-li kδ nulové, skok dle k2 (ve skutečnosti o jednu pozici dále než kam k2 ukazuje, protože ještě přeskakujeme na následující instrukci!).
$ Uložení k0 do k2 – tedy uchování aktuální pozice v programu
- Snížení hodnoty kδ o 1.
+ Zvýšení hodnoty kδ o 1.
! kδ←δ.
* (cokoliv jiného) δ←2·δ.

Vstupy programu byly uloženy v k3 a k4, program začínal na pozici k0=1, δ=k1 bylo inicializováno na 1 a k2 na 2. Výsledek byl předán v k6. Zbylý "registr" k5 sloužil jako pomocná proměnná.

Interpretovaný program vypadal takto (po přepsání neznámých znaků na hvězdičky a očíslování pozic):

1 > 11 * 21 # 31 - 41 - 51 +
2 < 12 # 22 < 32 > 42 < 52 *
3 + 13 > 23 * 33 + 43 + 53 >
4 * 14 > 24 * 34 < 44 > 54 <
5 > 15 + 25 * 35 + 45 < 55 >
6 > 16 + 26 # 36 < 46 # 56 +
7 * 17 + 27 - 37 # 47 > 57 #
8 # 18 * 28 > 38 > 48 > 58 *
9 < 19 > 29 < 39 < 49 ! 59 -
10 $ 20 < 30 $ 40 $ 50 * 60 *

A provádí toto:

1–4 δ=2, k2=6
5–6 δ=6
7–8 k6 ←2·k6, opakuj dokud k6 ≠ 0 (vše je typu word, pročež
všechny operace fungují modulo 65536, a tak k nule dojít musíme)
9–10 δ=5, k2=10
11–12 Prakticky stejným způsobem nulujeme k5.
13–18 δ=2, k2=26
19–21 δ=3 a pokud k3 ≠ 0, skáčeme na pozici 27.
22–26 δ=2, k2=208, zastavujeme se (skok mimo).
27 k3 ←k3 - 1
28–30 δ=4, k2=30
31 k4 ←k4 - 1
32–33 δ=6, k6 ←k6 + 1
34–35 δ=5, k5 ←k5 + 1
36–37 δ=4, pokud k4 ≠ 0, skáčeme na 31. Tímto jednoduchým cyklem přesouváme
původní hodnotu k4 do k5 a současně ji přičítáme ke k6, načež zbyde k4=0.
38–40 δ=5, k2=40
41 k5 ←k5 - 1
42–43 δ=4, k4 ←k4 + 1
44–46 δ=5 a pokud k5 ≠ 0, skáčeme na pozici 41. I hle, prohodili jsme k4 a k5!
47–49 k2=δ=2
50–52 k2 = 10
53–57 δ=5, k5=1, skáčeme (nepodmíněně) na pozici 11 (všimněte si,
že proměnné δ i k2 jsou nastaveny stejně jako když jsme se tam
dostaly minule – vše tedy bude probíhat stejně).
58–60 Sem se nikdy nedostaneme…

Povšimněte si nyní, že program se skládá ze dvou částí: inicializace (příkazy 1–10, vlastně jen k6←0) a velký cyklus (11–57) prováděný k3-krát a v každém průchodu přičítající k4 ke k6. Na konci vracíme k6 jako výstup programu… Vypadá to jako násobení dvou přirozených čísel, tváří se to jako násobení dvou přirozených čísel a nenechte se mýlit – je to násobení dvou přirozených čísel! Záhada jest rozřešena (zejména uvědomíme-li si, že pokud k4=0, provádíme vnitřní cyklus 65536-krát, takže tak jako tak nula po dlouhém počítání díky přetečení vyjde) a program můžeme triviálně zjednodušit na:

function thatsit(a,b:word):word;
begin
   thatsit := a*b;
end;

Jak prosté, milý Watsone!

Martin Mareš


9-4-5 Something rotten? (Zadání)


Jak už to tak v našem semináři poslední dobou bohužel bývá (slibujeme, že se polepšíme!!), zadání této úlohy nebylo jednoznačné. Respektive ono možná jednoznačné bylo, ale odporovalo uvedenému příkladu. A po právu. Formulace zadání odpovídalo úloze, že si silničáři v království vyberou, které cesty nechají rozpadnout a tyto cesty se posléze rozpadnou. My máme silničářům sdělit, kolik cest mohou vybrat.

Vyřešit takovou úložku je veskrze triviální, neboť k tomu, aby města zůstala navzájem dosažitelná, postačuje kostra grafu silnic, která má vždy N-1 silnic. Pokud tedy má zůstat království souvislé, stačí nám udržovat N-1 vybraných cest a zbytek cest se může rozpadnout. Každý vidí, že spočítat počet cest a odečíst od toho N-1 si nezaslouží v zadání nabízených 12 bodů.

Tedy dvě okolnosti nasvědčovaly tomu, že zadání chce říci něco jiného, než říká. Zadání totiž chtělo říci, že silničáři nemají ve své kompetenci určit, které cesty se rozpadnou. Tamější silničáři totiž fungují tak, že implicitně nedělají nic. Když jim však ze všech koutů království přicházejí zprávy, že se dohromady rozpadá již x silnic, potřebují vědět, jestli je to stále ještě O.K., nebo jestli už náhodou nehrozí to, že se království rozpadne na dvě a více částí a měli by začít něco dělat. Jelikož poddaní neznají (případně když už znají, tak cesou alespoň zkomolí) názvy měst, hlásí silničářům pouze počty rozpadlých silnic.

Vaším úkolem tedy bylo na základě mapy silnic zjistit, kdy musejí silničáři začít pracovat, tedy maximální počet cest, které se mohou rozpadnout, aniž by to ohrozilo celistvost království. Této úložce se v terminologii teorie grafů říká hledání minimálního řezu v grafu, resp. v našem případě postačuje nalezení jeho velikosti. Co je to minimální řez? Řez v grafu je množina hran, které když se vypustí, tak se graf rozpadne. Minimální řez je pak samozřejmě řez, který je nejmenší ze všech možných řezů grafu. Silničáři tedy musí pracovat tehdy, pokud se počet rozpadlých silnic značně přiblížil velikosti minimálního řezu v jejich systému silnic.

Úloha hledání řezů v grafu souvisí s jinou zajímavou grafovou úložkou, s takzvanými toky v sítích. Síť není opět nic jiného než graf, avšak jelikož úloha má svůj předobraz v inženýrských sítích – potrubních a elektrických rozvodech – zkoumanému grafu se přezdívá síť. Tok v síti je pak prostě nějaké konkrétní rozložení proudu, ať již elektrického, nebo vody, na jednotlivé spojnice (hrany) sítě. Předpokládá se, že v jednom místě v síti je takzvaný zdroj, ze kterého to teče, a dále je tam jeden spotřebič, do kterého vše teče a jinde v síti již žádný proud nevzniká ani nezaniká, tj. to co do ostatních uzlů vstoupí, to z nich i vystoupí. [MJ: Zlí jazykové tvrdí, že to není připad vodovodních ani elektrovodných sítí, protože tam se vše ztrácí všude…]

Evidentně spotřebič odebírá právě to, co zdroj vypouští. Když na rozložení proudu dáme omezení, že po každé spojnici může protékat buď jednotkový objem libovolným směrem, nebo nic, pak maximální objem proudu vypouštěný zdrojem nám říká, kolik je maximální počet hranově nezávislých cest mezi zdrojem a spotřebičem. To odpovídá velikosti minimálního řezu oddělujícího spotřebič od zdroje. Toto tvrzení zde ponecháme bez důkazu a odkážeme laskavého čtenáře na knihu L. Kučery "Kombinatorické algoritmy". Když takto pro všechny možné spotřebiče a zdroje prozkoumáme minimální řezy, které je oddělují, nalezneme hledaný minimální řez.

Všimněte si, že můžeme zafixovat jeden konkrétní zdroj a prozkoumat jen všechny možné spotřebiče. To vyplývá z toho, že pokud se nějakým řezem graf rozpadne, speciálně tedy minimálním, pak námi vybraný zdroj zůstane v jedné z částí grafu a libovolný spotřebič z druhé části grafu nemůže odebírat více než je velikost použitého minimálního řezu. Zároveň vůči jednomu ze spotřebičů bude pro přepravu použita maximální zátěž minimálního řezu, tj. všechny jeho hrany. (Rozmyslete si správnost těchto tvrzení.)

Jak tedy zjistit velikost maximálního toku mezi daným zdrojem a spotřebičem? Tuto úložku vyřešíme tak, že budeme tok postupně zlepšovat. Na začátku řekněme, že nikde nic neteče. Poté se pokusíme nalézt takovou cestu od zdroje ke spotřebiči, že po jednotlivých hranách této cesty buď nic neteče, nebo po nich něco teče, avšak v opačném směru, tj. ve směru od spotřebiče ke zdroji. Pomocí této cesty můžeme zlepšit tok tak, že po jejích hranách, po kterých nic neteklo, necháme téci jednotkový objem směrem ke spotřebiči a po hranách, po kterých teklo něco směrem od spotřebiče, nebude téci nic. Snadno nahlédneme, že takto zlepšený tok bude korektní, tedy v dotčených uzlech bude i nadále platit to, že co do nich vstupuje, to z nich i vystupuje, a opačně. Pozorný čtenář již jistě vytušil, že takovéto zlepšení provedeme maximálně N-1-krát.

Zbývá doplnit, jak nalézt zlepšující cestu. Zlepšující cestu budeme hledat průchodem grafu do šířky a to tak, že budeme používat pouze zlepšující cesty, tj. budeme chodit pouze po hranách, kde nic neteče, nebo kde jdeme proti proudu. Takto budeme nalézat vrcholy, do kterých vede zlepšující cesta. Pokud již víme, že do daného vrcholu zlepšující cesta vede, tak ho již znovu procházet nebudeme, neboť nám postačuje nalezení nějaké zlepšující cesty. Hledání skončí tehdy, když nalezneme zlepšující cestu až ke spotřebiči, nebo tehdy, když už z žádného dosaženého vrcholu nelze jít po nevyužité hraně, či proti proudu. Jelikož při tomto průchodu musíme v nejhorším případě probrat téměř všechny hrany, je časová složitost této fáze O(M), kde M je počet hran. (Předpokládáme, že M>N).

Celková časová složitost pak dosáhne O(N2M), neboť pro N spotřebičů budeme vyhledávat maximální tok, což znamená maximálně N-krát nalézt zlepšující cestu v čase O(M). Jelikož počet hran M<N2, lze též použít hrubší odhah O(N4). Paměťová složitost je O(M), neboť si musíme pamatovat aktuální tok a popis grafu.

Zbývá snad jen dodat, že pro hledání minimálního řezu existuje i algoritmus pracující v čase O(N3) a taktéž pravděpodobnostní algoritmus, jenž řešení nalezne v průměrném čase O(N2 log2 N). Pravděpodobnostní algoritmus je algoritmus, který si v průběhu výpočtu může házet kostkou. Některá tvrzení jsme zde ponechali bez důkazu (např. správnost algoritmu hledání maximálního toku), neboť rozsahem přesahují možnosti tohoto řešení. Zvídavé čtenáře tedy odkazujeme již zmíněnou knihu od Dr. Kučery, kde ke všem zde uvedeným tvrzením a algoritmům nalezne důkaz jejich správnosti. Vzorový program je pro jednoduchost napsán s časovou složitostí O(N4), neboť z hlediska počtu hran nemá optimálně napsané vyhledávání minimálního toku.

Program

Michal Koucký


9-4-6 Top secret (Zadání)


Opravdu náhodná čísla není možné generovat "čistým" algoritmem. Každý takový algoritmus má podle definice předem předvídatelné chování, a tedy jím vygenerovaná čísla není možné považovat za opravdu náhodná, protože jsou efektivně vyčíslitelná. (Je možné sestrojit algoritmus, který bude generovat posloupnost "náhodných" čísel, která se nikdy nezačne opakovat, např. číslice čísla π. Ani takovou posloupnost ale není možné považovat za posloupnost opravdu náhodných čísel.) [Pozn. MJ: Nikdo ovšem dosud nedokázal, že něco jako náhodná čísla vůbec může existovat – pokud je vesmír deterministický, náhodná čísla neexistují, ale nepředvídatelná čísla stále ještě ano – zkuste se nad tím zamyslet.]

Musíme se tedy vzít na pomoc něco z reálného světa. Budeme se zde zabývat pouze metodami, které jsou vhodné pro spojení s počítačem. (Vynecháme obligátní házení kostkou, losování předmětů, atp.)

Všechny následující metody jsou založeny na tom, že měří náhodnou složku nějakého jevu.

Jednoduše realizovatelné je měřit s velkou přesností, co člověk považuje za chvíli, a za náhodné číslo prohlásit zbytek po dělení této hodnoty malým číslem:

uses Crt;

function Random256: Byte;
{ Generuje náhodné číslo v rozsahu 0..255 }
 label start;
 var x: longint;
 begin
start:
 writeln('Za chvíli stiskni klávesu.');
 x := 0; while not keypressed do inc(x);
 while keypressed do readkey;
 if x < 100000 then begin
  writeln('Tohle není žádný rychlokurs!');
  goto start;
  end;
 Random256 := Byte(x); {rychlejší `x mod 256'}
end;

Modifikace tohoto postupu je použita ve velmi rozšířeném programu Pretty Good Privacy (PGP). Pro masové použití např. v bankách je ovšem tento postup nevhodný.

Brownův pohyb, rozpad radioaktivního materiálu a další (prozatím) náhodné fyzikální jevy, jsou v praxi těžko použitelné, jelikož k jejich automatickému měření je třeba drahé zařízení.

Nejsnáze realizovatelné je měření šumu nějaké elektrické veličiny:

  • šum éteru – měří se s velkou přesností proud, který teče z antény.
  • šum sítě – měří se s velkou přesností napětí v zásuvce.
  • šum polovodičového přechodu (Snem většiny konstruktérů diod je vyrobit takovou, která vůbec nešumí. Existuje ale také malá, nicméně dobře placená, skupina konstruktérů diod, jejíž snem je vyrobit diodu, která šumí co nejlépe.)

Je možné, že za pár let bude pro podporu šifrování standardní součástí PC obvod pro generování náhodných čísel. Zatím se vyrábějí pouze specializované desky.

Jan Kotas