Algoritmi i strukture podataka - II KOLOKVIJUM     5.02.2007.

 

 

NAPOMENA: Svi zadaci sem treceg su vec uradjeni na vezbama!!!

1.  Zadat je prirodan broj n i pozitivni realni brojevi c, wi i pi(i=1,2,…,n) pri čemu je sa c označena vrednost kapacitet nekog ranca, sa wi su označene težine predmeta koje se mogu staviti u ranac, dok  pi su vrednosti tih predmeta. Predmeti se mogu rezati. Potrebno je odrediti realne brojeve  xi (i=1,2,…,n)  koji označavaju koji se deo i-tog predmeta stavlja u ranac tako da ukupna težina predmeta stavljenih u ranac, ∑i=1...n wi*xi , ne bude veća od c, a da ukupna vrednost predmeta ranca ∑i=1...n pi*xi bude maksimalna.

l      IDEJA: za svaki predmet se izračuna profitabilnost pi/wi (vrednost po jedinici težine). Predmeti se sortiraju silazno po profitabilnosti te se u tom redosledu stavljaju u ranac dokle ima mesta. Kod svakog stavljanja u ranac nastoji se staviti što veći deo predmeta.

/* prethodno su nizovi sortirani po profitabilnosti */

#define MAXLEN    30

 float w[MAXLEN], p[MAXLEN], x[MAXLEN];

 void smestanjePredmeta (int n, float c) {

   float cu;

   int i;

   for (i=1; i<=n; i++) x[i] = 0.0;

   cu = c;

   for (i=1; i<=n && cu>0; i++) {

     if (w[i] > cu) {

        x[i] = cu/w[i];

        return; }

     x[i]=1.0;

     cu -= w[i];}

   return; }

 

Primer: n=3, wi=(2,3,4), pi=(1,7,8), c=6. Profitabilnosti predmeta pi/wi=(1/2,7/3,2). Algoritam stavlja u ranac ceo drugi predmet, pa ga popunjava s ľ trećeg predmeta, te je rešenje xi=(0,1,3/4) i maksimalna vrednost u rancu je 13.

 

2. Dat je neusmereni povezani graf G=(V,E) sa n čvorova. Potrebno je ustanoviti da li u grafu G postoji trougao (tj. takva tri čvora da između svaka dva od njih postoji grana). Konstruisati algoritam složenosti O(nlog2 7) koji daje odgovor na ovo pitanje.

Neka je A matrica povezanosti grafa G. Posto je graf G neusmeren,

matrica A je simetricna. Razmotrimo vezu elemenata matrice B =AA (proizvod matrica) i grafa G. Prema definiciji

proizvoda matrica je

B[i; j] =

Iz ove jednakosti sledi da je uslov B[i; j] > 0 ispunjen akko postoji indeks k,

takav da su oba elementa A[i; k] i A[k; j] jedinice. Drugim recima, B[i; j] > 0

je ispunjeno ako i samo ako postoji cvor vk, takav da je k != i, k != j i da su

oba qvora vi i vj povezana sa vk. Prema tome, u grafu postoji trougao koji sadrzi

temena vi i vj akko je vi povezan sa vj i B[i; j] > 0. Konacno, u G postoji trougao

akko postoje takvi indeksi i, j da je A[i; j] = 1 i B[i; j] > 0.

Navedena analiza sugerise algoritam. Treba izracunati matricu B = A A

i proveriti ispunjenost uslova A[i; j] = 1, B[i; j] > 0 za sve parove(i; j). Slozenost provere ovog uslova je O(n2), te preovladjujuci deo vremenske slozenosti algoritma potice od mnozenja matrica. Time je problem nalazenja trougla u grafu sveden na problem mnozenja matrica. Za mnozenje matrica moze se iskoristiti Strasenov algoritam i tako dobiti algoritam za nalazenje trougla u grafu slozenosti O(n2:81).

 

 

3. Odredite pomocni niz za KMP algoritam za uzorak P=cgccgcg iz 2 slovne azbuke {c,g}.

 

STRANA 119 u knjzi: algoritam i primer

H[i]: 001123

 

4. Implementirajte rekurzivnu funkciju za INORDER obilazak binarnog stabla, a potom implementirajte iterativnu (nerekurzivnu) verziju funkcije koja realizuje INORDER obilazak binarnog stabla.

 

Neka je stablo uvedeno kao:

typedef struct cvor { int broj; struct cvor *levo, *desno; } drvo;

 

Rekurzivna verzija:

 

void pisi_lkd (drvo* koren) {           /* Infiksno ispisivanje.           */

  if (koren) {

    pisi_lkd (koren->levo); printf ("%d ", koren->broj); pisi_lkd (koren->desno);

  }

}

 

 

 

Iterativna verzija:

 

void INORDER_I(drvo *koren)

{

     drvo *cvor;

     cvor=koren;

 

    while (1)

      {

          while (cvor)   //spustanje u stablu po lancu levih pokazivaca

              {

                  PUSH(stek, cvor);

                   cvor=cvor->levo;

               }

          //kad se dodje do praznog levog podstabla, uzima se cvor sa vrha steka i posecuje (stampa)

            if (!prazan(stek))

             {

                 cvor=POP(stek);

                 printf(”%d”, cvor->broj);

                 cvor=cvor->desno; //ponavlja se postupak za desno podstablo

             }

            else return; //algoritam zavrsava rad kad se stek isprazni

     }

}

 

 

 

 

5. 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).

 

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(xk,yk) od tačkeA'(xk,axk + m')
(A' je projekcija od A u vertikalnom smeru na pravu q u pravcu y-ose)
jeste:
d(A,A')=dk=yk-axk -m' (dkje 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 dk bude veća ili jednaka od nule. Zapravo to znači da polovina brojeva yk-axk će biti veća ili jednaka od m' .
Otuda, za k=1..n se problem svodi na traženje medijane za yk-axk,o čemu je bilo reči kod rangovskih statistika u petoj glavi. To jest tada se ukazalo da algoritam rangovskih statistika moze naci n/2-ti po velicini clan za O(n) vreme. Otuda je ovaj algoritam linearne slozenosti.

 

 

Izrada zadataka:180 min

Svaki zadatak vredi po 10 poena.