706 matches
-
și ieșirea inferioară a comparatorului D conectează la conductoarele de ieșire b1 și b4, respectiv, ale rețelei de comparare și aceste conductoare de ieșire ale rețelei de comparare conțin valorile finale la timpul 2. În același timp, la timpul 2, comparatorul E are disponibile valorile la intrare, și figura 2(d) arată că acesta și produce valorile de ieșire la timpul 3. Aceste valori sunt conținute de conductoarele de ieșire ale rețelei b2 și b3, iar secvența de ieșire {2, 5
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
că dacă la intrare se aplică secvența {9, 6, 5, 2} vom obține la ieșire aceeași secvență ordonată crescător de sus în jos, adică {2, 5, 6, 9}. Acest aspect poate fi ilustrat edificator în figura 3 : Presupunând că fiecare comparator are același timp de execuție, timpul unitate, putem defini timpul de execuție al unei rețele de comparare, ca fiind timpul necesar ca fiecare conductor de ieșire să primească valorile odată ce conductoarele de intrare și le-au primit pe ale lor
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de execuție al unei rețele de comparare, ca fiind timpul necesar ca fiecare conductor de ieșire să primească valorile odată ce conductoarele de intrare și le-au primit pe ale lor. Acest timp este egal cu numărul cel mai mare de comparatoare pe care fiecare element de intrare trebuie să-l traverseze de la intrare până la ieșire. Mai formal, definim adâncimea unui conductor după cum urmează. Un conductor de intrare al unei rețele de comparare are adâncimea 0. Dacă comparatorul are două conductoare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
mai mare de comparatoare pe care fiecare element de intrare trebuie să-l traverseze de la intrare până la ieșire. Mai formal, definim adâncimea unui conductor după cum urmează. Un conductor de intrare al unei rețele de comparare are adâncimea 0. Dacă comparatorul are două conductoare de intrare cu dimensiunile dx și dy, atunci conductoarele lor de ieșire au dimensiunile de max(dx, dy) + 1. Pentru că într-o rețea de comparare nu sunt bucle, adâncimea unui conductor este bine definită și vom
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de intrare cu dimensiunile dx și dy, atunci conductoarele lor de ieșire au dimensiunile de max(dx, dy) + 1. Pentru că într-o rețea de comparare nu sunt bucle, adâncimea unui conductor este bine definită și vom defini adâncimea unui comparator ca fiind egală cu adâncimea conductoarelor lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
dy) + 1. Pentru că într-o rețea de comparare nu sunt bucle, adâncimea unui conductor este bine definită și vom defini adâncimea unui comparator ca fiind egală cu adâncimea conductoarelor lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
vom defini adâncimea unui comparator ca fiind egală cu adâncimea conductoarelor lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate de timp pentru a produce o valoare de ieșire și dacă intrările în rețea se aplică la timpul 0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
lor de ieșire. În figura 2 este prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate de timp pentru a produce o valoare de ieșire și dacă intrările în rețea se aplică la timpul 0, un comparator de adâncime d furnizează valorile de ieșire la timpul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
prezentată adâncimea unui comparator. Adâncimea unei rețele de comparare este adâncimea maximă a unui conductor de ieșire sau adâncimea maximă a unui comparator. De exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate de timp pentru a produce o valoare de ieșire și dacă intrările în 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ă
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
exemplu, rețeaua din figura 2 are adâncimea trei deoarece comparatorul E are adâncimea trei. Dacă fiecare comparator consumă o unitate de timp pentru a produce o valoare de ieșire și dacă intrările în 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D.
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a comparatorului B. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile corecte, ceea ce se întâmplă în pasul 3. O rețea de comparare poate fi asemănată cu o procedură în care se specifică câte comparații trebuie să
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile corecte, ceea ce se întâmplă în pasul 3. O rețea de comparare poate fi asemănată cu o procedură în care se specifică câte comparații trebuie să survină dar nu cu o
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 din figura 2 la intrare secvența {9,6,5,2} și după primii doi comparatori
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 va exista nici un comparator (1,2). Astfel valoarea minimă din rețea va fi în final pe conductorul 2. În
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 va exista nici un comparator (1,2). Astfel valoarea minimă din rețea va fi în final pe conductorul 2. În figura 6 putem observa acest aspect: Un alt aspect de semnalat ar fi că o rețea de comparare cu n intrări și c comparatori se
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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) furnizează la ieșire f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
un singur comparator cu intrările f(x) si f(y) furnizează la ieșire f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține valoarea min(f(x), f(y)) iar la ieșirea inferioară valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține valoarea min(f(x), f(y)) iar la ieșirea inferioară valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y implică f(x) ≤ f(y). Corespunzător avem identitățile: min(f(x), f(y)) = f(min
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y implică f(x) ≤ f(y). Corespunzător avem identitățile: min(f(x), f(y)) = f(min(x,y)) , max(f(x), f(y)) = f(max(x,y)) . 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de intrare ai. Rezultatul apare banal: când f(a) este aplicat rețelei firul de intrare va primi în mod automat valoarea f(aiă, pentru pasul inductiv se consideră un fir de adâncime d, unde d ≥1. Firul este 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]