Úloha 1

Pre danú postupnosť $pole[]$ a indexy $a$, $b$ vypočítajte súčet $pole[a]+pole[a+1]+\dots+pole[b]$.

Ako efektívne vypočítať súčet hodnôt na intervale?

Priamočiare riešenie je prejsť všetky hodnoty a spočítať súčet hodnôt

In [1]:
#vstupne hodnoty
pole = [16, 19, 40, 26, 19, 39, 26, 18, 18, 21, 32, 12, 27, 8, 25, 18, 18, 17, 42, 4]
a, b = 2, 6
#vypocet suctu od tretieho po siedmy prvok (od indexu 2 po 6)
sucet = 0
for index in range(a, b+1): #rozsah od a po b
    sucet += pole[index]
print(sucet)
150

To isté je možné v jazyku Python vypočítať aj pomocou funkcie sum:

In [2]:
sum(pole[a:b+1])
Out[2]:
150

Čo ak potrebujeme takýchto súčtov počítať veľa? Napríklad aké sú vzdialenosti medzi mestami počas jazdy vlakom. Hodnoty uvedené vyššie sú vzdialenosti na jednotlivých úsekoch na trase Košice-Bratislava. Na každý zakúpený lístok sa vytlačí prejdená vzdialenosť na trase, ktorá určuje výslednú cenu.

Aby sa nemuselo zakaždým počítať (čo by malo zložitosť $\Theta(n.q)$, kde $n$ je počet prvkov v poli a $q$ je počet otázok/lístkov), tak by sme mohli napr. všetky dvojice predpočítať do dvojrozmerného poľa $sucet[i][j]$ a potom odpovedať v konštantom čase. To vieme urobiť v čase $\Theta(n^2.n)=\Theta(n^3)$, ale aj dynamickým programovaním v čase $\Theta(n^2)$. Celková časová zložitosť by bola $\Theta(n^2+q)$, čo pri veľkom počte otázok ($q >> n$, teda $q$ je rádovo väčšie ako $n$) už bude efektívnejšie. Predpočítanie ako aj pamäťová zložitosť je $\Theta(n^2)$.

Dá sa to aj efektívnejšie?

Ak by sme sa pozreli na cestovný poriadok vlaku (cp.sk), tak by ste asi vzdialenosť z Margecian do Ružomberka (teda od indexu 2 po index 6) vedeli vypočítať asi aj z hlavy ako rozdiel $185-35=150$ R604Dargov-cp.sk

Prefixový súčet

