644 matches
-
a1 care conectează la o intrare a comparatorului A; un conductor care conectează ieșirea superioară a comparatorului A la o intrare a comparatorului C; un conductor de ieșire b1, care vine de la ieșirea superioară a comparatorului C. Fiecare intrare a comparatorului este conectată la un conductor care este fie unul din cele n conductoare de intrare a1, a2, . . . , an, ale rețelei, fie este conectat la ieșirea altui comparator. În mod similar, fiecare ieșire a comparatorului este conectată la un conductor care
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ieșire b1, care vine de la ieșirea superioară a comparatorului C. Fiecare intrare a comparatorului este conectată la un conductor care este fie unul din cele n conductoare de intrare a1, a2, . . . , an, ale rețelei, fie este conectat la ieșirea altui comparator. În mod similar, fiecare ieșire a comparatorului este conectată la un conductor care este fie una din cele n conductoare de ieșire b1, b2, . . . , bn fie este conectată la intrarea altui comparator. Principala cerință pentru interconectarea comparatoarelor este ca graful
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a comparatorului C. Fiecare intrare a comparatorului este conectată la un conductor care este fie unul din cele n conductoare de intrare a1, a2, . . . , an, ale rețelei, fie este conectat la ieșirea altui comparator. În mod similar, fiecare ieșire a comparatorului este conectată la un conductor care este fie una din cele n conductoare de ieșire b1, b2, . . . , bn fie este conectată la intrarea altui comparator. Principala cerință pentru interconectarea comparatoarelor este ca graful de interconexiuni să fie aciclic: dacă trasăm
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ale rețelei, fie este conectat la ieșirea altui comparator. În mod similar, fiecare ieșire a comparatorului este conectată la un conductor care este fie una din cele n conductoare de ieșire b1, b2, . . . , bn fie este conectată la intrarea altui comparator. Principala cerință pentru interconectarea comparatoarelor este ca graful de interconexiuni să fie aciclic: dacă trasăm o cale de la 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
la ieșirea altui comparator. În mod similar, fiecare ieșire a comparatorului este conectată la un conductor care este fie una din cele n conductoare de ieșire b1, b2, . . . , bn fie este conectată la intrarea altui comparator. Principala cerință pentru interconectarea comparatoarelor este ca graful de interconexiuni să fie aciclic: dacă trasăm o cale de la 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
care este fie una din cele n conductoare de ieșire b1, b2, . . . , bn fie este conectată la intrarea altui comparator. Principala cerință pentru interconectarea comparatoarelor este ca graful de interconexiuni să fie aciclic: dacă trasăm o cale de la 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
interconexiuni să fie aciclic: dacă trasăm o cale de la 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 la intrare. De exemplu, în figura 2(aă, presupunem că secvența {9, 5, 2, 6} apare la conductoarele lor de intrare la pasul 0. La pasul 0 numai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
furnizează o valoare la ieșire numai când i se aplică ambele valori la intrare. De exemplu, în figura 2(aă, presupunem că secvența {9, 5, 2, 6} apare la conductoarele lor de intrare la pasul 0. La pasul 0 numai comparatoarele A și B au valorile de intrare disponibile. Presupunând că fiecare comparator are nevoie de o unitate de timp pentru a-și calcula valorile de ieșire, comparatoarele A și B furnizează valorile de ieșire la pasul 1. Valorile rezultate se
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
la intrare. De exemplu, în figura 2(aă, presupunem că secvența {9, 5, 2, 6} apare la conductoarele lor de intrare la pasul 0. La pasul 0 numai comparatoarele A și B au valorile de intrare disponibile. Presupunând că fiecare comparator are nevoie de o unitate de timp pentru a-și calcula valorile de ieșire, comparatoarele A și B furnizează valorile de ieșire la pasul 1. Valorile rezultate se pot vedea în figura 2(b). Remarcați că ambele comparatoare A și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
apare la conductoarele lor de intrare la pasul 0. La pasul 0 numai comparatoarele A și B au valorile de intrare disponibile. Presupunând că fiecare comparator are nevoie de o unitate de timp pentru a-și calcula valorile de ieșire, comparatoarele A și B furnizează valorile de ieșire la pasul 1. Valorile rezultate se pot vedea în figura 2(b). Remarcați că ambele comparatoare A și B furnizează valorile lor în același timp sau "în paralel." Acum, la timpul 1, comparatoarele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
că fiecare comparator are nevoie de o unitate de timp pentru a-și calcula valorile de ieșire, comparatoarele A și B furnizează valorile de ieșire la pasul 1. Valorile rezultate se pot vedea în figura 2(b). Remarcați că ambele comparatoare A și B furnizează valorile lor în același timp sau "în paralel." Acum, la timpul 1, comparatoarele C și D, dar nu și E au valorile de intrare disponibile. O unitate de timp mai târziu, la timpul 2, ele furnizează
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
comparatoarele A și B furnizează valorile de ieșire la pasul 1. Valorile rezultate se pot vedea în figura 2(b). Remarcați că ambele comparatoare A și B furnizează valorile lor în același timp sau "în paralel." Acum, la timpul 1, comparatoarele C și D, dar nu și E au valorile de intrare disponibile. O unitate de timp mai târziu, la timpul 2, ele furnizează valorile de ieșire după cum se vede în figura 2(c). Comparatoarele C și D operează în paralel
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
în paralel." Acum, la timpul 1, comparatoarele C și D, dar nu și E au valorile de intrare disponibile. O unitate de timp mai târziu, la timpul 2, ele furnizează valorile de 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
disponibile. O unitate de timp mai târziu, la timpul 2, ele furnizează valorile de 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ș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 de ieșire ale rețelei b2 și b3, iar secvența de ieșire {2, 5
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
că dacă la intrare se aplică secvența {9, 6, 5, 2} vom obține la ieșire aceeași secvență 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 este bine definită și vom
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 o valoare de ieșire și dacă intrările în rețea se aplică la timpul 0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 o valoare de ieșire și dacă intrările în rețea se aplică la timpul 0, un comparator de adâncime d furnizează valorile de ieșire la timpul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 o valoare de ieșire și dacă intrările în rețea se aplică la timpul 0, un comparator de adâncime d furnizează valorile de ieșire la timpul d; adâncimea unei rețele este deci egală
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 o valoare de ieșire și dacă intrările în rețea se aplică la timpul 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]