Metode de organizare a efectelor de animaţie în Pascal

Principiile didactice sunt teze fundamentale, norme generale care stau la baza proiectării, organizării şi desfăşurării activităţilor de predare - învăţare, în vederea realizării optime a obiectivelor educaţionale. Principiile didactice au caracter general-normativ, sistematic şi dinamic-deschis.

Caracterul general rezultă din faptul că principiile didactice vizează toate componentele procesului de învăţământ, sunt aplicabile permanent în procesul de predare - învăţare la informatică. Principiile didactice au caracter normativ prin funcţia lor, orientativă şi reglatoare, în stabilirea obiectivelor, în structurarea conţinutului, în alegerea formelor de realizare a procesului de predare - învăţare, în alegerea strategiilor didactice prin îmbinarea metodelor, a mijloacelor de instruire şi realizarea evaluării.

Caracterul sistematic rezultă din faptul că principiile didactice sunt sisteme de norme care trebuie aplicate în fiecare forma de activitate didactică. Nerespectarea unui principiu didactic poate conduce la anularea sau atenuarea celorlalte.

Caracterul dinamic deschis al principiilor didactice rezulta din faptul că acestea nu sunt rigide. Numărul principiilor nu este limitat, ele pot multiplica sau integra în principii cu o sfera mai larga. Principiile didactice permit manifestarea creativităţii în proiectarea şi realizarea activităţii instructiv-educative.

§1. Principiul intuiţiei sau unităţii dintre senzorial şi raţional

Principiul intuiţiei exprimă necesitatea obiectelor, fenomenelor şi proceselor prin intermediul simţurilor, care realizează cunoaşterea senzoriala a realităţii, ca punct de plecare şi de uşurare a înregistrării esenţialului realităţii spre cunoaşterea logica, raţională, contribuind la înfăptuirea unităţii dintre senzorial şi raţional.

Principiul intuiţiei a apărut ca un demers legic împotriva învăţării scolastice, învăţării mecanice, pe de rost, împotriva buchiselii. Principiul intuiţiei a corespuns necesităţii psiho-pedagocice a realizării unui învăţământ bazat pe înţelegere, legat de viaţă, realist.

Realizând unitatea dintre cunoaşterea senzoriala şi cea raţională, principiul intuiţiei nu înseamnă deci rămânerea la treapta cunoaşterii senzoriale. El realizează treapta cunoaşterii senzoriale, pentru uşurarea înţelegerii, pentru a ajunge la treapta dificilă, dar de mare importanţă pentru cunoaştere, treapta învăţării logice (a cunoaşterii raţionale), bazată pe studierea elementelor şi conexiunilor abstracte, esenţiale şi generale exprimate, prin noţiuni, concepte, idei, teorii, principii etc. Numai astfel se poate ajunge prin învăţare la însuşirea ştiinţei. Principiul intuiţiei face ca învăţarea să fie mai întâi ca o reflectare în mintea elevilor sub formă de percepţii şi reprezentări. Percepţiile şi reprezentările nu sunt simple imagini (fotografii) globale ale realităţii, ci ele sunt acte psihice de cunoaştere activă, de reflectare cognitivă, care stau la baza realizării proceselor psihice ideatice sub forma noţiunilor, ideilor, teoriilor etc., deci de cunoaştere (învăţare) raţională. În acest context, a intui înseamnă a observa şi a gândi în acelaşi timp.

Principiul intuiţiei se realizează prin îmbinarea materialului didactic intuitiv-natural la scara lor reala, şi de substitute (machete, modele, reprezentări grafice, mijloace audio-vizuale, mijloace logico-matematice etc.).

Pedagogul elveţian Robert Dottrens spunea: „Nu există obiectul, nu trebuie să aibă loc predarea”.

Îmbinarea echilibrată a celor trei componente: imaginea, cuvântul şi elementele logico-matematice reprezintă esenţa intuiţiei pentru o învăţare eficientă.

