• IV Konstrukcija algoritama indukcijom
• V Algoritmi za rad sa nizovima i skupovima

Konstrukcija algoritama indukcijom

IV1 Primer nekorektne upotrebe indukcije

Bipartitivni graf

41.  Dat je povezan neusmeren graf G=(V, E). Konstruisati algoritam koji  će ustanoviti da li G jeste bipartitivni graf i u slučaju pozitivnog odgovora konstruisati razlaganje čvorova grafa u disjunktnu uniju. (Prema primeru 6.22 iz knjige, postoji tačno jedno ovakvo razlaganje za povezan bipartitivni graf G).

REšENJE:

   Neka čvor x pripada skupu čvorova V. 

1. Uklonimo čvor x i razložimo ostataka grafa G bez čvora x.(upotrebom indukcije)

2. Označimo prvi od dva disjunktna podskupa sa A, a drugi skup sa B.

3.

   3.1. Ako je x povezan samo sa čvorovima iz A, priključujemo čvor x skupu B.

   3.2.  Inače, ako je x povezan samo sa čvorovima iz B, priključujemo čvor x skupu A.

  3.3.  Inače, ako je x povezan sa čvorovima iz A i B, onda graf nije bipartitivan, jer razlaganja je jednoznačno.

OVO REšENJE NIJE KOREKTNO !!!

 Naime, u koraku 3.3 koristi se da je graf nakon koraka 1 ostao povezan, što ne mora biti tačno => manji ulaz problema nije isti kao polazni ulaz problema, te se ni ne može koristiti indukcija.

Rešenje bi bilo korektno da je u koraku 1 izabran čvor x  takav da graf bez čvora x ostaje povezan.

IV2  Problem  povezivanja kontira (oblast: računarska grafika): Spojiti učešljavanjem presek dve zadate konture.

Problem kontura se obrađuje u poglavlju 4.6 u knjizi.

PODSEĆANJE:

Jedan od primena u CAD, CAM, VLSI dizajn oblastima je i uklanjanje skrivenih linija unutar crteža ili pak izrada konture crteža.

Npr. zgrade jednog grada se zadaju ako uređen triplet   gdei su leva i desna koordinata zgrade i, je visina zgrade.

