Primene računara (4. godina/ R smer)

G1
Konstruisati algoritam linearne složenosti koji utvrđuje da li je zadatihntačaka u ravni kolinearno.

R(ešenje)

Algoritam Kolinearne (p₁,p₂,...,p_n)

input:    p1,p2,...,pn        /* tačke u ravni zadate parovima koordinata*/
output:  kolinearne         /* 0/1 */
  {
     kolinearne=1;
     j=3;
     while ( (kolinearne == 1)  && (j<=n))
         {
          /*  da li su (x1,y1) , (x2,y2), (xj,yj)  kolinearne? */
          if  ((y2-y1)*(xj-x1)   !=  (yj-y1)*(x2-x1)) kolinearne=0;
          j++;
       }
  }

G2
Konstruisati algoritam linearne složenosti koji za datih n tačaka i datu pravu p pronalazi pravu paralelnu sa p koja dati skup tačaka deli na dva podskupa jednake veličine (tačka prave se može uračunati u bilo koji od podskupova).

R

Jednačina prave p: y=ax + m
Jednačina prave q paralelne sa p: y=ax + m'

Za k=1..n rastojanje tačke A(x_k,y_k) od tačkeA'(x_k,ax_k + m')
(A' je projekcija od A u vertikalnom smeru na pravu q u pravcu y-ose)
jeste:
d(A,A')=d_k=y_k-ax_k -m' (d_kje pozitivno/negativno ako je tačka iznad/ispod prave q)

Da bi se zadovoljio zahtev iz formulacije onda se m' bira tako da polovina brojeva d_k bude veća ili jednaka od nule. Zapravo to znači da polovina brojeva y_k-ax_k će biti veća ili jednaka od m' .
Otuda, za k=1..n se problem svodi na traženje medijane za y_k-ax_k,o čemu je bilo reči kod rangovskih statistika u petoj glavi.
 

G3
Konveksni omotač zadatih tačaka je najmanji konveksan mnogougao koji sadrži sve tačke skupa i predstavlja se temenima navedenim u cikličnom redosledu. (algoritmi za konstrukciju konveksnog omotača: uvijanje poklona i Grahamov dati su u glavi 7).
Neka je raspoloživa crna kutija koja pronalazi konveksni omotač unije dva disjunktna konveksna monogugla P₁ i P₂za vreme proprcionalno zbiru broja njegovih temena. Konstruisati algoritam vremenske složenosti O(n log n) koji koristi ovu crnu kutiju da bi i odredio konveksni omotač datog skupa od n tačaka u ravni.

R

uputstvo: primeniti zadatak G2 radi pronalaska deobne prave p1, takve da dati skup od n tačaka u ravni bude podeljen na dva podskupa iste kardinalnosti ili kardinalnosti koja se razlikuje za +1, odnosno -1. Potom se konstruiše se rekurzivni algoritam, gde se rekurzija koristi za dobijanje konveksnih omotača za mnogouglove P1 i P2 (to su dva podskupa sa manje od n tačaka). Upotrebi se i crna kutija kako bi se objedinili konveksni omotači od P1 i P2 u konveksni omotač datog skupa od n tačaka u ravni.

Složenost konstruisanog rekurzivnog algoritma je:
T(n)=2T(n/2) + cn , gde složenost crne kutije je O(n) po formulaciji zadatka, a po zadatku G2 particioniranje u deobne podskupove je linerarne složenosti.
Kako je već rešavana gornja diferencna jednačina, onda T(n)=O(n log n)
 

G4
a) Za tačku P u ravni se kaže da dominira nad tačkomQako su x i y koordinata tačke P veće od odgovarajućih koordinata tačke Q. Tačka P je maksimalna u datomskupu tačaka P ako ni jedna tačka izP ne dominira nad njom.Konstruisati algoritam složenosti O (n log n ) za nalaženjesvih maksimalnih tačaka datog skupa P od n tačaka.

b) Rešiti odgovarajući problem u tri dimenzije (definicija dominacije će se odnositi na sve tri koordinate).

R

a)

Mogu u skupu i sve tačke da budu maksimalne.
Ako su sve tače različite, mora bar jedna da bude maksimalna (SP: ako tačka nije max, onda postoji neka koja njom dominira, pa je ona max ili ne ,...)
 
 

  Lema 1: Ako tačka P nije max, onda njom dominira neka max tačka.

  Lema2: Ako skupu tačaka S dodamo novu tačku R koja ne dominira niti jednom od starih max tačaka za k=1..n: M_{12,..., Mk iz S, onda one ostaju maksimalne, a nova tačka R maksimalna ako njom ne dominira nijednaod starih maksimalnih tačaka.}

  Lema3: Ako ima više tačaka sa istom x koordinatom,onda eventualno maksimalna tačka može biti samo ona sa najvećom y koordinatom.
 
 

