15,469 matches
-
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 intrare sortate într-o singură secvență de ieșire de asemeni sortată. Rețeaua MERGER[n] poate fi văzută ca un BITONICSORTER[n] cu
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 intrare sortate într-o singură secvență de ieșire de asemeni sortată. Rețeaua MERGER[n] poate fi văzută ca un BITONICSORTER[n] cu primul semi-cleaner modificat ca să compare intrările i și n - i + 1 pentru i = 1, 2, . . . , n/2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 intrare sortate într-o singură secvență de ieșire de asemeni sortată. Rețeaua MERGER[n] poate fi văzută ca un BITONICSORTER[n] cu primul semi-cleaner modificat ca să compare intrările i și n - i + 1 pentru i = 1, 2, . . . , n/2. Aici n = 8. (a) Rețeaua descompusă în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n] este diferit de BITONICSORTER[n]. Corespunzător adâncimea lui MERGER[n] este lg n, aceeași ca cea a lui BITONIC-SORTER[n]. Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii ale lui SORTER[n/2] pentru a sorta (în paralel) două subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1, în care caz putem utiliza un fir pentru a sorta secvența de 1element , de vreme ce o secvență de 1-element este deja sortată. Figura 15 (b
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a sorta (în paralel) două subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1, în care caz putem utiliza un fir pentru a sorta secvența de 1element , de vreme ce o secvență de 1-element este deja sortată. Figura 15 (b) arată rezultatul folosirii recursiei iar figura 15 (c) arată rețeaua curentă obținută prin înlocuirea căsuțelor MERGER în figura 15 (b) cu rețelele de interclasare curente. Datele traversează
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
subsecvențe de lungime n/2 fiecare. Cele două secvențe care rezultă sunt apoi asamblate de MERGER[n]. Cazul limită pentru recursie este când n = 1, în care caz putem utiliza un fir pentru a sorta secvența de 1element , de vreme ce o secvență de 1-element este deja sortată. Figura 15 (b) arată rezultatul folosirii recursiei iar figura 15 (c) arată rețeaua curentă obținută prin înlocuirea căsuțelor MERGER în figura 15 (b) cu rețelele de interclasare curente. Datele traversează lg n etaje în rețeaua
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
folosirii recursiei iar figura 15 (c) arată rețeaua curentă obținută prin înlocuirea căsuțelor MERGER în figura 15 (b) cu rețelele de interclasare curente. Datele traversează lg n etaje în rețeaua SORTER[n]. Fiecare intrare individuală în rețea este deja o secvență sortată de 1-element . Acest prim etaj al lui SORTER[n] constă în n/2 copii ale lui MERGER[2] care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețeaua SORTER[n]. Fiecare intrare individuală în rețea este deja o secvență sortată de 1-element . Acest prim etaj al lui SORTER[n] constă în n/2 copii ale lui MERGER[2] care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețea este deja o secvență sortată de 1-element . Acest prim etaj al lui SORTER[n] constă în n/2 copii ale lui MERGER[2] care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
care lucrează în paralel pentru a interclasa perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
perechi de secvențe de 1- element pentru a produce secvențe sortate de lungime 2. Cel de-al doilea etaj conține n/4 copii ale lui MERGER[4] care interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
interclasează perechi de astfel de secvențe sortate de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de 2-elemente pentru a produce secvențe sortate de lungime 4. În general, pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform principiului zero-unu (Teorema 2
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
pentru k = 1, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform principiului zero-unu (Teorema 2), poate sorta valori arbitrare. Putem analiza adâncimea unei rețele de sortare recursiv
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform principiului zero-unu (Teorema 2), poate sorta valori arbitrare. Putem analiza adâncimea unei rețele de sortare recursiv. Adâncimea D(n) a lui SORTER[n] este adâncimea D(n/2) a SORTER[n/2] (sunt două copii
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
istoria lor. Aparent ele au fost prima dată explorate în 1954 de P. N. Armstrong, R. J. Nelson, si D. J. O'Connor. În primii ani ai lui 60, K. E. Batcher a descoperit prima rețea capabilă să interclaseze două secvențe de n numere în timpul O(lgn) . El a folosit interclasarea par-impar și de asemenea a arătat cum poate fi folosită această tehnică pentru a sorta n numere în timpul O(lg2n) . La scurt timp după aceea a descoperit un sortator bitonic
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
ea, meniul principal cu butoanele aferente acestuia. În vederea desenării unor astfel de rețele utilizăm o procedură care încarcă valorile dintr-un fișier de tip *.val, prin care se poate introduce de la tastatură numărul de fire precum și valorile efective, ce reprezintă secvența de intrare pentru rețea. Totodată în cadrul programului prin intermediul unei proceduri se oferă și posibilitatea de încărcare a unei rețele dintr-un fișier de tip *.sn, în sensul de a schimba în mod voit modul de comparare prin introducerea de la tastatură
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
permite realizarea de fapt a rețelei de sortare finală. În cadrul acestei proceduri există condiția de verificare cu privire la încărcarea unui fișier de valori, care în caz afirmativ reface toate firele cu valorile de rezervă și șterge toate comparatoarele, prin secvența: De fapt toate acestea se regăsesc în toate procedurile din care se apelează un tip de rețea, drept pentru care le-am prezentat numai pentru procedura redată anterior. După această parte urmează apelul procedurilor specifice, ce fac sortarea și desenarea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
sale respectiv imaginea în care se face desenarea precum și imaginea folosită pentru salvare, după cum urmează: Totodată procedura conține și posibilitatea de verificare și corectare pentru cazul în care fereastra de vizualizare iese în afara ecranului, aspect ce poate fi observat în secvența: În fine în partea de program intitulat „utils.pas” găsim modul de implementare a funcțiilor și procedurilor ce pot fi apelate și care în mod firesc sunt necesare în vederea realizării scopului propus. Astfel, pentru început putem prezenta funcțiile ce permit
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
propus. Astfel, pentru început putem prezenta funcțiile ce permit calculul maximului și minimului dintre două numere, declarate în felul următor: O altă funcție necesară care calculează spațiul ocupat de cel mai mare număr pozitiv dintre datele de intrare apare în secvență: Funcția care returnează poziția X a celui mai din dreapta comparator dintre toți comparatorii care au adâncimea dată ca parametru apare în modul următor: Pe lângă funcțiile ce sunt implementate în cadrul programului și care au fost prezentate anterior, în continuare vom
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
le induce conductoarelor: Modul de implementare a semi-cleanerului poate fi remarcată prin utilizarea procedurii următoare, în care își fac apariția și procedurile de adăugare și sortare a comparatorilor: Algoritmul de sortare bitonică poate fi de asemenea pus în evidență prin secvența: Algoritmul de sortare prin interclasare în care este prezentă adăugarea, sortarea comparatorilor precum și sortarea bitonică, se poate evidenția în cele ce urmează: Modul de implementare a algoritmului de sortare ce își face prezența în cadrul procedurii ce este apelată la accesarea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
unor proceduri analizate anterior precum și un instrument folosit pentru pictarea background-ului imaginii, în speță brush, care setează de obicei culoarea pe care să scrii, pot fi expuse sub forma: Afișarea datelor de intrare în rețea poate fi prezentată în secvența următoare, din care se desprind câteva aspecte legate de modul de setare a culorii fontului, a culorii background-ului pe care se desenează, a mărimii fontului, precum și procedura de afișare a unui text pe un canvas: Afișarea datelor de ieșire
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
culorii background-ului pe care se desenează, a mărimii fontului, precum și procedura de afișare a unui text pe un canvas: Afișarea datelor de ieșire din rețea, în mod asemănător, poate fi exemplificată după cum urmează: Afișarea de comparatori este realizată în secvența pe care o propun și în care pe lângă instrumentele brush, pen și funcția ce calculează poziția X pe imagine a fiecărui comparator relativ la poziția sa în tabloul de comparatori, utilizez și o procedură de desenare a unei elipse ce
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
creșterea și descreșterea” personajului ales, comunismul, cu ajutorul unor decupaje cronologice previzibile, delimitate de schimbarea deținătorilor vizibili ai puterii. Periodizarea pare ușor deductibilă din orice istorie a comunismului est-central-european: al Doilea Război Mondial, cucerirea puterii, stalinismul, comunismul național, modernizarea, implozia. SÎnt secvențe ce ar putea fi regăsite oriunde În fostul „lagăr socialist” dacă nu ar fi Însoțite de nominalizările poloneze: Gomulka, Gierek, Jaruzelski. Astfel de personalizări ale regimului trimit la un cunoscut reflex al istoriei politice, acela de a se Încredința șirului
[Corola-publishinghouse/Science/1866_a_3191]