1,064 matches
-
1 să plaseze în secvența de ieșire f(aj) înaintea lui f(ai) atunci când la intrare se aplică {f(a1), f(a2), . . . , f(an)}. Dar deoarece f(aj) = 1 și f(ai) = 0, obținem contradicția că rețeaua nu reușește să sorteze secvența zero- unu {f(a1), f(a2), . . . , f(an)} corect. Putem să afirmăm faptul că o rețea de comparare cu n intrări va sorta corect secvența de intrare {n, n - 1, . . . , 1} numai dacă va sorta corect cele n-1
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Dar deoarece f(aj) = 1 și f(ai) = 0, obținem contradicția că rețeaua nu reușește să sorteze secvența zero- unu {f(a1), f(a2), . . . , f(an)} corect. Putem să afirmăm faptul că o rețea de comparare cu n intrări va sorta corect secvența de intrare {n, n - 1, . . . , 1} numai dacă va sorta corect cele n-1 secvențe {1, 0, 0, . . . , 0, 0}, {1, 1, 0, . . . , 0, 0}, . . . , {1, 1, 1, . . . , 1, 0}. Întradevăr dacă una din cele n-1 secvențe
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețeaua nu reușește să sorteze secvența zero- unu {f(a1), f(a2), . . . , f(an)} corect. Putem să afirmăm faptul că o rețea de comparare cu n intrări va sorta corect secvența de intrare {n, n - 1, . . . , 1} numai dacă va sorta corect cele n-1 secvențe {1, 0, 0, . . . , 0, 0}, {1, 1, 0, . . . , 0, 0}, . . . , {1, 1, 1, . . . , 1, 0}. Întradevăr dacă una din cele n-1 secvențe nu ar fi sortate corect atunci unul din comparatori generează la ieșirea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
intrare {n, n - 1, . . . , 1} numai dacă va sorta corect cele n-1 secvențe {1, 0, 0, . . . , 0, 0}, {1, 1, 0, . . . , 0, 0}, . . . , {1, 1, 1, . . . , 1, 0}. Întradevăr dacă una din cele n-1 secvențe nu ar fi sortate corect atunci unul din comparatori generează la ieșirea superioară numărul mai mare iar la ieșirea inferioară pe cel mic. Deci, la aplicarea secvenței {n, n-1,...,1} numere ce vor intra în acel comparator sortate descrescător, vor ieși tot sortate
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
1 secvențe nu ar fi sortate corect atunci unul din comparatori generează la ieșirea superioară numărul mai mare iar la ieșirea inferioară pe cel mic. Deci, la aplicarea secvenței {n, n-1,...,1} numere ce vor intra în acel comparator sortate descrescător, vor ieși tot sortate descrescător. Observăm că rețeaua de comparare din figura 9 poate fi considerată pe baza principiului zero- unu o rețea de sortare, deoarece toate secvențele cu patru elemente formate doar din 1 și 0 : {0,0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de sortare trebuie să avem cel puțin un comparator între oricare două conductoare i și j. Secțiunea 3 O rețea de sortare bitonică Primul pas în construirea unei rețele de sortare eficiente este construirea unei rețele de comparare care poate sorta orice secvență bitonică, o secvență care fie crește monoton și apoi descrește monoton, fie descrește monoton ca apoi sa crească monoton. De exemplu, secvențele {1, 4, 6, 8, 3, 2} și {9, 8, 3, 2, 4, 6} sunt ambele bitonice
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
0i1j0k sau de forma 1i0j1k, pentru orice i, j, k ≥0. Observați că o secvență care este fie monoton crescătoare, fie monoton descrescătoare este de asemenea bitonică. Sortatorul bitonic pe care îl vom realiza este o rețea de comparare care sortează secvențe bitonice de 0 sau de 1. Semi-cleanerul Un sortator bitonic este compus din câteva etaje, fiecare din ele fiind numit semi- cleaner, sau semi-nivelatoare. Fiecare semicleaner este o rețea de comparare de adâncime 1 în care linia i este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
mai departe despărțit în două cazuri. Cele patru cazuri sunt arătate în figura 11. În fiecare caz arătat este conținută lema. Sortatorul bitonic Combinând recursiv semi-cleaner, ca în figura 12, putem construi un sortator bitonic, care este o rețea ce sortează secvențe bitonice. Primul etaj al unui BITONIC-SORTER[n] constă în SEMICLEANER[n], care, conform lemei 3, furnizează două secvențe bitonice având dimensiunea pe jumătate astfel că fiecare element din jumătatea de sus este cel puțin la fel de mic decât orice element
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
două secvențe bitonice având dimensiunea pe jumătate astfel că fiecare element din jumătatea de sus este cel puțin la fel de mic decât orice element din jumătatea inferioară. Astfel putem completa sortarea folosind două copii ale BITONIC- SORTER[n/2] pentru a sorta cele două jumătăți recursiv. În figura 12 (aă, recursia este arătată explicit iar în figura 12 (bă, recursia a fost utilizată pentru a arăta micile semi-cleaner-uri care compun progresiv restul sortatorului bitonic, adâncimea D(nă a lui BITONIC-SORTER[n] este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Pentru toate cazurile fiecare element din jumătatea superioară este cel puțin la fel de mic ca și orice element din jumătatea inferioară, ambele jumătăți sunt bitonice și cel puțin o jumătate este curată. Astfel o secvență bitonică de tip zero-unu poate fi sortată de BITONIC-SORTER, având o adâncime de lg n. În urma aplicării principiului analog principiului zero-unu rezultă că orice secvență bitonică de numere arbitrară poate fi sortată de această rețea. Dacă considerăm două secvențe de 0-uri și 1-uri se poate
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cel puțin o jumătate este curată. Astfel o secvență bitonică de tip zero-unu poate fi sortată de BITONIC-SORTER, având o adâncime de lg n. În urma aplicării principiului analog principiului zero-unu rezultă că orice secvență bitonică de numere arbitrară poate fi sortată de această rețea. Dacă considerăm două secvențe de 0-uri și 1-uri se poate demonstra că ,dacă fiecare element dintr-o secvență este mai mic sau egal cu orice element din cealaltă secvență, atunci una din cele două secvențe
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a de-a doua secvență sunt 1, deci ce-a de-a doua secvență este curată. Secțiunea 4 Rețeaua de interclasare Rețeaua noastră de sortare va fi construită din rețele de interclasare, care sunt rețele care pot asambla două secvențe sortate de intrare într-o singură secvență sortată de ieșire. Vom modifica BITONIC-SORTER[n] pentru a crea o rețea cu interclasare MERGER[n]. Ca și în cazul sortatorului bitonic, vom dovedi corectitudinea rețelei cu interclasare numai pentru secvențe de 0 și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
deci ce-a de-a doua secvență este curată. Secțiunea 4 Rețeaua de interclasare Rețeaua noastră de sortare va fi construită din rețele de interclasare, care sunt rețele care pot asambla două secvențe sortate de intrare într-o singură secvență sortată de ieșire. Vom modifica BITONIC-SORTER[n] pentru a crea o rețea cu interclasare MERGER[n]. Ca și în cazul sortatorului bitonic, vom dovedi corectitudinea rețelei cu interclasare numai pentru secvențe de 0 și 1 la intrare. Rețeaua cu interclasare se
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
unui semi-cleaner obișnuit. De vreme ce o secvență bitonică inversată este tot bitonică, totuși ieșirile de sus și cele de jos ale primului etaj al rețelei de interclasare satisface proprietățile lemei 3, și astfel partea superioară și cea de jos poate fi sortată bitonic în paralel pentru a produce ieșirea sortată a unei rețele cu interclasare. Secvența bitonică de intrare {a1, a2, . . . , an/2-1, an/2, an, an-1, . . . , an/2+2, an/2+1} este transformată în două secvențe bitonice {b1, b2, . . . , bn
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de intrare {a1, a2, . . . , an/2-1, an/2, an, an-1, . . . , an/2+2, an/2+1} este transformată în două secvențe bitonice {b1, b2, . . . , bn/2} si {bn, bn-1, . . . , bn/2+1}. O rețea care asamblează două secvențe de intrare sortate într-o singură secvență de ieșire de asemeni sortată. Rețeaua MERGER[n] poate fi văzută ca un BITONICSORTER[n] cu primul semi-cleaner modificat ca să compare intrările i și n - i + 1 pentru i = 1, 2, . . . , n/2. Aici n = 8
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
lui MERGER[n] este diferit de BITONICSORTER[n]. Corespunzător adâncimea lui MERGER[n] este lg n, aceeași ca cea a lui BITONIC-SORTER[n]. Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii ale lui SORTER[n
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii ale lui SORTER[n/2] pentru a sorta (în paralel) două subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii ale lui SORTER[n/2] pentru a sorta (în paralel) două subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1, în care caz putem utiliza un fir pentru a sorta secvența de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
pentru a sorta (în paralel) două subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1, în care caz putem utiliza un fir pentru a sorta secvența de 1element , de vreme ce o secvență de 1-element este deja sortată. Figura 15 (b) arată rezultatul folosirii recursiei iar figura 15 (c) arată rețeaua curentă obținută prin înlocuirea căsuțelor MERGER în figura 15 (b) cu rețelele de interclasare curente. Datele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
recursiei iar figura 15 (c) arată rețeaua curentă obținută prin înlocuirea căsuțelor MERGER în figura 15 (b) cu rețelele de interclasare curente. Datele traversează lg n etaje în rețeaua SORTER[n]. Fiecare intrare individuală în rețea este deja o secvență sortată de 1-element . Acest prim etaj al lui SORTER[n] constă în n/2 copii ale lui MERGER[2] care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
este deja o secvență sortată de 1-element . Acest prim etaj al lui SORTER[n] constă în n/2 copii ale lui MERGER[2] care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]