laboratorul 1 programare paralela
Post on 31-Jan-2022
10 Views
Preview:
TRANSCRIPT
Laboratorul 1 –Programare Paralela
-Timp alocat 4 ore
Obiectul lucrarii de laborator
Limbajul Java. Notiuni introductive. Introducere în programarea
paralelă. Medii de dezvoltare a programelor paralele.
Bibliografie
https://netbeans.org/
http://ro.wikipedia.org/wiki/Java_%28limbaj_de_programare%29
Tudor Sorin, Java, Editura L&S, 2012
http://www.infobits.ro/java/
Aspecte teoretice privind limbajul Java
Conform Wikipedia, Java este un limbaj de programare orientat-obiect, puternic tipizat, conceput
de către James Gosling la Sun Microsystems (acum filială Oracle) la începutul anilor ʼ90, fiind lansat
în 1995. Cele mai multe aplicații distribuite sunt scrise în Java, iar noile evoluții tehnologice permit
utilizarea sa și pe dispozitive mobile gen telefon, agenda electronică, palmtop etc. În felul acesta se
creează o platformă unică, la nivelul programatorului, deasupra unui mediu eterogen extrem de
diversificat. Acesta este utilizat în prezent cu succes și pentru programarea aplicațiilor destinate
intranet-urilor[10]
.
Limbajul împrumută o mare parte din sintaxă de la C și C++, dar are un model al obiectelor mai
simplu și prezintă mai puține facilități de nivel jos. Un program Java compilat, corect scris, poate fi
rulat fără modificări pe orice platformă care e instalată o mașină virtuală Java (engleză Java Virtual
Machine, prescurtat JVM). Acest nivel de portabilitate (inexistent pentru limbaje mai vechi cum ar
fi C) este posibil deoarece sursele Java sunt compilate într-un formatstandard numit cod de octeți
(engleză byte-code) care este intermediar între codul mașină (dependent de tipul calculatorului) și
codul sursă.
Mașina virtuală Java este mediul în care se execută programele Java. În prezent, există mai mulți
furnizori de JVM, printre care Oracle, IBM, Bea, FSF. În 2006, Sun a anunțat că face disponibilă
varianta sa de JVM ca open-source.
Există 4 platforme Java furnizate de Oracle:
Java Card - pentru smartcard-uri (carduri cu cip)
Java Platform, Micro Edition (Java ME) — pentru hardware cu resurse limitate, gen PDA
sau telefoane mobile,
Java Platform, Standard Edition (Java SE) — pentru sisteme gen workstation, este ceea ce se
găsește pe PC-uri,
Java Platform, Enterprise Edition (Java EE) — pentru sisteme de calcul mari, eventual
distribuite.
Istoric al versiunilor
23 ianuarie 1996, JDK 1.0 - versiunea inițială
19 februarie 1997, JDK 1.1
8 decembrie 1998, J2SE 1.2
8 mai 2000, J2SE 1.3
6 februarie 2002, J2SE 1.4
30 septembrie 2004, J2SE 5.0, numărul de versiune 1.5 este păstrat ca număr intern de
versiune
11 decembrie 2006, Java SE 6
14 februarie 2012, Java SE 7
18 martie 2014, Java SE 8
Medii de dezvoltare integrate
Un IDE (engleză integrated development environment) este un mediu de lucru care permite
dezvoltarea de aplicații folosind anumite limbaje de programare (cele suportate de IDE, adică cele
pentru care a fost creat acel IDE). Pentru Java sunt folosite următoarele:
JCreator - gratuit JCreator LE
Eclipse - gratuit
NetBeans - gratuit
BEA Workshop
BlueJ - gratuit
CodeGuide - comercial
DrJava - gratuit
IntelliJ IDEA - gratuit Idea Community Edition
JBuilder - comercial
JDeveloper - comercial, platformă multiplă
KDevelop - gratuit (platformă GNU/Linux, Cygwin)
Exemplu de program java
import java.util.Scanner; class suma{ public static void main(String[] args){ int a,b; Scanner scanner=new Scanner(System.in); System.out.print("a="); a=scanner.nextInt(); System.out.print("b="); b=scanner.nextInt(); System.out.println(a+b);} }
Modul de lucru fara mediu de programare 1. Se intra in folderul ce contine compilaorul java.
2. Se deschide aplicatia cmd.exe pentru a lansa comenzi de compilare si executie program.
3. Se schimba folderul current cu D:\jdk1.6.0\bin
4. Folosind editorul NotePad se scrie programul Java. 5. Se compileaza programul cu linia de comanda:
6. Se lanseaza in executie fisierul suma.class:
Instructiuni Java 1.Instructiunea vida Aceasta se marcheaza prin caracterul ; 2. Instructiunea compusa Este alcatuita din { ... }
3. Instructiunile de incrementare, decrementare i++; ++i; i--; --i;
4. Instructiunea de atribuire variabila=expresie 5. Instructiunea if Are doua forme: if (explogica) instructiune; if (explogica) instructiune1; else instructiune2; 6. instructiunea while while(explogica) instructiune ex ... s=0; i=1; while(i<4) { s+=i*i; i++;} ... se obtine s=0+1*1+2*2+3*3=14 7. do-while do{ instructiuni }while(explogica); ex ... s=0;i=1; do{
s+=i*i; i++; }while(i<4); ... s=0+1*1+2*2+3*3=14 8. instr. for for(exp1;exp2;exp3) instructiune ex ... s=0; for(i=1;i<=3;i++) s+=i*i; ... s=0+1*1+2*2+3*3=14 9. instr. break break; ex ... s=0; for(i=1;i<100;i++) { s++; if(i%5==0) break; } ... s=1+1+1+1+1=5 10. instr. continue continue; 11. instr switch switch (exp){
case exp1:instr1;break; ... case expk:instrk;break; [default: instr;]}; ex ... s=10;i=3; switch (i){ case 1:s+=10;break; case 2:s+=20;break; case 3:s+=30;break; default: s+=100;}; ... se obt. s=40 12. Afisarea datelor se realizeaza prin metodele (functiile): System.out.print("date ce se afiseaza"); System.out.println("date ce se afiseaza pe ecra"); 13. declarare variabile tip listavariabile; ex int a,b,c;
Citirea datelor cin.class Functii de citire date 1. cin.linie(); exemplu String x; x=cin.linie(); 2. Integer.parseInt(cin.linie()); ex int a; a=Integer.parseInt(cin.linie()); 3. Long.parseLong(cin.linie()); ex long a; a=long.parseLong(cin.linie()); 4. Float.parseFloat(cin.linie()); ex float a; a=Float.parseFloat(cin.linie());
Masive (vectori si tablouri bidim) 1. Se declara o variabila care contine adrese catre masive Exemple int[] v; //adresa spre un vector int[][] t; //adresa spre un tablou bidim
in general tipc[][]...[] numemasiv 2. Se aloca memorie spre un masiv. Adresa de inceput a unui masiv se va retine intr-o variabila declarata ca mai sus. Alocarea de memorie se realizeza prin constructii de forma: numemasiv=new tipc[dim1]...[dimk]; OBS Indicii componentelor incep de la 0. Exemplu Pentru decalaratiile din etapa 1: v=new int[4]; Astfel obtinem vectorul cu comp. : v[0], v[1], v[2], v[3] de tip int. t=new int[3][4]; Astfel se obtine tabloul cu componentele: t[0][0], t[0][1], t[0][2], t[0][3] t[1][0], t[1][1], t[1][2], t[1][3] t[2][0], t[2][1], t[2][2], t[2][3] OBS Acesul la o componenta se realizeaza prin constructii de forma: numemasiv[i1]...[ik]. Probleme rezolvate 1. Afisati primii 20 termeni din sirul lui Fibonacci (1,1, 2, 3, 5, 8, …).
class fibo { public static void main(String[] s) { int a=1,b=1,i,c;
System.out.print(a+" "+b+" "); for(i=3;i<=20;i++) { c=a+b; a=b; b=c; System.out.print(c+" "); } } }
2. Verificati daca un numar natural este patrat perfect, fara a folosi functia Math.sqrt(x).
class prim { public static void main(String[] s) { int a=100; int i,sw=0; for(i=1;i<=a/2;i++) if(i*i==a) {sw=1; i=a;} if(sw==1) System.out.println("numar patrat perfect"); else System.out.println("numarul nu este patrat perfect"); } }
3. Se dau doua numere natural. Afisati cel maimare numar dintre ele. import java.util.Scanner;
class numere{ public static void main(String[] s){ int a,b,max;
Scanner scanner=new Scanner(System.in); System.out.print("a="); a= scanner.nextInt(); System.out.print("b="); b= scanner.nextInt(); if(a>b) max=a; else max=b; System.out.println("max="+max);
} }
4. Se da un sir de n numere natural. Afisati sirul ordonat crescator. Exemplu Intrare n=4 34 2 56 4 Iesire 2 4 34 56 import java.util.Scanner;
class ordonar{ public static void main(String[] s){ int aux,i,j,n,x[]; Scanner scanner=new Scanner(System.in); System.out.print("n="); n= scanner.nextInt(); x=new int[n]; for(i=0;i<n;i++){ System.out.print("x["+i+"]="); x[i]= scanner.nextInt(); } for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(x[i]>x[j]){ aux=x[i]; x[i]=x[j]; x[j]=aux;} for(i=0;i<n;i++) System.out.print(x[i]+" "); } }
5. Se dau m<n. Afisati toate numerele palindrom cuprinse intre m si n.
import java.util.Scanner; public class palindrom {static int pal(int x) {int r,aux; aux=x; r=0; while(aux>0) {r=r*10+(aux%10); aux=aux/10; } if(r==x) return 1; return 0;
} public static void main(String[] s) { Scanner scanner=new Scanner(System.in); int m= scanner.nextInt(); int n= scanner.nextInt(); int i; for(i=m;i<=n;i++) if(pal(i)==1) System.out.print(i+" "); } }
Probleme de rezolvat 1. Se dau patru numere natural a, b, c. Verificati daca numerele sunt lungimele laturilor unui triunghi. Exemplu Intrare a=10 b=14 c=12 Iesire Sunt lungimile laturilor unui triunghi 2. Se dau numere naturale pana se introduce 0. Calculati media aritmetica a numerelor impare citite. Exemplu 7 4 3 0 Se va afisa 5.00 3. Se dau a, b, c numere natural nenule. Afisati cel mai mic multiplu comun pentru a, b, c. Exemplu Intrare a=100 b=150 c=200 cmmmdc=600 4. Se da un vector v=(v[1],...,v[n]). Vrem permutarile circulare ale lui v la dreapta. Exemplu n=4 v=(1,2,3,4)
se va afisa 1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1 5. Se da un vector x cu n componente. Vrem cel mai mic numar si pozitiile lui. Exemplu n=5 x=(3,6,3,4,6) Max=3 Poz: 1 3 6. Se dau un vector cu n componente. Afisati componentele pare distincte in ordine crescatoare. Exemplu Pentru n=5 x=(2,6,3,4,6) Se va afisa 2 4 6
Divide et Impera
Obiective laborator
Înțelegerea conceptului teoretic din spatele descompunerii
Rezolvarea de probleme abordabile folosind conceptul de Divide et Impera
Importanţă – aplicaţii practice
Paradigma Divide et Impera stă la baza construirii de algoritmi eficienți pentru diverse
probleme:
Sortări (ex: MergeSort, QuickSort)
Cautarea intr-un sir ordonat (cautarea binara)
Turnurile din Hanoi
Problema tablei cu gauri
Un alt domeniu de utilizare a tehnicii divide et impera este programarea paralelă pe mai
multe procesoare, sub-problemele fiind executate pe mașini diferite.
Prezentarea generală a problemei
O descriere a tehnicii D&I: “Divide and Conquer algorithms break the problem into several
sub-problems that are similar to the original problem but smaller in size, solve the sub-
problems recursively, and then combine these solutions to create a solution to the original
problem.” [7]
Deci un algoritm D&I împarte problema în mai multe subprobleme similare cu problema
inițială şi de dimensiuni mai mici, rezolva sub-problemele recursiv şi apoi combina
soluțiile obţinute pentru a obține soluția problemei inițiale.
Sunt trei pași pentru aplicarea algoritmului D&I:
Divide: împarte problema în una sau mai multe probleme similare de
dimensiuni mai mici.
Impera (stăpânește): rezolva subprobleme recursiv; dacă dimensiunea sub-
problemelor este mica se rezolva iterativ.
Combină: combină soluțiile sub-problemelor pentru a obține soluția problemei
inițiale.
Complexitatea algoritmilor D&I se calculează după formula:
T(n) = D(n) + S(n) + C(n),
unde D(n), S(n) şi C(n) reprezintă complexitățile celor 3 pași descriși mai sus: divide,
stăpânește respectiv combină.
Probleme clasice
1. Sortarea prin interclasare
Sortarea prin interclasare (MergeSort [1]) este un algoritm de sortare de vectori ce
folosește paradigma D&I:
Divide: împarte vectorul inițial în doi sub-vectori de dimensiune n/2.
Stăpânește: sortează cei doi sub-vectori recursiv folosind sortarea prin
interclasare; recursivitatea se oprește când dimensiunea unui sub-vector este
1 (deja sortat).
Combina: Interclasează cei doi sub-vectori sortați pentru a obține vectorul
inițial sortat.
Pseudocod:
MergeSort(v, start, end) // v – vector, start – limită
inferioră, end – limită superioară
if (start == end) return; // condiția de oprire
mid = (start + end) / 2; // etapa divide
MergeSort(v, start, mid); // etapa stăpânește
MergeSort(v, mid+1, end);
Merge(v, start, end); // etapa combină
Merge(v, start, end) // interclasare sub-vectori
mid = (start + end) / 2;
i = start;
j = mid + 1;
k = 1;
while (i <= mid && j <= end)
if (v[i] <= v[j]) u[k++] = v[i++];
else u[k++] = v[j++];
while (i <= mid)
u[k++] = v[i++];
while (j <= end)
u[k++] = v[j++];
copy(v[start..end], u[1..k-1]);
Complexitatea algoritmului este dată de formula: T(n) = D(n) + S(n) + C(n), unde
D(n)=O(1), S(n) = 2*T(n/2) și C(n) = O(n), rezulta T(n) = 2 * T(n/2) + O(n).
Folosind teorema Master [8] găsim complexitatea algoritmului: T(n) = O(n * lg n).
2. Căutarea binară
Se dă un vector sortat crescător (v[1..n]) ce conține valori reale distincte și o valoare x.
Sa se găsească la ce poziție apare x în vectorul dat.
Pentru rezolvarea acestei probleme folosim un algoritm D&I:
Divide: împărțim vectorul în doi sub-vectori de dimensiune n/2.
Stăpânește: aplicăm algoritmul de căutare binară pe sub-vectorul care
conține valoarea căutată.
Combină: soluția sub-problemei devine soluția problemei inițiale, motiv
pentru care nu mai este nevoie de etapa de combinare.
Pseudocod:
BinarySearch(v, start, end, x)
if (start > end) return; // condiția de oprire (x nu se află în
v)
mid = (start + end) / 2; // etapa divide
// etapa stăpânește
if (v[mid] == x) return mid
if (v[mid] > x) return BinarySearch(v, start, mid-1, x);
if (v[mid] < x) return BinarySearch(v, mid+1, end, x);
Complexitatea algoritmului este data de relația T(n) = T(n/2) + O(1), ceea ce implica: T(n)
= O(lg n).
3. Turnurile din Hanoi
Se considera 3 tije A, B, C şi n discuri de dimensiuni distincte (1, 2.. n ordinea crescătoare a
dimensiunilor) situate inițial toate pe tija A în ordinea 1,2..n (de la vârf către baza). Singura
operație care se poate efectua este de a selecta un disc ce se află în vârful unei tije şi
plasarea lui în vârful altei tije astfel încât să fie așezat deasupra unui disc de dimensiune
mai mare decât a sa. Sa se găsească un algoritm prin care se mută toate discurile pe tija B
(problema turnurilor din Hanoi).
Pentru rezolvarea problemei folosim următoarea strategie [9]:
mutam primele n-1 discuri de pe tija A pe tija C folosindu-ne de tija B.
mutam discul n pe tija B.
mutam apoi cele n-1 discuri de pe tija C pe tija B folosindu-ne de tija A.
Pseudocod [10]:
Hanoi(n, A, B, C) // mută n discuri de pe tija A pe tija B fol tija C
if (n >= 1)
Hanoi(n-1, A, C, B);
Muta_disc(A, B);
Hanoi(n-1, C, B, A);
Complexitatea: T(n) = 2*T(n-1) + O(1), recurenta ce conduce la T(n) = O(2n).
Probleme de rezolvat
1. Scrieti cate un program java pentru problemele prezentate anterior.
2. Folosind metoda divide et impera determinate cmmmdc a n numere natural nenule.
3. Folosind metoda divide et impera determinati suma componentelor unui vector.
4. Folosind metoda divide et impera determinate numarul de componente impare dintr-un vector.
top related