První série třicátého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

---

• Termín série: 30. října 2017 (seriál 13. listopadu 2017)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Sladkou odměnu pošleme každému, kdo vyřeší tři libovolné úlohy na plný počet bodů.

Zadání úloh

• 30-1-1: Oprava databáze
• 30-1-2: Telefonní hlavolam
• 30-1-3: Placení v čajovně
• 30-1-4: Cesta v bunkru
• 30-1-5: Zavirování sítě
• 30-1-6: Karetní hlavolam
• 30-1-7: Assembler

---

30-1-1 Oprava databáze (7 bodů)

---

Máme databázi osob, kde každý záznam obsahuje jen dva údaje: jméno osoby a její e-mail. V databázi jsou ale chyby a existuje mnoho záznamů buď se stejným e-mailem, nebo se stejným jménem.

Správci databáze se konečně rozhodli nepořádek vyřešit a pro každou osobu, která je v databázi, chtějí zjistit, kolik záznamů tam vlastně má. Platí, že kdykoli se dva záznamy shodují ve jméně nebo v e-mailu, patří stejné osobě.

Příklad: Záznamy Pepa <pepa@example.com>, Josef <pepa@example.com> a Josef <josef@example.com> všechny patří jedné a té samé osobě.

Řešení

---

30-1-2 Telefonní hlavolam (10 bodů)

---

Aby se náš hrdina dostal k panu Nápovědovi, musí ve správném pořadí stisknout N tlačítek, očíslovaných od jedničky do N, přičemž každé tlačítko se stiskne právě jednou a existuje jen jedno správné pořadí. Naštěstí nám protistrana posílá řadu dvojic čísel, kde dvojice (I,J) znamená, že číslo I ve správném pořadí přijde před číslem J (nemusí však být těsně vedle sebe).

Dohromady dostaneme až M dvojic a je zaručeno, že dohromady nám dvojice jednoznačně určují pořadí (protistrana není nikterak zlomyslná). Za každou další napovězenou dvojici si ale musíme zaplatit, takže bychom chtěli najít správné seřazení na co nejmenší počet dvojic (dvojice dostáváme v nějakém náhodném pořadí).

Příklad: Pro N = 4 se protistrana rozhodla, že nám postupně napoví dvojice (2, 1), (3, 4), (3, 2), (4, 1), (2, 4) a (3, 1). Správné pořadí je 3, 2, 4, 1 a je jednoznačně určené po pěti nápovědách – o poslední nápovědu tedy už nemusíme žádat.

Řešení

---

30-1-3 Placení v čajovně (12 bodů)

---

Filip si před zátahem na Nápovědu kupuje Puerh ve svém oblíbeném čajovém obchodě. Protože má v peněžence mnoho drobných, chtěl by se jich zbavit, zvláště těch nejtěžších mincí.

Celková cena čaje je H korun. Existuje N různých mincí o hodnotách H₁, … , H_N a hmotnostech M₁,… ,M_N. Zároveň víme, kolik mincí každého druhu má Filip v peněžence.

Prodavači musíme dát mince celkové hodnoty alespoň H. Pokud nemáme přesnou částku, tak nám vrátí, ale vždy nejtěžší možnou sadou mincí. Zároveň platí, že můžeme zaplatit K mincemi a prodavač vrátí maximálně L mincí.

Na základě znalosti všech parametrů vyberte mince, kterými má Filip zaplatit, aby měl na konci transakce co nejlehčí peněženku.

Řešení

---

30-1-4 Cesta v bunkru (15 bodů)

---

Pan Nápověda se rozhodl vystavět svůj bunkr jako nejdokonalejší bludiště na světě. Jeho zdi mají tvar Hilbertovy křivky, což je jistá křivka procházející všemi body roviny. Aby bludiště dokázal v konečném čase postavit, musel místo opravdové Hilbertovy křivky použít její aproximaci určitého konečného řádu r≥ 1.

