- https://www.wikiwand.com/en/Prefix_sum
- flags = bitové značení, jestli daný prvek v poli chceme “zpackovat”
- suma prefixů nad flags
- výsledek značí na jakou pozici bychom měli daný prvek přesunout
- jestli jsou z počátečního bodu vidět ostatní body, resp. jaké body jsou vidět
- pomocí sumy prefixů pro max. úhel; bod, který je dál, ale má menší úhel, než je úhel již předešlého viditelného bodu, tak daný bod není viditelný
pre_scan = není potřeba neutrální prvek, byl by úhel prvního bodu ?? (asi spíš scan než prescan???)
s = 0 + 0 + lib. příznakp = 1 + 0 nebo 0 + 1g = 1 + 1- kolečko s tečkou
- na levé straně předchozí stav
- nahoře aktuální vysledek operace sečtení
- na začátek
stop
- porovnáváme po bitech
- jdeme od nejnižšího bitu po nejvyšší
f značí novou sekvenci nad kterou se má sort provádět
- nebudeme řešit medián, vezmeme první prvek\
-
- kontrole jestli není seřazené
- ZKOUŠKA - kontrola je v paralelním prostředí logaritmická
- zkontrolují plus
and redukce
-
- logaritmický broadcast ve scanu
- slide 43 - čárky jsou desetinné čárky
- na konci seznamu ukazuje seznam sám na sebe
- nastavit všechno na
1 kromě posledního - ten je nastaven na 0
- problém - zjistit kdy jste na uspání / probuzení
- potřeba vědět sumu prefixu - tedy potřebují
- součástí písemných prací už 20 let
- “kloboučku hop”
- počet procesorů $\frac{n}{\log n}$!!
- Na zkoušce!!
- né na půlsemce
-
- seznam sousednosti (adjacency list)