Na dijagramu levo niže zgrade su zadate redom tripletima

    (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

dok na dijagramu desno niže kontura je zadata kao vektor

   (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)

gde uređeni parovi (1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0) opisuju levu koordinatu i visinu fragmenta konture. 

Primer ulaza u problem kontura

1 11 52 6 73 13 912 7 1614 3 2519 18 2223 13 2924 4 28

Primer odgovarajućeg izlaza

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

REšENJE:
Skica rešenja linerane složenosti

(1)

inicijalizacija: pronaći prvi segment preseka dve konture

(2)

otkriti koja od dve konture ima nižu y vrednost na tekućoj x poziciji

(3)

iscrtatai konturu do sledećeg preseka

(4)

ići na korak  2  sve dok se ne dostigne kraj konture

Neka su konture zadate pomoću dvaju nizova gde svaki zasebno čuva x, y koordinate, tj.:

Sky1x, Sky1y veličine n za I konturuSky2x, Sky2y veličine m za II konturu

Rešenje su nizovi Sky3x, Sky3y, gde Sky3x je niz  veličine  n+m koji povezuju sortirane Sky1x,  Sky2x, dok
 Sky3y sadrži niži od  Sky1y, Sky2y ako se konture preklapaju, odnosno0 ako se ne preklapaju.

Inicijalizacija:

i = 0;j = 0;k = 0;

// napredovati ka prvoj presecnoj tacki// i postaviti na 0 visine svih tacaka koje prethode presecnoj while (Sky1x[i] < Sky2x[0]) { Sky3x[i] = Sky1x[i]; Sky3y[k] = 0; i = i + 1; k = k + 1;}while (Sky2x[j] < Sky1x[0]) { Sky3x[j] = Sky2x[j]; Sky3y[k] = 0; j = j + 1; k = k + 1;}

//glavna petlja
while (i<n) and (j<n)
 {
      // proveriti koja x vrednost se umece
      if (Sky1x[i]<Sky2x[j])
         {
             Sky3x[k] = Sky1x[i];  // ubaciti x vrednost
             Sky3y[k] = min(Sky1y[i],Sky2y[j-1]);        // ubaciti nizu visinu od dve moguce
           i = i + 1;
         }
  else
   { Sky3x[k] = Sky2x[j];
    Sky3y[k] = min(Sky1y[i-1],Sky2y[j]);
    j = j + 1;
    k = k + 1;
   }
}

Jasno da algoritam je linerane složenosti, jer se elementarni koraci obavljaju jednim prolazom kroz niz.

Algoritmi za rad sa nizovima i skupovima

V1  Kutije su numerisane redom od 1 do n, gde je n paran broj.U i-toj kutiji je smeštena količina od a[i] objekata. Konstruisati algoritam kojiće spojiti sadržaje po dve kutije, ali tako da maksimalna količina objekata u po dve kutije budečto je moguće manja.

Resenje:

1. sortirati niz a i rezultat je niz b
2. formirati parove (b[1],b[n]), (b[2], b[n-1]),..., (b[i], b[n-i+1]), i <= n/2

Pretpostavimo suprotno, tj. uočimo spajanje sadržaja po dve kutije koje umesto para (b[1], b[n]) ima parove(b[1], b[i]), (b[j], b[n])
Ako ta dva para se zamene parovima (b[1], b[n]), (b[i], b[j]), onda zbog (*), (**) se ne uvećava max zbirova,gde važi da:
(*)     b[1]+b[n] <= b[j] + b[n]
(**)     b[i]+b[j] <= b[j] + b[n]
Slično, ako se iz rezulatata koraka 2, umesto para (b[i], b[n-i+1]), i = 1 . . n/2
koriste drugi parovi,onda se opet n/2 puta primeni diskusija slična kao za (*), (**) uz zaključak da svih n/2 premeštanja parova imaju povećanje maksimuma zbirova => parovi (b[1],b[n]), (b[2], b[n-1]),..., (b[i], b[n-i+1]),  i <= n/2, su optimalno rešenje zadatka.

V2.  Dat je skup S od n realnih brojeva. Konstruisati algoritam složenosti O(n) koji pronalazi broj koji nije u S

Rešenje:

Taj broj može biti broj za jedan veći od najvećeg broja u skupu S.
Max svih brojeva se može naći jednim prolazom kroz skup S takošto se inicijalno postavida je jednak 1. članu, a potom se prelazi kroz svaki sledećičlan skupa i ukoliko je tekućičlanveći od max do tada, onda se promenljiva max ažurira i dobija vrednost tekućegčlana skupa S.
Kako se kroz skup S prolazi tačno jednom i za svakičlan obavljaju operacije poređenja sa promenljivommax i eventualna ažuriranja njene vrednosti (što je const vreme), onda je ukupna vremenska složenost O(n).
Algoritam manje složenosti ne može da rešava problem za svaki ulaz, jer ne može da pregleda svih n članova skupa S.

V3. Dat je skup S od n realnih brojeva i realan broj x. Konstruisati algoritam složenosti O(n log n) koji utvrđuje da li u S postoje dva elementa kojima je zbir jednakx.

Rešenje:

1. sortirati skup S i neka je rezulat S₁
2. za svako y iz skupa S₁ binarnom pretragom tražitičlan jednak sa brojem x-y

V4.  Neka je E zadati niz brojeva x[1], x[2],..., x[n]. Višestrukost broja x u E je brojpojavljivanja x u E. Odrediti element E višestrukosti veće od n/2 ("preovlađujući element") ili ustanoviti da takav ne postoji.

na primer: 2 3 2 5 5 5 5 2 5 1 5 4 5 = > 5 je preovlađujući

Jedna od ideja: izvrši se sortiranje, te ako postoji preovlađujući broj, on je u sredini i izvrši se za njega provera pozicije u sortiranom nizu. Može li efikasnije?

Ideja 2: Odrediti medijanu (videti u knjizi poglavlje o rangovskim statistikama - medijana je n/2-ti najmanji element), te0' je nađen kandidat za proveru. Može li efikasnije ?

Ideja 3: Ako je x[i] različito od x[j] i ako se izbace oba ova elementa iz niza, onda ako postoji  y koji je preovlađujući element starog niza, onda je on preovladjujući element i novog niza (obratno ne važi).

U algoritmu se u jednom prolazu koriste promenljive C, M, gde C je jedini kandidat za preovladjujuci element u nizu x[0],x[1],..,x[i-1].
M je broj pojavljivanja elementa C u nizu x[0], x[1],...,x[i-1], bez onih elemenata C koji su izbaceni.
Ako je x[i]==C, onda se M uvecava za 1, a inace smanjuje za 1. (tada se smatra da x[i] moze biti izbacen zajedno sa nekim clanom jednakim C).
Ako M postane 0, onda C dobije novu vrednost x[i] i time i M postane 1.

Algoritam Preovladjuje (x,n):
ulaz: x, n /* niz pozitivnih brojeva x, dimenzije n*/
izlaz: preovlada /* preovladjujuci alaement (ako postoji) ili -1 */

C=x[0];
M=1;
for(i=1; i < n; i++)
    if (M==0)
    {C=x[i]; M=1;}
    else
        if (x[i]==C) M++; else M--;

if (M==0) preovlada=-1;   /*nema preovladjujuceg elementa*/
else brojac=0;
for (i=0; i < n; i++)
    if (x[i]==C) brojac++;
if (brojac > n/2) preovlada=C; else preovlada=-1;

V5.

  Dat je niz od n prirodnih brojeva sa više ponavljanja elemenata, tako da je broj različitih elemenata u nizu O(log n).

a) Konstruisati algoritam za sortiranje ovakvih nizova, u kome se izvršava najviše O(n log log n) upoređivanja brojeva.
b) Zašto je složenost ovog algoritma manja od donje graniceΩ(n log n) za sortiranje?

