Proiect  - Analiza Algoritmilor

Universitatea Politehnica Bucuresti

1. Introducere

    Diagramele de decizie binara reprezinta o noua forma de reprezentare a unor functii sau expresii logice. Astfel, pornind de la o expresie logica ce are ca variabile un set de forma X1, ... , Xn, si un set de operatori : SAU '+', SI '*', NEGAT '!' va trebui sa obtinem un arbore de decizie binara. Modul de constructie al acestui arbore este :

    Ca exemplu putem considera urmatoarea functie simpla : f = X1+X2*X3;

    Se obtine un arbore de forma :

1.1 Fisiere

    Proiectul a fost conceput in JCreator 1.5 folosind ca mediu de programare Java SDK 2.0 . Proiectul contine urmatoarele fisiere sursa :

Arbore.java  - Contine functii necesare prelucrarii si representarii de arbori.

Nod.java      - Contine declaratia unui nod specific DDB.

ExprLogic     - Implemmentarea unor functii necesare evaluarii si prelucrarii unor expresi logice.

BDD.java      - Contine definitia appletului.

2. Implementare

    Asa cum se observa din exemplul de mai sus, pentru a putea transforma o expresie logica intr-o diagrama de decizie binara vom avea avea nevoie de anumite functii de prelucrare a unei expresi logice, precum si de implementarea unui arbore.

Asupra unei expresi logice avem nevoie sa efectuam urmatoarele operatii :

Eliminarea unei variabile pe high, adica inlocuirea acesteia cu 1 si obtinerea expresiei echivalente.

Eliminarea unei variabile pe low, ce consta in inlocuirea acesteia cu 0 si obtinerea expresiei echivalente.

Evaluarea unei expresii ce consta in determinarea dependentei acesteia de o variabila sau valoarea acesteia, in cazul in care expresia logica nu mai depinde de nici o variabila.

Implementarea arborelui se va face recursiv tinand seama de urmatoarele aspecte :

Un nod don arbore poate fi un nod terminal sau neterminal. Nodurile terminale retin valoarea functiei in momentul in care aceasta nu mai depinde de variabile. Nodurile neterminale contin urmatoarea variabila de care functia mai depinde, fie in expresia initiala, fie dupa inlocuirea unor variabile cu diverse valori.

2.1 Functii

    Eliminarea unei variabile pe low.

Trebuie sa avem in vedere mai multe aspecte :

1. Daca variabila apare negat atunci valoarea ei va fi '1'.
2. Daca variabila apare intr-un produs in forma normala (nu este negata) atunci produsul respectiv va trebui eliminat din expresie.
3. Daca variabila apare negata in contextul unui produs atunci produsul va ramane, fiind eliminata doar variabila.
4. Daca variabila apare intr-o suma sub forma normala atunci ea va fi eliminata.
5. Daca apare in cadrul unei sume sub forma negata atuci ea va fi inlocuita cu '1';

Utilizand aceste conditii necesare eliminarii unei variabile pe low functia poate fi descrisa astfel :

Pentru <fiecare aparitie in expresia logica>

   {

      Daca <variabila este in forma normala>

              {

                  Daca <este in cadrul unui produs>

                          Elimina Produsul

                  Daca <este in cadrul unei sume>

                          Elimina Variabila;

               }    

       Daca <Variabila este in forma negata>    // !Xi

               {

                  Daca <este in cadrul unui produs>

                        Elimina Variabila;

                  Daca <este in cadrul unei sume>

                        Inlocuieste Variabila cu '1';

               }

         expresia logica = noua expresie logica;

     }

    Implementarea functie consta in lucrul cu stringuri si caractere. Daca de exemplu caracterul din fata fata variabilei gasite la o pozitie oarecare este '*' atunci variabila este in cadrul unui produs. Daca in fata ei se afla caracterul ! atunci ea este sub forma negata.

    In expresie pot aparea si paranteze, in special pentru a nega expresia dintre ele. Aceste paranteze sunt evaluate in special in momentul in care cand in expresie nu mai exista variabile.

