7,885 matches
-
permit execuția doar a unei singure operații la un moment dat. În această lucrare voi încerca să mă ocup într-o oarecare măsura și de investigarea algoritmilor de sortare bazați pe un model de calcul care folosește o rețea de comparare, rețea în care pot fi executate simultan mai multe operații de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând, ele pot executa doar comparații. Astfel, un algoritm cum ar fi counting sort (sortarea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
această lucrare voi încerca să mă ocup într-o oarecare măsura și de investigarea algoritmilor de sortare bazați pe un model de calcul care folosește o rețea de comparare, rețea în care pot fi executate simultan mai multe operații de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând, ele pot executa doar comparații. Astfel, un algoritm cum ar fi counting sort (sortarea prin numărare) nu poate fi implementat pe o rețea de comparare. În
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
încerca să mă ocup într-o oarecare măsura și de investigarea algoritmilor de sortare bazați pe un model de calcul care folosește o rețea de comparare, rețea în care pot fi executate simultan mai multe operații de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând, ele pot executa doar comparații. Astfel, un algoritm cum ar fi counting sort (sortarea prin numărare) nu poate fi implementat pe o rețea de comparare. În al doilea rând
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând, ele pot executa doar comparații. Astfel, un algoritm cum ar fi counting sort (sortarea prin numărare) nu poate fi implementat pe o rețea de comparare. În al doilea rând, dacă în cazul modelului RAM operațiile se execută secvențial - adică una după alta în timp - într-o rețea de comparare operațiile pot fi executate simultan, adică “în paralel”. După cum vom vedea, această caracteristică permite realizarea unei
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cum ar fi counting sort (sortarea prin numărare) nu poate fi implementat pe o rețea de comparare. În al doilea rând, dacă în cazul modelului RAM operațiile se execută secvențial - adică una după alta în timp - într-o rețea de comparare operațiile pot fi executate simultan, adică “în paralel”. După cum vom vedea, această caracteristică permite realizarea unei rețele de comparare care să sorteze n valori într-un timp subliniar. În secțiunea 1 vom începe prin a defini rețelele de comparare și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
doilea rând, dacă în cazul modelului RAM operațiile se execută secvențial - adică una după alta în timp - într-o rețea de comparare operațiile pot fi executate simultan, adică “în paralel”. După cum vom vedea, această caracteristică permite realizarea unei rețele de comparare care să sorteze n valori într-un timp subliniar. În secțiunea 1 vom începe prin a defini rețelele de comparare și rețelele de sortare. De asemenea vom da o definiție naturală pentru “timpul de execuție” în cazul unei rețele de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de comparare operațiile pot fi executate simultan, adică “în paralel”. După cum vom vedea, această caracteristică permite realizarea unei rețele de comparare care să sorteze n valori într-un timp subliniar. În secțiunea 1 vom începe prin a defini rețelele de comparare și rețelele de sortare. De asemenea vom da o definiție naturală pentru “timpul de execuție” în cazul unei rețele de comparare arătând legătura dintre acesta și adâncimea rețelei. În secțiunea 2 se demonstrează principiul zero- unu care simplifică foarte mult
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
care să sorteze n valori într-un timp subliniar. În secțiunea 1 vom începe prin a defini rețelele de comparare și rețelele de sortare. De asemenea vom da o definiție naturală pentru “timpul de execuție” în cazul unei rețele de comparare arătând legătura dintre acesta și adâncimea rețelei. În secțiunea 2 se demonstrează principiul zero- unu care simplifică foarte mult procesul de analiză a corectitudinii unei rețele de sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o rețea de sortare care știe să sorteze n valori de intrare în timpul O(log2 n), iar în secțiunea 6 se va prezenta softul realizat în vederea reprezentării grafice a unor astfel de rețele de sortare. Secțiunea 1 Rețele de comparare Rețelele de sortare sunt rețele de comparare care întotdeauna sortează datele primite la intrare, astfel că vom începe cu prezentarea rețelelor de comparare și a caracteristicilor lor. O rețea de comparare este compusă numai din fire și comparatori. Un comparator
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
sorteze n valori de intrare în timpul O(log2 n), iar în secțiunea 6 se va prezenta softul realizat în vederea reprezentării grafice a unor astfel de rețele de sortare. Secțiunea 1 Rețele de comparare Rețelele de sortare sunt rețele de comparare care întotdeauna sortează datele primite la intrare, astfel că vom începe cu prezentarea rețelelor de comparare și a caracteristicilor lor. O rețea de comparare este compusă numai din fire și comparatori. Un comparator, prezentat în figura 1(aă, este un
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
prezenta softul realizat în vederea reprezentării grafice a unor astfel de rețele de sortare. Secțiunea 1 Rețele de comparare Rețelele de sortare sunt rețele de comparare care întotdeauna sortează datele primite la intrare, astfel că vom începe cu prezentarea rețelelor de comparare și a caracteristicilor lor. O rețea de comparare este compusă numai din fire și comparatori. Un comparator, prezentat în figura 1(aă, este un dispozitiv cu două intrări, x și y, și două ieșiri, x' și y', care implementează următoarea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
astfel de rețele de sortare. Secțiunea 1 Rețele de comparare Rețelele de sortare sunt rețele de comparare care întotdeauna sortează datele primite la intrare, astfel că vom începe cu prezentarea rețelelor de comparare și a caracteristicilor lor. O rețea de comparare este compusă numai din fire și comparatori. Un comparator, prezentat în figura 1(aă, este un dispozitiv cu două intrări, x și y, și două ieșiri, x' și y', care implementează următoarea funcție: Din cauză că reprezentarea grafică a comparatorului din figura
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
un loc în altul. Firele pot conecta ieșirea unui comparator cu intrarea altuia, dar, oricum, ele sunt fie fire de intrare în rețea fie fire de ieșire din rețea. De-a lungul acestei secțiuni, vom presupune că o rețea de comparare conține n fire de intrare a1, a2, . . . , an, prin care valorile ce urmează a fi sortate întră în rețea și n fire de ieșire b1, b2, . . . , bn, care livrează rezultatele calculate de rețea. De asemenea, vom vorbi de secvența de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
la valorile de pe conductoarele de intrare și de ieșire. Deci vom folosi același nume atât pentru conductor cat și pentru valoarea pe care o poartă. Intenția noastră va putea fi dedusă din 6 context. Figura 2 prezintă o rețea de comparare, care constă dintrun set de comparatoare interconectate prin conductoare. Vom desena o rețea de comparare cu n intrări ca o colecție de n linii cu comparatoarele dispuse vertical. De reținut că o linie nu reprezintă un singur conductor, ci, mai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
pentru conductor cat și pentru valoarea pe care o poartă. Intenția noastră va putea fi dedusă din 6 context. Figura 2 prezintă o rețea de comparare, care constă dintrun set de comparatoare interconectate prin conductoare. Vom desena o rețea de comparare cu n intrări ca o colecție de n linii cu comparatoarele dispuse vertical. De reținut că o linie nu reprezintă un singur conductor, ci, mai degrabă, o secvență de conductoare distincte care conectează diferite comparatoare. Linia de deasupra, de exemplu
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ieșirea unui comparator la intrarea altuia, de la intrare la ieșire etc., calea pe care am trasat-o nu trebuie să facă o buclă și să treacă de două ori prin același comparator. Așa că putem să desenăm o rețea de comparare cum e cea din figura 2 cu intrările în rețea dispuse la stânga iar ieșirile dispuse la dreapta; datele vor parcurge rețeaua de la stânga la dreapta. Fiecare comparator furnizează o valoare la ieșire numai când i se aplică ambele valori
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ieșire după cum se vede în figura 2(c). Comparatoarele C și D operează în paralel și ele. Ieșirea superioară a compararatorului C și ieșirea inferioară a comparatorului D conectează la conductoarele de ieșire b1 și b4, respectiv, ale rețelei de comparare și aceste conductoare de ieșire ale rețelei de comparare conțin valorile finale la timpul 2. În același timp, la timpul 2, comparatorul E are disponibile valorile la intrare, și figura 2(d) arată că acesta și produce valorile de ieșire
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
C și D operează în paralel și ele. Ieșirea superioară a compararatorului C și ieșirea inferioară a comparatorului D conectează la conductoarele de ieșire b1 și b4, respectiv, ale rețelei de comparare și aceste conductoare de ieșire ale rețelei de comparare conțin valorile finale la timpul 2. În același timp, la timpul 2, comparatorul E are disponibile valorile la intrare, și figura 2(d) arată că acesta și produce valorile de ieșire la timpul 3. Aceste valori sunt conținute de conductoarele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ordonată crescător de sus în jos, adică {2, 5, 6, 9}. Acest aspect poate fi ilustrat edificator în figura 3 : Presupunând că fiecare comparator are același timp de execuție, timpul unitate, putem defini timpul de execuție al unei rețele de comparare, ca fiind timpul necesar ca fiecare conductor de ieșire să primească valorile odată ce conductoarele de intrare și le-au primit pe ale lor. Acest timp este egal cu numărul cel mai mare de comparatoare pe care fiecare element de intrare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
este egal cu numărul cel mai mare de comparatoare pe care fiecare element de intrare trebuie să-l traverseze de la intrare până la ieșire. Mai formal, definim adâncimea unui conductor după cum urmează. Un conductor de intrare al unei rețele de comparare are adâncimea 0. Dacă comparatorul are două conductoare de intrare cu dimensiunile dx și dy, atunci conductoarele lor de ieșire au dimensiunile de max(dx, dy) + 1. Pentru că într-o rețea de comparare nu sunt bucle, adâncimea unui conductor
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de intrare al unei rețele de comparare are adâncimea 0. Dacă comparatorul are două conductoare de intrare cu dimensiunile dx și dy, atunci conductoarele lor de ieșire au dimensiunile de max(dx, dy) + 1. Pentru că într-o rețea de comparare nu sunt bucle, adâncimea unui conductor este bine definită și vom defini adâncimea unui comparator ca fiind egală cu adâncimea conductoarelor lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o rețea de comparare nu sunt bucle, adâncimea unui conductor este bine definită și vom defini adâncimea unui comparator ca fiind egală cu adâncimea conductoarelor lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate de timp pentru a produce
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
0, un comparator de adâncime d furnizează valorile de ieșire la timpul d; adâncimea unei rețele este deci egală cu timpul necesar ca rețeaua să producă valorile la toate conductoarele de ieșire. O rețea de sortare este o rețea de comparare pentru care secvența de ieșire crește monoton pentru orice secvență de intrare. Bineînțeles, nu orice rețea de comparare este o rețea de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că după timpul 1, cea mai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
egală cu timpul necesar ca rețeaua să producă valorile la toate conductoarele de ieșire. O rețea de sortare este o rețea de comparare pentru care secvența de ieșire crește monoton pentru orice secvență de intrare. Bineînțeles, nu orice rețea de comparare este o rețea de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că după timpul 1, cea mai mică dintre cele patru valori de intrare se obține fie la ieșirea superioară a comparatorului A sau la
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile corecte, ceea ce se întâmplă în pasul 3. O rețea de comparare poate fi asemănată cu o procedură în care se specifică câte comparații trebuie să survină dar nu cu o procedură în care adâncimea sa fizică depinde de numărul de intrări și ieșiri. De aceea vom descrie practic familii de rețele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]