IB002 - 1. sada domácich úloh
Úloha je určená pre študentov sem. skupín IB002/11, IB002/12. Každý, kto má túto skupinu
riadne zapísanú, je povinný odovzdať vypracované obidva príklady. Študenti, ktorí nepatria do
týchto skupín môžu úlohu odovzdať a majú nárok na opravenie, nie však na bonusové body.
Termín odovzdania: 5.4. do 23:42
Zpôsob odovzdania: elektronicky do odovzdávarne v ISe (pdf dokument formátu A4) alebo
papierovo na mojích cvičeniach. Nezabudnite i v elektronickej verzii uviesť meno a UČO.
Vypracovanie ako dvojica: Úlohy je možné vypracovať ako dvojica. Dvojica odovzdáva len
jedno riešenie podpísané oboma menami. Body dostanú obaja z dvojice. Každý príklad je
hodnotený samostatne, je teda možné vytvoriť rozdielne páry pre prvý a druhý príklad.
Hodnotenie: Základ je 0 bodov. Za výborne vypracované riešenia môžete získať až dva body za
príklad. Za neodovzdaný príklad, za riešenie, ktoré je extrémne nedostatočné (prázdny papier) a
za opisovanie naopak 2 body za príklad strácate.
Príklad 1
Študenti prvého ročníka Fakulty informatiky sa rozhodli, že si spravia skupinovú fotku, aby
mohli svojim vnúčatám ukazovať, akí boli v mladosti kockatí. Na fotke mali stáť v jednom
rade medzi sebou pomiešaní študenti počítačovej grafiky, spracovania prirodzeného jazyka a
teoretickej informatiky. Ako to už býva zvykom, študenti teoretickej informatiky mali s celým
fotením problém. Odmietli sa usmievať, pokiaľ nebola splnená zvláštna podmienka, ktorej
dôvodom ako obvykle nikto iný nerozumel: každý teoretický informatik chcel mať niekde v rade
naľavo od seba nižšieho študenta grafiky a niekde napravo od seba vyššieho študenta spracovania
prirodzeného jazyka (nemuseli stáť bezprostredne pri ňom). Podmienke sa nakoniec po dlhom
organizovaní a presúvaní podarilo vyhovieť a vznikla skutočne dokonalá fotka. Fotografa však to
naťahovanie štvalo a preto radšej pred ďalším fotením vyhlásil súťaž. Každému študentovi, ktorý
mu prinesie algoritmus, ktorý s čo najlepšou časovou zložitosťou zistí, či zoradenie vyhovuje
podmienke, sľúbil vybaviť bonusové body do predmetu IB002.
Vstupom sú dve postupnosti A a B, každá dĺžky n (počet študentov), kde prvý prvok zodpovedá
najľavejšiemu študentovi. A udáva obor štúdia a obsahuje čísla z množiny 1, 2, 3, kde 1 predstavuje
študenta grafiky, 2 študenta teoretickej informatiky a 3 študenta spracovania prirodzeného jazyka.
B obsahuje čísla udávajúce výšky študentov v centimetroch. Pre piateho študenta zľava je teda
jeho obor uložený v A[5] a jeho výška v B[5]. Výstupom má byť true alebo false podľa toho,
či je podmienka teoretických informatikov v tejto postupnosti splnená.
Navrhnite pre fotografa algoritmus splňujúci podmienky, zdôvodnite jeho korektnosť a tiež určte
a zdôvodnite jeho asymptotickú časovú zložitosť (nie je nutné dokazovať formálne, istú úroveň
by ale zdôvodnenie mať malo).
Príklad 2
Nasledujúci algoritmus zoradí číselnú postupnosť a = (a1, . . . , an) uloženú v poli A
vzostupne.
i := n - 1;
while (i > 0) do
begin
x := Ai;
j := 0;
while (j < n - i) && (Ai+j+1 < x) do
begin
Ai+j := Ai+j+1;
j := j + 1
end;
Ai+j := x;
i := i - 1
end
a) Formulujte vstupnú podmienku  a výstupnú podmienku .
b) Vysvetlite slovne princíp fungovania algoritmu.
c) Vyberte si 3 rôzne stavy výpočtu algoritmu na postupnosti (1, 9, 2, 5, 8, 6) ihneď po prevedení
piateho riadku (pred vnútorným cyklom) a zapíšte hodnoty všetkých programových
premenných v týchto miestach.
d) Nájdite invarianty pre vonkajší a vnútorný cyklus a dokážte s ich pomocou parciálnu
korektnosť vzhľadom k podmienkam  a .
e) Určte časovú zložitosť výpočtu algoritmu v najhoršom prípade a to presne (počítajte ako
operáciu len priradenie do premennej) i asymptoticky.