Zbývá nám spočítat čas hi. Jestliže výrobní operace i nemá žádné předcházející operace, můžeme ji okamžitě spustit. Hodnota hi je v takovém případě přímo rovna délce trvání operace i. Pokud operace i má nějaké předcházející operace p1,p2,...,pk, je třeba vykonat nejprve tyto předcházející operace. Výrobní operace i může začít nejdříve v čase, který je maximem z časů hp1, hp2,..., hpk. Když víme, kdy operace i začne a známe délku jejího trvání, umíme triviálně spočítat, kdy skončí.
Hodnoty hi budeme počítat rekurzívně. Program obsahuje rekurzívní
funkci urci_cas(i),
která spočítá hodnotu hi. Pokud operace i
nemá předchůdce, bude to jednoduše čas jejího trvání. Jestliže operace i
má nějaké předchůdce, spustí se funkce urci_cas pro každého
předchůdce operace i, z takto získaných časů se vezme maximum a k němu
se připočítá čas trvání operace i.
Navíc, jakmile vypočítáme hodnotu hi
pro nějaké i, uložíme si ji do pomocného pole. Když později zavoláme
funkci urci_cas pro stejné i znovu, tato funkce už nebude znovu
počítat, ale jednoduše vrátí už vypočítanou hodnotu z pole.
Nejprve dokážeme, že popsaný program vždy skončí. Předpokládejme, že bychom počítali nějakou hodnotu hi a při jejím výpočtu bychom potřebovali vypočítat nějakou hodnotu hj1 pro předcházející operaci j1. Při vśpočtu hj1 bychom potřebovali vypočítat nějakou hodnotu hj2 a tak bychom se vnořovali hlouběji a hlouběji, až bychom zjistili, že k výpočtu nějakého hjk potřebujeme znát hi. To by způsobilo nekonečné volání rekurze. Takovýto případ však může nastat jedině tehdy, jestliže není možné vykonat operaci i, protože operace i se může provést až po skončení j1 a j1 lze provést až po skončení j2 atd., a jk je možné vykonat až po skončení i. Dostali jsme tedy cyklus, takže i není možné provést vůbec. V zadání je však uvedeno, že všechny operace lze provést, takže tento případ nemůže nastat a náš algoritmus vždy skončí.
Na závěr zhodnotíme výpočtovou složitost algoritmu. Předpokládejme, že pro každou operaci máme seznam předcházejících operací uložen ve spojovém seznamu. Označme n počet výrobních operací a m celkový počet předcházejících operací pro všechny operace v technologickém plánu výrobku. V první části algoritmu načítáme a ukládáme potřebné údaje. Tato část má časovou složitost O(m+n).
V druhé části algoritmu zavoláme funkci urci_cas(i) pro každé i
od 1 do n. V rámci každého takového volání se funkce může ještě dále
rekurzívně volat. Funkci urci_cas(i) voláme pro každé i jednou
z hlavní části algoritmu a pro každou operaci, pro níž je operace i
předchůdcem, tuto funkci opět zavoláme. Celkem se tedy vykoná m+n volání
funkce urci_cas. Pro každou hodnotu i se ale hodnota
urci_cas(i) počítá pouze jednu a při dalších voláních se jen najde
výsledek v poli v konstantním čase. Máme tedy přesně m volání funkce
urci_cas, která proběhnou v konstantním čase. Zbývajících n
volání počítá hodnotu. Při volání, které počítá hodnotu, se projde seznam
všech předcházejících operací a hledá se maximum z časů. Délka takovéhoto
volání je tedy úměrná počtu předcházejících operací (pokud zanedbáme čas
potřebný na vnořená rekurzivní volání). Celkový čas všech n volání,
která počítají hodnotu, bude tedy O(m+n). Všech m+n volání bude také
trvat dobu O(m+n). Celková časová složitost algoritmu je proto O(m+n).
Paměťová složitost je rovněž O(m+n).
Dvě poznámky na závěr. Pokud bychom vypočítané hodnoty ve funkci
urci_cas neukládali do pole, ale počítali bychom je vždy znovu,
dostaneme algoritmus s exponenciální časovou složitostí. Všimněte si, že
úlohu je možné jednoduše přetransformovat do teorie grafů - operace budou
představovat vrcholy grafu a hrany (orientované) povedou vždy od operace
k jejímu předchůdci. Úkolem je potom nalézt orientovanou cestu s největším
součtem časů ve vrcholech. Algoritmus, který jsme uvedli, je v grafové
terminologii pouze jednoduchou modifikací prohledávání do hloubky.
Nejprve si ukážeme jednodušší konstrukci řetězce. Mějme N-prvkovou abecedu {a1, a2, ..., aN}. Řetězec bude tvořen N-1 úseky tvaru a1a2...aN a ukončen bude znakem a1. Například pro abecedu {a,b,c} sestrojíme řetězec abcabca. Tento řetězec obsahuje celkem (N-1) N +1 = N2 - N +1 znaků. Pro N=15 tedy dostáváme řetězec délky 211.
Zbývá dokázat, že takto sestrojený řetězec skutečně obsahuje každou permutaci znaků abecedy jako vybraný podřetězec. Rozdělíme si tedy řetězec na N-1 úseků tvaru a2a3...aN. Mezi každými dvěma těmito úseky, stejně jako za posledním a před prvním z nich, se nachází znak a1. Vezměme nyní libovolnou permutaci znaků abecedy. Nejprve z této permutace vynecháme znak a1. Zbytek permutace je jistě vybraným podřetězcem našeho řetězce, neboť z každého úseku tvaru a2a3...aN můžeme vybrat právě jeden znak tak, abychom z j-tého úseku vybrali j-tý znak permutace různý od a1.
Nechť je nyní znak a1 umístěn v permutaci na i-tém místě, tzn. před ním leží i-1 znaků. Potom z řetězce vybereme v pořadí i-tý výskyt znaku a1. Před ním se nachází i-1 úseků tvaru a2a3...aN, a tedy a1 bude i ve vybraném podřetězci na i-tém místě. Dokázali jsme, že pro libovolnou permutaci znaků abecedy můžeme nalézt takový vybraný podřetězec našeho řetězce, který se této permutaci rovná.
Nyní si popíšeme jinou, složitější konstrukci. Budeme vytvářet posloupnost řetězců T(1), T(2), T(3),..., přičemž T(N) obsahuje všech N! permutací N znaků jako podřetězce. Ukážeme si způsob, jak z T(N) sestrojit T(N+1) (pro N >= 3).
Řetězce T(1), T(2) a T(3) zvolíme pevně: T(1)=a1, T(2)=a1a2a1 a T(3)=a1a3a2a1a3a1a2. Jsou to nejkratší možné řetězce pro N=1, 2, 3 (to lze snadno dokázat ověřením všech možností).
Mějme nyní abecedu {a1, a2,... ,aN}. K řetězci T(N) vytvoříme posloupnost základních bodů. První základní bod řetězce T(N) je index prvního výskytu znaku a1 v T(N). Pro i>1 je i-tým základním bodem index prvního výskytu znaku ai za (i-1)-ním základním bodem v řetězci. Například v T(3)=a1a3a2a1a3a1a2 je posloupnost základních bodů (1,3,5).
Algoritmus pro konstrukci řetězce T(N) z řetězce T(N-1):
Řetězec T(N) sestrojený naším algoritmem (pro N >= 3) má délku N2-2N+4. Toto tvrzení dokážeme matematickou indukcí. Délka řetězce T(3) je 7, což je rovno 32-2x3 + 4. Předpokládejme nyní, že délka T(N-1) je (N-1)2-2(N-1)+4 a dokážeme, že potom délka řetězce T(N) je N2-2N+4. Řetězec T(N) vznikl přidáním 2N-3 znaků do řetězce T(N-1), jeho délka je (N-1)2-2(N-1)+4 + 2N-3 = N2 -2N+4. Dokázali jsme tedy, že délka řetězce T(N) je skutečně N2-2N+4.
Nakonec je třeba dokázat, že řetězec T(N) obsahuje všech N! permutací znaků abecedy jako podřetězce. Tento důkaz je poměrně zdlouhavý, takže uvedeme jen základní myšlenku. Řetězec T(N) rozdělíme na úseky. První úsek začíná prvním základním bodem a končí druhým základním bodem. Pro 2 <= i <= N-1 bude i-tý úsek začínat znakem a1, který je hned za i-tým základním bodem, a končit znakem ai, který se vyskytuje poprvé za (i+1)-ním základním bodem.
Matematickou indukcí (vzhledem k N) lze dokázat, že každý z takto vytvořených úseků obsahuje znaky a1,a2... aN a začíná znakem a1. Řetězec obsahuje N-1 takovýchto úseků a každý z nich obsahuje právě jeden základní bod s výjimkou prvního úseku, který obsahuje dva základní body. Další vlastností dvou sousedních úseků i-tého a (i+1)-ního je jejich vzájemné překrytí ve dvou znacích, a to a1 a ai.
Nechť má naše permutace znak a1 na i-tém místě. Uvažujme nejprve případ že i <= N-1. V permutaci vybereme první výskyt znaku a1 z i-tého úseku řetězce T(N). Z i-tého úseku je možné použít ještě jeden znak, neboť se v něm vyskytují všechny znaky, a to až za vybraným znakem a1. Před i-tým úsekem je i-1 úseků a za ním je N-i-1 úseků. Při výběru jednoho znaku z každého úseku tedy dostaneme všechny permutace se znakem a1 v i-té pozici. Překrytí sousedních úseků nezpůsobí problémy, protože při výběru znaku a1 z i-tého úseku je možné všechny ostatní znaky a1 ignorovat a další společné znaky se stávají hraničními prvky úseků. Hraniční prvek je považován za prvek patřící jen do jednoho úseku.
Zbývá dokázat tvrzení v případě, že a1 je v permutaci na N-tém místě. V tomto případě řetězec T(N) rozdělíme na úseky se základními body jako hraničními body úseků. Počet úseků je N-1 a každý z nich obsahuje znaky a1, a2,... aN. Jestliže na poslední místo vybereme poslední výskyt znaku a1 v řetězci T(N), tento znak nepatří do žádného z výše uvedených úseků. Řetězec T(N) tedy obsahuje všechny permutace se znakem a1 na posledním místě.
Uvedený algoritmus pro N=15 dává následující řetězec délky 199:
pruzkum(i,j),
která nám říká, zda je a[i]<a[j] nebo a[j]<a[i].
Ukážeme si nejprve řešení pro sudé n. Rozdělíme všechny prvky pole
do dvojic a v každé dvojici prvky porovnáme (pomocí funkce
pruzkum). Prvky se nám rozdělí na dvě podmnožiny -- do množiny X
dáme ty, které byly při porovnávání v dvojici větší a do množiny Y ty,
které byly při porovnávání menší. Je zřejmé, že žádný prvek z množiny X
nebude nejmenším prvkem v poli, neboť existuje aspoň jeden menší prvek
(ten, který s ním byl ve dvojici). Proto při hledání minima stačí hledat
mezi prvky množiny Y. Podobně žádný prvek z Y nebude největším
prvkem pole a proto stačí maximum hledat mezi prvky množiny X.
Nejmenší z prvků množiny Y najdeme jednoduše. V proměnné min si
budeme pamatovat nejmenší dosud nalezený prvek. Na začátku to bude
libovolný prvek množiny Y. Potom budeme nejmenší dosud nalezený prvek
porovnávat vždy s dalším a dalším prvkem množiny Y. Pokaždé, když bude
porovnávaný prvek menší než prvek uložený v proměnné min,
stane se
on dosud nejmenším nalezeným prvkem (uloží se do proměnné min).
Podobně budeme hledat i největší prvek v množině X.
V případě, že n je liché, budeme postupovat stejným způsobem, jenom do dvojic rozdělíme jen prvních n-1 prvků a poslední prvek nakonec přidáme do množiny X i do množiny Y. V některých případech můžeme ještě jedno porovnávání ušetřit -- pokud se tento poslední prvek stane nejmenším prvkem množiny Y (a tudíž i nejmenším prvkem celého pole), pak ho můžeme z množiny X vynechat, neboť jistě nebude současně největším prvkem. Případ n=1 ošetříme zvlášť. V tomto případě není třeba nic porovnávat - jediná strana má současně nejvyšší i nejnižší preference.
Nyní spočítáme, kolik porovnání v nejhorším případě vykonáme pro dané
n. Je-li n sudé, vznikne nám n/2 dvojic. Pro každou dvojici provedeme
jedno porovnání, abychom zjistili, který prvek je větší. Množiny X a Y
budou mít každá n/2 prvků. Pro nalezení minima (nebo maxima) v množině
s x prvky použijeme x-1 porovnání (do proměnné min uložíme
nejprve první prvek, potom tuto proměnnou postupně porovnáme se všemi
ostatními x-1 prvky). K nalezení minima v množině Y tedy potřebujeme
n/2-1 porovnání a k nalezení maxima v množině X dalších n/2-1
porovnaní. Celkový počet porovnání tedy bude
n/2+(n/2-1)+(n/2-1)=(3n-4)/2
Pro liché n budeme mít (n-1)/2 dvojic, takže na začátku vykonáme (n-1)/2 porovnání ve dvojicích. Množiny X a Y však budou mít (n-1)/2+1 prvků, takže k nalezení minima nebo maxima z takovéto množiny potřebujeme (n-1)/2 porovnání. Celkový počet provedených porovnání proto bude (n-1)/2+(n-1)/2+(n-1)/2=(3n-3)/2
Došli jsme k závěru, že pro n sudé vykonáme nejvýše (3n-4)/2 porovnání a pro n liché nejvýše (3n-3)/2 porovnání. Tento výsledek lze zapsat i jedním vzorcem s použitím horní celé části ({}) a dolní celé části ([]) takto: 2{n/2} + [n/2] - 2
Na závěr pár slov o implementaci popsaného algoritmu. Množiny X a Y
nebudeme vytvářet na začátku výpočtu celé, ale průběžně. Nejprve
vezmeme první dva prvky v poli, porovnáme je a menší z nich se stane
počáteční hodnotou proměnné min, zatímco větší bude počáteční
hodnotou proměnné max. Potom budeme brát vždy další a další dvojici,
porovnáme vždy její prvky navzájem, následně menší z nich porovnáme
s proměnnou min (a pokud bude třeba, tak obsah min změníme)
a větší porovnáme s proměnnou max. Pro lichá n je třeba nakonec
zvlášť zpracovat poslední prvek. Takto naprogramovaný algoritmus bude mít
lineární časovou složitost (tzn. O(n)) a konstantní paměťovou složitost.
Zbývá už jen popsat, jak násobíme registr R0 dvěma. Jednou možností by bylo uložit do některého dalšího registru hodnotu 2 a potom použít algoritmus násobení uvedený v příkladu ve studijním textu. My však využijeme trochu zjednodušený algoritmus, který lze použít pouze pro násobení konstantou. V cyklu budeme po jedné snižovat hodnotu R0, dokud neklesne na nulu, a při každém snížení R0 dvakrát zvýšíme o 1 hodnotu registru R2. Po skončení cyklu máme v R2 dvojnásobek hodnoty, kterou jsme měli původně v R0. Zbývá už jen přesunout hodnotu z R2 zpět do R0, což provedeme dalším cyklem, který vždy jednou sníží R2 a zvýší R0, dokud nebude v R2 nula.
Náš stroj bude pracovat tak, že v cyklu bude snižovat registr R1 a počítat další člen Fibonacciho posloupnosti, dokud nebude v R1 nula. Po k průchodech tohoto cyklu bude registr R0 obsahovat Fk a registr R2 bude obsahovat Fk-1. Celkem se provede n průchodů, takže stroj správně vypočítá hodnotu Fn.
Před prvním prováděním cyklu (tj. po nula průchodech) potřebujeme mít v registru R0 číslo F0=1 a v registru R2 číslo F-1=0. Toho dosáhneme snadno příkazem R0++.
Zbývá nám prozkoumat, co potřebujeme provádět v těle cyklu. V registru R0 máme číslo Fk a v registru R2 číslo Fk-1. Chceme dosáhnout toho, aby v registru R0 bylo Fk+1=Fk+Fk-1, tj. součet registrů R0 a R2, a v registru R2 aby bylo Fk, tj. číslo, které bylo původně v R0. Budeme postupovat tak, že hodnotu v R0 přičítáme k registrům R2 a R3 (a to tak, že budeme v cyklu R0 snižovat, dokud neklesne na nulu, a pokaždé při tom zvýšíme R2 a R3). Po skončení této operace máme v R0 nulu, v R2 máme Fk+1 a v R3 máme Fk. Potřebujeme nyní ještě obsahy registrů přemístit tak, abychom do R0 dostali obsah R2 a do R2 obsah R3. To provedeme opět obvyklým způsobem (dvěma "přesýpacími" cykly).