Proiect  - Analiza Algoritmilor

Universitatea Politehnica Bucuresti

Algebra booleana formeaza un domeniu extrem de important in cadrul stiintei calculatoarelor si a sistemelor digitale. Multe din problemele ce apar in  domenii  precum inteligenta artificiala, scheme logice, combinatorica, pot fi exprimate ca o succesiune de operatii asupra unor functii logice. Astfel de aplicati necesita algoritmi eficientii de reprezentare si manipulare a functiilor logice. Din pacate multe din operatiile logice pe care am vrea sa le aplicam asupra functiilor logice cum ar fi setul de variabile de intrare pentru care functia ia valoarea ‘1’ sau compararea a doua expresii logice si determinarea echivalentei dintre ele necesita solutii complexe ale problemei NP – Complete sau coNp-Complete. In consecinta, toate metodele de rezolvare ale acestor probleme necesita, in cel mai rau caz, un  timp ridicat de rezolvare care creste exponential cu dimensiunea problemei. In practica, daca utilizam un set de algoritmi mai inteligenti de reprezentare si manipulare a functiilor logice putem evita complexitatea exponentiala a rezolvarii unor probleme.

                O larga varietate de metode a fost conceputa pentru o mai buna reprezentare si manipulare a functiilor logice. Metodele clasice de reprezentare precum cele cu Tabel de Adevar, Diagrame Karnaught sau sub forma de Suma de produse, sunt destul de costisitoare, deoarece fiecare functie de n variabile are o reprezentare de dimensiuni 2ⁿ sau chiar mai mare. Metode mai bune permit o reprezentare care pentru o gama larga de functii nu au o dimensiune exponentiala.

               O noua metoda conceputa, ce contine algoritmi de reprezentare si manipulare a functiilor logice permite retinerea functiilor logice sub forma de grafuri aciclice. Aceste grafuri poarta denumirea de Diagrame de Decizie Binara (DDB). Acesta noua conceptie, permite reprezentarea si manipularea functiilor logice intr-o maniera mult mai eficienta.

               Acesta metoda are cateva avantaje fata de metodele amintite anterior in ceea ce priveste manipularea functiilor. In primul rand, functiile folosite in mod frecvent au o reprezentare rezonabila prin aceasta noua metoda. De exemplu, toate functiile pare (indiferent de paritate) sunt reprezentate de grafuri unde numarul de varfuri creste la cel mult patratul numarului de variabile ca apar in functii. In al doilea rand performantele unei aplicatii bazate pe aceasta reprezentare, in momentul in care executa o secventa de operatii descreste incet, pana la final. De aceea, complexitatea in timp a unei singure operatii este determinata de dimensiunea grafului functiei respective asupra careia se efectueaza operatia. De exemplu, pentru a obtine functia complementara unei functii date timpul necesar acestei operatii este proportional cu dimensiunea grafului respectiv, in tipm ce pentru o operatie de combinare a doua functii binare (adunare, inmultire, etc.) este necesar un timp proportional cu produsul dimensiunilor celor doua grafuri. In final, aceasta reprezentare, sub forma de grafuri reduse, reprezinta forma canonica a functiei, care este unica fiecarei functii. Aceasta proprietate este foarte importanta in momentul in care dorim sa testam echivalenta a doua functii logice diferite.

                Din pacate aceasta metoda are si cateva dezavantaje. La inceputul procesului de creare a grafului este necesara alegerea unei ordini a variabilelor de intrare . Pentru unele functii, graful corespunzator este foarte sensibil la aceasta ordonare a variabilelor. Problema alegerii unei ordonari care minimizeaza dimensiunea grafului este ea insasi o problema de tip NP – Complete. Se pot pune totusi cateva conditii asupra alegerii variabilelor astfel incat calculatorul sa poata alege de cele mai multa ori o ordine corecta.  Mai important sunt functiile logice sau expresiile unor circuite logice de dimensiuni rezonabile, dar a caror reprezentare, indiferent de ordonarea variabilelor  implica un graf a carui dimensiuni sunt prea mari pentru ca acesta sa fie practic.

1.1. Notatii

Vom presupune ca functia pe care dorim sa o reprezentam este data sub forma X1, … ,Xn. In descrierea unui sistem cum ar fi o retea logica combinationala sau o expresie logica, trebuie sa alegem o ordine a variabilelor de intrare, iar aceasta ordine trebuie sa fie aceeasi pentru toate functiile ce urmeaza a fi reprezentate. Functia ce rezulta in momentul inlocuirii unei variabile Xi a functiei f, cu o constanta b = {0,1} se numeste restrictia lui f .

       f |xi=b(x1, . . . ,xn) = f (x1, . . . ,xi-1,b,xi+1, . . . ,xn)

                In mod similar functia rezultata prin inlocuirea unei variabile cu o alta functie logica poarta denumirea de compozitie a lui f . Se noteaza f |xi=g.

       f |xi=g(x1, . . . ,xn) = f (x1, . . . ,xi-1,g(x1, . . . ,xn),xi+1, . . . ,xn)

                Unele functii nu depind de intregul lor set de argumente. Setul de depndente al unei functi f este If si contine argumentele de care functia f depinde.

     If = { i | f |xi=0 ¹ f |xi=1}

                 Setul de variabile pentru care functia respectiva ia valoarea 1 se numeste setul satisfacator al functiei si se noteaza :  

   Sf = { (x1, . . . ,xn) | f (x1, . . . ,xn) = 1 }.

2. Reprezentare

Definitia 1: Un graf functie este un graf ce contine doua tipuri de noduri. Un timp neterminal care are ca atribut un index index(v) Î {1, . . . ,n}, si doua noduri copii : low(v),high(v) Î . Un nod terminal v are ca atribut una din valorile value(v)Î{0,1}. In continuare, pentru orice nod neterminal daca low(v) este de asemenea un nod neterminal atunci trebui ca index(v) < index(low(v)). In mod similar, daca high(v) este un nod neterminal trebui ca index(v) < index(high(v)).

          Trebuie retinut deasemenea ca acest graph este unul aciclic de aceea indici nodurilor neterminale trebui da fie date urmand conditiile de mai sus.

Definitia 2: Un graf functie G avand drept radacina nodul  v descrie o functie fv definita recursiv astfel :

1. Daca  v este un nod terminal:

       a.  Daca value(v)=1, atunci fv=1

       b.  Daca value(v)=0, atunci fv=0

2. Daca veste un nod neterminal cu : index(v)=i,atunci fv este :

     fv(x1, . . . ,xn) = x-i×flow(v)(x1, . . . ,xn) + xi×fhigh(v)(x1, . . . ,xn).