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

Řešení úloh

9-3-1 Odporné odpory p. Odporného (Zadání)

Tento příklad byl značně nepraktický. Jeho řešení je totiž v samotném důsledku k ničemu. Spojováním resistorů vznikají často neceločíslené výsledky (racionální čísla) a ty lze sotva dle zadání zadat na vstupu. Nehledě na to, že odpory skutečných resistorů nejsou přesné. Tedy člověk by v praxi spíše chtěl sestavit složení resistorů, které má velikost odporu v nějakém malém intervalu kolem požadované hodnoty (velikost tohoto intervalu charakterizuje požadovanou přesnost). Naše zadání však bylo jiné. Naneštěstí složitost tohoto problému je natolik veliká, že přesný výpočet výsledku zabere tolik času, že už pro malý počet resistorů (řádově desítky) se řešení, v případě že zapojení neexistuje, nedočkáme. Pro lidi libující si v počítání složitosti je následující odstavec.

Pouhé hledání zapojení ze sériových kombinací je NP-úplný problém – úlohu je možno triviálním polynomiálním převodem transformovat na známý NP-úplný problém batohu. Z tohoto plyne, že zatím nikdo nezná řešení této podúlohy v polynomiálním čase. Naše zapojení může však navíc mít i paralelní spoje… Ptáte se tedy jistě, jak se tedy takovéto úlohy v praxi řeší? Inu vězte, že existují složitější algoritmy, které v průměrném případě řeší např. problém batohu v čase O(N3), ale ty přesahují obtížnost našeho semináře. Můžete se o nich dozvědět na některých přednáškách na MFF UK.