REšENJE:

  a) Svaki element niza umetnuće se kao jedno polje čvora AVL stabla (ili nekog balansiranog binarnog stabla pretrage). Drugo polje čvora će čuvati broj pojava tog elementa u nizu. Ako jebroj različitih elemenata u nizu O(log n), onda je broj čvorova u AVL stablu  O(log n),
te je visina stabla O(n log log n) => broj upoređivanja je najviše O(n log log n).

  Zatim se stablo obilazi inorder obilaskom i njegovi elemeenti se kopiraju u neopadajućem redosledu u izlazni niz dužine n tako što se svaki element kopira onoliko puta kolika je vrednost odgovarajućeg brojačkog polja.

b) Opisani algoritam pod a) nije obuhvaćen modelom stabla odlučivanja, jer je pri konstrukciji algortma bilo od značaj da postoji relativno mali broj različitih elemenata u nizu, tj. vrednosti elemenata niza su bile značajne.

V6. Dat je hip sa n elemenata tako da najveći element je u korenu. Dat je i realan broj x. Konstruisati algoritam koji samo utvrđuje da li je k-ti najveći element hipa manji ili jednak od x. Nije nužno odrediti k-ti najveći element hipa. Vremenska složenost algoritma mora da (nezavisno od veličine hipa) bude O(k). Dozvoljeno je koristiti memorijski prostor veličine O(k) (u slučaju da se koristi rekurzija, dozvoljeno je koristiti memorijski prostor veličine O(k) za pamćenje rekurzivnih poziva, tj. za stek).

   k-ti najveći element hipa veći od x <=> postoji k elemenata hipa koji su veći od x, k >= 0

broj=0;  /* promenljiva koja cuva broj elemenata vecih od x; ova promenljiva mora ziveti, tj. cuvati vrednost izmedju rekurzivnih poziva,
                 te je staticka ili globalna ili ...*/

odgovor=NE;  /* odgovor da li je k-ti najveći element hipa manji ili jednak od x */

Algoritiam Utvrdi (Hip H sa korenom v, x, k)
   ulaz: H, k, x
   izlaz: odgovor DA/NE

{

       
if (!v) return ODGOVOR;
if (v->vrednost > x) broj++;

        if (broj > k) return (odgovor==DA);

Utvrdi(H sa korenom v->prviSin, x,k);

Utvrdi(H sa korenom v->drugiSin, x,k);

}

Bez obzira na veličinu hipa, broj rekurzivnih poziva f-je Utvrdi je O(k), jer algoritam se rekurzivno spušta niz hip H i uvećava promenljivu broj sve dok se ne prođe ceo hip H ili se ne izbroji k elemenata. Za pamćenje rekurzivnih poziva potrebno je koristiti stek, tj. memorijski prostor O(k)

Za razmišljanje:  Za svako n koje je stepen dvojke navesti primer niza kod koga se pri sortiranjumergesort-om vrši maksimalan broj upoređivanja.

Jelena Grmuša

Primene računara