Mapu bunkru si můžeme nakreslit jako čtvercovou síť velikosti (2^r+1+1)×(2^r+1+1) políček, přičemž políčka ležící na Hilbertově křivce tvoří zdi a ostatními políčky je možné procházet. Bludiště řádů 1, 2 a 3 vypadají následovně:

Z obrázku je také vidět, jak se křivka obecně konstruuje: Křivka řádu r+1 vznikne ze 4 kopií křivky řádu r, které vhodně natočíme a pospojujeme šedými políčky.

Vaším úkolem bude nalézt v Hilbertově bludišti nejkratší cestu mezi zadanými dvěma políčky. Například mezi políčky (6,6) a (6,10) obsahuje nejkratší cesta 41 políček a vypadá následovně:

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Vstup má jediný řádek. Na něm se nachází pět mezerou oddělených čísel: řád Hilbertovy křivky (1≤ r≤ 30), dvojice souřadnic počátečního políčka a dvojice souřadnic cílového políčka. Souřadnice se skládají z čísla řádku (číslováno shora od 0) a čísla sloupce (číslováno zleva od 0).

Formát výstupu: Výstupem je jediné přirozené číslo: počet políček na nejkratší cestě mezi zadanou dvojicí políček.

Příklad: Předchozímu obrázku odpovídá vstup 3 6 6 6 10 a výstup 41.

Řešení

---

30-1-5 Zavirování sítě (10 bodů)

---

Janky oblíbený virus infiltruje počítačovou síť. Předpokládáme, že síť je stromem, kde vrcholy jsou počítače a hrany jsou propojením mezi počítači. Na začátku si vybereme několik počítačů, které nakazíme virem. Následně se virus může šířit a platí, že počítač se nakazí, pokud alespoň polovina počítačů, se kterými je propojený, je nakažena.

Najděte, kolik nejméně počítačů musíte nakazit (popřípadě které), aby se v dalších krocích postupně nakazily všechny počítače.

Příklad: Následující graf se dá vyřešit nakažením jednoho (jakéhokoliv) vrcholu, z něj se nákaza rozšíří na všechny stroje.

Řešení

---

30-1-6 Karetní hlavolam (9 bodů)

---

Nápověda si rád ověřuje bystrost svých studentů podle toho, jak rychle dokáží provádět binární operace s celými čísly. Jednou z těchto operací je xor, známý též jako „exkluzivní nebo“ a značený ⊕.

Pokud chceme spočítat xor dvou (kladných celých) čísel A a B, nejprve obě převedeme do dvojkové soustavy. Jednotlivým cifrám dvojkového zápisu říkáme bity a číslujeme je od nuly zprava: poslední cifra je nultý bit, předposlední je první bit atd.

Výsledek dostaneme opět ve dvojkové soustavě, a to následovně: i-tý bit výsledku je 1 právě tehdy, když jsou i-té bity čísel A a B různé.

Příklad: spočítáme 26 ⊕6 (uprostřed jsou čísla přepsaná do binární soustavy):

26       = 11010
6        = 00110
26 xor 6 = 11100 = 28

Takže 26 ⊕6 = 28

Recepční na stůl vyloží N karet, na každé kartě je kladné celé číslo. Úkolem je najít dvojici karet s takovými čísly A a B, že hodnota A⊕B je největší možná.

Řešení

---

30-1-7 Assembler (15 bodů)

---

V letošním seriálu se ponoříme hlouběji do nitra nejen našich počítačů a notebooků, ale i chytrých mobilních telefonů, a nahlédneme pod křemíkovou pokličku procesorů. Naučíme vás, jak vlastně vypadají příkazy, které procesor umí provádět, zkusíme si něco pomocí nich naprogramovat a povíme si i něco o paralelním počítání. Teď ovšem nepředbíhejme a začněme hezky od začátku…

0xE3A00001 nebo mov r0, 1

