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.