Prezentarea materialului intuitiv este un mijloc de învăţare eficientă, organizată, dirijată, sistematică, activă, corelată cu interesele şi trebuinţele elevului, elevii nu ştiu să observe, ei trebuie învăţaţi să vadă şi să desprindă din obiecte şi fenomene esenţialul, dar şi specificul particularul. Nu este suficient să priveşti, să mânuieşti, să pipăi, să cântăreşti obiectele pentru a obţine o cunoştinţă ştiinţifică despre realitate, ci este necesar să sesizezi esenţialul prin problematizare. Obiectele nu-l instruiesc singure pe elev, ci profesorul instruieşte cu ajutorul acestora prin orientarea gândirii şi interpretării, prin problematizare, prin emitere de ipoteze. Dacă profesorul nu îndrumă intuiţia elevilor, ei reţin caracterele particulare ale obiectelor (culoare, formă, mărime, mişcare) care le atrag atenţia şi nu sesizează esenţialul, de aceia este necesară intuirea polimodata, dirijată prin cuvânt, sistematizată după un plan, într-o ordine logică. Instruirea nu se reduce la furnizarea imaginilor sau reprezentărilor unor obiecte, evenimente, la înlocuirea „verbalismului cuvântului” cu „verbalismul imaginii”. Nu modelul în sine şi simpla intuire duce la învăţarea cu sens şi are efecte formative, ci acţiunea cu modelul, prin care elevul însuşi descoperă relaţii, principii, legităţi.

Download Grafica

Tipul de date fişier în Pascal

O temă destul de dificilă din cursul liceal de informatică este tema „Tipuri structurate de date. Tipul fişier (file)”.

Despre necesitatea cunoaşterii şi aplicabilitatea tipului de date fişier ne conving culegerile de probleme la informatică.

Practica arată că elevul trebuie să revină periodic la rezolvarea diferitor probleme cu aplicarea tipului de date fişier. Acest fapt contribuie la dezvoltarea gîndirii analitice, a intuiţiei şi a creativităţii, calităţii necesare pentru studierea ulterioară a informaticii atît la treapta liceală, cît şi în învăţămîntul universitar.

Unii elevi învaţă mai eficient rezolvînd probleme rezolvate. Nu este vorba de memorarea rezolvării (deşi şi acest lucru este util la o anumită etapă de învăţare, nu oricine poate rezolva orice, dar oricine poate învăţa o rezolvare), ci de reluarea rezolvării pe altă cale. În acest scop profesorul poate propune elevilor rezolvarea unor exemple mai dificile, urmate ulterior de discuţii asupra metodelor de rezolvare.

Să nu uităm de sfatul lui G.Polya: „Dacă vreţi să învăţaţi să rezolvaţi probleme, trebuie... să rezolvaţi probleme”.

Teza are drept scop studierea detaliată a temei şi formularea unor metode şi strategii didactice pebtru predarea – învăţarea – evaluarea temei „Tipul de date fişier”.

Lucrarea constă din două capitole:

Capitolul I constă din 9 paragrafe, unde sunt expuse noţiunile teoretice generale despre tipul de date fişier şi anume: clasificarea fişierelor, fişiere cu tip, fişire fără tip, fişiere text, proceduri şi funcţii definite asupra tipului de date fişier.

Capitolul II constă din 5 paragrafe. Acest capitol conţine informaţii referitoare la: curriculum liceal la tema „Tipul de date fişier (file)”, unde sunt prezente numărul de ore (opţional) şi aranjarea lor pentru predare-învăţare; tratarea temei „Tipul de date fişier (file)” în manualul Informatica. Limbajul de programare Pascal. Manual pentru clasele IX-XI de Anatol Gremalschi, Iurie Mocanu şi Ion Spinei; necesitatea utilizării problematizării la lecţiile de informatică. La fel se conţine un şir de probleme de dificultate diferită ce pot fi propuse elevilor pentru antrenament şi consolidarea cunoştinţelor la tema „Tipul de date fişier (file)”. Ultimul paragraf al acestui capitol, şi anume „Sugestii privind evaluarea” aduce cititorului un set de teste de evaluare formativă şi sumativă ce au ca scop determinarea nivelului de cunoştinţe a elevilor, a abilităţilor lor, determinarea erorilor şi posibilitatea lichidării lor.

Prezenta lucrarea are drept scop familiarizarea cititorului cu noţiuni de predare – învăţare – evaluare a temei tipul fişier în liceu. Această lucrare poate fi utilă studenţilor şi profesorilor.

§1. Clasificarea fişierelor