Procesor si můžeme představit jako takovou malou krabičku, která krok za krokem čte instrukce a každou z nich vykoná. Všechny tyto instrukce musí být nějakým způsobem „zadrátované“ v procesoru, a tak nás asi nepřekvapí, že tam nenajdeme složité instrukce typu spočítej faktoriál nebo nakresli hrocha, ale mnohem jednodušší instrukce. O to rychleji je však procesor dokáže vykonávat: typický dnešní procesor jich zvládne přes 2 miliardy za sekundu!

Instrukce musíme procesoru předávat v nějakém formátu, kterému rozumí. Protože počítače si již od počátku lépe rozumí s čísly než se slovy, i instrukce jsou pro procesor zakódované pomocí čísel. To, jaké číslo znamená kterou instrukci, se může u jednotlivých procesorů značně lišit. Proto existují instrukční sady, což jsou pevně dané předpisy, jaké číslo odpovídá jaké instrukci. Pokud jste někdy slyšeli pojmy jako x86, ARM, PowerPC nebo MIPS, to všechno jsou instrukční sady. Díky tomu dva x86 procesory chápou instrukci číslo 123 identicky nehledě na to, jestli jsou od Intelu či AMD.

I když počítače lépe rozumí číslům, u lidí tomu tak zdaleka není. Schválně, dokážete z následujících čísel v šestnáctkové soustavě aspoň trochu vytušit, co by ARMový procesor provedl?

  0c 00 a0 e3
  2a 10 a0 e3
  91 00 03 e0

Pokud nemáte tušení, nebojte. Protože to nešlo většině lidí, velmi záhy stvořili assemblery. No posuďte sami, nečte se tohle lépe?

  MOV  r0, #12
  MOV  r1, #42
  MUL  r3, r1, r0

Pokud si spojíte MUL se slovem multiply, možná i odhadnete, že tento program vynásobí 12 a 42, i když jste nikdy žádný assembler neviděli. Assemblery nám tedy ve své nejjednodušší podobě umožňují zapsat instrukce pro člověka čitelnějším způsobem. Assembler se však stále před použitím musí tzv. assemblovat, neboli přeložit do číselné podoby instrukcí, kterou jsme viděli dříve.

V celém našem seriálu se budeme věnovat procesorům z rodiny ARM. Rodina ARM zahrnuje několik architektur, neboť si ARM postupně prošel několika verzemi, jejich koncepty jsou však na úrovni assembleru naštěstí velmi podobné, takže by nás neměla jiná verze ARMu zaskočit. Tyto procesory najdete ve většině chytrých telefonů a tabletů a například i v Raspberry Pi.

Protože většina z vás asi nemá v šuplíku ARMový procesor, na kterém byste mohli testovat svá řešení úložek, připravili jsme si pro vás jednoduchý simulátor. Ten již bohužel neběží, kdybyste chtěli poradit s rozchozením nějakého vlastního, tak se nám ozvěte.

Čísla, čísla, čísla…

Zatímco počítače umí pracovat s nejrůznějšími typy dat (textem, obrázky, zvukem, …), jejich procesory zvládnou zpracovávat jenom čísla. A navíc ta čísla nesmí být moc velká. Typický procesor pracuje najednou buďto s 32-bitovými nebo 64-bitovými celými čísly. My si budeme povídat o jedné ze starších verzí architektury ARM, která je 32-bitová. Práci s čísly si nicméně pro větší názornost předvedeme na 8-bitových číslech.

Nejprve se podíváme, jak se ukládají přirozená (celá nezáporná) čísla; říká se jim také čísla bez znaménka. Procesor je ukládá ve dvojkové soustavě, v každém bitu je uložena jedna číslice dvojkového zápisu. Například číslo 42 bychom zapsali jako 0010 1010 (protože 42 = 2⁵ + 2³ + 2¹). Řády bývá zvykem oddělovat po čtveřicích, nebo ještě lépe číslo místo ve dvojkové soustavě zapisovat v šestnáctkové (hexadecimální; s číslicemi 0 až 9 a a až f). Čtyři dvojkové číslice totiž odpovídají právě jedné šestnáctkové. Šestnáctkové zápisy se obvykle uvozují znaky 0x, takže číslo 42 bychom zapsali jako 0x2a.

