LOG-SPACE algoritmy

Na prácu s $n$-prvkovým poľom určite treba aspoň rádovo $\lceil\log_2 n\rceil$ bitov pamäte. Toto je teda v istom zmysle najmenšia prakticky zaujímavá pamäťová zložitosť programov $S(n)$.

• Každá použitá premenná musí byť jednoduchého celočíselného typu (napr. int)
• U celočíselných premenných nám nebude záležať na presnom rozsahu, nemusí vás teda napr. trápiť, či sú 32-bitové alebo 64-bitové. Namiesto toho si povolený rozsah hodnôt, ktoré sa do premenných zmestia, definujeme nasledovne: Nech $n$ je veľkosť vstupu (teda napr. počet čísel na vstupe). Potom do premenných môžeme ukladať len hodnoty ktoré sú polynomiálne veľké v závislosti od $n$. Môžeme mať teda napr. premennú, ktorá bude nadobúdať hodnoty $−n .. n$, hodnoty $−3n^5 .. 3n^5$, čí len hodnoty $−4 .. 7$. Nesmieme však už mať premennú nadobúdajúcu napr. hodnoty $0 .. 2^n$. Pre pohodlie budeme aj typy char a boolean považovať za celočíselné, a teda povolené. Žiadne iné typy premenných (teda napr. ani polia alebo ukazovatele) nie sú povolené.
• Výnimku z predchádzajúcich pravidiel tvoria vstup a výstup. Vstup programu bude dostupný v nejakých špeciálnych premenných (zväčša to budú polia), ktoré môže váš program len čítať. A podobne výstup bude váš program ukladať do iných špeciálnych premenných, do ktorých smie len zapisovať.
• Vaše programy nesmú používať rekurziu.

Príklad 1

Nájdite maximum v poli čísel.

from random import randrange

A = [randrange(10, 100) for _ in range(randrange(10,50))] #vstup
B = [None] #vystup

print(*A)
print(*B)

31 34 50 45 92 73 61 22 42 38 89 98 77 18 64 25 57 76 93 58 52 61 67 45 10 70 63 66 39 49 22 81 29 42
None

Príklad 2

Nájdite maximum v poli čísel a aj jeho index.

Príklad 3

Nájdite v poli čísel to, ktoré sa tam vyskytuje najčastejšie.

from random import randrange

A = [randrange(1,6) for _ in range(randrange(10, 50))] #vstup
B = [None] #vystup

print(A)

[2, 1, 1, 1, 2, 5, 1, 2, 2, 2, 5, 5, 2, 4, 1, 3, 1, 2, 5, 5, 5, 4, 2, 2, 4, 4, 4, 1, 1, 4, 4, 3, 3, 1, 3, 1, 2, 3, 3]

• CountingSort - početnosť a potom maximum z nich

  $T(n) \in O(n+k)$

  $S(n) \in O(k)$

  problém pre vstup $n=2$ ... $0, 10^{18}$

• usporiadanie a početnosti počítame priebežne jedným prechodom cez usporiadané pole

  $T(n) \in O(n \cdot \log n )$

  $S(n) \in O(n)$

Príklad 4 - Čínsky výškomer (PAZ1b/palma.strom.sk)

Nájdite medián z výšok v rozsahu $0..130$.

Úloha 1

Vypíšte usporiadané pole.

from random import randrange

A = [randrange(1,6) for _ in range(randrange(10, 50))] #vstup
B = [None for _ in A] #vystup

Úloha 2

Na vstupe je číslo $n$ a dve polia $A[0..n-1]$ a $B[0..n-1]$ obsahujúce postupnosti čísel. Napíšte log-space program, ktorý zistí, či sa tieto postupnosti líšia len poradím prvkov. Teda napr. pre polia $A= (3,1,4,1,5)$ a $B= (1,4,5,1,3)$ je odpoveď áno, pre $A= (1,2,2)$ a $B= (2,1,1)$ je odpoveď nie.

• bez obmedzenia ... usporiadame a porovnáme prvok za prvkom

• pre každý prvok z A spočítame početnosti v oboch poliach a porovnáme

Úloha 3

