1,004 matches
-
pentru a obține o rețea cu interclasare care poate interclasa, două secvențe deja sortate într-o singură secvență sortată. În cele din urmă în secțiunea 5 vom asambla aceste rețele de interclasare într-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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 dispozitiv cu două
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 și obținerea valorilor de ieșire
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 intrare {a1, a2, . . . , an} și de secvența de ieșire {b1,b2, . . . ,bn}, referindu-ne la valorile
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețeaua din figura 5 poate fi considerată o rețea de sortare bazată pe sortare prin inserție: Interesant de remarcat ar fi să arătăm că dacă vom insera un comparator oriunde într-o rețea de sortare, atunci rețeaua obținută nu va sorta corect orice secvență de intrare. Astfel pentru a întări această supoziție aplicăm rețelei din figura 2 la intrare secvența {9,6,5,2} și după primii doi comparatori din rețea, respectiv (1,2) și (3,4) adăugam comparatorul (2,3Ă
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
și alte rețele de comparare, principiul zero-unu ne va permite să ne îndreptăm atenția asupra secvențelor de ieșire care constau numai din cifre de 0 sau 1. Odată ce am construit o rețea de sortare și am dovedit că poate sorta toate secvențele zero-unu vom apela la principiul zero-unu pentru a dovedi că rețeaua sortează corespunzător secvențe de orice alte valori. Demonstrația principiului zero-unu se sprijină pe noțiunea de funcție monoton crescătoare . Demonstrație. Mai întâi vom demonstra afirmația că, dacă f
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
asupra secvențelor de ieșire care constau numai din cifre de 0 sau 1. Odată ce am construit o rețea de sortare și am dovedit că poate sorta toate secvențele zero-unu vom apela la principiul zero-unu pentru a dovedi că rețeaua sortează corespunzător secvențe de orice alte valori. Demonstrația principiului zero-unu se sprijină pe noțiunea de funcție monoton crescătoare . Demonstrație. Mai întâi vom demonstra afirmația că, dacă f este o funcție monoton crescătoare, atunci un singur comparator cu intrările f(x) si
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
fir sunt valorile funcției f aplicate valorilor de pe același fir din figura 2. Când o rețea de comparare este o rețea de sortare, lema 1 permite demonstrarea următorului rezultat remarcabil. Teorema 2 Dacă o rețea de comparare cu n intrări sortează corect toate cele 2n secvențe posibile de 0-uri și 1-uri, atunci ea sortează corect toate secvențele de numere arbitrare. Demonstrație Presupunem prin reducere la absurd că rețeaua sortează toate secvențele zero-unu, dar există o secvență de numere arbitrare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețea de comparare este o rețea de sortare, lema 1 permite demonstrarea următorului rezultat remarcabil. Teorema 2 Dacă o rețea de comparare cu n intrări sortează corect toate cele 2n secvențe posibile de 0-uri și 1-uri, atunci ea sortează corect toate secvențele de numere arbitrare. Demonstrație Presupunem prin reducere la absurd că rețeaua sortează toate secvențele zero-unu, dar există o secvență de numere arbitrare pe care rețeaua nu le sortează corect. Adică, există o secvență de intrare {a1, a2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Teorema 2 Dacă o rețea de comparare cu n intrări sortează corect toate cele 2n secvențe posibile de 0-uri și 1-uri, atunci ea sortează corect toate secvențele de numere arbitrare. Demonstrație Presupunem prin reducere la absurd că rețeaua sortează toate secvențele zero-unu, dar există o secvență de numere arbitrare pe care rețeaua nu le sortează corect. Adică, există o secvență de intrare {a1, a2, . . . , an} conținând elementele ai și aj astfel încât ai < aj, dar rețeaua plasează pe aj înaintea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
posibile de 0-uri și 1-uri, atunci ea sortează corect toate secvențele de numere arbitrare. Demonstrație Presupunem prin reducere la absurd că rețeaua sortează toate secvențele zero-unu, dar există o secvență de numere arbitrare pe care rețeaua nu le sortează corect. Adică, există o secvență de intrare {a1, a2, . . . , an} conținând elementele ai și aj astfel încât ai < aj, dar rețeaua plasează pe aj înaintea lui ai în secvența de ieșire. Definim o funcție monoton crescătoare f ca: Din moment ce rețeaua plasează
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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]