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

Zadání úloh

9-4-1 Cor Sair strikes back (12 bodů)

Poté, co pirát ve výslužbě Cor Sair zdárně vyřešil svá trable s hamižným hokynářem Mer Chantem (viz úloha 9-1-2), stal se v širém okolí uznávaným odborníkem přes vážení břemen a třídění předmětů. Jednoho dne však dostal od královské výzvědné služby následující tajné poslání:

Agenti zadrželi na poště 12 značně těžkých balíků adresovaných do sousední ne tak docela spřátelené země a od zpravodajské kanceláře JPP (Jedna Paní Povídala) se dozvěděli, že jeden z těchto balíků by měl obsahovat tajné dokumenty ukradené ministerstvu deratizace. Jelikož všechny balíky vypadaly stejně, agenti záhy přišli na to, jak inkriminovanou zásilku odhalit – měla by se lišit hmotností! Netušili však, je-li lehčí nebo těžší a nechtěli mnoha váženími vzbudit přílišnou pozornost okolí (my i vy jistě tušíte, že ji vzbudí nehledě na počet vážení, ale pochopte, že oni to nevědí), a proto Cor Sair ovi zadali, ať vymyslí, jak co nejmenším počtem vážení na rovnoramenných vahách onen balík objeviti a ještě zjistiti, zda je lehčí neb težší.

Po vás pro tentokráte nechceme, abyste psali jakýkoliv program, pouze zkuste popsat postup (tedy vlastně algoritmus), jak tento problém vyrešit.

Řešení

9-4-2 Green Bit Problem (10 bodů)

Jak již bylo zmíněno v předminulé sérii, na Zemi se začali vyskytovat Ufouni, malá to zelená stvoření obývající zapomenuté kouty Vesmíru a my již umíme vyměňovat si s nimi informace prostřednictvím 128-bitových binárních čísel – v úloze 9-2-3 jste vyřešili, jak taková čísla převádět do nám čitelného tvaru (to jest jak je zrcadlově převracet).

Při komunikaci s Ufouny se ovšem objevil ještě jeden zajímavý problém: jak u takového dlouhého čísla rychle zjisit, kolik je v něm jedničkových bitů. Pro tento účel se opět používá překládacího stroje, jenž jest programován ve velice jednoduchém programovacím jazyce, který disponuje stovkou 128-bitových proměnných a jedním jediným příkazem: přiřazením typu a = b °c, kde a je proměnná, b a c jsou proměnné nebo konstanty a ° je jedna z operací + (sčítání), - (odčítání), * (násobení), / (dělení), & (bitový logický součin), | (bitový logický součet), < (bitový posun b doleva o c bitů) a > (bitový posun b doprava o c bitů). Vstup dostanete v proměnné x, výstup budiž na konci výpočtu uložen v proměnné y.

Řešení

9-4-3 Hellish Clocks (13 bodů)

V jednom pekle měli svérázný systém měření času: v každém z N pater pekla byly jedny hodiny ukazující na svém ciferníku čas v pekelných hodinách (těch bylo každý den 37). Jelikož mnohé z hodin se opožďovaly, předcházely, občas zastavovaly či dělaly jiné nepředloženosti, pořídili si čerti centrální ovládání – od každých hodin vedly dráty k řídícímu pultu v Luciferově kanceláři, na němž bylo N tlačítek, jimiž mělo jít posunout ručičku daných hodin na nejbližší další pekelnou hodinu.

Jenže jak už to v pekle bývá, i tento systém měl nějaký háček: každé tlačítko totiž neposouvalo jenom jedny hodiny a jenom jednu hodinu, ale ručičky na hned několika cifernících o různé počty hodin. Nakonec se přeci jen podařilo zjistit, jak které tlačítko funguje.

Vaším úkolem je napsat program, kterému čerti zadají, o kolik hodin posune které tlačítko kupředu ručičky na kterém ciferníku, kolik které hodiny zrovna ukazují a na jaký čas si je přejí nastavit (pro všechny ciferníky stejný) a program odpoví, kolikrát zmáčknout které tlačítko (na pořadí mačkání evidentně nezáleží), aby bylo dané konfigurace dosaženo, případně sdělí, že to nejde.

Řešení

9-4-4 Whatsit? (10 bodů)

Zkuste přijít na to, k čemu je (mimo zmatení řešitelů, samozřejmě) určena následující pascalská funkce a jak by se dala naprogramovat efektivněji:

function whatsit(a,b:word):word;
const s:string='><+*>>*#<$*#>>+++*><#<:=]'
 + '#-><$->+<+<#><$-<+><#>>!*+*><>+#:-)';
