706 matches
-
comparatoarele ca simple linii verticale cum se poate vedea în figura 1 (b). Intrările sunt plasate în stanga liniei verticale iar ieșirile în dreapta, cu valoarea minimă pe firul de sus și valoarea maximă pe firul de jos. Putem gândi astfel comparatorul ca un dispozitiv care sortează cele două intrări ale sale (în ordine crescătoare). Vom presupune că fiecare comparator execută o operație în timpul O(1). Cu alte cuvinte, presupunem că intervalul de timp între introducerea valorilor de intrare x și y
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
liniei verticale iar ieșirile în dreapta, cu valoarea minimă pe firul de sus și valoarea maximă pe firul de jos. Putem gândi astfel comparatorul ca un dispozitiv care sortează cele două intrări ale sale (în ordine crescătoare). Vom presupune că fiecare comparator execută o operație în timpul O(1). Cu alte cuvinte, presupunem că intervalul de timp între introducerea valorilor de intrare x și y și obținerea valorilor de ieșire x' și y' este constant. Un fir transmite informații dintr-un loc în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Cu alte cuvinte, presupunem că intervalul de timp între introducerea valorilor de intrare x și y și obținerea valorilor de ieșire x' și y' este constant. Un fir transmite informații dintr-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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ș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 degrabă, o secvență de conductoare distincte
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, din figura 2, reprezintă trei conductoare: conductorul de intrare a1 care
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, din figura 2, reprezintă trei conductoare: conductorul de intrare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o linie nu reprezintă un singur conductor, ci, mai degrabă, o secvență de conductoare distincte care conectează diferite comparatoare. Linia de deasupra, de exemplu, din figura 2, reprezintă trei conductoare: conductorul de intrare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
degrabă, o secvență de conductoare distincte care conectează diferite comparatoare. Linia de deasupra, de exemplu, din figura 2, reprezintă trei conductoare: conductorul de intrare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
care conectează diferite comparatoare. Linia de deasupra, de exemplu, din figura 2, reprezintă trei conductoare: conductorul de intrare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
trei conductoare: conductorul de intrare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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]