Fişierul este o colecţie organizată de informaţii (date, rezultate, programe sursă, programe direct executabile etc.), dispuse pe unul sau mai multe suporturi externe.

Componentele unui fişier se numesc înregistrări (articole) şi pot avea dimensiune fixă sau variabilă. Numărul de componente dintr-un fişier este variabil, fiind limitat doar de capacitatea de memorare a suportului utilizat. Sfîrşitul unui fişier este uneori marcat printr-o componentă specială (end of file - caracterul ^Z).

Fişierul, în contextul limbajului Pascal, este o structură de date omogenă, formată din componente de acelaşi tip, exceptînd tipul fişier.

Înregistrarea este constituită dintr-o mulţime de valori ale unor caracteristici asociate unui obiect, proces etc., din domeniul aplicaţiei.

Componentele înregistrării asociate diverselor caracteristici sunt denumite cîmpuri de date.

Limbajul Pascall permite utilizarea fişierelor cu înregistrări de lungime fixă (stabilită la momentul prelucrării) şi variabilă (două înregistrări alăturate sunt separate prin marcaje speciale, de exemplu prin caracterele CR/LF - sfîrşit de linie).

Din punct de vedere fizic (al suportului extern), fişierul este o succesiune de octeţi.

Accesul la componentele unui fişier are la bază următorul mecanism: fiecare fişier are un indicator (pointer) al componentei curente, cea accesibilă în acel moment. Pentru fiecare acces la fişier (adică, pentru fiecare operaţie de citire sau scriere), indicatorul avansează de la componenta curentă la următoarea componentă, care devine astfel componenta curentă.

Modul de acces la componente poate fi: secvenţial (accesul la componenta n din fişier trebuie precedat de inspectarea componentelor 0, 1, 2,    , n-1) şi direct sau aleator (poziţionarea se face direct pe componenta respectivă).

Cînd se lucrează cu un fişier, acestuia i se asociază o variabilă tampon avînd tipul de bază al componentelor fişierului. Variabila tampon realizează interfaţa între fişier şi program.

Variabilelor fişier (utilizate în programe, atunci cînd lucram cu fişiere) li se asociază, de obicei, fişiere fizice, aflate pe suport extern şi gestionate de către sistemul de operare. În conţinuare, vom nota cu f variabila fişier utilizată la un moment dat.

Din punct de vedere al limbajului Pascal şi al conţinutului lor, fişierele se împart în două mari categorii:

• fişiere text, în care toate datele sunt sub formă de caractere ASCII (un caracter/octet). Practic, fişierele text conţin caractere organizate în linii de lungime variabilă, liniile consecutive fiind separate printr-un marcaj de sfîrşit de linie (end of line) reprezentat prin perechea de caractere de control Carriage Return şi Line Feed - CR/LF.


• fişiere binare, în care toate datele sunt memorate în formă identică cu cea din memoria principală. Practic, fişierele binare sunt fişiere cu componente de tipuri definite de programator.

Fişierele binare se împart, la rîndul lor, în două clase:

• fişiere cu tip (în care înregistrările au structura şi lungimea fixe, precizate la momentul fiecărei prelucrări);

fişiere fără tip (în care înregistrările sunt blocuri binare de lungime fixă, precizată ca parametru în procedura de deschidere a fişierului; nu se face nici o ipoteză referitoare la structura blocurilor; un bloc este o succesiune de octeţi)

Download Fisiere

Auto Draft