Bity čísla číslujeme od 0 do 7, nejnižší řád má číslo 0, nejvyšší 7; i-tý bit má tedy váhu 2ⁱ. Nejmenší 8-bitové číslo je tudíž 0000 0000 = 0, nejvyšší 1111 1111 = 2⁰ + 2¹ + … + 2⁷ = 2⁸ - 1 = 255.

Pokud při sčítání čísel dojde k přetečení, čili výsledek se nevejde do 8 bitů, pak přebytečnou část výsledku prostě odřízneme. To je totéž, jako kdybychom řekli, že počitáme modulo 2⁸. Například:

Odčítání také probíhá modulo 2⁸, takže kdyby mělo vyjít záporné číslo, přičteme k prvními číslu 2⁸, aby výsledek vyšel kladný. Třeba takto:

V posloupnosti sčítání a odčítání se tedy nemusíme o přetékání starat: dokud víme, že výsledek se vejde do 8-bitového čísla, vyjde správně.

Také si všimněme, že číslo 254 se chová stejně jako -2. To ostatně dává smysl, neboť tato dvě čísla se liší o násobek 2⁸, takže jsou modulo 2⁸ stejná. Toho můžeme využít k reprezentaci záporných čísel. Jen by se nám občas hodilo, abychom uměli poznat záporné číslo od kladného.

Proto zavedeme reprezentaci čísel se znaménkem pomocí dvojkového doplňku. Nejvyšší bit nám poslouží jako znaménkový bit: bude-li nulový, ukládáme nezáporné číslo obvyklým způsobem (bude tedy v rozsahu 0 až 127). Čísla s jedničkou ve znaménkovém bitu budeme považovat za záporná: 1111 1111 bude znamenat -1, 1111 1110 = -2, … až 1000 0000 = -128. Ukládáme tedy o 256 více, než je hodnota záporného čísla. Dohromady proto dovedeme ukládat všechna čísla od -128 do 127.

Dodejme ještě, že sčítání a odčítání funguje úplně stejně pro čísla se znaménkem jako bez znaménka: obojí pracuje modulo 2⁸, jen si pokaždé výsledek vykládáme různě. Násobení a dělení už ale musí znaménka brát v úvahu.

Škatulata, hejbejte se

Procesor si čísla, se kterými zrovna pracuje, potřebuje někde pamatovat. K tomu slouží registry. Registry našeho ARMu jsou 32-bitové a je jich celkem 16. Prvních 13 z nich se jmenuje r0, r1, …, r12 a jsou general purpose (tedy k obecnému použití), což znamená, že si do nich můžeme ukládat naprosto cokoliv. Poslední tři registry mají speciální význam, o kterém si však něco povíme až v příštím dílu seriálu.

První instrukcí, kterou si společně představíme, je MOV. Ta slouží k přesunu dat (z anglického MOVe). Pozor na to, že argumenty dostává v pořadí kam, co. První argument je vždy název registru, druhý argument může být buď název jiného registru nebo číselná konstanta. Pokud chceme v ARMovém assembleru zapsat číselnou konstantu, je třeba před samotné číslo napsat znak #. Pro pořádek ještě zmíníme, že zavináčem začíná komentář do konce řádku. Příklad použití:

 MOV  r7,  #42   @ Do r7 se uloží číslo 42
 MOV  r10, r7    @ Do r10 se uloží číslo 42 z r7
 MOV  r2,  #0xFF @ Do r2 se uloží číslo 255

