3,716 matches
-
timpul de execuție” în cazul unei rețele de comparare arătând legătura dintre acesta și adâncimea rețelei. În secțiunea 2 se demonstrează principiul zero- unu care simplifică foarte mult procesul de analiză a corectitudinii unei rețele de sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețelei. În secțiunea 2 se demonstrează principiul zero- unu care simplifică foarte mult procesul de analiză a corectitudinii unei rețele de sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi celula de bază în construcția rețelei de sortare. În secțiunea 4 vom modifica puțin sortatorul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi celula de bază în construcția rețelei de sortare. În secțiunea 4 vom modifica puțin sortatorul bitonic pentru a obține o rețea cu interclasare care poate interclasa, două secvențe deja sortate într-o singură secvență sortată. În
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi celula de bază în construcția rețelei de sortare. În secțiunea 4 vom modifica puțin sortatorul bitonic 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
modifica puțin sortatorul bitonic 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețea se aplică la timpul 0, un comparator de adâncime d furnizează valorile de ieșire la timpul d; adâncimea unei rețele este deci egală cu timpul necesar ca rețeaua să producă valorile la toate conductoarele de ieșire. O rețea de sortare este o rețea de comparare pentru care secvența de ieșire crește monoton pentru orice secvență de intrare. Bineînțeles, nu orice rețea de comparare este o rețea de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețeaua să producă valorile la toate conductoarele de ieșire. O rețea de sortare este o rețea de comparare pentru care secvența de ieșire crește monoton pentru orice secvență de intrare. Bineînțeles, nu orice rețea de comparare este o rețea de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că după timpul 1, cea mai mică dintre cele patru valori de intrare se obține fie la ieșirea superioară a comparatorului A sau la cea superioară a comparatorului B.
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cu o procedură în care adâncimea sa fizică depinde de numărul de intrări și ieșiri. De aceea vom descrie practic familii de rețele de comparare. De exemplu, scopul este de a dezvolta o familie, numită SORTER, de rețele eficiente de sortare. Vom specifica o anume rețea în cadrul unei familii de rețele prin numele familiei și numărul de intrări (care este întotdeauna egal cu numărul de ieșiri). De exemplu, rețeaua de sortare cu n intrări și n ieșiri din familia SORTER
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
dezvolta o familie, numită SORTER, de rețele eficiente de sortare. Vom specifica o anume rețea în cadrul unei familii de rețele prin numele familiei și numărul de intrări (care este întotdeauna egal cu numărul de ieșiri). De exemplu, rețeaua de sortare cu n intrări și n ieșiri din familia SORTER este numită SORTER[n]. Se poate demonstra că fiind dat un număr n=8, de exemplu, ca putere a lui 2 se poate construi o rețea de comparare cu n=8
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
în care conductorul de ieșire superioară furnizează întotdeauna valorile minime de la intrare iar cea inferioară pe cele maxime. Spre exemplificare propun rețeaua din figura 4: Se poate observa că și 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ă
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de ieșire superioară furnizează întotdeauna valorile minime de la intrare iar cea inferioară pe cele maxime. Spre exemplificare propun rețeaua din figura 4: Se poate observa că și 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
4: Se poate observa că și 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
și se reține maximul care constituie dimensiunea rețelei. Complexitatea algoritmului este O(n+că deoarece se parcurge odată lista de c comparatori și apoi tabloul cu n elemente. Secțiunea 2 Principiul zero-unu Principiul zero-unu afirmă că dacă o rețea de sortare lucrează corect atunci când la orice intrare se aplică doar numere din mulțimea {0,1}, atunci va lucra corect și cu numere arbitrare de intrare, numerele pot fi întregi, reale sau, în general, orice set de valori liniar ordonate. Cum va
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
intrare se aplică doar numere din mulțimea {0,1}, atunci va lucra corect și cu numere 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
din figura 2 cu funcția monoton crescătoare f(x) = [x/ 2] aplicată la intrările sale. Valorile de pe fiecare 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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,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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 ca o rețea de sortare cu n intrări trebuie să conțină 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ŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, presupunerea făcută este falsă și deci întro rețea 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, presupunerea făcută este falsă și deci întro rețea 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
nu poate fi vorba despre o rețea de sortare. De aici, presupunerea făcută este falsă și deci întro rețea 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
De aici, presupunerea făcută este falsă și deci întro rețea 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]