Algoritmus našeho řešení je prostý — backtracking, tj. zkoušet všechny možnosti a nezkoumat zbytečné a nesmyslné případy, (tzv. ořezávaný backtracking. Na začátku máme k dispozici pouze pole nepoužitých odporů vstupních velikostí. Z pole vybíráme nepoužité odpory a zkoušíme je spojovat nejprve sériově a pak paralelně. Každým spojením označíme původní 2 odpory za použité a nový odpor přidáme na konec pole. Poté zavoláme rekurzivně algoritmus znovu. Algoritmus končí s dalším rekurzívním voláním, pokud nalezne v poli odpor hledané velikosti. Je-li nalezená velikost navíc s doposud nejmenším počtem resistorů, zapojení si program zapamatuje. Pokud se projde celé pole odporů a všechny odpory jsou použity, nebo už nelze dosáhnout výsledného odporu (současné zapojení se sériovým zapojením zbylých resistorů má menší odpor než je zadaný výsledný odpor ).

Pokud celý algoritmus skončí a zapamatoval si nějakou kombinaci odporů, pak tato kombinace obsahuje určitě nejmenší počet resistorů – prošly se všechny možnosti a žádná nebyla menší. Výsledné zapojení se pak vypíše ve formě aritmetického výrazu, který se v průběhu algoritmu mění dle testovaného zapojení. resistory odpovídají číslům, `+' je sériové zapojení, `*' je paralelní zapojení. Ve výrazu jsou použity závorky. Tedy náš program vlastně hledá vhodné uzávorkovaní a doplnění operátorů +, * v aritmetickém výrazu. Najde-li řešení, vytiskne ho.

Spránost je zajištěna probíráním všech možností. Každé uzávorkování výrazu odpovídá jednoznačně jednomu zapojení. Např. `(50+1)*7' je paralelní zapojení `7' a seriového `50,1'. Pro zvýšení rychlosti začíná algoritmus s nejmenším počtem rezistorů – spojuje dvojičku. Tu pak spojí s jiným odporem. Najde-li 1. řešení, prohlásí jej za mimimální. Dalších řešení výrazu ale s větším počtem operátorů, tj. resistorů, si nevšímá. Nepočítá zbytečně kombinace odporů stejné velikosti, které už se dříve vyskytly. Mám-li 3 resistory, každý s odporem 5, je zbytečné po jednom každý z nich připojovat k jinému resistoru, dostanu totiž pokaždé stejný výsledek.

Popis programu: Program je natolik dobře komentován, že je zbytečné zde dále něco popisovat. Jen tolik, že je napsán v jazyce C a veškerou práci dělá rekurzivní procedura zapoj.

Program

Martin `Mafi' Bělocký

9-3-2 Cosi prohnilého? (Zadání)

Nejprve pár slov k vašim řešením. Většina z vás řešila úlohu tak, že postupně zkusili smazat každou hranu a poté otestovat, zda se království rozpadne. Tento přímočarý přístup nevede k příliš rychlému algoritmu, ale budiž. Horší je však to, jak někteří z vás realizovali test souvislosti; místo optimálních O(c) (c je počet hran) napsali test v čase O(c·m) (m značí počet měst), někteří experti dokonce v exponenciálním čase! K exponenciálním algoritmům se uchylujte jen v případě krajní nouze!!!

Někteří z vás výše uvedený triviální postup vylepšili: když zjistím, že se po vymazání silnice království nerozpadlo, tak jsem zároveň našel nějaký cyklus silnic. Žádná ze silnic na cyklu není kritická, nebudu ji proto už zkoumat. Několik světlých vyjímek použilo algoritmus s optimální rychlostí…

Hodnotil se popis a zdůvodnění algoritmu + správnost programu + efektivita; maximální bodové příděly byly 3+3+4.

A nyní už k vlastnímu řešení. Je snadné si uvědomit, že kritické silnice (tzv. mosty, řečeno terminologií teorie grafů) jsou přesně ty, které nejsou součástí žádného cyklu. Jde tedy o to, jak efektivné poznat, které hrany jsou součástí nějakého cyklu. Graf budeme rekurzivně procházet, půjde o upravené procházení do hloubky (upravené proto, že v klasickém případě neprocházíme obecný graf, nýbrž strom). Při procházení vrcholy průběžně číslujeme (čísly 1, 2, …), číslo vrcholu u značme pu. Klíčem k řešení je návratová hodnota funkce h(l, u), která realizuje prohledávání (u je aktuální vrchol, l jeho předchůdce – vrchol, ze kterého jsme se do u dostali). Jedná se o nejmenší číslo vrcholu, na něž narazíme při procházení grafu na hlubší úrovni než je u. Čili je to minimum z čísel už projitých sousedů, nepočítaje v to souseda l (na tyto vrcholy narazíme ihned) a z návratových hodnot rekurzivního vyvolání funkce h(u,w) pro všechny w – dosud neprojité sousedy u.

Pokud jste tento popis vstřebali, tak zbývá jen nahlédnout (a dokázat!), že hrana (u,w) je součástí nějakého cyklu právě tehdy, když při zavolání h(u,w) z vrcholu u dostaneme číslo ≤ pu. Obcházíme-li totiž nějaký takový cyklus směrem u →w →u, pak jednou (nejpozději v posledním kroku) narazíme na vrchol s číslem ≤ pu.

Naopak, nechť při procházení pod vrcholem w narazíme na vrchol v takový, že pv ≤ pu. To ovšem znamená, že mezi u a v vede cesta (zde využijeme toho, že rekurzivně nezkoumáme přechůdce, tj. vrchol l. Jinak bychom mohli dostat cestu u →l →u) tvaru u →w → případné další vrcholy s číslem > pu →v (na v jsme narazili pod vrcholem w) a také cesta používající vrcholy s čísly ≤ pu (při procházení grafu jsme někdy byli ve v, pak jsme (souvisle) přešli do u, a teprve pak jsme začali používat čisla větší než pu). Máme tedy cyklus obsahující hranu (u,w).

Takže z vrcholu u zavoláme rekurzivně funkci postupně na všechny dosud neprojité sousedy w a je-li návratová hodnota příliš vysoká, tak hranu (u,w) vypíšeme, je totiž kritická.

Ještě krátce k programu. Graf (město) je reprezentován tak, že pro každý vrchol máme uložen seznam sousedů (v poli sou) a jejich pocet (v poli st, jakožto stupeň). Zbytek by měl být jasný.

A jaká že je složitost algoritmu? Každou hranu zkoumáme dvakrát (z obou na ní ležících vrcholů), na každé město pouštíme jednou funkci hledej(...). Čili časová složitost je O(c+m).

Program

Robert Šámal

9-3-3 Mikroassembler (Zadání)

Tato úloha byla mírně neobvyklá v tom, že vlastně ani nešlo o vymýšlení nějakých algoritmů, ale pouze o důkazy, že něco je či není možné. Samozřejmě důkaz existence je možno (ale nikoliv nutno) provést konstrukcí hledaného objektu (což se v tomto vzorovém řešení ostatně činí), důkaz neexistence musí být poněkud pečlivější a lépe rozmyšlený, aby se v něm nepředpokládaly věci, které nemusí být pravda (běžnou chybou např. bylo tvrdit, že "instrukce JEQ je nepostradatelná, protože bez ní by nešly implementovat cykly" bez jediného slova o tom, proč se příslušné programy nedají převést na jiné bez cyklů).

Nejprve zkusíme dokázat, bez kterých instrukcí se zaručeně obejít nelze:

Instrukci DEC samotnou ovšem lze nahradit velice snadno ostatními instrukcemi: Použijeme dvě pomocné paměťové buňky označené α a β (takové jistě máme k dispozici, protože každý konečný program může použít pouze konečně mnoho paměťových buněk, zatímco paměť jako taková je nekonečně velká) a DEC φ provedeme takto:

CLR α α= 0
CLR β β= 0 (výsledek)
JEQ α,φ,5 φ= 0 ⇒Hotovo
INC α Udržujeme α= β+ 1
JEQ α,φ,3 φ= β+ 1 ⇒Výsledek je β
INC β Zkoušíme novou hodnotu β
JEQ α,α,-3 Znovu test rovnosti…
CLR φ A teď kopírujeme β zpět do φ
JEQ β,φ,3 Hotovo?
INC φ Ne, zvýšíme
JMP φ,φ,-2 A znovu test…

Zkrátka a dobře: hledáme výsledek operace tak, že začneme nulou a postupně přičítáme jedničku, dokud nezjistíme, že zkoumané číslo zvýšené o jedna je rovno číslu původnímu. Jelikož všechna čísla jsou konečná, musíme v konečném čase dojít k cíli.

Instrukci CLR je nutno nahrazovat mírně sofistikovanějším způsobem: nemůžeme totiž snižovat nějakou proměnnou tak dlouho, dokud se nestane nulou, jelikož nemáme způsob, jak bychom to zjistili, nevíme-li o ostatních paměťových místech vůbec nic. Vezmeme si tedy dvě buňky paměti (cílovou buňku φ a pomocnou buňku α) a zařídíme, aby obsahovaly různé hodnoty (pokud jsou hodnoty náhodou stejné, prostě jednu zvýšíme o jedna). Nyní v každém kroku obě snížíme a dle definice instrukce DEC budou nadále různé, pokud ovšem nevyjdou obě 0 (k tomuto opět po nějaké době dojít musí, protože všechna čísla byla konečná!). Tedy takto:

INC α Trik…
JEQ α,φ,-1 Nyní α≠ φ
JEQ α,φ,4 Již hotovo (α= φ= 0)
DEC α Obě snížíme o 1
DEC φ
JMP α,α,-3 A zkoušíme znovu…

Zkrátka a dobře, firma Sirius Cybernetics tedy není ničím jiným než bandou podvodníků snažících se zneužít hlouposti ostatních (jak to již v počítačovém průmyslu jest dlouholetou tradicí)…

Martin Mareš

9-3-4 Komplikátor (Zadání)

Nejdříve dáme dohromady něco podprográmků pro jednotlivé základní operace. Tyto prográmky nejsou nikterak těžké, přesto v nich nemálo z vás nasekalo spoustu chyb. Nejčastější chybou bylo zničení obsahu zdrojových operandů po výpočtu. Pokud byla některá proměnná použita ve výrazu vícekrát, pouze poprvé měla správnou hodnotu, v dalších výskytech nabyla většinou hodnoty 0. Někteří si to uvědomili a tak po každém výpočtu její hodnotu obnovili. Ale není jednodušší ji vůbec nezničit? Já používám 0–2 pomocné proměnné, které slouží jako počítadla, takže vstupních proměnných se vůbec nemusím dotknout.

Převaděč aritmetických výrazů:

Tento problém se dá řešit různými přístupy. Každý z nich se ve vašich řešení aspoň jednou vyskytl. Přístupy jsou seřazeny podle elegance řešení:

  1. Nejméně elegantní je nalezení podvýrazu, který můžeme vyhodnotit, vypsání assemblerovského prográmku a nahrazení starého podvýrazu v řetězci nově přiřazenou pomocnou proměnnou. Toto provádíme, dokud není v řetězci pouze 1 proměnná (a to výsledek). Je nasnadě, že zcela zbytečně mnohokrát modifikujeme vstupní řetězec.
  2. O něco hezčí je použití rekurzivní procedury, která prochází řetězec zleva doprava. Narazí-li na levou závorku `(', pak se zavolá pro příslušný podvýraz a vrátí číslo proměnné, ve které je uložen podvýsledek. Díky této abstrakci můžeme předstírat, že dostaneme výraz složený pouze z proměnných a operací 2 priorit.
    V další fázi projdeme tento abstraktní řetězec zleva doprava a rozdělíme si jej na skupinky s operacemi `*', `/', `%', které jsou pospojovány operacemi `+', `-'. Pak můžeme pomocí zásobníkové proměnné vyhodnotit všechny operace.
  3. Nejobecnějším a asi nejelegantnějším je algoritmus RPN (Reverse Polish Notation), který se dá modifikovat pro libovolné přiřazení priorit jednotlivým operacím, pro vyhodnocování zleva i zprava, pro použití unárních funkcí a jiné speciality (čtěte: zvrhlosti).

Aritmetický výraz budeme číst v jednom průchodu zleva doprava, při výpočtu budeme používat 2 oddělené zásobníky: pro operandy a pro operátory. Načteme-li operand (proměnnou), neuděláme nic než že ji uložíme na vrchol zásobníku. Tam bude čekat na vyhodnocení. Pod ní bude uložena buď ve výrazu předcházející proměnná nebo nějaký mezivýsledek vlevo od této proměnné.

Načteme-li naopak operátor, umístíme jej na vrchol zásobníku operátorů. Pak však porovnáme jeho prioritu s prioritou předchozího operátoru. Je-li vyšší (např. `*' před `+'), pak jej musíme vyhodnotit před novým operátorem (v zásobníku operandů pak už nebude vstupní proměnná, ale výsledek podvýrazu s vyšší prioritou – díky tomu se nám to samo rozdělí na prioritní podvýrazy). Takto se pokusíme vyhodnocovat předchozí operátory tak dlouho, dokud bude jejich priorita vyšší než priorita nová. Po těchto operacích se nám mnoho čekajících operátorů vyhodnotí, mezivýsledky se v paměti zkombinují a zůstane nám tam mezivýsledek nový.

Vyhodnocení aritmetické operace se provede vybráním dvou operandů z vrcholu zásobníku, výpočtem operace a uložením mezivýsledku.

Nyní je potřeba vyřešit technické detaily: závorky a konec řetězce. Konec řetězce můžeme považovat za operaci s nejnižší prioritou vůbec (takže odstraní ze zásobníku úplně všechno), která však není binární, ale unární (převezme výsledek a předá jej). Při výskytu levé závorky nesmíme nic předběžně vyhodnotit. Musíme počkat až na odpovídající pravou závorku, vyhodnotit vše mezi nimi a teprve pak předchozí operace. Nejjednodušší je považovat levou závorku `(' za operaci s nejvyšší prioritou vůbec (takže se před ní nic nevyhodnotí) a pravou závorku `)' za operaci s velmi nízkou prioritou (takže se vyhodnotí vše až k levé závorce).

Zde musíme ale udělat jednu výjimku: aby se vyhodnocování zastavilo na levé závorce a nepokračovalo dál na předchozí operace, musíme u levé závorky na zásobníku nastavit velmi nízkou prioritu. Tyto dva protichůdné požadavky na levou závorku splníme tak, že operátor má dvě priority: první v okamžiku porovnávání s předchozími operátory na zásobníku a druhou pro uložení vlastní priority na zásobník. U všech ostatních operátorů budou tyto priority stejné, ledaže bychom chtěli, aby se některý vyhodnocoval zprava doleva (vhodné např. pro umocňování). Pak bude jedna z nich o jedničku vyšší (která?).

Další tohoto vyhodnocování se dá snadno zahrnout kontrola výrazu (pomocí jedné stavové proměnné udávající, jaký objekt je zrovna očekáván). V programu použijeme vstupní funkci, která nám místo jednotlivých znaků bude přímo vracet tokeny, tj. nejmenší rozpoznatelné lexikální objekty (proměnné, operátory, závorky).

V zásobníku operandů budou uložena čísla proměnných. Při načtení vstupní proměnné se tam jenom uloží číslo 1–26, při spočítání mezivýsledku se tam uloží index na zaručeně novou proměnnou. Je možno implementovat hezký memory management, my si vystačíme se stále se zvyšujícím číslem první volné proměnné (pak budou v paměti díry), protože máme k dispozici libovolně velkou paměť. Obecně by paměťová složitost závisela na hloubce vnoření daného výrazu, které je však také lineární.

Časová složitost je O(n), protože výraz projdeme jednou zleva doprava, konečnost je zřejmá, neboť v programu nepoužíváme žádné podezřelé cykly. Časová složitost je O(n), neboť hloubka vnoření výrazu může být lineární s délkou, jako je tomu např. u výrazu a+(b+(c+(d+…))).

Program

Robert Špalek

9-3-5 Top secret (Zadání)

Označme M = (p-1) ·(q-1). Ze zadání vyplývá, že máme řešit rovnici

(t ·s) mod M = 1,

která se dá převést na klasickou diofantovskou rovnici

ax + by = 1.

Uvažujme Euklidův algoritmus ve variantě, která pro daná a, b nejen vypočítá jejich největšího společného dělitele D(a,b), ale také poskytne konstruktivní důkaz, že D(a,b) je lineární kombinací čísel a a b. (V našem případě je D(a,b) = D(s,M) = 1.)

procedure Euclid(a,b:integer;
                 var d,x,y:integer);
var d1,x1,y1:integer;
begin
  d := a; x := 1; y := 0; d1 := b;
  x1 := 0; y1 := 1;
  repeat
    if d > d1 then begin
      x := x - x1 * (d div d1);
      y := y - y1 * (d div d1);
      d := d mod d1;
    end else begin
      x1 := x1 - x * (d1 div d);
      y1 := y1 - y * (d1 div d);
      d1 := d1 mod d;
      end;
  until (d = 0) or (d1 = 0);
  if d = 0 then begin
    d := d1;
    x := x1;
    y := y1;
    end;
end;

Dokážeme, že během výpočtu dvojice čísel a,b a d,d1 mají tytéž společné dělitele, a navíc d = ax + by a d1 = ax1 + by1. Před vstupem do cyklu toto tvrzení zřejmě platí. Ukážeme, že průchodem cyklem se jeho platnost nezmění. Uvažujme případ d > d1, pro opačnou situaci je úvaha analogická.

Označíme u=D(d,d1), pak d=u·α, d1=u·β, D(α,β)=1 a D(d mod d1, d1) = D((u·α) mod (u·β), u·β) = D((u·α) - (u·β)·((u·α) mod (u·β)),(u·β)) = u·D(α-β·((u·α) mod (u·β)), β) = u.

Druhá podmínka se také zachovává: a·(x-x1·(d / d1)) + b·( y-y1·(d / d1)) = ax + by - (ax1 + by1)·(d / d1) = d-d1·(d / d1) = d mod d1.

Po ukončení cyklu tedy bude D(a,b) = D(d,d1) = D(d,0) = d resp. D(a,b)=D(0,d1)=d1.

Časová složitost algoritmu je stejná jako u algoritmu Euklidova – to jest O(log a + log b) průchodů cyklem. (Je možné poměrně snadno dokázat, např. použitím Fibonacciho čísel, že každými dvěma průchody cyklem se d zmenší alespoň dvakrát).

Uvedeným algoritmem vypočteme celočíselné řešení rovnice ax+by=D(a,b). Pro nalezení 0<t<M musíme ještě výsledek znormalizovat podle modulu. Při normalizaci můžeme využít snadno dokazatelného faktu, že |x|< b, resp. |y|< a.

Se započítáním časových složitostí operací s čísly je časová složitost algoritmu O(log 3N), kde N=p·q.

Zbývá dodat postup pro šifrovací exponent s. Vygenerujeme náhodné číslo s, 1<s<M. Dokud není D(M,s)=1, inkrementujeme. Tento postup je zaručeně konečný, protože D(M,M-1)=1. Jelikož jsou prvočísla p,q velka, je M sudé, a tedy se můžeme omezit na s>2 a hledání provádět s krokem 2.

Odvození dobrého odhadu časové složitosti hledání s by vyžadovalo hlubší poznatky z teorie čísel. (Intuitivně je vidět, že s najdeme většinou velmi rychle.)

Procedura pro výpočet klíčů pro algoritmus RSA počíta s čisly typu Integer. Převedení na počítání s velkými čísly je pouze technickou záležitostí. Testování soudělnosti M a s probíhá společně s generováním t.

procedure RSAKey(P,Q:Integer;var S,T:Integer);
var M,D,X,Y: Integer;
begin
  M := (P-1)*(Q-1);
  S := 3 + 2*Random(M div 2 - 1);
  repeat
    Euclid(S,M,D,X,Y);
    if D=1 then break;
    inc(S,2);
  until false;
  if X<0 then T:=M+X;
end;

Jan Kotas