Když už jsme si pořídili počítač, bylo by hezké, kdyby i něco počítal. K tomu si musíme ukázat ještě jeden registr, který se chová jinak než všechny ostatní. Nazývá se CPSR a je to takzvaný registr příznaků (anglicky flag register). Aritmetické operace mohou do tohoto registru nastavit jednotlivé příznaky podle toho, jak výpočet dopadl. Na ARMu máme čtyři aritmetické příznaky, a to N (Negative), pokud je výsledek záporný, Z (Zero), pokud je výsledek nula, a V (oVerflow) upozorňující, že došlo k přetečení. Čtvrtým příznakem je C (Carry), do kterého se uloží ten bit výsledku, který se do registru při ukládání již nevejde (tedy na našem 32-bitovém ARMu 32. bit, číslujeme-li od nuly). K čemu je to dobré, uvidíme záhy.

Sčítání a odčítání zajišťuje šestice instrukcí ADD (ADD), ADC (ADd with Carry), SUB (SUBtract), RSB (Reverse SuBtract), SBC (SuBtract with Carry), RSC (Reverse Subtract with Carry). Pozor na to, že odčítání nastavuje carry opačně, než odpovídá definici!

• ADD a, b: a = a + b
• ADC a, b: a = a + b + carry
• SUB a, b: a = a - b
• RSB a, b: a = b - a
• SBC a, b: a = a - b - (1 - carry)
• RSC a, b: a = b - a - (1 - carry)

Instrukce, které pracují s carry, nám umožňují sčítat velmi velká čísla – to, co se nám přeneslo z předchozího bloku, prostě přičteme k bloku dalšímu. Jelikož je u odčítání carry definováno obráceně, SBC a RSC odčítají jeho negaci. Také pozor, že na ARMu příznaky mění pouze varianty instrukcí zakončené písmenem S, např. ADDS nebo RSCS!

ARM nám zároveň umožňuje uložit výsledek do libovolného registru, k čemuž slouží instrukce se třemi parametry, např. ADD c, a, b uloží a + b do c. Stejně jako u MOV je a registr a b může být registr nebo číslo.

Nejlépe si to ukážeme na příkladu:

  MOV   r1, #42
  MOV   r2, #30
  ADD   r3, r1, r2   @ r3 = 72
  SUB   r4, r1, r2   @ r4 = 12
  RSCS  r1, r2       @ r1 = -12, příznak N

Pro násobení existuje na ARMu mnoho instrukcí, my si pro jednoduchost ukážeme pouze jednu z nich, která nám pro násobení malých čísel bude stačit. Je to MUL (MULtiply) pro násobení znaménkových čísel a používá stejný formát argumentů jako aritmetické instrukce. U ní existuje i varianta MULS, která nastaví příslušné příznaky. S dělením je situace přehlednější, existují pouze instrukce SDIV (Signed DIVide) pro znaménkové dělení a UDIV (Unsigned DIVide) pro bezznaménkové, ovšem tyto instrukce nemají variantu nastavující příznaky. Násobení i dělení používají opět 2 až 3 argumenty se stejným významem jako ostatní aritmetické operace.

Úkol 1 [4b]

Napište v assembleru posloupnost instrukcí, která do registru r0 spočítá povrch kvádru, jehož rozměry jsou zadané v registrech r1, r2 a r3.

Podobnou kategorii operací představují bitové operace AND (bitové and), ORR (bitové or), EOR (bitové xor) a BIC (bitové and not). Tyto instrukce vždy berou tři argumenty, tedy cílový registr, zdrojový registr a třetím parametrem může být další zdrojový registr nebo číslo.

Tyto operace fungují nezávisle pro jednotlivé bity čísla: i-tý bit výsledku z_i spočítáme z i-tých bitů vstupních čísel x_i a y_i. Pro AND je přitom z_i=1 právě tedy, když je x_i = y_i = 1. Pro OR je z_i=1, kdykoliv x_i=1 nebo y_i=1. A pro EOR potřebujeme, aby právě jeden z bitů x_i a y_i byl jednička. NOT prostě přepne jedničku na nulu nebo nulu na jedničku. Zde je příklad:

  MOV   r1, #0xF0FF
  MOV   r2, #0x0FF0
  AND   r3, r1, r2   @ r3 = 0x00F0
  ORR   r4, r1, r2   @ r4 = 0xFFFF
  EOR   r5, r1, r2   @ r5 = 0xFF0F