Alocarea memoriei în Turbo Pascal

Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le voi prezenta în continuare. Definiţie: Printr-un tip de dată  înţelegem o mulţime cu elemente numite valori. De sxemplu:{-32768, -32767,...0,1, ...32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. În Turbo Pascal un astfel de tip se numeşte integer şi este predefinit. Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului. De exemplu, pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc. Pentru fiecare tip se defineşte modul în care se memorează valorile sale. De exemplu, pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi. Pentru a lucra cu date de un anumit tip se folosesc variabile. O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi). Tipurile de date pot fi simple şi structurate. Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Noţiunea de tip de date este strînsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date. De exemplu, mulţimea este o structură de date. În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Variabilele declarate în secţiunea var a unui program sau subprogram se numesc variabile statice. Numărul variabilelor statice se satabileşte în momentul scrierii programului şi nu poate fi schimbat în timpul execuţiei. Există însă situaţii în care numărul necesar de variabile nu este cunoscut din timp. De exemplu, presupunem că este necesară prelucrarea datelor referitoare la persoanele care formează o listă de aşteptare (o coadă) la o casă de bilete. Lungimea cozii este nedefinită. De fiecare dată cînd apare o persoană nouă, trebuie să se creeze o variabilă de tipul respectiv. După ce persoana pleacă – variabile evine inutilă. Variabilele care sunt create şi eventual distruse în timpul execuţiei programului se numesc variabile dinamice O structură de date este formată din datele propriu-zise şi relaţiile dintre ele. În funcţie de modul de organizare, o structură de date poate fi implicită sau explicită. Tablourile, şirurile de caractere, articolele, fişierele şi mulţimile sunt structuri implicite de date. Relaţiile dintre componentele acestor structuri sînt predefinite şi nemodificabile. De exemplu, toate componentele unui şir de caractere au un nume comun, iar caracterul s[i+1] este succesorul caracterului s[i] în virtutea poziţiei ocupate. Structurile de date se clasifică în două mari categorii: statice şi dinamice. Criteriul de clasificare este dat de modul de alocare a memoriei interne. Întrucît structura tablourilor, şirurilor de caractere, articolelor, mulţimilor, fişierelor nu se modifică în timpul execuţiei oricărul program sau subprogram, structurile respective reprezintă structuri statice de date.

§1. Tabloul

Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale. Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi. Definiţie: Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare. Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente. Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indicii. Exemplul 1: Distanţa dintre două mulţimi în plan se consideră distanţa dintre două puncte ale acestor mulţimi, situate cel mai aproape unul de altul. Aflaţi distanţa dintre două mulţimi de puncte date. (pr.38, §5, [1])

Download Alocarea-memoriei

Modulul Graph în Turbo Pascal

1. Iniţializarea regimului grafic

Placa grafică sau adaptorul de ecran este componenta hard a calculatorului care asigură gestiunea memoriei şi controlul monitorului video. Driver-ul grafic este componenta soft-ului care comandă placa grafică. Placa grafică tratează ecranul în două moduri:

În regimul text fiecare caracter ce apare la ecran este păstrat în memoria calculatorului în doi octeţi, unul cuprinde codul ASCII al caracterului, iar al doilea culorile, iluminarea, culoarea fonului şi clipirea. În regimul grafic memoria ecranului are un cod pentru fiecare pixel prin care se determină culoarea pixelui.

Zona de memorie ecran pentru memorarea unui ecran se numeşte pagină video. Pagina video care apare la un moment dat pe ecran se numeşte pagină vizibilă. Prelucrarea informaţiei grafice în Pascal este susţinută de modulul Graph.

Modulul Graph pune la dispoziţie circa 90 de proceduri şi funcţii păstrate în fişierul graph.tpu. Utilizarea procedurilor şi funcţiilor grafice este posibilă dacă în partea declarativă uses vom declara modulul graph. Fiecare regim grafic are driver-ul său specific. Tabelul  următor conţine lista regimurilor grafice posibile pentru diferite adaptoare grafice. În prima coloniţă sunt indicare  tipurile de drivere, în a doua – numărul de pixeli de pe ecran, în coloniţa a treia este indicată palitra de culori a regimului dat, în ultima coloniţă sunt indicate numărul de pagini video care se pot încărca simultan în memoria videoadaptorului.

Orice program Turbo Pascal ce conţine prelucrarea informaţiei grafice trebuie să cuprindă:

[like url=http://resurse-educationale.uv.ro/]Iniţializarea regimului grafic se relizează prin procedura InitGraph cu formatul:

InitGraph(var GraphDriver:integer; {tipul adaptorului}

var GraphMode:integer; {regimul grafic}

var DriverPath:string); {calea spre driver}

De exemplu:

procedure ini;

var gd, gm:integer;

begin

gd:=detect;

initgraph(gd,gm,'c:\tp\bgi');

if graphresult<>grok then halt(1);

end;

Download Modulul Graph

Biblioteci în Turbo Pascal

Modulul UNIT  - este o unitate de program, textul căruia se compilează de sinestătător (autonom). Această unitate de program include descrierea constantelor, variabilelor, tipurilor de date utilizate, a procedurilor şi funcţiilor ce vor fi create şi care mai apoi vor putea fi chemate în programul de bază. Însă structura internă a modulului personal este ascunsă (în programul unde se apelează unit-ul) de utilizator.

Structura generală  a unui UNIT

Un modul poate fi despărţit în cîteva compartimente: antetul unit-ului, secţiunea de interfaţă, secţiunea de implementare, secţiunea de iniţializare (ea poate să lipsească).

Antetul unit-ului

Antetul modulului puţin se deosebeşte de antetul programului. În modul în locul cuvîntului rezervat Program se utilizează  cuvîntul rezervat Unit. Tot aici pot fi indicate directivele compilatorului.

La alegerea numelui modulului este necesar de luat în consideraţie următoarea latură specifică: vom ţine cont ca numele unit-ului să nu coincidă cu numele căreiva funcţii sau proceduri standarde, cuvînt rezervar sau numele alttui obiect de programare din interiorul programului. La această cerinţă se mai adaugă încă una: numele unit-ului trebuie să corespundă cu numele fişierului în care se păstrează acest unit. Deaceea numele unit-ului nu trebuie să conţină mai mult de opt simboluri.

Secţiunea de interfaţă

Nou spre deosebire de structura unui program este secţiunea de interfaţă. În acest compartiment se descriu toate constantele, tipurile de date şi variabilele, procedurile şi funcţiile accesibile în acest modul pentru a putea fi utilizate în cadrul altor programe externe. Secţiunea de interfaţă conţine toată informaţia, necesară pentru a putea fi accesată de altă programe, descrisă în modulul dat. Orice altă informaţie despre modul pentru a putea fi utilizat nu este necesară.

În secţiunea de interfaţă   este posibil de a face accesibili pentru utilizare module deja create indicînd numele lor în compartimentul uses. După operatorul uses se declară tipurile de date, vatiabilele ce vor fi utilizate la descrierea procedurilor şi funcţiilor descries în acest modul.

Toate procedurile şi funcţiile ce vor putea fi utilizate mai apoi în alte programe sunt descries în secţiunea de interfaţă indicîndu-se numele lor şi parametrii. Textul ca atare al procedurilor şi funcţiilor va fi mai apoi descries în secţiunea de implementare unde se va mai indica încă o dată numele procedurii sau funcţiei.

În practică este posibil şi cazul cînd secţiunea de interfaţă lipseşte aşa cum este indicat în exemplul leer.pas, ce conţine modulul Leer. Acest modul este foarte simplu şi este pur demonstrative.

unit Leer;

INTERFACE

{Acest compartiment este gol}

IMPLEMENTATION

uses crt;

begin

clrscr;

writeln(‘Salut!’)

end.

Secţiunea de implementare

Secţiunea de implementare este compartimentul modulului în care se scrie textul propriu zis al procedurilor şi funcţiilor descries în secţiunea de interfaţă. Procedurile şi funcţiile se descriu exact aşa cum ne-am obişnuit să o facem în programele obişnuite. Tipurile de date şi structura lor sunt inaccesibile pentru cealaltă pasrte a unit-ului şi sunt utilizate numai în secţiunea de implementare. La fel ca şi secţiunea de interfaţă secţiunea de implementare poate să fie vidă.

Secţiunea de iniţializare

Secţiunea de iniţializare reprezintă blocul principal al modulului. Instrucţiunile Indicate în acest bloc se îndeplinesc primele, adică mai întîi se îndeplinesc instrucţiunile din secţiunea de iniţializare a modulului, apoi instrucţiunile ce se conţin între begin şi end al programului Pascal ce utilizează modulul în cauză. De exemplu programul de mai jos exemplu.pas va fi realizat în felul următor: unit-ul Leer.tpu în secţiunea de implementare conţine instrucţiunile clrscr – curăţirea ecranului, apoi writeln(‘Salut!’) – afişează la ecran cuvîntul  Salut după care se va realiza instrucţiunea writeln(‘Program demonstrativ’).

program exemplu;

uses Leer;

begin

writeln(‘Program demonstrativ’)

end.

Pentru a putea utiliza acest unit în alte programe Pascal este necesar de a salva acest unit cu nume_unit.pas, apoi se va compila unit-ul tastînd [F9] (Compile) iar pentru opţiunea Destination se va instala valoarea Disk. În urma acestei operaţii pe disc se va forma fişierul nume_unit.tpu. dacă ve-ţi tasta [Ctrl+F9] atunci după compilare va apărea informaţia Can not run a unit care ne informează că unit-ul nou creat nu se poate realiza desinestătător.

Download Biblioteci in Pascal

Paralab. Описание параллельных методов решения сложных вычислительных задач

1.1. Сортировка данных

Общая схема параллельных вычислений при сортировке данных (см. раздел 3 пособия) состоит в разделении исходного упорядочиваемого набора на блоки и их распределения между процессорами, в ходе сортировки блоки пересылаются между процессорами и содержащиеся в них данные сравниваются между собой для упорядочения. Результирующий (отсортированный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами.

В системе ПараЛаб в качестве методов упорядочения данных представлены пузырьковая сортировка, сортировка Шелла, быстрая сортировка.

1.1.1. Алгоритм пузырьковой сортировки

Напомним кратко общую схему данного метода упорядочения данных [1]. Алгоритм основан на применении базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки:

// операция "сравнить и переставить"

if ( a[i] > a[j] ) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

На первой итерации алгоритма осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение ("всплывание пузырька"); далее для продолжения сортировки этот уже упорядоченный элемент не рассматривается и действия алгоритма повторяются:

// пузырьковая сортировка

for ( i=1; i<n; i++ ){

for ( j=0; j<n-i; j++ )

<сравнить и переставить элементы (a[j],a[j+1])>

}

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов происходит строго последовательно. Для организации параллельных вычислений обычно используется модификация алгоритма пузырьковой сортировки – метод чет-нечетной перестановки [23]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:

(a₁, a₂), (a₃, a₄),…, (a_n-1, a_n) (при четном n),

на четных итерациях обрабатываются элементы

(a₂, a₃), (a₄, a₅),…, (a_n-2, a_n-1) (при нечетном n).

После n-кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.

Параллельное обобщение этого алгоритма не вызывает затруднений, так как сравнение элементов в парах происходит независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один элемент исходного массива. Предположим, что процессоры соединены  в кольцо и элементы a_i расположены на процессорах p_i (i=1, 2,..., n). Тогда сравнение пары значений a_i и a_i+1 1≤ i <n, располагаемых на процессорах P_i и P_i+1 соответственно, можно организовать следующим образом:

- выполнить взаимообмен имеющихся на процессорах P_i и P_i+1 значений (с сохранением на этих процессорах исходных элементов);

- сравнить на каждом процессоре P_i и P_i+1 получившиеся одинаковые пары значений ai и a_i+1; результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т.е P_i+1) запоминает для дальней обработки большее значение пары

a_i =min(a_i , a_i+1 ),    a_i+1 =max(a_i , a_i+1).

Рассмотренная параллельная схема может быть надлежащим образом адаптирована и для случая p<n, когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера n/p) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров P_i и P_i+1 для совместного упорядочения содержимого блоков A_i и A_i+1 и может быть осуществлено следующим образом:

- выполнить взаимообмен блоков между процессорами P_i и P_i+1;

- объединить блоки A_i и A_i+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре P_i, а другую часть (с большими значениями соответственно) – на процессоре P_i+1.

Следует отметить, что сформированные в результате такой процедуры блоки на процессорах P_i и P_i+1 совпадают по размеру с исходными блоками A_i и A_i+1 и все значения, расположенные на процессоре P_i, являются меньшими значений на процессоре P_i+1.

Рассмотренная процедура обычно именуется в литературе как операция "сравнить и разделить" (compare-split). Для пояснения такого параллельного способа сортировки на рис. 1 приведен пример упорядочения данных при n=8, p=4 (т.е. блок значений на каждом процессоре содержит n/p =2 элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция "сравнить и разделить"; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

Вычислительная трудоемкость алгоритма определяется выражением:

Tp  =6 (n/p)² +2n

Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая часть отражает суммарную сложность всех итераций алгоритма чет-нечетной перестановки блоков (для слияния двух упорядоченных блоков размера n/p необходимо 2(n/p) операций).

Download Lab_3