Opis algoritma:
1. Sortiramo u opadajućem poretku sve tačke po vrednosti x kooordinate. Ukolikoima više tacaka sa istom x koordinatom, zadržavamo samo onu sa najvećom y koordinatom. (Lema 3)
2. Pretpostavimo da je dobijen niz P1, P2,..., Pk, k<=n

Tacka P1 (sa najvećom x koordinatom) je sigurno maksimalna tačka.
3. Neka je Y vrednost y koordinate tačke P1.
4. Prema lemi 1 i lemi 2 tačka P2 je maksimalna akko njome ne dominira tačka P1, tj. ako je y koordinata tačke P2 veća od Y.
5. Ako je njena y koordinata veća od Y, onda se tačka P2 dodaje skupu maksimalnihtacaka, dok Y uzima vrednost y koordinate tačke P2.
6. Analogno dalje: tačka P3 je max akko njome ne dominiraju do tada otkrivene max tačke, tj. akko je y koordinata tačke P3 veća od Y.
7. Opisana procedura ponavlja se za i=4, 5, ..., k

b)

1. slično delu a) izvrši se sortiranje tacaka po opadajućim x koordinatama.
2. Za tačke se cuvaju u sortiranom redosledu projekcije nadjenih maksimalnih tacaka u ravni yOz
3. Ako nad projekcijom nove tačke dominira neka projekcija eliminiše se nova tačka.

Inace, nova tačka eliminiše neke od projekcija nakon umetanja svoje projekcije.
U delu 3 se za proveru dominantnih projekcija može koristiti binarna pretraga.

G5
Dat je skup intervala na pravoj, predstavljenih koordinatama krajeva.Konstruisati algoritam složenosti O (n log n ) za nalaženje svih intervala koji se sadrže u nekom drugom intervalu iz skupa.

R

Algoritam IntervaliPresek (parovi koordinata levih i desnih krajeva duži)

Ulaz: (l1,r1), ..., (ln,rn)  /*parovi koordinata levih i desnih krajeva duži*/

Izlaz: (lk,rk)       
/*parovi koordinata levih i desnih krajeva duži koje se sadrže u drugoj duži */
Ideja: duž nije sadržana u drugoj duži ako je levi kraj duži manji od 
levog kraja druge duži 
ili je desni kraj  duži veći od desnog kraja druge duži.   
POJAČANA IH: U skupu sa manje od n duži  umemo da odredimo i 
označimo duži koje su sadržane u nekoj drugoj duži istog skupa i 
umemo da odredimo do tada najveći desni kraj

Opis algoritma:

1. sortiranje duži u rastućem poretku po njihovim levim krajevima 
(ako dve duži imaju isti levi kraj, dodatno se sortiraju po 
desnim krajevima u opadajućem poretku )

2. u prvom koraku  ne biva markirana prva duž (jer nije sadržana ni 
u jednoj duži, jer desni krajebi duži su u opadajućem poretku ako im je jednak
levi kraj), a do tada najveći desni kraj duži je vrednost desnog kraja 
prve duži

3. pretpostavimo da je problem rešen za prvih n-1 duži (tako što su markirane sve 
duži koje su sadržane u nekoj drugoj duži i da je poznat do tada najveći 
desni kraj za tih n-1 duži)

4. Razmotrimo n-tu duž:
       Ako je njen desni kraj veći od do tada najvećeg desnog kraja, onda ona nije 
sadržana ni u jednoj duži, te je ne markiramo i njen desni kraj stavimo za 
do tada najveći desni kraj.
       U suprotnom, ta duž je sadržana u drugoj duži, te je markiramo.

(BSO pretpostavimo da ne postoje duži čiji su i levi i desni krajevi jednaki).
Nakon primene algoritma markirane su duži koje su sadržane u drugoj.

G6
Dato je n pravougaonika sa stranicama paralelnim osama. Konstruisati algoritam složenosti O(n log n) za nalaženje  pravougaonikasadržanih u nekom drugom pravougaoniku.

R
Uputstvo: iskoristiti zadatke G4 i G5
 

G7
Opisati algoritam svođenja problema sadržanih intervala (zadatak G5)na problem određivanja maksimalne tačke
(zadatak G4).

R
Neka je skup intervala na pravoj/duži Di zadat skupom parova (Li,Ri).
Ideja je da se svakom i-tom intervalu/svakoj i-toj duži pridruži tačka Pi sa koordinatama (-Li,Ri).

Lema1: Tačka Pi dominira tačkom Pk ako i samo ako je duž Dk sadržana u duži Di.
D1:       Tacka Pi=(-Li,Ri) dominira tačkom Pk=(-Lk,Rk )
               ako i samo ako vazi -Lk <= - Li && Rk <= Ri
               tj. ako i samo ako vazi Lk >= Li && Rk >= Ri
              tj. ako i samo ako je duž Dk sadržana u duži Di.

Dakle, duž Dk je sadržana u nekoj duži ako i samo ako tačka Pk nije maksimalna.
Time je problem određivanja sadržanih duži sveden na problem određivanje maksimalnih duži. 

Naslovna - Jelena Grmusa

Primene racunara