Hop sem, hop tam

Občas se nám může hodit skočit na jiné místo programu. K tomu na ARMu slouží instrukce B (Branch) (v jiných instrukčních sadách se často jmenuje JMP (JuMP)). Abychom mohli assembleru říct, kam má daný skok vést, tak si příslušné místo v programu pojmenuje návěštím (anglicky label). Návěští v sobě může mít číslice, písmena anglické abecedy a podtržítka. Hezký nekonečný cyklus by mohl vypadat třeba takto:

  MOV   r1, #42
cyklus:
  SUB   r1, #1
  B     cyklus

Pokud bychom nyní chtěli v assembleru začít psát nějaké užitečnější programy, asi by nám velmi rychle začaly chybět podmínky. To většina procesorů řeší implementací podmíněných skoků – v případě, že se podmínka vyhodnotí jako pravdivá, procesor skočí na cílové návěští, v opačném případě pokračuje následující instrukcí. Jaké podmínky procesor umí? Zde se konečně dostáváme k využití registru příznaků, neboť podmínky využívají právě uložených příznaků.

Pro snazší pochopení názvů podmínek si ještě představme instrukci CMP (CoMPare). Ta se chová naprosto identicky jako SUBS, akorát výsledek se nikam neukládá, pouze se podle něho nastaví příslušné příznaky. V pravém sloupci následující tabulky naleznete význam podmínky po provedení CMP a,b. Sloupce příznaků obsahují 1 pro nastavený příznak a 0 pro nenastavený.

podmínka	Z	C	N	V	význam
EQ (EQual)	1				a = b
NE (Not Equal)	0				a ≠ b
CS (Carry Set)		1			a ≥ b (neznaménk.)
HS (Higher Same)
CC (Carry Clear)		0			a < b (neznaménk.)
LO (LOwer)
VS (oVerflow Set)				1	Došlo k přetečení
VC (oVerflow Clear)				0	Nedošlo k přetečení
HI (HIgher)	Z=0 ∧ C=1				a > b (neznaménk.)
LS (Lower Same)	Z=1 ∨ C=0				a ≤ b (neznaménk.)
GT (Greater Than)	Z=0 ∧ N=V				a > b (znaménkově)
LE (Lower Equal)	Z=1 ∨ N≠V				a ≤ b (znaménkově)
GE (Greater Equal)	N = V				a ≥ b (znaménkově)
LT (Lower Than)	N ≠ V				a < b (znaménkově)
MI (MInus)			1		a-b < 0
PL (PLus)			0		a-b ≥ 0

Příznaky MI a PL moc nemá smysl používat po CMP. Lepší je použít LT/LO nebo GE/HS. Pro výsledky aritmetických operací se však hodí.

Například si ukažme jednoduchý cyklus, který (pokud je r1 ≥ 1) spočítá součin r1 ·(r1-1) ·… ·1 do r0:

  MOV   r0, #1
cyklus:
  MUL   r0, r1
  SUBS  r1, #1
  BNE   cyklus  @ skoč, pokud r1 není 0.

ARM je mezi instrukčními sadami výjimečný tím, že dovoluje podmínku k mnoha dalším instrukcím než jen ke skokům. Nicméně zatím se bez toho obejdeme.

Úkol 2 [5b]

Vymyslete, jak pomocí podmíněných skoků zapsat následující pseudokód:

  if r1 == 0:
    r0 = r0+1
  else:
    r0 = r0-1
  r2 = r0*2

Úkol 3 [6b]

Napište v assembleru posloupnost instrukcí, která do registru r0 spočítá největšího společného dělitele čísel zadaných v registrech r1 a r2.

To je pro tento rychlý úvod do assemblerů vše, příště se vrhneme na paměti a další pěkné věci.

Jan „Goci“ Gocník & Martin „Medvěd“ Mareš

Řešení

Menu