Functie :

 ------------------------------------------------------------------------------------------------------


String elimVarPeLow (int nrVar, String expr)
{
boolean apar, cont, neg, next;
int pozitie =-1, indxStanga=-1, indxDreapta=-1;

String subS,subS1;
char chr;
apar = true;
next = false;
while (apar)

     {

       if (next)
            {

              pozitie = expr.indexOf(Variabile[nrVar],pozitie+1);} // se cauta variabila in expresie
       else

              pozitie = expr.indexOf(Variabile[nrVar]);

       neg = false;

        if (pozitie == -1) // daca nuse gaseste
                apar = false; // se iese

        else // daca este gasita
            {

               if (expr.length()!=pozitie+Variabile[nrVar].length())
                        chr = expr.charAt(pozitie+Variabile[nrVar].length());
              else chr ='o';
                     if ((chr<='9' && chr>='0')) // se testeaza daca nu apare o cifra dupa variabila
                          next = true;
                     else // astfel incat sa se confunde ex: X11 cu X1
                           {
                               cont = true;
                               indxStanga = pozitie; // se cauta produse in care intra variabila

                               while (cont)
                                    if (indxStanga == 0)
                                            break;
                                    else // daca nu este la inceputul expresiei se face cautare
                                        { // spre stanga
                                           chr = expr.charAt(pozitie - 1);
                                           if (chr == '!')
                                                { neg = true; // se neaga deci devine 1
                                                  indxStanga --;
                                                  break;
                                                }
                                           chr = expr.charAt(indxStanga - 1);
                                           if (chr != '(' && chr != '+') 
                                                indxStanga --; // indicele se decrementeaza
                                           else
                                                break;
                                        }

                                cont = true; // se incepe o cautare la dreapta

                                indxDreapta = pozitie + Variabile[nrVar].length();

                                while (cont)
                                    if (indxDreapta != expr.length()) // daca nu se afla la cap de sir
                                        {
                                            chr = expr.charAt(indxDreapta);
                                             if (neg)
                                                 {
                                                    if ( chr == '*' || chr =='+' || chr ==')') // daca nu este ) sau +
                                                            cont = false;
                                                  }
                                             else
                                                   if (chr != ')' && chr != '+') // daca nu este ) sau +
                                                        indxDreapta ++;
                                                   else
                                                        {
                                                            cont = false;
                                                            if (expr.charAt(indxDreapta)=='+')
                                                            indxDreapta++;
                                                            if (chr == ')' && expr.charAt(indxStanga-1)!='(')
                                                                       if (indxStanga!=0)
                                                                            indxStanga--;
                                                         }
                                            }
                                        else
                                            { cont = false; // daca s-a ajuns la capat se sterge semnul din stanga
                                               if (indxStanga!=0)
                                                       indxStanga --;
                                            }

                        subS=new String(expr.substring(0,indxStanga));
                        subS1 =new String(expr.substring(indxDreapta,expr.length()));
                        if (!neg)
                                subS = subS+subS1;
                        else
                                subS = subS+"1"+subS1;
                        expr = new String (subS);

                    }
           }

    }

return expr;

}

 ------------------------------------------------------------------------------------------------------

  Eliminarea unei variabile pe high.

Ca si la eliminarea pe low trebuie sa avem in vedere mai multe aspecte :

1. Daca variabila apare negat atunci valoarea ei va fi '0'.
2. Daca variabila apare intr-un produs in forma normala (nu este negata) atunci variabila va fi eliminata din produs.
3. Daca variabila apare negata in contextul unui produs atunci produsul va fi eliminat cu totul.
4. Daca variabila apare intr-o suma sub forma normala atunci ea va fi inlocuita cu '1'.
5. Daca apare in cadrul unei sume sub forma negata atuci ea va fi eliminata;