Vidíme, že stačí si pamätať súčty od začiatku (posledný stĺpec vpravo na vyššie uvedenom obrázku), tzv. prefixové súčty, a potom rýchlo vypočítame súčet na intervale ako rozdiel dvoch hodnôt. Súčet od a po b, t.j. $sum([a:b+1])=sum([0:b+1)-sum([0:a])$, teda $sum([a:b+1]) = PS[b+1]-PS[a]$, keďže prefixový súčet začína nulou (aby sa dalo počítať aj od indexu nula, začiatku).

Tento súčet vieme vypočítať v čase aj v pamäti $\Theta(n)$, postupním pripočítavaním:

In [3]:
#vstup: pole, a, b
n = len(pole)
PS = [0 for _ in range(n+1)] #prefixovy sucet
for i in range(n):
    PS[i+1] = PS[i]+pole[i]
print(PS)
print(PS[b+1]-PS[a])
[0, 16, 35, 75, 101, 120, 159, 185, 203, 221, 242, 274, 286, 313, 321, 346, 364, 382, 399, 441, 445]
150

V jazyku Python to (bez úvodnej nuly) vieme vypočítaž aj použitím funckie accumulate z knižnice itertools:

In [4]:
import itertools
print(*itertools.accumulate(pole))
16 35 75 101 120 159 185 203 221 242 274 286 313 321 346 364 382 399 441 445

Úloha 2

Pri nákupoch cez verejné obstarávanie sa vyberá zvyčajne najnižšia cena. Ako overiť, či vysúťažená cena bola naozaj najnižšia? Predstavme si, že vláda objednala pre svojich občanov respirátory. Z dostupných zverejnených cien v rôznych dňoch overte, či nákup bol efektívny. Teda zistite najmenšiu cenu dostupnú v období zverejnenia verejného obstarávania (čo je niekoľko dní). Napríklad si vezmime vývoj ceny respirátora FPP2 na heureke: vývoj ceny respirátora FPP2 na heureka.sk

Aká bola minimálna cena v období 11/2019-12/2019 a aká v období medzi 22.3.2020 a 25.3.2020 ?

Nájsť minimum na súvislom úseku v poli môžeme obdobne ako súčet riešiť priamočiaro

In [5]:
pole = [1, 1, 1, 1, 1, 2, 19, 9]
a, b = 5, 7 #minimum na indexoch od 5 az po 7

m = pole[a] #zacneme prvym prvkom
for index in range(a+1, b+1): #postupne prechadzame dalsie prvky
    if pole[index] < m: #ak najdeme mensi prvok
        m = pole[index] #zaktualizujem si doteraz najmensi prvok
    #m = min(m, pole[index]) ... kratsi zapis pouzitim funkcie min
print(m)
2

V jazyku Python s použitím funkcie min priamo na "kúsok" (slice) poľa:

In [6]:
#minimum na intervale 4 az 5
a, b = 4, 5
print(a, '-', b, ':', min(pole[a:b+1]))
#minimum na intervale 5 az 7
a, b = 5, 7
print("{} - {} : {}".format(a, b, min(pole[a:b+1]))) #formatovanie retazca v Python 3
4 - 5 : 1
5 - 7 : 2

V prípade veľa otázok/dopytov na minimálnu cenu to zase nie je efektívne. Ako to zrýchliť?

"Prefixovým minimom" to nepôjde ... minimum na úseku $<a, b>$ nevieme určiť z miním na úsekoch $<0, a-1>, <0, b>$. Pomôže nám nasledujúca štruktúra.

Intervalový strom

Nad poľom (graficky) si vytvoríme úplný binárny strom a vyplníme tak, že hodnota vo vrchole bude minimum zo všetkých hodnôt v listoch v podgrafe z daného vrchola (grafová terminológia), teda minimum zo všetkých hodnôt v jeho podstrome. V intervalovom strome môžu byť použité aj funkcie max, sum. (Obrázok z interaktívnej vizualizácie) Ukladať si daný strom môžeme do poľa rovnako ako haldu. Na obrázku sú pri vrcholoch aj čísla udávajúce reprezentujúci interval podstromu daného vrcholu. Intervalový strom Najmenšiu hodnodu na intervale a dokonca aj aktualizáciu, teda zmenu hodnoty prvku vieme potom urobiť v čase $\Theta(\log n)$. Zmena hodnoty prvku (v poli/liste stromu) znamená aktualizáciu všetkých hodnôt smerom nahor (ku koreňu). Pre najmenšiu hodnotu na intervale treba prejsť niektoré vrcholy - podstromy. Napríklad pre interval 6. až 8. hodnoty treba vybrať minimum z dvoch červenou zvýraznených hodnôt: Výpočet na intervale intervalového stromu Pre 15 hodnôt a interval 3-15 by to vyzeralo nasledovne: Výpočet na intervale intervalového stromu n=15 Vidíme, že sa doplní na veľkosť mocniny dva a zoberú sa do úvahy len 4 červeno zvýrazné prvky - tie sa nájdu prechodom od krajného prvku ku koreňu (zvýraznené modrou farbou, teda dvakrát výška stromu), t.j. v časovej zložitosti $\Theta(2.\log n) = \Theta(\log n)$.

Úloha 3

Vrátime sa k ceste vlakom. Úlohou je teraz implementovať rezervačný systém miesteniek. Máme zadanú kapacitu vlaku a postupne požiadavky na kúpu lístka (medzi 2 stanicami pre $x$ ľudí).

Obsadenosť si môžeme uložiť do intervalového stromu. Zistenie, či je voľná kapacita na zakúpenie lístka vieme urobiť nájdením maximálnej obsadenosti na intervale medzi 2 stanicami a porovnaním s celkovou kapacitou vlaku a počtom ľudí. Po zakúpení by ale bolo potrebané aktualizovať viacero hodnôt a celý podstrom nad nimi, čo by zhoršilo časovú zložitosť. Efektívne sa to dá riešiť zaznamenaním prírastkov do všetých červených vrcholoch ($+x$). Podrobnejšie informácie nájdete v úlohe z Olympiády v informatike OI-2007-A-I-2 so vzorovým riešením.

In [ ]: