Třetí série devátého ročníku KSP

Zadání úloh

9-3-1 Odporné odpory p. Odporného (10 bodů)

Žil byl jednou jeden elektrikář, který se jmenoval pan Odporný. Náplní jeho práce bylo skládat odpory. Lidé si na něj ale často stěžovali, jelikož chtěli-li po něm poskládat z dostupných rezistorů rezistor o daném odporu, museli odporně dlouho čekat, protože panu Odpornému šlo skládání velice pomalu, a dokonce občas pan Odporný odpověděl, že úkol splnitelný není, což mu nevěřili.

Vaším úkolem je panu Odpornému pomoci a vymyslet algoritmus a napsat program, který bude daný problém řešit: to jest pro daný seznam hodnot odporů dostupných rezistorů a daný výsledný odpor buďto příslušnou kombinaci nalezne nebo odpoví, že taková neexistuje. Všechny odpory jsou zadávány v Ohmech. Pokud existuje více řešení, nalezněte to, v němž se použije nejmenší počet rezistorů.

Již dostupné (ať již přímo nebo složením jiných) rezistory je možno spojovat buďto sériově (to jest za sebe – jako na prvním obrázku) nebo paralelně (vedle sebe – na druhém obrázku). Odpor výsledné kombinace je pro sériové zapojení součtem jednotlivých dílčích odporů, pro paralelní je převrácenou hodnotou součtu jejich převrácených hodnot. Jiná zapojení nejsou přípustná.

Příklad 1: Jsou k dispozici 2 rezistory o odporech 10 Ω a 20 Ω, požadovaný odpor je 5 Ω. Výsledek: Nelze sestavit.

Příklad 2: Jsou k dispozici rezistory o odporech

(1 Ω, 1 Ω, 1 Ω, 1 Ω, 50 Ω),

požadovaný odpor je 50.25 Ω. Je možno použít například kombinaci (1x1x1x1)+50 (`x' značí paralelní zapojení, `+' sériové).

Řešení

9-3-2 Cosi prohnilého? (12 bodů)

V jednom nejmenovaném království zjistili královští rádcové, že existují silnice, které když se rozpadnou, silniční síť (a tím pádem i celé království) se rozdělí na dvě části. To se královi nelíbilo a uložil jim, aby kázali přednostně udržovat tyto kritické silnice. Nyní ovšem potřebují vědět, které to jsou a vás najali, abyste vyrobili program, jenž je najde.

Vstupem programu je počet měst N (města jsou očíslovaná 0, … , N-1) následovaný dvojicemi čísel, které reprezentují silnice (silnice jsou obousměrné). Seznam je ukončen dvojicí (0,0), což je okruh kolem královského paláce. Výstupem je seznam kritických silnic.

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

Řešení

9-3-3 Mikroassembler (12 bodů)

Firma Sirius Cybernetics uvedla s ohromnou reklamou na trh počítač μ1 s údajně nejjednodušší možnou instrukční sadou. Samozřejmě to (jak již tomu u reklamních sloganů bývá) není pravda. Na vás je, abyste našli přebytečnou instrukci (to jest takovou, že každý program tuto instrukci obsahující je možno přepsat na program, který dělá totéž a tuto instrukci nepoužívá) a popsali, jak ji lze nahradit. Pokud existuje takových instrukcí více, nalezněte všechny a zkuste dokázat, že ty ostatní jsou již vskutku nutné. A nyní již k tomu, jak onen počítač funguje:

μ1 má paměť složenou z jednotlivých paměťových buněk očíslovaných přirozenými čísly, přičemž v každé buňce je uloženo opět libovolné přirozené číslo. Na počátku běhu programu jsou na smluvených místech v paměti uložena vstupní data (ostatní buňky obsahují nedefinované hodnoty), na konci výpočtu pak na jiných místech uloženy výsledky. K dispozici jsou následující instrukce:

Program začíná běh svojí první instrukcí a končí při pokusu o skok před tuto instrukci. Na ukázku uveďme například program pro sečtení čísel na adresách 1 a 2, přičemž výsledek uloží na adresu 0.

         CLR    3
         CLR    0
         JEQ    1,3,4
         DEC    1
         INC    0
         JEQ    3,3,-3
         JEQ    2,3,-7
         DEC    2
         INC    0
         JEQ    3,3,-3

Řešení

9-3-4 Komplikátor (11 bodů)

Jistě vás při čtení předchozí úlohy napadlo, že možnosti popisovaného assembleru μ1 jsou naprosto minimální. Kupodivu to není tak docela pravda: jde v něm naprogramovat prakticky cokoliv, co jde zapsat v Pascalu. Jelikož by ale bylo přeci jen příliš pracné vytvořit překladač z Pascalu do tohoto assembleru, zkuste napsat program, který do tohoto assembleru překládá alespoň běžné celočíselné aritmetické výrazy obsahující:

Vstupem vašeho programu by měl být výraz v textovém tvaru, výstupem pak program pro μ1 vyčíslující tento výraz, přičemž hodnoty proměnných budou zadány na adresách 1 (a) až 26 (z) a hodnota výrazu bude po skončení výpočtu uložena na adrese 0. Například ukázkový program od předchozí úlohy je jednou ze správných odpovědí pro výraz a+b.

Řešení

9-3-5 Top secret (10 bodů)

Dnešní úloha se bude zabývat volbou vhodných klíčů pro šifrovací algoritmus RSA uvedený v minulé sérii.

Náhodně zvolíme dvě navzájem různá dostatečně velká prvočísla p, q, p ≠ q. Označíme si N=p ·q a K = (p-1)·(q-1). (O tom, jak náhodně volit dostatečně velká prvočísla, bude úloha příští.)

Náhodně zvolíme šifrovací exponent s, 1 < s < K tak, aby byl nesoudělný s K.

Najdeme celé číslo 0 < t < K, které vyhovuje rovnici (t·s) mod K = 1. Je možné dokázat (to po vás nechceme), že takové číslo existuje právě jedno.

Zveřejníme dvojici [N,s] – veřejný klíč, pomocí kterého může kdokoli zašifrovat nám určenou zprávu. Do trezoru si uložíme tajný klíč – dvojici [N,t], kterou budeme dešifrovat příchozí zprávy.

Příklad: Zvolili jsme prvočísla p = 11, q = 13 a šifrovací exponent s = 23. Pro tyto hodnoty je N = 143, t = 47.

Úloha: Vymyslete algoritmus a sestrojte program, který pro daná dvě prvočísla vypočítá nějakou dvojici klíčů pro šifrování algoritmem RSA. (Návod: Pokuste se zobecnit Euklidův algoritmus pro hledání největšího společného dělitele.)

Poznámka: Pokud chcete znovu použít nějakou část svých řešení minulých úloh, stačí, když na ni uvedete pouze odkaz.

Řešení