var k:array [0..6] of word;
begin
   k[0]:=1; k[1]:=1; k[2]:=2;
   k[3]:=a; k[4]:=b;
   while chr(k[0])<=s[0] do begin
   case s[k[0]] of
      '<': k[1]:=(k[1]+6) mod 7;
      '>': k[1]:=(k[1]+2) mod 7;
      '#': if k[k[1]]<>0 then k[0]:=k[2];
      '$': k[2]:=k[0];
      '-': dec(k[k[1]]);
      '+': inc(k[k[1]]);
      '!': k[k[1]]:=k[1];
      else inc(k[k[1]],k[k[1]]);
      end;
   inc(k[0]);
   end;
whatsit:=k[6];
end;

Řešení

9-4-5 Something rotten? (12 bodů)

Váš program z minulé série na hledání kritických silnic si královští úředníci velmi oblíbili a nyní vás žádají o vyřešení podobného problému: potřebují zjistit, kolik silnic se jim může rozpadnout, aniž by se království rozdělilo na dvě části.

Tedy: vstupem programu je počet měst N (města jsou očíslována 0, …, N-1) následovaný dvojicemi čísel reprezentujících obousměrné silnice. Seznam je ukončen dvojicí (0,0), což je okruh kolem královského paláce. Výstupem je počet silnic, které se mohou rozpadnout aniž by se silniční síť rozdělila na dvě části.

Příklad: 5 (0,1) (0,2) (0,3) (1,2) (2,3) (1,4) (2,4) (3,4) (0,0). Výstup: 2.

Řešení

9-4-6 Top secret (10 bodů)

Minule jsme vám slíbili, že tato úloha bude o generování náhodných velkých prvočísel. A opravdu vás nezklameme. Taková prvočísla se generují většinou tak, že se najde velké náhodné číslo a pak se testuje na prvočíselnost. Pokud se jedná o číslo složené, test na prvočíselnost opakujeme s číslem o jedničku větším (pokud nemáme opravdu dokonalý generátor náhodných čísel, není vhodné generovat nové náhodné číslo, ježto pak není zaručena konečnost algoritmu).

Ale jak testovat u velkých čísel prvočíselnost? Klasický algoritmus – pokusné dělení čísly od 2 od √n – je nepoužitelný, jelikož bychom se výsledku nedočkali. Nejčastěji se používá pravděpodobnostní algoritmus založený na následujícím tvrzení, které je rozšířením malé Fermatovy věty:

(i) Jestliže pro nějaké 0 < a < n platí

an-1 mod n ≠ 1,

je n číslo složené. A obráceně:

(ii) Jestliže pro nějaké 0 < a < n platí

an-1 mod n = 1,

je n prvočíslo s pravděpodobností větší než 0.5.

V praxi se ukazuje, že tato pravděpodobnost je daleko větší než 0.5 a že pro náhodná a jsou pravděpodobnosti rozumně nezávislé.

Návod na testování prvočíselnosti čísla n:

  1. Vyloučíme triviální případy: provedeme pokusné dělení n prvočísly od 2 do (třeba) 1000. Pokud je n některým z nich dělitelné, je již vše jasné.
  2. Vygenerujeme náhodné číslo 0<a<n a vypočteme an-1 mod n. Pokud vyjde něco jiného než 1, je n jasně složené a končíme.
  3. Bod 2. několikrát (třeba 20-krát) zopakujeme, abychom zvýšili pravděpodobnost správnosti výsledku.
  4. Prohlásíme, že číslo n je asi prvočíslo.

Z teoretického hlediska by se mohlo zdát, že generování prvočísel pouze s nějakou praděpodobností je nepoužitelné. Ve vesmíru a životě je ale málokdy něco na 100%. Když počítače, na kterých výpočty provádíme, mají pravděpodobnost chyby 10-4, můžeme jásat nad prvočísly s pravděpodobností chyby 10-10.

Úloha: Běžné funkce pro generování náhodných čísel generují pouze čísla pseudonáhodná: posloupnost "náhodných" čísel se začne po čase opakovat. Zdůvodněte, proč je tento fakt při generování klíčů pro RSA nepříjemný, a zkuste vymyslet, jak generovat opravdu náhodná čísla. Při řešení tohoto problému se nemusíte omezovat na čistě programátorské postupy. Provedení praktických experimentů a použití znalostí z jiných oborů (např. fyziky nebo chemie) oceníme zvláštní prémií.

Popsaný algoritmus ovšem není zcela korektní – negeneruje totiž všechna prvočísla se stejnou pravděpodobností. Zkuste se zamyslet nad tím, proč a jak by se tento problém dal odstranit. Můžete nám také napsat svůj názor na tento miniseriál o moderním šifrování.

Řešení