15,469 matches
-
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 superioară numărul mai mare iar
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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,0,0} 21 {0,0,0,1} {0,0,1,0} {0,0,1,1} {0,1,0,0} {0,1,0,1} {0,1,1,0} {0,1
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
0,0,0} {1,0,0,1} {1,0,1,0} {1,0,1,1} {1,1,0,0} {1,1,0,1} {1,1,1,0} {1,1,1,1}, aplicate la intrarea rețelei din figura 9 determină următoarele secvențe la ieșirea din rețea: {0,0,0,0} {0,0,0,1} {0,0,1,1} {0,1,1,1} {1,1,1,1}, sortate. O remarcă pe care o putem face(se poate observa și din figura 9Ă este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cel puțin un comparator între liniile i și i+1 pentru orice i = 1, 2, ..., n-1. Întradevăr presupunând că între conductoarele i și j (i<jă nu există nici un comparator pe tot parcursul rețelei și aplicând la intrare o secvență în care elementul de pe poziția i este mai mare decât elementul de pe poziția j, la ieșirea din rețea vom avea pe pozițiile i și j două elemente nesortate. Deci nu poate fi vorba despre o rețea de sortare. De aici
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. Secvențele zero-unu
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. Secvențele zero-unu care sunt bitonice
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. Secvențele zero-unu care sunt bitonice au o structură simplă. Ele sunt de forma 0i1j0k sau de forma 1i0j1k, pentru orice i, j, k ≥0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. Secvențele zero-unu care sunt bitonice au o structură simplă. Ele sunt de forma 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
8, 3, 2} și {9, 8, 3, 2, 4, 6} sunt ambele bitonice. Secvențele zero-unu care sunt bitonice au o structură simplă. Ele sunt de forma 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 comparată
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
1 în care linia i este comparată cu linia i + n/2 pentru i = 1, 2, . . . , n/2. Presupunem că n este par) În figura 10 este prezentat SEMI-CLEANER[8], un semi-cleaner cu 8 intrări și 8 ieșiri. Când o secvență bitonică de 0 și 1 se aplică la intrarea unui semi-cleaner , acesta produce o secvență de ieșire în care valorile cele mai mici sunt plasate la ieșire în jumătatea superioară, cele mai mari în jumătatea inferioară și ambele jumătați sunt
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
2, . . . , n/2. Presupunem că n este par) În figura 10 este prezentat SEMI-CLEANER[8], un semi-cleaner cu 8 intrări și 8 ieșiri. Când o secvență bitonică de 0 și 1 se aplică la intrarea unui semi-cleaner , acesta produce o secvență de ieșire în care valorile cele mai mici sunt plasate la ieșire în jumătatea superioară, cele mai mari în jumătatea inferioară și ambele jumătați sunt bitonice. De fapt, cel puțin una din jumătate este constantă, adică conține numai sau 0uri
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
jumătatea superioară, cele mai mari în jumătatea inferioară și ambele jumătați sunt bitonice. De fapt, cel puțin una din jumătate este constantă, adică conține numai sau 0uri sau numai 1 -uri, de aici și denumirea de "semi-cleaner." (Reținem că toate secvențele constante sunt bitonice.Ă Următoarea lemă dovedește această proprietatea ale semi-cleaner-urilor. Sunt arătate două eșantioane diferite de valori de intrare și de ieșire de 0 și de 1 Intrările se presupun a fi bitonice. Un semicleaner asigură faptul că fiecare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
element de ieșire din jumătatea superioară este cel puțin la fel de mic ca orice element de ieșire din jumătatea inferioară. Mai mult, ambele jumătăți sunt bitonice, și cel puțin o jumătate este curată. Lema 3 Dacă intrarea unui semi-cleaner este o secvență de 0 și 1, atunci ieșirea are următoarele proprietăți: atât jumătatea superioară cât și jumătatea inferioară sunt bitonice, fiecare element din jumătatea superioară este cel puțin la fel de mic decât orice element din jumătatea inferioară și cel puțin o
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 din
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 din jumătatea inferioară. Astfel putem completa sortarea folosind două copii ale BITONIC- SORTER[n/2] pentru a sorta cele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 dată prin recurență, cu soluția D(nă = lg n. Secvența de intrare se presupune a fi o secvență bitonică de zerouri și un-uri și fără a restrânge generalitatea presupunem că este de forma 00 . . . 011 . . . 100 . . . 0. Subsecvențele de 0- uri sunt albe iar subsecvențele de 1-uri sunt
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 dată prin recurență, cu soluția D(nă = lg n. Secvența de intrare se presupune a fi o secvență bitonică de zerouri și un-uri și fără a restrânge generalitatea presupunem că este de forma 00 . . . 011 . . . 100 . . . 0. Subsecvențele de 0- uri sunt albe iar subsecvențele de 1-uri sunt gri. Putem gândi cele n intrări ca fiind
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
intervine într-o subsecvență de 0-uri. 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 demonstra că ,dacă fiecare element dintr-o secvență este mai mic sau egal cu orice element din cealaltă
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 este constantă. Considerând faptul că orice element
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 este constantă. Considerând faptul că orice element din prima secvență este mai mic sau egal cu orice element din cea de-a doua
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 este constantă. Considerând faptul că orice element din prima secvență este mai mic sau egal cu orice element din cea de-a doua secvență, rezultă că elementul cu valoare maximă din prima secvență este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]