Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (1. soutěžní den) 47. ročníku

Řešení programátorské úlohy P-III-1 musí obsahovat popis použitého algoritmu, zdůvodnění jeho správnosti, diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu) a program zapsaný v jazyce Pascal nebo C. V řešení úlohy P-III-2 požadujeme nejen uvést navržené kódy, ale také podrobně zdůvodnit, proč mají požadované vlastnosti a jak se s nimi pracuje. V úloze P-III-3 popište, vysvětlete a zdůvodněte navrženou síť, spočítejte její hloubku a zakreslete schéma sítě.

P-III-1 Jednotková podmatice

Je dána čtvercová matice celých čísel A velikosti N x N, jejíž prvky mají hodnotu 0 nebo 1. Napište program, který určí velikost maximální jednotkové podmatice obsažené v A.

Jednotkovou podmaticí matice A rozumíme libovolný souvislý čtvercový výřez z matice A takový, že na jeho hlavní diagonále jsou samé 1 a všechny ostatní prvky mají hodnotu 0. Hlavní diagonála je úhlopříčka vedoucí z levého horního do pravého dolního rohu podmatice.

Vstupem programu je velikost matice N, N <= 20, a dále obsah matice zadaný po řádcích (tzn. N řádků, z nich každý obsahuje N čísel 0 nebo 1). Výsledkem je jediné číslo - velikost strany maximální jednotkové podmatice obsažené v zadané matici A.

Příklad

Pro matici velikosti N=5 tvořenou následujícími prvky:
11000
10101
00010
10001
01010

bude výsledkem číslo 3, neboť maximální jednotková podmatice má velikost 3x3 (je na řádcích 1-3 a ve sloupcích 2-4).

P-III-2 Kódy

Při přenosu dat (posloupností bitů) po linkách mezi počítači může někdy dojít k chybě: čas od času se stane, že se místo některého vyslaného bitu přijme na konci linky bit jiný. Nedochází ovšem k tomu, že by se při přenosu některý bit zcela ztratil nebo že by naopak bit přibyl.

Pro přenos dat po nespolehlivých vedeních se proto často používají různé zabezpečovací kódy. K přenášeným bitům b1..bn se přidají navíc kontrolní bity c1..cm tak, aby podle nich bylo možné na druhé straně linky zjistit, zda se zpráva přenesla v pořádku.

Nejjednodušším možným zabezpečovacím kódem je paritní kód doplňující jediný bit c1 takový, aby celkový počet jedničkových bitů v celé zprávě byl sudý. Tento kód umožňuje spolehlivě odhalit nejvýše jeden chybný bit v celé zprávě (ať již to byl jeden z datových bitů bi nebo přidaný paritní bit). Neumožňuje však přesně zjistit, který bit je chybný (což by se rovnalo opravení tohoto bitu, jelikož jsou pouze dvě možnosti, jakou hodnotu může mít).

a) Navrhněte zabezpečovací kód, který k n-bitové zprávě přidá m zabezpečovacích bitů tak, aby případnou chybu v jednom bitu zprávy bylo možné nejen zjistit, ale také opravit.

b) Navrhněte zabezpečovací kód, který k n-bitové zprávě přidá m zabezpečovacích bitů tak, aby bylo možné ověřit správnost došlé zprávy za předpokladu, že při jejím přenosu dojde k chybě v nejvýše dvou bitech (včetně bitů zabezpečovacích).

V obou případech se snažte o co nejmenší prodloužení zprávy (tzn. minimalizujte počet přidaných bitů m) a dokažte, že navržený kód skutečně požadované vlastnosti má.

P-III-3 Kombinační sítě

Abeceda je konečná neprázdná množina symbolů, s nimiž kombinační síť pracuje. Obsahuje vždy speciální symbol @ (prázdný symbol).

Základním stavebním prvkem kombinačních sítí jsou kombinační hradla (dále jen hradla). Každé z nich má dva vstupy a jeden výstup a je jednoznačně určeno svou přechodovou funkcí. Ta každé kombinaci možných hodnot na vstupech hradla (což jsou některé ze symbolů abecedy) jednoznačně přiřazuje hodnotu na výstupu. Symbol @ je funkcí přiřazen právě tehdy, když je přítomen tentýž symbol na kterémkoliv ze vstupů hradla.

Kombinační síť se skládá ze vstupů I1 až In, výstupů O1 až Oma hradel H1 až Hk. Každý ze vstupů hradla Hi je přímo připojen na některý ze vstupů sítě nebo na výstup nějakého hradla Hj, j < i (v síti tedy nemohou vzniknout cykly), případně na něj může být trvale připojen libovolný ze symbolů abecedy (konstanta). Stejným způsobem jsou připojeny i výstupy sítě.

Výpočet kombinační sítě probíhá v taktech. V nultém taktu jsou na všech vstupech sítě vstupní data a na výstupech všech hradel symboly @. V každém dalším taktu se nastaví výstupy všech hradel podle toho, jaké hodnoty byly na jejich vstupech v taktu předchozím. Tímto způsobem se pokračuje tak dlouho, dokud na alespoň jednom z výstupů sítě je symbol @. Poté se výpočet sítě zastaví a její výstupy obsahují výsledek výpočtu.

Podle toho, jak probíhá výpočet, je možné síť rozdělit do hladin. Do i-té hladiny zařadíme ta hradla, která v i-tém taktu mají na svém výstupu platnou hodnotu (tedy jiný symbol abecedy než @) a o krok dříve ještě tuto podmínku nesplňovala. Výpočet tedy bude probíhat tolik taktů, kolik má síť hladin.

Navrhnout kombinační síť řešící danou úlohu znamená zvolit abecedu, popsat přechodové funkce všech použitých hradel (například tabulkou) a určit propojení sítě (tj. vzájemné propojení hradel, vstupů a výstupů). Při návrhu sítě se snažíme dosáhnout co nejrychlejšího výpočtu, což znamená minimalizovat počet hladin sítě.

Kombinační sítě můžeme pro větší přehlednost znázorňovat graficky - jednotlivá hradla jsou reprezentována obdélníčky (nahoře jsou zakresleny vstupy, dole výstup), přičemž hradla v téže hladině se umisťují vedle sebe. Uvnitř každého obdélníčku je označení příslušné přechodové funkce. Nad všemi hladinami jsou zakresleny vstupy sítě, zcela dole pak výstupy sítě.

Soutěžní úloha

Navrhněte kombinační síť s abecedou {0,1,2,3,4,5,6,7,8,9,@}, n vstupy A1,..,An a n výstupy B1,..,Bn fungující jako třídící síť: Umístíte-li na vstupy nějakou posloupnost čísel, na výstupech se po ukončení výpočtu objeví tatáž posloupnost uspořádaná do neklesajícího pořadí.

Hodnotí se nejen správnost, ale také rychlost výpočtu navržené sítě - snažte se tedy dosáhnout co nejmenšího počtu hladin.