15,469 matches
-
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 mai mic sau egal cu elementul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
-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 mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
doua secvență, rezultă că elementul cu valoare maximă din prima secvență este mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
maximă din prima secvență este mai mic sau egal cu elementul cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- a de-a doua secvență
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cu valoare minimă din cea de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- a de-a doua secvență sunt 1, deci ce-a de-a doua secvență este curată
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de-a doua secvență. Astfel avem 2 cazuri: 1: dacă valoarea minimă din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- a de-a doua secvență sunt 1, deci ce-a de-a doua secvență este curată. Secțiunea 4 Rețeaua de interclasare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
din cea de-a doua secvență este 0 atunci maximul din prima secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
secvență este tot 0, de unde rezultă că toate elementele din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
din prima secvență sunt 0, deci prima secvență este curată. 2: dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ce- 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 1 la intrare. Rețeaua cu interclasare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
vom dovedi corectitudinea rețelei cu interclasare numai pentru secvențe de 0 și 1 la intrare. Rețeaua cu interclasare se bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a asambla cele două secvențe de intrare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
dovedi corectitudinea rețelei cu interclasare numai pentru secvențe de 0 și 1 la intrare. Rețeaua cu interclasare se bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a asambla cele două secvențe de intrare X
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de 0 și 1 la intrare. Rețeaua cu interclasare se bazează pe următoarea intuiție. Date două secvențe sortate dacă inversăm ordinea celei de a doua secvențe și apoi concatenăm cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a asambla cele două secvențe de intrare X și Y, este suficient pentru a face o
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cele două secvențe, secvența rezultată este bitonică. De exemplu fiind date secvențele zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a asambla cele două secvențe de intrare X și Y, este suficient pentru a face o sortare bitonică asupra lui X concatenat cu YR. Putem construi MERGER[n] modificând primul semi-cleaner al BITONIC-SORTER[n]. Ideea este să efectuăm o inversare implicită a celei de-a
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
pentru a face o sortare bitonică asupra lui X concatenat cu YR. Putem construi MERGER[n] modificând primul semi-cleaner al BITONIC-SORTER[n]. Ideea este să efectuăm o inversare implicită a celei de-a doua jumătate de intrări. Fiind date două secvențe sortate {a1, a2, . . . , an/2} și {an/2+1, an/2+2, . . . , an} pentru a fi interclasate, dorim să obținem efectul sortării bitonice a secvenței {a1, a2, . . . , an/2, an, an-1, . . . , an/2+1}. De vreme ce semi-cleaner-ul sortatorului BITONIC-SORTER[n] compară
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
efectuăm o inversare implicită a celei de-a doua jumătate de intrări. Fiind date două secvențe sortate {a1, a2, . . . , an/2} și {an/2+1, an/2+2, . . . , an} pentru a fi interclasate, dorim să obținem efectul sortării bitonice a secvenței {a1, a2, . . . , an/2, an, an-1, . . . , an/2+1}. De vreme ce semi-cleaner-ul sortatorului BITONIC-SORTER[n] compară intrările i și n/2 + i, pentru i = 1, 2, . . . , n/2, noi facem ca primul etaj al rețelei cu interclasare să compare intrările i
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cu interclasare să compare intrările i și n - i + 1, figura 13 prezintă corespondența. Singura subtilitate este că ordinea ieșirilor de la partea de jos a primului etaj al MERGER[n] este inversată față de ordinea ieșirilor 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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/2} si {bn, bn-1, . . . , bn/2+1}. O rețea care asamblează două secvențe de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]