Majme dva log-space programy $F$ a $G$. Program $F$ dostane vstup v poli $A[0..n-1]$ a vyrobí z neho výstupné pole $B[0..n-1]$. Program $G$ dostane na vstupe pole $B$, ktoré vyrobil program $F$, a svoj výstup zapíše do výstupného poľa $C[0..n-1]$. Dokážte, že existuje log-space program $H$, ktorý na vstupe dostane pole $A$ a na výstupe vyrobí zodpovedajúce pole $C$.

$F: A \rightarrow B$

$G: B \rightarrow C$

---

$H: A \rightarrow C$

• Program $H$ má dať výsledok pole $C$, tak nech funguje ako program $G$ ... vždy keď program $G$ potrebuje hodnotu $B[i]$, tak spustíme celý program $F$ a do premennej si zapíšeme to, čo by zapísal $F$ do $B[i]$, ostatné zápisy do $B$ ignorujeme.

Úloha 2 - pokračovanie

• usporiadame obe postupnosti a porovnáme výsledky ... namiesto toho vieme určiť $k$-te číslo v usporiadaní - porovnáme k-te čísla v $A$ aj v $B$

Úloha 4

Napíšte log-space program, ktorý vynásobí dve veľké čísla zadané ako postupnosti cifier ($n$-ciferné).

A=(2)
B=(3)
C=(6, 0)

A=(9)
B=(9)
C=(1, 8)

A=(7,3,1) #n ... cislo 137
B=(3,2,1) #n ... cislo 123

137*123

16851

C=(1,5,8,6,1,0) #2n

Úloha 5

Daný je neorientovaný graf bez cyklov, tzv. les. Napíšte log-space program, ktorý na vstupe dostane popis lesa a dva jeho vrcholy a zistí, či dotyčné dva vrcholy ležia v tom istom komponente súvislosti.

Úloha 6

Napíšte log-space program, ktorý pre danú permutáciu zistí, koľko má cyklov. Vstupom je celočíselná premenná $n$ a pole $P[0..n-1]$. Výstupom je celočíselná premenná $c$.

Na permutáciu sa môžeme dívať ako na orientovaný graf, ktorého vrcholmi sú čísla $0$ až $n-1$ a v ktorom máme pre každé $i$ orientovanú hranu z vrcholu $i$ do vrcholu $P[i]$.

Napr. permutácia (2,5,4,3,0,1) má tri cykly (0,2,4), (1,5) a (3) (komponenty prislúchajúceho grafu).

Úloha 7

Napíšte log-space program, ktorý pre zadaný strom a dva jeho vrcholy $u$ a $v$ vypočíta vzdialenosť dotyčných dvoch vrcholov – teda najmenšie číslo $k$ také, že na to, aby sme sa dostali z $u$ do $v$, stačí postupne prejsť po $k$ hranách daného stromu.

Nech $n=5$, teda máme strom s 5 vrcholmi a 4 hranami. Nech ďalej $A[0..3] = (0,3,2,2)$ a $B[0..3] = (3,1,3,4)$, teda v našom strome máme hrany 0-3, 3-1, 2-3 a 2-4.Pre $u= 2$ a $v= 4$ by bolo správnym výstupom $d= 1$, keďže medzi vrcholmi 2 a 4 máme priamu hranu. Pre $u= 4$ a $v= 0$ by bolo správnym výstupom $d= 3$. Najkratšia cesta z vrcholu 4 do vrcholu 0 vedie cez vrcholy 2 a 3.

Úloha 8

Rozdelili sme veľký súbor na $n$ častí, každá bola zaslaná v jednom pakete. Do cieľa dorazilo v "náhodnom" poradí $n-1$ z nich. Určte, ktorú časť treba poslať znova.

from random import shuffle

pole = list(range(1, 11))
shuffle(pole)
print(pole[:-1])

[8, 1, 7, 10, 3, 6, 5, 9, 4]

A = pole[:-1] #vstup
B = [None] #vystup

• triviálne riešenie by bolo pamätať si pole $n$ logických hodnôt ... nemôžeme

• postupne hľadáme všetky čísla od $0$ po $n-1$ ... časová zložitosť je $O(n^2)$

• kontrolný súčet

Algoritmy

ÚINF/TVY/15 - Teória vypočítateľnosti

ÚINF/ANP/15 - Algoritmicky neriešiteľné problémy

ÚINF/PDS1/21 - Paralelné a distribuované systémy

ÚINF/KOPR/19 - Konkurentné programovanie

ÚINF/KVAD/15 - Kvantové algoritmy