Utilizand aceste conditii necesare eliminarii unei variabile pe high functia poate fi descrisa astfel :

Pentru <fiecare aparitie in expresia logica>

   {

      Daca <variabila este in forma normala>

              {

                  Daca <este in cadrul unui produs>

                          Elimina Variabila

                  Daca <este in cadrul unei sume>

                          Inlocuieste Variabila cu '1';

               }    

       Daca <Variabila este in forma negata>    // !Xi

               {

                  Daca <este in cadrul unui produs>

                        Elimina Produsul;

                  Daca <este in cadrul unei sume>

                       Elimina Variabila;

               }

         expresia logica = noua expresie logica;

     }

Functie :

 ------------------------------------------------------------------------------------------------------

 String elimVarPeHigh (int nrVar, String expr)
{
boolean apar, cont,cont1,next, neg = false;
int pozitie = -1, indxStanga=-1, indxDreapta=-1;
String subS,subS1;
char chr;
apar = true;
next = false;

while (apar) // cat timp mai apare variabila in expresie
    { if (next) // daca apar variabile de genu X11 si se cauta X1
        {
            pozitie = expr.indexOf(Variabile[nrVar],pozitie+1); // se cauta variabila in expresie
            next = false;
         }
       else
            pozitie = expr.indexOf(Variabile[nrVar]);
       neg = false;
     if (pozitie == -1) // daca nu se gaseste

            apar = false; // se iese
     else // daca este gasita
            {
                if (expr.length()!=pozitie+Variabile[nrVar].length()) // daca este la sfarsitul expresiei
                        chr = expr.charAt(pozitie+Variabile[nrVar].length());
                else chr ='o';
                if (chr<='9' && chr>='0') // se testeaza daca nu apare o cifra dupa variabila
                        next = true;
                else // astfel incat sa se confunde ex: X11 cu X1
                    {
                        cont = true;
                        indxStanga = pozitie; // se cauta produse in care intra variabila
                        while (cont)
                                if (indxStanga != 0) // daca nu este la inceputul expresiei se face cautare
                                    { // spre stanga
                                        chr = expr.charAt(indxStanga - 1);
                                        if (chr == '!') // cat timp nu se intanlesc caracterele ( sau +
                                              {
                                                neg = true;
                                                indxStanga --; // indicele se decrementeaza (din high => low)
                                                cont1 = true;
                                                while(cont1)
                                                        if (indxStanga != 0) // daca nu este la inceputul expresiei se face cautare
                                                            { // spre stanga
                                                               chr = expr.charAt(indxStanga - 1);
                                                               if (chr != '(' && chr != '+')
                                                                           indxStanga --; // indicele se decrementeaza
                                                               else
                                                                    {
                                                                        cont1 = false;
                                                                        cont = false; break; // altfel se iese din bucla
                                                                     }
                                                              }
                                                          else
                                                              {
                                                                cont1 = false;
                                                                cont = false; break; // altfel se iese din bucla
                                                               }

                                                 } else break;

                                       }
                                  else cont = false;

                        cont = true; // se incepe o cautare la dreapta

                        indxDreapta = pozitie + Variabile[nrVar].length();
                        while (cont)
                            if (indxDreapta == expr.length())
                                    break;
                            else // daca nu se afla la cap de sir
                                {
                                    chr = expr.charAt(indxDreapta);
                                    cont1 = true;
                                    if (!neg)
                                            if ( chr == '*' || chr =='+'|| chr ==')') // daca nu este ) sau +
                                                    cont = false;
                                    if (neg)
                                          while (cont1) // daca este negat adica din 1 devine 0
                                                if (indxDreapta != expr.length()) // daca nu se afla la cap de sir   
                                                         {
                                                                chr = expr.charAt(indxDreapta);
                                                                if (chr != ')' && chr != '+') // daca nu este ) sau +
                                                                        indxDreapta ++;
                                                                else
                                                                        {
                                                                            if (chr == ')' && expr.charAt(indxStanga-1)=='+')
                                                                                    if (indxStanga!=0)
                                                                                           indxStanga --;
                                                                            cont1 = false; cont = false;   
                                                                            if (expr.charAt(indxDreapta)=='+') // semnul se pastreaza la stanga aici se sterge
                                                                                    indxDreapta++;

                                                                          }
                                                            }
                                                else
                                                           {  cont = false; // daca s-a ajuns la capat se sterge semnul din stanga
                                                              cont1 = false;
                                                              if (indxStanga!=0)
                                                                    indxStanga --;
                                                            }
                                }
                    subS=new String(expr.substring(0,indxStanga)); // se elimina factorul din expresie
                    subS1 =new String(expr.substring(indxDreapta,expr.length()));
                    if (neg)
                        subS = subS+subS1;
                    else
                        subS = subS+"1"+subS1;
                    expr = new String (subS);
                }
        }
    }
return expr;
}

