15,469 matches
-
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Ă. Aceasta va avea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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Ă. Aceasta va avea ca efect aducerea valorii 2 (minimul din rețea) pe conductorul 2, iar până la finalul rețelei nu
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
arbitrare de intrare, numerele pot fi întregi, reale sau, în general, orice set de valori liniar ordonate. Cum va trebui să construim rețele de sortare ș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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 este o
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 f(y
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Astfel, comparatorul produce valorile f (min(x,y)) și f (max(x,y)) când f (x) și f (y) se aplică la intrările lui, ceea ce completează demonstrația. Se poate face observația că dacă se aplică o funcție monoton crescătoare unei secvențe sortate, se obține tot o secvență sortată. Astfel, considerând oricare două elemente a și b din secvența sortată avem a<b. Cum funcția este monoton crescătoare avem f(a)<f(b). Considerând „a<b implică f(a) <f(b)” se
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
x,y)) și f (max(x,y)) când f (x) și f (y) se aplică la intrările lui, ceea ce completează demonstrația. Se poate face observația că dacă se aplică o funcție monoton crescătoare unei secvențe sortate, se obține tot o secvență sortată. Astfel, considerând oricare două elemente a și b din secvența sortată avem a<b. Cum funcția este monoton crescătoare avem f(a)<f(b). Considerând „a<b implică f(a) <f(b)” se demonstrează că oricare ar fi a
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
f (y) se aplică la intrările lui, ceea ce completează demonstrația. Se poate face observația că dacă se aplică o funcție monoton crescătoare unei secvențe sortate, se obține tot o secvență sortată. Astfel, considerând oricare două elemente a și b din secvența sortată avem a<b. Cum funcția este monoton crescătoare avem f(a)<f(b). Considerând „a<b implică f(a) <f(b)” se demonstrează că oricare ar fi a,b,c astfel încât a<b și c>a și c
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a) <f(b)” se demonstrează că oricare ar fi a,b,c astfel încât a<b și c>a și c>b avem f(a)<f(b)<f(c). Demonstrația poate continua folosind inducția matematică astfel încât oricare ar fi o secvență {x1,x2,x3,...,xn} cu x1<x2<x3<...<xn avem f(x1) <f(x2)<f(x3)<..<f(xn). Se poate folosi inducția luând în considerare adâncimea fiecărui conductor într-o rețea oarecare de comparare pentru a demonstra un rezultat mai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
xn). Se poate folosi inducția luând în considerare adâncimea fiecărui conductor într-o rețea oarecare de comparare pentru a demonstra un rezultat mai puternic decât afirmația din lemă: dacă se presupune că un conductor primește valoarea ai când se aplică secvența a rețelei, atunci el ia valoarea f(aiĂ când se aplică secvența de intrare f(a) . Deoarece firele de ieșire sunt incluse în această propoziție demonstrarea ei va demonstra lema. Pentru început considerăm un fir de adâncime 0 care este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o rețea oarecare de comparare pentru a demonstra un rezultat mai puternic decât afirmația din lemă: dacă se presupune că un conductor primește valoarea ai când se aplică secvența a rețelei, atunci el ia valoarea f(aiĂ când se aplică secvența de intrare f(a) . Deoarece firele de ieșire sunt incluse în această propoziție demonstrarea ei va demonstra lema. Pentru început considerăm un fir de adâncime 0 care este în firul de intrare ai. Rezultatul apare banal: când f(a) este
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ieșirea unui comparator de adâncime d, și firul de intrare în acest 18 comparator are o adâncime strict mai mică decât d. Prin inducție, de aceea, dacă firele de intrare în comparator poartă valorile ai și aj când se aplică secvența de intrare a atunci ele poartă valorile f(ai) și f(aj) când secvența de intrare f(a) este aplicată. Conform afirmației noastre anterioare, firele de ieșire ale acestui comparator vor purta f(min(ai, aj)) și f(max(ai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
are o adâncime strict mai mică decât d. Prin inducție, de aceea, dacă firele de intrare în comparator poartă valorile ai și aj când se aplică secvența de intrare a atunci ele poartă valorile f(ai) și f(aj) când secvența de intrare f(a) este aplicată. Conform afirmației noastre anterioare, firele de ieșire ale acestui comparator vor purta f(min(ai, aj)) și f(max(ai, aj)). De vreme ce ele poartă min(ai, aj) și max(ai, aj) atunci când secvența de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
când secvența de intrare f(a) este aplicată. Conform afirmației noastre anterioare, firele de ieșire ale acestui comparator vor purta f(min(ai, aj)) și f(max(ai, aj)). De vreme ce ele poartă min(ai, aj) și max(ai, aj) atunci când secvența de intrare este a, lema este dovedită. Ca un exemplu de aplicare a lemei 1, figura 8 prezintă rețeaua de sortare din figura 2 cu funcția monoton crescătoare f(x) = [x/ 2] aplicată la intrările sale. Valorile de pe fiecare fir
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 pe care rețeaua nu le
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, . . . , an} conținând elementele
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 lui ai
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 lui ai în secvența de ieșire. Definim
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă aj înaintea lui ai în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă aj înaintea lui ai în secvența de ieșire, când se aplică la intrare secvența {a1, a2, . . . , an}, ar urma conform lemei 1 să plaseze în secvența de ieșire
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă aj înaintea lui ai în secvența de ieșire, când se aplică la intrare secvența {a1, a2, . . . , an}, ar urma conform lemei 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ș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ă aj înaintea lui ai în secvența de ieșire, când se aplică la intrare secvența {a1, a2, . . . , an}, ar urma conform lemei 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ai în secvența de ieșire. Definim o funcție monoton crescătoare f ca: Din moment ce rețeaua plasează aj înaintea lui ai în secvența de ieșire, când se aplică la intrare secvența {a1, a2, . . . , an}, ar urma conform lemei 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 secvențe
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 nu ar
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]