Řešení každého příkladu musí obsahovat popis použitého algoritmu, zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu). V praktických úlohách P-I-2 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal nebo C. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možné v případě nejasností otestovat jeho funkčnost. Slovní popis řešení ovšem musí být jasný a srozumitelný i bez toho, že by bylo třeba nahlédnout do zdrojového textu programu. V úloze P-I-1 se odladěný program nutně nepožaduje, stačí místo něj uvést dostatečně podrobný slovní zápis algoritmu nebo neodladěný zdrojový text nejdůležitějších částí programu. V úloze P-I-4 místo výsledného programu nakreslíte schémata navržených kombinačních sítí.
P-I-1 Večírek
Na večírku se sešlo několik hostů. Víme, kteří z nich se vzájemně
znají a kteří ne. Vztah "znát se" uvažujeme zásadně jako
symetrický, tzn. o libovolné dvojici lidí platí, že buď se
navzájem znají, nebo ani jeden z dvojice nezná toho druhého.
Hostitel chce posadit každého hosta buď v hale, nebo v obývacím
pokoji. Navrhněte algoritmus, který určí, kolika způsoby může
hostitel rozmístit své hosty do obou místností tak, aby se
v rámci každé místnosti všichni navzájem znali.
Vstupem algoritmu (programu) je počet hostů N, N <= 100, a dále seznam těch dvojic hostů, kteří se spolu znají. Pro jednodušší zadávání vstupních dat si jednotlivé hosty označíme celými čísly od 1 do N, takže na vstupu bude zadán seznam dvojic čísel. Výsledkem bude jediné číslo udávající počet možných rozdělení hostů.
Program bude číst všechna vstupní data z textového souboru NAKLAD.IN. Na prvním řádku souboru je uvedeno jedno kladné celé číslo C představující nosnost auta, C <= 10000. Druhý řádek obsahuje jediné kladné celé číslo N určující počet nabízených výrobků, N <= 1000. Následující řádky souboru NAKLAD.IN obsahují N kladných celých čísel - hmotností jednotlivých výrobků (menších než 10000).
Do výstupního souboru NAKLAD.OUT program zapíše jediný řádek
s výsledkem výpočtu. Výsledkem bude slovo ANO, pokud je možné
vybrat z nabídky takovou skupinu výrobků, aby byl součet jejich
hmotností roven přesně C. V opačném případě program napíše do
výstupního souboru slovo NE.
ANO, neboť auto o nosnosti 1000 kg přesně
zaplníme, pokud naložíme výrobek o hmotnosti 800 kg a oba
nabízené výrobky o hmotnostech 100 kg.
P-I-3 Okna
Na počítači máme nainstalován operační systém MO-P-Windows
pracující v grafickém rozlišení 300 x 200 bodů. Momentálně máme
spuštěno několik aplikací a na obrazovce je zobrazeno jejich
N oken. Každé okno je obdélníkové (příp. čtvercové), známe přesné
umístění a velikost jednotlivých oken. Okna se mohou na obrazovce
částečně nebo úplně překrývat.
Chceme spustit další aplikaci, která potřebuje zobrazit jedno nové okno. Známe velikost nového okna a požadujeme, aby na obrazovce nezakrylo ani část žádného z oken, která jsou tam již zobrazena. Napište program, jenž pro nové okno najde vhodné umístění na obrazovce, nebo případně oznámí, že dostatečně velké volné místo neexistuje.
Program čte vstupní data z textového souboru OKNA.IN. Na prvním řádku souboru je zadán počet již zobrazených oken N. Následuje N řádků specifikujících velikost a umístění jednotlivých oken. Pro každé z oken jsou zadána čtyři celá čísla x1, y1, x2, y2 představující souřadnice bodu na obrazovce [x1,y1], který tvoří levý horní roh okna, a bodu [x2,y2], v němž leží pravý dolní roh okna. Souřadnice bodů na obrazovce se zadávají tak, že bod v levém horním rohu celé obrazovky má souřadnice [0,0] a bod v pravém dolním rohu má souřadnice [299,199]. První souřadnice nějakého bodu na obrazovce znamená vodorovnou vzdálenost tohoto bodu od levého okraje obrazovky, druhá souřadnice určuje svislou vzdálenost bodu od horního okraje obrazovky. Poslední řádek vstupního souboru OKNA.IN obsahuje dvě celá čísla určující velikost nově umisťovaného okna (nejprve šířka, pak výška okna). Oba rozměry nového okna jsou vyjádřeny počtem bodů v používaném grafickém zobrazení.
Výsledek výpočtu programu zapíše na jeden řádek do výstupního
textového souboru OKNA.OUT. Výsledkem bude buď dvojice čísel,
která znamená souřadnice levého horního rohu nalezeného
přípustného umístění pro nové okno (libovolného jednoho umístění,
je-li více možností), nebo slovo NELZE, pokud takovéto okno
nelze na obrazovku umístit. Požadavek, aby se nové okno
nepřekrývalo s žádným z ostatních oken znamená, že žádný hraniční
bod nového okna nesmí ležet v jiném okně ani na jeho hranici.
P-I-4 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ž Om a hradel H1 až Hk. Každý ze vstupů hradla Hi je přímo připojen na některý ze vstupů sítě Ii 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ě.
| XOR | Y | ||
| 0 | 1 | X | 0 | 0 | 1 |
| 1 | 1 | 0 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | XOR | XOR | XOR | XOR | XOR | XOR | XOR | Výstup |
Příklad: Je-li N=4 a na jednotlivých vstupech sítě jsou zadány hodnoty 6, 3, 7, 3, musí mít výstup A hodnotu 3 a výstup B hodnotu 7.
Příklad: Pro k=3 bude mít kombinační síť 7 vstupů a 3 výstupy. Vstupy jsou označeny čísly 0, 1, 2, 3, 4, 5, 6. Pokud na jednotlivé vstupy zadáme hodnoty (po řadě podle čísel vstupů) 0, 0, 0, 1, 0, 1, 1, musí výstupy sítě nabýt hodnot po řadě 0, 1, 1. Hodnota 1 je totiž na vstupech číslo 3, 5 a 6, nejmenším z těchto čísel je 3 a zápis čísla 3 ve dvojkové soustavě zní 011. Na každém z výstupů se objeví jedna cifra tohoto dvojkového zápisu (se zachováním pořadí cifer).