------------------------------------------------------------------------------------------------------      

Evaluarea unei expresii

Evaluarea unei expresii logice consta in :

- determinarea dependentei acestei expresii de o variabil (daca mai apare in cadrul ei o variabila sau nu).

- in cazul in care in expresie nu mai apare nici o variabila se determina valoarea nogica a acesteia, care poate fi '1' sau '0'

    Trebuie avut in vedere ca expresia care nu mai contine variabile va fi o insiruire de valori {1,0 }ce apar in diverse sume sau produse, precum si paranteze ce cuprind in cadrul lor alte expresii de 0 sau 1.

     Pentru a afla valoarea finala a unei expresii trebuie inlocuiti diversi termeni cu valoarea lor de adevar. De exemplu daca apare "1*1" valoarea acestei expresii va fi 1, daca apare "!(0)" il vom inlocui cu 1, (0) cu '0', "1+1" cu 1, etc..

Functie :

 ------------------------------------------------------------------------------------------------------

String evalExpr (int nrVar, String expr)
{
 int indx;
 boolean apare,cont;
 char chr;
 int poz;
 String subS, subS1;

for(indx = 0; indx <= nrVariabile; indx ++) // se cauta dependenta expresiei de alte variabile
    {    
        poz = expr.indexOf(Variabile[indx]);
        if (poz != -1 )
            if (expr.length()==poz+Variabile[indx].length())
                return Variabile[indx];
            else
                if (!(expr.charAt(poz+Variabile[indx].length())>='0' && expr.charAt(poz+Variabile[indx].length())<='9'))
                    return Variabile[indx];
     }

 cont = true;
 while (cont) // cat timp exista paranteze
    {
        cont = false;
        apare = true;
        while (apare) // se cauta expresii de genu : !() si se inlocuiesc cu 1
            {
                indx = expr.indexOf("!()");
                if (indx != -1)    
                    {
                        subS=new String(expr.substring(0,indx));        
                        subS1 =new String(expr.substring(indx+3,expr.length()));       
                        subS = subS+"1"+subS1;
                        expr = new String (subS);
                        cont = true;
                    }
                else
                        apare = false;
            }

 apare = true;

 while (apare) // se cauta expresii de genu : () si se inlocuiesc cu 0
            {
                indx = expr.indexOf("()");
                if (indx != -1)
                    {
                        subS=new String(expr.substring(0,indx));
                        subS1 =new String(expr.substring(indx+2,expr.length()));
                        subS = subS+"0"+subS1;
                        expr = new String (subS);   
                        cont = true;

                     }

                else
                        apare = false;
             }

 apare = true;

 while (apare) // se cauta expresii de genu : !(1) si se inlocuiesc cu 0
         {
              indx = expr.indexOf("!(1)");
              if (indx != -1)
                    {
                       subS=new String(expr.substring(0,indx));
                       subS1 =new String(expr.substring(indx+4,expr.length()));
                       subS = subS+"0"+subS1;
                       expr = new String (subS);   
                       cont = true;
                    }
             else
                        apare = false;
          }
 

 apare = true;

 while (apare) // se cauta expresii de genu : (1) si se inlocuiesc cu 1
        {
            indx = expr.indexOf("(1)");
            if (indx != -1)
                   {
                       subS=new String(expr.substring(0,indx));
                       subS1 =new String(expr.substring(indx+3,expr.length()));
                       subS = subS+"1"+subS1;
                       expr = new String (subS);
                       cont = true;
                    }
            else
                    apare = false;
          }

 apare = true;

 while (apare) // se cauta expresii de genu : !(0) si se inlocuiesc cu 1
        {
            indx = expr.indexOf("!(0)");
            if (indx != -1)
                  {
                       subS=new String(expr.substring(0,indx));
                       subS1 =new String(expr.substring(indx+4,expr.length()));
                       subS = subS+"1"+subS1;
                       expr = new String (subS);
                       cont = true;
                    }
            else
                       apare = false;
         }

apare = true;

while (apare) // se cauta expresii de genu : (0) si se inlocuiesc cu 0
        {
            indx = expr.indexOf("(0)");
            if (indx != -1)
                  {
                       subS=new String(expr.substring(0,indx));
                       subS1 =new String(expr.substring(indx+3,expr.length()));
                       subS = subS+"0"+subS1;
                       expr = new String (subS);
                       cont = true;
                   }
            else
                       apare = false;
        }

apare = true;

while (apare) // se cauta expresii de genu : 1*1 si se inlocuiesc cu 1
        {
            indx = expr.indexOf("1*1");
            if (indx != -1)
                    {
                        subS=new String(expr.substring(0,indx));
                        subS1 =new String(expr.substring(indx+3,expr.length()));
                        subS = subS+"1"+subS1;
                        expr = new String (subS);
                        cont = true;

                    }
            else
                     apare = false;
           }

 apare = true;

 while (apare) // se cauta expresii de genu : 1+1 si se inlocuiesc cu 1
          {
                indx = expr.indexOf("1+1");
                if (indx != -1)
                    {
                        subS=new String(expr.substring(0,indx));
                        subS1 =new String(expr.substring(indx+3,expr.length()));   
                        subS = subS+"1"+subS1;
                        expr = new String (subS);
                        cont = true;

                     }
                else
                        apare = false;
            }

 apare = true;

 while (apare) // se cauta expresii de genu : 1+1 si se inlocuiesc cu 1
        {
            indx = expr.indexOf("0+1");
            if (indx != -1)
                {
                    subS=new String(expr.substring(0,indx));
                    subS1 =new String(expr.substring(indx+3,expr.length()));
                    subS = subS+"1"+subS1;
                    expr = new String (subS);
                    cont = true;
                }
            else
                    apare = false;
        }

 apare = true;

 while (apare) // se cauta expresii de genu : 1+1 si se inlocuiesc cu 1
        {
            indx = expr.indexOf("1*0");
            if (indx != -1)
                {
                    subS=new String(expr.substring(0,indx));
                    subS1 =new String(expr.substring(indx+3,expr.length()));
                    subS = subS+"0"+subS1;
                    expr = new String (subS);
                    cont = true;   
                  }
            else
                    apare = false;
         }


 if (expr.indexOf("1") != -1)
        return "1"; // expresia este egala cu 1
 else
        return "0"; // expresia este egala cu 0;
}

 ------------------------------------------------------------------------------------------------------

Constructia arborelui

    La costructia arborelui avem nevoie de evaluarea expresiei logice in fiecare nod si anume sa gasim dependenta expresiei logice dupa eliminarea variabilelor anterioare pe low sau pe high. Pentru constructia arborelui avem nevoie de o functie recursiva care sa apeleze cele trei functii prezentate mai sus. Astfel pa fiecare pas se evalueaza expresia :

Functie :

 ------------------------------------------------------------------------------------------------------

Evalueaza <expresie>;

Daca <valoare = 0 sau valoare = 1 >

     Trece  <nod nou>;

     Intoarce;

Altfel

     Trece <nod nou>;

     Elimina <variabila>;

     Apeleaza functie <stanga, expresie noua>;

     Apeleaza functie <dreapta, expresie noua>;

Complexitatea acestei functii depinde mult de numarul de variabile ce apar in aceasta expresie

Daca notam cu n numarul de variabile putem estima complexitatea ca fiind :

C((n*2ⁿ))

Arbore Creare (int nrVar1, String expr, int directie, Arbore Arb, ExprLogic e) // se creeaza un nou arbore dupa o expresie
{
String str1;
String val;
boolean rad;
Arbore Arb1 = new Arbore();
Nod n;
int nrVar = nrVar1;
val =new String(e.evalExpr(nrVar, expr)); // se testeaza dependenta expresiei de variabile
rad = false;

if ( val.compareTo("1")==0 || val.compareTo("0")==0 ) // daca este un nod terminal (expresia este = cu 0 sau 1)
        if (directie == 1) // daca directie 1 se adauga in stanga altfel in dreapta
            {
                n = new Nod(1,val); // se creeaza un nou nod
                if (Arb.radacina == null) // daca radacina este nula (primul nod)
                    { Arb = new Arbore(n);Arb.setParinte(Arb);rad =true;} // noul nod va fi radacina
                else
                      Arb.nouLeft(n); // altfel se adauga noul nod in functie de directie
                return Arb.getParinte(); // se returneaza radacina
            }
        else
            {
                n = new Nod(1,val); // analog
                if (Arb.radacina == null)
                    {Arb = new Arbore(n);Arb.setParinte(Arb);rad =true;}
                else
                    Arb.nouRight(n);
                return Arb.getParinte();
             }
  else // daca nu este un nod terminal (expresia mai depinde de o variabila)
    {
        n = new Nod(0,val); // se adauga variabila gasita
        if (Arb.radacina == null) // daca radacina este null => noul nod va fi radacina
            { Arb = new Arbore(n);
              rad =true;
              Arb.setParinte(Arb);
            }
        else
            if ( directie == 1 ) // daca radacina !=null se adauga la stanga sau dreapta
                { // in functie de directie
                  Arb.nouLeft(n);
                }
            else
                {
                    Arb.nouRight(n);
                }

        str1 = expr; // se elimina variabila gasita pe low
        while (str1.compareTo(expr)==0)
                       {
                        str1 = e.elimVarPeLow(nrVar,expr);
                        nrVar++; // se ca    uta pozitia la care aceasta este
                        }
        nrVar--;
        if (rad) // daca am eliminat variabila pe low
                Creare(nrVar1+1, str1, 1, Arb,e); // apelam recursiv functia de creare spre stanga
        else // radacina este noul nod creat
            if (directie == 1 )
                    Creare(nrVar1+1, str1, 1, Arb.getLeft(),e);
            else
                    { Creare(nrVar1+1, str1, 1, Arb.getRight(),e);}
                      str1 = expr; // se elimina variabila gasita pe high
                      while (str1.compareTo(expr)==0) // cat timp nu este eliminata
                            {
                                str1 = e.elimVarPeHigh(nrVar,expr);
                                nrVar++; // se cauta in lista de variabile pozitia acesteia
                             }
                     nrVar--;

                    if (rad)
                        { Creare(nrVar1+1, str1, 0, Arb,e);} // se apeleaza recursiv functia spre dreapta (high)
                    else
                          if (directie == 1 )
                                { Creare(nrVar1+1, str1, 0, Arb.getLeft(),e); }
                          else
                                  Creare(nrVar1+1, str1, 0, Arb.getRight(),e); return Arb.getParinte();

                }
}