ÚINF/APA1/21 - Aproximačné a pravdepodobnostné algoritmy

Aproximačné - väčšinou polynomiálne algoritmy riešiace NP-úplný problém, pričom nemusia dať optimálny výsledok, ale len jeho $c$-aproximácia (násobok)

Pravdepodobnostné - odpoveď iba s určitou pravdepodobnosťou, napr. s jednostrannou chybou (rozhodovací problém - asi áno/určite nie) ... je číslo $x$ prvočíslo?

FPT algoritmy (fixed-parameter tractable) ... polynomiálne od veľkosti vstupu, ale exponenciálne od parametra $k$

http://fptschool.mimuw.edu.pl/slides/lec2.pdf

Exaktné exponencionálne algoritmy - Maximálna nezávislá množina

• triviálne $O(m \cdot 2^n)$
• ak max. stupeň $\Delta \leq 1$, tak vyberieme izolované vrcholy a z každej hrany jeden vrchol. Ináč vrchol s maximálnym stupňom $v$, riešením je maximum z MNM bez vrchola ($n-1$) a MNM bez vrchola $v$ a jeho susedov+vrchol $v$ ($n-3$) ... $T(n) = T(n-1)+T(n-3)+O(n)$, teda $T(n) \in O(1.4656^n)$.
• ak vyberieme vrchol $v$ najmenšieho stupňa $k$, tak aspoň jeden z vrcholov $\{v\} \cup N_v$ musí byť v optimálnom riešení. Vyskúšame všetky možnosti, veľkosti najviac $n-(k+1) \leq n-3$, teda $T(n)=T(n-3).n$, t.j. $O\left(3^{\frac{n}{3}}\right) = O(1.4423^n)$

úloha 1

V úlohe o maximálnej nezávislej množine uvažujme teraz len vstupy, v ktorých platí,že každé zviera má nanajvýš dva konflikty. Nájdite algoritmus s polynomiálnou časovou zložitosťou, ktorý pre ľubovoľný takýto vstup vypočíta, koľko najviac zvierat vieme pustiť do výbehu.

import numpy as np
r = np.roots([1, -1, 0, -1])
print('Korene:', r)
r = r[np.isreal(r)]
print('Zložitosť:', max(np.real(r[r > 0])))

Korene: [ 1.46557123+0.j         -0.23278562+0.79255199j -0.23278562-0.79255199j]
Zložitosť: 1.4655712318767682

• izolované vrcholy zoberieme
• na ceste každý druhý začneme krajným $\left\lceil \frac{d}{2} \right\rceil$, kde $d$ je dĺžka cesty (počet hrán)
• v cykle každý druhý $\left\lfloor \frac{d}{2} \right\rfloor$

úloha 2

Ukážte, ako pomocou algoritmu úlohy 1 zlepšiť algoritmus MNM. Akú časovú zložitosť bude mať algoritmus, ktorý takto dostanete?

$T(n) = T(n-1)+T(n-4)+O(n)$, teda $T(n) \in O(1.3803^n)$

viac na OI-35-A-?-4 [http://oi.sk/archiv/2019/sl-2019-1-zad-A.pdf]

Online algoritmy

vstup dostávame po častiach (blokoch), nie celý

• Dvaja zlodeji majú vrece s lupom. Vo vreci je $n$ predmetov. Brali ich potme, takže o nich nič nevedia. Zlodeji si tento lup teraz idú rozdeliť. Robia to tak, že vždy vytiahnu z vreca jeden predmet, pozrú sa na jeho cenu a rozhodnú sa, kto ho dostane. Zlodeji by si chceli veci rozdeliť čo najviac rovnomerne. Presnejšie, ich cieľom je, aby súčet cien na drahšej kôpke bol čo najmenší.
• Objednávanie pacientov u lekára (postupne ako volajú).
• Festivalové leto - lístky sa začínajú predávať v rôznych termínoch a rýchlo sa vypredajú

kompetetívna zložitosť je porovnanie k offline algoritmu (ak by sme mali k dispozícii celý vstup) ... $c$-kompetetívny algoritmus

• Dokážte, že algoritmus, ktorý dá všetky predmety jednému lupičovi, je 2-kompetitívny.
• Nájdite 3/2-kompetitívny algoritmus pre tento problém.
• Dokážte, že žiadny algoritmus pre tento problém nemôže byť lepší ako 3/2-kompetitívny.