6 matches
-
finală, inerția interclase este nulă și inerția intraclasă este egală cu inerția totală, deoarece acum există o singură clasă ce conține toate elementele. În consecință, pe măsură ce se execută agregările, prin regruparea elementelor, se constată că inerția intraclasă crește, în timp ce inerția interclasă scade. Prin urmare, principiul algoritmului de agregare conform varianței constă în căutarea în fiecare etapă a împărțirii celei mai bune, în care varianța internă a fiecărei clase să fie minimă și în consecință varianța interclase să fie maximă. Strategia de
A M P E L O G R A F I E M E T O D E ? I M E T O D O L O G I I D E D E S C R I E R E ? I R E C U N O A ? T E R E A S O I U R I L O R D E V I ? ? D E V I E by Doina DAMIAN, Liliana ROTARU, Ancu?a NECHITA, Costic? SAVIN () [Corola-publishinghouse/Science/83089_a_84414]
-
Î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 într-o rețea de sortare care știe să sorteze n valori de intrare în timpul O(log2 n
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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ă intrările i și n/2 + i, pentru i = 1, 2, . . . , n/2, noi facem ca primul etaj
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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. 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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, 2, . . ....,lg n, etajul k constă din n/2k copii ale lui MERGER[2k] care asamblează perechi de secvențe
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
și trasează 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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]