Analiza și proiectarea [616090]

Analiza și proiectarea
algoritmilor
Curs, anul II – Calculatoare, Tehnologia informației ,
Ingineria sistemelor multimedia
Puncte de credit: 5
Autor: Dr. Árpád GELLÉRT
Web: http://webspace.ulbsibiu.ro/arpad.gellert
ESmail: [anonimizat] Universitatea “Lucian Blaga” din Sibiu,
Catedra de Calculatoare și Automatizări

2Cuprins (1)
Partea I – Limbajul Java
/square6Structura lexicală și instrucțiuni
/square6Variabile și constante
/square6Tablouri și matrici
/square6Tratarea excepțiilor
/square6Operații I/O
/square6Crearea claselor
/square6Interfețe grafice
/square6Fire de execuție
/square6Colecții

3Partea II – Analiza algoritmilor
/square6Complexitate, notații asimptotice
/square6Recurențe
/square6Algoritmi de căutare și sortare
/square6Tabele de dispersie
/square6Arbori binari
/square6HeapSuri
/square6Grafuri Cuprins (2)

4Partea III – Proiectarea algoritmilor
/square6Divide et impera
/square6Greedy
/square6Programare dinamică
/square6Backtracking
/square6Algoritmi genetici
/square6Rețele neuronale Cuprins (3)

5Nota finală
Nota laborator (NL) = 0,5*T + 0,5*C Nota finală = 0,4*NL + 0,6*E
/square6T = Test susținut la laborator din aplicațiile prop use la laborator
în cadrul capitolului Limbajul Java ;
/square6C = Colocviu de laborator din aplicațiile propuse l a laborator în
cadrul capitolelor Analiza algoritmilor respectiv Proiectarea
algoritmilor ;
/square6E = Examen susținut din capitolele Analiza algoritmilor și
Proiectarea algoritmilor .

6Bibliografie de bază
[Knu00] Knuth D., Arta programării calculatoarelor , Teora, 2000.
[Cor00] Cormen T., Leiserson C., Rivest R., Introducere în algoritmi , Agora, 2000.
[Giu04] Giumale C., Introducere în analiza algoritmilor , Polirom, 2004.
[Wai01] Waite M., Lafore R., Structuri de date și algoritmi în Java , Teora, 2001.
[Log07] Logofătu D., Algoritmi fundamentali în Java , Polirom, 2007.
[Tan07] Tanasă Ș., Andrei Ș., Olaru C., Java de la 0 la expert , Polirom, 2007.

7/square6Geneza cuvântului algoritm: provine din
latinizarea numelui savantului AlSKhwarizmi (algoritmi) – matematician, geograf, astronom și astrolog persan (780S850), considerat și părintele algebrei moderne.Introducere (1)
/square6Algoritmul este o secvență de operații care transformă
mulțimea datelor de intrare în datele de ieșire.
/square6Proiectarea algoritmului constă în două etape:
/square6Descrierea algoritmului printrSun pseudolimbaj (sch emă logică,
pseudocod);
/square6Demonstrarea corectitudinii rezultatelor în raport cu datele de
intrare.
/square6Analiza algoritmului se referă la evaluarea
performanțelor acestuia (timp de execuție, spațiu d e
memorie).

8/square6Imlementarea algoritmilor se va face în limbajul Java. Medii de
dezvoltare:
/square6Java Development Kit (JDK) – http://www.oracle.com
/square6NetBeans – https://netbeans.org
/square6IntelliJ – https://www.jetbrains.com
/square6Eclipse – http://www.eclipse.org
/square6Android Studio – https://developer.android.com/studio/index.html
/square6Principalele caracteristici ale limbajului Java:
/square6Simplitate – elimină supraîncărcarea operatorilor, mo ștenirea multiplă, etc.;
/square6Complet orientat pe obiecte;
/square6Portabilitate – Java este un limbaj compilat și inte rpretat, fiind astfel
independent de platforma de lucru (W rite O nce, R un Enywhere);
/square6Oferă posibilitatea, prin JNI (Java Native Interface ), de a implementa aplicații
mixte (ex. Java/C++), prețul folosirii codului nati v fiind însă dependența de
platformă [Gor98];
/square6Permite programarea cu fire de execuție.Introducere (2)

9/square6În urma compilării codului sursă, se obține codul d e octeți (bytecode)
care este apoi interpretat de mașina virtuală Java (JVM). Astfel,
aplicația poate fi rulată pe orice platformă care f olosește mediul de
execuție Java.
/square6Pe lângă aplicații obișnuite, pot fi implementate a plicații web (applet),
aplicații server (servlet, JavaServer Pages, etc.), aplicații în rețea,
telefonie mobilă (midlet), aplicații distribuite RM I (Remote Method
Invocation), etc.
/square6Compilarea programelor (javac.exe): javac *.java
/square6Rularea programelor (java.exe): java * .java Compilator
Java .class Java
Virtual
Machine Cod sursă Bytecode Introducere (3)

Partea I
Limbajul Java

11 Limbajul Java
O aplicație simplă:
class HelloWorld{
public static void main(String args[]){
System.out.println("Hello world");
}
}
/square6Aplicația HelloWorld afișează la consolă mesajul “H ello world”.
/square6În orice aplicație trebuie să existe o clasă primar ă, care conține
metoda main de la care începe execuția în momentul rulării.
Parametrul args al metodei main este un tablou de șiruri de
caractere și reprezintă argumentele din linie de co mandă.
/square6Fișierul care conține clasa primară trebuie să aibă numele clasei
(case sensitive!).
/square6Java permite o singură clasă publică întrSun fișier .
/square6Compilarea programului: javac HelloWorld.java
/square6Rularea programului: java HelloWorld

12 Limbajul Java – convenții de scriere a codului [Web0 1]
/square6Principalele segmentele ale codului Java apar în urm ătoarea ordine:
/square6Declarația de pachet ( package );
/square6Directivele de import ;
/square6Declarația de clasă sau interfață;
/square6Declarațiile variabilelor membru ale clasei (statice) sau ale instanței;
/square6Constructori și metode;
/square6Convenții de nume
/square6Numele de clase, implicit de constructori, încep cu majusculă (ex.:
NumeClasa);
/square6Numele de metode încep cu literă mică (ex.: numeMeto da);
/square6Numele de variabile și obiecte încep cu literă mică (ex.: numeObiect);
/square6Numele constantelor se scriu cu majuscule, cuvintele fi ind despărțite
prin “_” (ex.: NUME_CONSTANTA);
/square6Numele trebuie să fie cât mai sugestive.

13 Limbajul Java – Structura lexicală
Structura lexicală a limbajului Java este foarte as emănătoare cu cea
a limbajului C++.
/square6Comentariile se fac ca în C++.
/square6Operatorii sunt în mare parte la fel ca în C++.
/square6Instrucțiunile sunt și ele foarte asemănătoare cu c ele din C++. O
diferență importantă constă în faptul că expresiile care apar în
instrucțiunile condiționale ( if , for , while , do ) sunt strict de tip
boolean , în timp ce în C++ pot fi de tip int .
/square6Tipurile de date se clasifică în două categorii:
/square6Tipuri de date primitive:byte (1 octet), short (2 octeți), int (4 octeți),
long (8 octeți), char (2 octeți – unicode), float (4 octeți), double (8
octeți), boolean (1 bit);
/square6Tipuri de date referință: clase, interfețe, tablouri . Există și variantele
referință (clase wrapper) ale tipurilor de date prim itive:Byte , Short ,
Integer , Long , Character , Float , Double , Boolean . Variantele referință
ale tipurilor de date primitive sunt necesare pentr u că în Java nu
există operatorul & pentru definiția unei referințe . Pentru șiruri de
caractere, pe lângă char[] , există și tipul referință String.

14 Limbajul Java – variabile
/square6Variabilele primitive se pot crea prin declarație. Exe mple:
/square6int i = 10;
/square6float f = 3.14f;
/square6double d = 3.14;
/square6Variabilele referință se pot crea doar cu operatorul new (care returnează
o referință). Variabilele de tip String și începând cu JDK 1.5, cele de tip
wrapper care se pot crea și prin declarație (făr new ). Exemple:
/square6Integer i = new Integer(10);
/square6Integer j = 20;
/square6String h= new String(“Hello”);
/square6String w= “world”;
/square6În Java nu este admisă supraîncărcarea operatorilor , excepție fiind doar
operatorul de adunare pentru clasa String , care permite concatenarea
șirurilor. Exemplu:
String h= “Hello”;
String w= “world”;
String s= h+ “ ” + w;
/square6Concatenarea unui String cu o variabilă primitivă determină conversia
implicită a acesteia în String . Exemplu:
String t= “Two”;
int i = 2;boolean b = true;String s = t+ “ = ” + i + “ is ” + b; //Rezultat: “Two = 2 is true”

15 Limbajul Java – constante
/square6Pentru crearea unei constante, declarația de variab ilă
trebuie precedată de cuvântul cheie final .
/square6Nu este permisă modificarea valorii unei constante.
/square6O clasă declarată final nu poate fi derivată (v.
moștenirea).
/square6Exemple
public class Main {
public static void main(String[] args) {
final String APA = "Analiza si proiectarea algoritm ilor";
final int TEN = 10;
TEN++; //Eroare!
APA = "Analiza, proiectarea si implementarea algori tmilor"; //Eroare!
int eleven = TEN + 1;
}
}

16 Limbajul Java – clasa String (1)
Principalele operații:
/square6substring cu parametrii index0 și indexf – returneaza subșirul care începe
la index0 și se termină la indexfS1 , lungimea fiind indexfSindex0 . Exemplu:
String str = “Hello world”;String substr = str.substring(0, 5); //Rezultat: “He llo”
/square6charAt – returnează caracterul de pe o anumită poziție din șir. Exemplu:
String str = “Hello world”;char c = str.charAt(6); //Rezultat: ‘w’
/square6length – retunează lungimea șirului în număr de caractere. Exemplu:
String str = “Hello world”;int len = str.length(); //Rezultat: 11
/square6equals / equalsIgnoreCase – permite comparația unui șir cu alt șir.
Returnează true dacă cele două șiruri sunt egale, r espectiv false dacă ele
nu sunt egale. Exemplu:String hello = “Hello”;if(hello.equals(“Hello”)) //Rezultat: true
System.out.println(“equal”); //Rezultat: “equal”

17 /square6compareTo / compareToIgnoreCase – compară două șiruri.
Returnează valoarea 0 dacă cele două șiruri sunt le xicografic egale, o
valoare negativă dacă parametrul este un șir lexico grafic mai mare
decât șirul curent și o valoare pozitivă dacă param etrul este un șir
lexicografic mai mic decât șirul curent. Exemplu:String hello = “Hello”;if(hello.compareTo(“Hello”) == 0) //Rezultat: 0
System.out.println(“equal”); //Rezultat: “equal”
/square6trim – elimină eventualele spații de la începutul și sfâ rșitul șirului.
Exemplu:String hello = “ Hello ”;hello = hello.trim(); //hello=“Hello”
/square6toLowerCase / toUpperCase – transformă toate literele din șir în
litere mici / mari. Exemplu:String str = “Hello world”;str = str.toUpperCase(); //Rezultat: “HELLO WORLD”
/square6split – separarea unui șir pe baza unui delimitator. Exemp lu:
String str = “Hello world”;String t[] = str.split(“ ”); //Rezultat: {“Hello”, “w orld”}; Limbajul Java – clasa String (2)

18 Limbajul Java – clasa StringTokenizer
/square6Permite separarea unui șir de caractere în simbolur i;
/square6Se instanțiază un obiect StringTokenizer , specificând șirul
de caractere și setul de delimitatori;
/square6Următoarea secvență de program afișează pe ecran simbolurile (cuvintele) șirului delimitate prin car acterele
spațiu și virgulă:
String str = "Analiza, proiectarea si implementarea algoritmilor";
StringTokenizer st = new StringTokenizer(str, " ,") ;
while(st.hasMoreTokens())
System.out.println(st.nextToken());
/square6Setul de delimitatori poate fi specificat și prin f uncția
nextToken :
while(st.hasMoreTokens())
System.out.println(st.nextToken(" ,"));

19 Limbajul Java – tablouri
/square6Posibilități de declarare a tablourilor:
/square6int[] fibo = new int[10];
/square6int fibo[] = new int[10];
/square6int n = 10; int fibo[] = new int[n];
/square6int fibo[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
/square6Tablou cu elemente primitive vs. referință:
/square6int pTab[] = new int[5]; //tablou (referinta!) cu 5 elem. primitive
for(int i=0; i<pTab.length; i++)
pTab[i] = i+1;
/square6Integer rTab[] = new Integer[5]; //tablou (ref erinta!) cu 5 elem. referinta
for(int i=0; i<rTab.length; i++)
rTab[i] = new Integer(i+1);
/square6Afișarea elementelor unui tablou:
/square6for(int i=0; i<fibo.length; i++)
System.out.println(fibo[i]);
/square6for(int i : fibo) //incepand cu JDK 1.5
System.out.println(i);

20 Limbajul Java – clasa Arrays
Principalele operații:
/square6 fill – permite umplerea tabloului sau a unei zone din tab lou cu o anumită valoare:
int tab[] = new int[5];
Arrays.fill(tab, 7); //Rezultat: tab={7,7,7,7,7}
Arrays.fill(tab, 1, 3, 8); //Rezultat: tab={7,8,8,7,7}
/square6 equals – compară două tablouri returnând true dacă au toat e elementele egale:
int a[] = {1,2,3,4}; int b[] = {1,2,3,4}; int c[] = {1,2,4,8}; System.out.println(Arrays.equals(a, b) ? "a==b" : " a!=b"); //Rezultat: “a==b”
System.out.println(Arrays.equals(a, c) ? "a==c" : " a!=c"); //Rezultat: “a!=c”
/square6 sort – sortează elementele tabloului în ordine crescătoar e folosind algoritmul Quicksort pentru tipuri primit ive
respectiv Mergesort pentru tipuri referință:
int pTab[] = {9,6,2,1,5,3};
Arrays.sort(pTab,1,4); //Rezultat: tab={9,1,2,6,5,3}
Arrays.sort(pTab); //Rezultat: tab={1,2,3,5,6,9}
Integer rTab[] = new Integer[5]; for(int i=0, k=rTab.length; i<rTab.length; i++, kSS ) //Rezultat : tab={5,4,3,2,1}
rTab[i] = new Integer(k);
Arrays.sort(rTab); //Rezultat : tab={1,2,3,4,5}
/square6 binarySearch – returnează poziția elementului căutat în tablou s au o valoare negativă dacă valoarea căutată
nu este găsită. Algoritmul folosit este căutarea bi nară, de aceea tabloul trebuie sortat înainte de ap elul acestei
metode. Exemplu:
int tab[] = {5,4,1,7,3}; //tablou nesortat
int v = Arrays.binarySearch(tab, 4); //Rezultat greș it: S4
Arrays.sort(tab); //Rezultat: tab={1,3,4,5,7}
v = Arrays.binarySearch(tab, 4); //Rezultat corect: 2

21 Limbajul Java – matrici
/square6Posibilități de declarare a matricilor:
/square6int m[][] = new int[3][4];
/square6int nRow=3, nCol=4; int m[][] = new int[nRow][nCol];
/square6int m[][] = new int[3][]; for(int i=0; i<3; i++)
m[i] = new int[4];
/square6int m[][] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
/square6Tablou multidimensional cu număr variabil de coloan e. Exemplu de alocare, inițializare și
afișare:
int m[][] = new int[3][]; for(int i=0, k=1; i<3; i++){
m[i] = new int[4+i]; for(int j=0; j<4+i; j++, k++)
m[i][j] = k;
}for(int i=0; i<3; i++){ //Rezultat afișat:
for(int j=0; j<4+i; j++) //1 2 3 4
System.out.print(m[i][j]+"\t"); //5 6 7 8 9
System.out.println(); //10 11 12 13 14 15
}
/square6O matrice mare m.length linii și m[0].length coloane.

22 Limbajul Java – conversii (1)
/square6Conversia variabilelor primitive
/square6Conversie implicită. Exemple:int a = 3, b = 2; double c = a/b; //Conversie din int in double. Rezulta t: 1.0
int d = 5; float f = d; //Conversie din int in float. Rezultat: 5.0
/square6Conversie explicită (casting). Exemplu: double pi = 3.14; int i = (int)pi; //Conversie din double in int . Rezultat: 3
/square6Conversia variabilelor primitive în variabile refer ință.
Exemple:
int x = 10; Integer y = new Integer(x); //Conversie din int in Integer
float m = 3.14f;Float n = new Float(m); //Conversie din float in Float
String str10 = String.valueOf(x); //Conversie din int in String

/square6Conversia variabilelor referință în variabile primi tive. Exemple:
Integer zece = new Integer(10); int z = zece.intValue(); //Conversie din Integer in in t
Double p = new Double(3.14); double q = p.doubleValue(); //Conversie din Double in double
String str20 = “20”;int d = Integer.parseInt(str20); //Conversie din Strin g in int
String strPi = “3.14”;double pi = Double.parseDouble(strPi); //Conversie St ring S double
/square6Autoboxing și inboxing (începând cu JDK 1.5). Exemp le:
int z = 10; Integer zece = z; //autoboxing Double pi = new Double(3.14); double p = pi; //unboxing Limbajul Java – conversii (2)

24 Limbajul Java – comparații (1)
/square6Variabile primitive (comparație)
int a = 5; int b = 5; System.out.println(a==b ? "a==b" : "a!=b"); //Rezult at : "a==b"
/square6Variabile referință. Dacă cel puțin una din variabil ele referință sSa creat cu new,
operatorii "==", "!=", "<", "<=", ">" și ">=" nu se p ot folosi pentru
comparații, fiind necesar apelul metodelor corespunzăto are existente în clasele
wrapper. Exemple:
/square6Comparație greșită (se compară adrese!): Integer a = new Integer(5); Integer b = new Integer(5); System.out.println(a==b ? "a==b" : "a!=b"); //Rezult at: "a!=b"
/square6Comparație greșită (se compară o adresă cu o valoare!):
Integer a = new Integer(5); Integer b = 5; System.out.println(a==b ? "a==b" : "a!=b"); //"a!=b"

/square6Comparație corectă (se compară valori!): Integer a = 5; Integer b = 5; System.out.println(a==b ? "a==b" : "a!=b"); //"a==b"
/square6Comparație corectă (se compară valori!):Integer a = new Integer(5); Integer b = new Integer(5); System.out.println(a.equals(b) ? "a==b" : "a!=b"); / /Rezultat : "a==b"
/square6Comparație corectă (se compară valori!):Integer a = new Integer(5); Integer b = new Integer(5); System.out.println(a.compareTo(b)==0 ? "a==b" : "a! =b"); //Rezultat: "a==b"
/square6Comparație corectă (se compară valori!):Integer a = new Integer(5); Integer b = new Integer(5); System.out.println(a.intValue()==b.intValue() ? "a= =b" : "a!=b"); //Rezultat: "a==b"Limbajul Java – comparații (2)

26 Limbajul Java – clasa File (1)
Clasa File oferă informații despre fișiere și directoare și p ermite
redenumirea respectiv ștergerea acestora. Principal ele operații:
/square6length – returnează dimensiunea în octeți a fișierului;
/square6getName – returnează numele fișierului;
/square6getPath / getAbsolutePath / getCanonicalPath – returnează calea fișierului;
/square6getAbsoluteFile / getCanonicalFile – returnează un obiect File aferent fișierului;
/square6isFile / isDirectory – returnează true dacă e fișier / director;
/square6canRead / canWrite – returnează true dacă aplicația poate citi / modifica fișierul;
/square6exists – verifică dacă fișierul există;
/square6delete – șterge fișierul sau directorul;
/square6deleteOnExit – șterge fișierul sau directorul la închiderea mașin ii virtuale;
/square6list – apelată pentru un director returnează un tablou d e tip String cu toate fișierele și
subdirectoarele din acel director. Exemplu:
File file = new File("e:\\algoritmi_curs"); String str[] = file.list(); for(int i=0; i<str.length; i++)
System.out.println(str[i]);
/square6listFile – apelată pentru un director returnează un tablou d e tip File cu toate fișierele și
subdirectoarele din acel director;
/square6listRoots – returnează un tablou de tip File reprezentând răd ăcinile sistemelor de fișiere
disponibile în sistem (ex.: "C:\\", "D:\\", "E:\\") ;

27 /square6mkdir – creează un director nou, returnând true în caz de succes. Exemplu:
File file = new File("algoritmi"); System.out.println(file.mkdir());
/square6mkdirs – creează un director nou, inclusiv directoarele in existente care apar în cale
/square6renameTo – permite redenumirea fișierelor, returnând true în caz de succes. Exemplu:
File file = new File("Algoritmi.pdf"); System.out.println(file.renameTo(new File("algoritm i_curs.pdf")));
/square6separator / separatorChar – returnează un String / char reprezentând separato rul
dependent de sistem: '/' în UNIX respectiv '\' în W in32. Limbajul Java – clasa File (2)

28 Limbajul Java – clasa System
Principalele operații
/square6currentTimeMillis – returnează un long
reprezentând timpul în milisecunde. Poate fi folosi t ca
parametru în constructorul clasei Date pentru
obținerea datei și orei în formatul dorit.
/square6exit(0) – provoacă ieșirea din aplicație.
/square6gc – rulează mecanismul de garbage collector pentru
eliberarea zonelor de memorie ocupate de obiecte neutilizate.
/square6getProperties – returnează un obiect Properties din
care se pot extrage diferite informații referitoare la
sistemul de operare.

29 Limbajul Java – clasa Math
Câteva exemple
public class Main {
public static void main(String[] args) {
double pi = Math.PI; System.out.println(pi); //3.141592653589793 System.out.println(Math.round(pi)); //3 S rotunjire la ce l mai apropiat intreg
System.out.println(Math.floor(pi)); //3.0 S rotunjire in jos
System.out.println(Math.ceil(pi)); //4.0 S rotunjire in s us
System.out.println(Math.pow(2, 3)); //8.0 S ridicare la pu tere
System.out.println(Math.sqrt(9)); //3.0 S radical System.out.println(Math.exp(1)); //2.718281828459045 5 S valoarea exponentiala
double e = Math.E; System.out.println(e); //2.718281828459045
System.out.println(Math.min(2, 8)); //2 S minimul System.out.println(Math.max(2, 8)); //8 S maximul System.out.println(Math.abs(S5)); //5 S valoarea absolu ta
System.out.println(Math.log(e)); //1.0 S logaritmul natur al
System.out.println(Math.random()); //valoare aleatoare s ubunitara
System.out.println(Math.sin(pi/2)); //1.0 S sinusul, exis ta si celelalte functii
System.out.println(Math.toDegrees(pi/2)); //90.0 S con versie in grade
System.out.println(Math.toRadians(180)); //3.14159265 3589793 S conv. in rad.
}
}
Aplicații propuse
1. Căutarea minimului și a maximului întrSun tablou de nelemente ;
2. Generarea și afișarea unui tablou cu numerele lui Fibona cci.
3. Căutarea minimului și a maximului întrSo matrice;4. Adunarea a două matrici;5. Înmulțirea a două matrici.6. Să se scrie un program care, prin intermediul clasei File , să permită navigarea în structura de directoare din s istem.

30 Limbajul Java – tratarea excepțiilor (1)
/square6Excepțiile sunt erorile care apar în timpul execuți ei programelor.
/square6O instrucțiune sau o secvență de instrucțiuni trebu ie inclusă întrSun bloc try în
vederea tratării eventualelor excepții pe care le p oate genera. Blocul try este
urmat de unul sau mai multe blocuri catch prin care sunt detectate diferitele
excepții. În blocul opțional finally se introduc zonele de cod care trebuie
executate indiferent că apare sau nu o excepție. Fo rma generală:
try {
//instructiuni care pot genera Exceptia1 si Excepti a2
}catch (Exceptia1 e1){
//instructiunile care se executa daca apare Excepti a1
}catch (Exceptia2 e2){
//instructiunile care se executa daca apare Excepti a2
}finally {
//instructiunile care se executa indiferent ca apar e sau nu o exceptie
}
/square6Dacă nu apar excepții, blocul try execută toate instrucțiunile. Dacă o instrucțiune
din blocul try generează o excepție, se caută blocul catch corespunzător,
trecând peste restul instrucțiunilor din try . Dacă există un catch corespunzător,
se execută instrucțiunile din acel bloc catch . Dacă nu este găsit un bloc catch
corespunzător, excepția este transmisă mai departe în ierarhia apelantă. Dacă
excepția ajunge în vârful ierarhiei fără să fie tra tată, programul afișează un
mesaj de eroare și se întrerupe.

31 /square6Este posibilă ignorarea excepțiilor și transmiterea lor mai sus prin throws în
ierarhia apelantă.
/square6În exemplul următor, dacă în metoda apare Exceptia1 sau Exceptia2 , ea este
ignorată, transmisă mai departe și tratată în metod a apelantă main (ca în
exemplul precedent):
public void metoda() throws Exceptia1, Exceptia2 {
//instructuni care pot genera Exceptia1 si Exceptia 2
} public static void main(String[] args) {
try {
metoda();
}
catch (Exceptia1 e1){
//instructiunile care se executa daca apare Excepti a1
}
catch (Exceptia2 e2){
//instructiunile care se executa daca apare Excepti a2
}finally {
//instructiunile care se executa indiferent ca apar e sau nu o exceptie
}
}Limbajul Java – tratarea excepțiilor (2)

32 Exemplul 1
/square6Implementați și apoi rulați următoarea secvență de cod:
String str = "I'm a String!"; int i = Integer.parseInt(str); System.out.println("Program execution finished…") ;
Conversia din String în int determină eșuarea execuției programului
datorită conținutului nenumeric al variabilei str . Astfel nu se mai ajunge
la afișarea mesajului "Program execution finished.. .". Excepția
semnalată este NumberFormatException .
/square6Tratarea excepției:
String str = "I'm a String!"; try {
int i = Integer.parseInt(str);
}catch (NumberFormatException nfe) {
System.out.println("Conversia nu a fost posibila!") ;
}
Excepția fiind tratată, execuția programului nu va mai eșua. Limbajul Java – tratarea excepțiilor (3)

33 Exemplul 2
/square6Implementați și apoi rulați următoarea secvență de cod:
int tab[] = new int[10]; tab[10] = 10;
Accesarea unui element inexistent, al 11Slea elemen t, nealocat,
determină o excepție ArrayIndexOutOfBoundsException .
/square6Tratarea excepției:
int tab[] = new int[10]; try {
tab[10] = 10;
}catch (ArrayIndexOutOfBoundsException aioobe) {
System.out.println("Ati accesat un element inexiste nt!");
}
/square6Evident, excepția nu apare dacă indexul folosit pen tru accesarea
tabloului este între 0 și 9. Limbajul Java – tratarea excepțiilor (4)

34 Limbajul Java – operații I/O (1)
Citirea șirurilor de caractere de la tastatură
/square6Fluxuri de caractere:
BufferedReader br = new BufferedReader(new InputStr eamReader(System.in));
String str = null; try {
str = br.readLine();
}catch (IOException ioe) {
ioe.printStackTrace();
}
/square6Fluxuri de octeți:
DataInputStream dis = new DataInputStream(System.in );
String str = null; try {
str = dis.readLine();
}catch (IOException ioe) {
ioe.printStackTrace();
}

35 Citirea valorilor de la tastatură
/square6Clasa DataInputStream pe lângă metoda readLine (folosită pe
pagina anterioară pentru introducerea șirurilor de caractere)
dispune și de funcții pentru citirea valorilor ( readInt ,
readDouble , etc.). Dar aceste metode sunt funcționale doar
pentru valori scrise prin interfața DataOutput ( writeInt ,
writeDouble , etc.).
/square6Citirea valorilor poate fi efectuată prin citire de șiruri de
caractere urmată de conversia acestora:
DataInputStream dis = new DataInputStream(System.in );
String str = null; try {
str = dis.readLine();
}catch (IOException ioe) {
ioe.printStackTrace();
}int i = Integer.parseInt(str); Limbajul Java – operații I/O (2)

36 Limbajul Java – operații I/O (3)
Citirea din fișiere
Următoarea secvență de cod afișează pe ecran toate liniile citite din fișierul
input.txt . Citirea se face prin aceeași clasă DataInputStrea m care în loc de un
InputStream va primi ca parametru un FileInputStrea m:
FileInputStream fis = null; try{
fis = new FileInputStream("input.txt");
}catch(FileNotFoundException fnfe){
fnfe.printStackTrace();
}DataInputStream dis = new DataInputStream(fis); String str = null; try{
while((str = dis.readLine()) != null)
System.out.println(str);
dis.close(); System.in.read();
}catch(IOException ioe){
ioe.printStackTrace();
}

37 Scrierea în fișiere
/square6Următoarea secvență de program scrie în fișierul data.txt întregul 10 și valoarea
float 3.14
try{
FileOutputStream fos = new FileOutputStream("data.tx t");
DataOutputStream dos = new DataOutputStream(fos);
dos.writeInt(10); dos.writeFloat(3.14f); dos.close();
}catch(IOException ioe){
ioe.printStackTrace();
}
/square6Fiind scrise prin metodele writeInt și writeFloat , valorile pot fi citite din fișier
folosind metodele readInt respectiv readFloat ale clasei DataInputStream
try{
FileInputStream fis = new FileInputStream("data.txt" );
DataInputStream dis = new DataInputStream(fis);
System.out.println(dis.readInt()); System.out.println(dis.readFloat()); dis.close();
}catch(IOException ioe){
ioe.printStackTrace();
}Limbajul Java – operații I/O (4)

Clasa Scanner
/square6Citire de la tastatură (începând cu JDK 1.5):
Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int n = sc.nextInt(); double d = sc.nextDouble(); System.out.println(str + " " + n + " " + d); sc.close();
/square6Citire din FileInputStream (începând cu JDK 1.5):
FileInputStream f = null; try {
f = new FileInputStream("data.txt");
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}Scanner sc = new Scanner(f); String str = sc.nextLine(); int n = sc.nextInt(); double d = sc.nextDouble(); System.out.println(str + " " + n + " " + d); sc.close(); Limbajul Java – operații I/O (5)

/square6Citire din File (începând cu JDK 1.5):
File f = new File("data.txt"); Scanner sc = null; try {
sc = new Scanner(f);
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}String str = sc.nextLine(); int n = sc.nextInt(); double d = sc.nextDouble(); System.out.println(str + " " + n + " " + d); sc.close();
/square6Citirea unui fișier linie cu linie (începând cu JDK 1.5): :
FileInputStream f = null; try {
f = new FileInputStream("input.txt");
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}Scanner sc = new Scanner(f); while(sc.hasNext())
System.out.println(sc.nextLine());
sc.close(); Limbajul Java – operații I/O (6)

40 Arhivare ZIP
Arhivarea unui fișier constă în citirea datelor din acel fișier prin FileInputStream și scrierea
lor în arhivă prin ZipOutputStream . Pentru viteză mai mare, transferul datelor se fac e printrS
un tablou de tip byte :
String fisier = "Algoritmi.pdf"; //fisierul care se arhiveaza
String zip = "Algoritmi.zip"; //numele arhivei byte buffer[] = new byte[1024]; try{
FileInputStream fileIn = new FileInputStream(fisier );
FileOutputStream f = new FileOutputStream(zip); ZipOutputStream zipOut = new ZipOutputStream(f);
zipOut.putNextEntry(new ZipEntry(fisier));
int nBytes; while((nBytes = fileIn.read(buffer, 0, 1024)) != S1 )
zipOut.write(buffer, 0, nBytes);
zipOut.close();
fileIn.close(); f.close();
}catch(ZipException ze){
System.out.println(ze.toString());
}catch(FileNotFoundException fnfe){
fnfe.printStackTrace();
}catch(IOException ioe){
ioe.printStackTrace();
}Limbajul Java – operații I/O (7)

41 Dezarhivare ZIP
Dezarhivarea unui fișier constă în citirea datelor din arhivă prin ZipInputStream și scrierea
lor prin FileOutputStream în fișierul destinație. Pentru eficiență, transferu l datelor se face
printrSun tablou de tip byte :
String fisier = "Algoritmi.pdf"; //numele fisierului destinatie
String zip = "Algoritmi.zip"; //numele arhivei byte buffer[] = new byte[1024]; try{
FileInputStream fileIn = new FileInputStream(zip); FileOutputStream fileO = new FileOutputStream(fisie r);
ZipInputStream zipIn = new ZipInputStream(fileIn);
zipIn.getNextEntry();
int nBytes; while((nBytes = zipIn.read(buffer, 0, 1024)) != S1)
fileO.write(buffer, 0, nBytes);
fileIn.close(); fileO.close();
}catch(ZipException ze){
System.out.println(ze.toString());
}catch(IOException ioe){
ioe.printStackTrace();
}Limbajul Java – operații I/O (8)

42 Aplicații propuse
1. Să se scrie un program care cere introducerea num elui utilizatorului și afișează pe ecran
mesajul Hello urmat de numele introdus (afișareScitireSafișare).
2. Citirea unui întreg până la introducerea unei val ori valide (tratând excepția
NumberFormatException ).
3. Să se implementeze un program care citește de la tastatură lungimea unui tablou de tip String
și elementele acestuia (numele studenților din semi grupă). Sortați în ordine alfabetică tabloul
(v. metoda sort a clasei Arrays ). Atenție, șirurile trebuie transformate după citi re astfel încât
toate literele să fie mici sau toate mari (v. toLowerCase sau toUpperCase din String ).
4. Modificați prima aplicașie propusă astfel încât s ă citească și vârsta utilizatorului. Dacă vârsta
introdusă depășește 100 să afișeze mesajul "Ești bă trân!", altfel să afișeze "Ești tânăr!";
5. Să se implementeze un program care citește de la tastatură lungimea unui tablou de valori
întregi și elementele acestuia. Să se sorteze tablo ul folosind metoda sort a clasei Arrays . Să se
afișeze pe ecran tabloul sortat.
6. Să se implementeze un program care citește dintrS un fișier întrSun tablou de tip String numele
studenților din semigrupă. Sortați în ordine alfabe tică tabloul (v. metoda sort a clasei Arrays ).
Atenție, șirurile trebuie transformate după citire astfel încât toate literele să fie mici sau toate
mari (v. toLowerCase sau toUpperCase din String ).
7. Să se citească dintrSun fișier un tablou de valor i întregi și să se afișeze pe ecran media lor
aritmetică. Separarea valorilor de pe linii se va f ace prin clasa StringTokenizer prezentată
anterior.
8. Studiați clasa RandomAccessFile care, spre deosebire de FileInputStream și FileOutputStream
(acces secvențial), permite citirea respectiv scrie rea unei anumite locații din fișier. Limbajul Java – operații I/O (9)

43 Java oferă suportul prin numeroase clase pentru internaționalizarea și naționalizarea aplicațiilor
/square6Clasa Locale
Locale locale = Locale.getDefault(); System.out.println(locale.getCountry()); //RO System.out.println(locale.getDisplayCountry()); //Ro mânia
System.out.println(locale.getDisplayCountry(Locale. FRANCE)); //Roumanie
System.out.println(locale.getDisplayLanguage()); //r omână
System.out.println(locale.getDisplayLanguage(Locale .FRANCE)); //roumain
System.out.println(locale.getDisplayName()); //român ă (România)
System.out.println(locale.getLanguage()); //ro Locale g = Locale.GERMANY; System.out.println(g.getLanguage()); //de
/square6Clasa NumberFormat
System.out.println(NumberFormat.getInstance(locale) .format(12.3)); //12,3
System.out.println(NumberFormat.getCurrencyInstance (locale).format(6.8)); //6,80 LEI
/square6Clasa DateFormat
Date date = new Date(2009S1900, 8S1, 31); //YS1900, MS1, D
System.out.println(DateFormat.getDateInstance(0, lo cale).format(date)); //31 august 2009
System.out.println(DateFormat.getDateInstance(2, lo cale).format(date)); //31.08.2009 Internaționalizare și naționalizare

44 Limbajul Java – crearea claselor (1)
/square6Definiția unei clase trebuie să conțină cuvântul ch eie class , numele clasei și corpul clasei.
Opțional, înainte de cuvântul class pot fi folosiți modificatorii public (clasa este vizibilă în
toate pachetele), abstract (v. clase abstracte) sau final (clasa nu poate fi derivată).
Exemplu:
class Person {
private String name; public void setName(String name){
this.name = name;
}public String getName(){
return name;
}
}
/square6Clasele pot conține:
/square6Variabile membru;
/square6Constructori;
/square6Metode.
/square6Tipuri de acces: private , protected , public
/square6Variabilele și metodele private pot fi accesate doa r în cadrul clasei în care sSau declarat;
/square6Variabilele și metodele protejate pot fi accesate î n interiorul clasei, al subclaselor (v. moștenirea) sau
în pachetul ( package ) în care au fost declarate;
/square6Variabilele și metodele publice pot fi accesate ori unde;
/square6Tipul de acces este implicit protejat (dacă nu se p recizează).
/square6Recomandare (încapsulare, v. cursul POO):
/square6Variabile private;
/square6Set de metode publice care să permită accesarea var iabilelor private.

45 Exemplul 1 (un singur pachet)
package person; public class Person {
private String name; private String address; private int age; private void setName(String name){
this.name = name;
}private String getName(){
return name;
}protected void setAddress(String address){
this.address = address;
}protected String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}int getAge(){
return age;
}
}Limbajul Java – crearea claselor (2)
package person; public class Main {
public static void main(String[] args) {
Person p = new Person();
p.name = "Popescu"; //Eroare!
p.setName("Popescu"); //Eroare!
p.setAddress("Str. N. Balcescu, Nr. 5"); p.setAge(103);
System.out.println("Numele: " + p.getName()); //Eroare!
System.out.println("Adresa: " + p.getAddress()); System.out.println("Varsta: " + p.getAge());
}
}

46 Limbajul Java – crearea claselor (3)
Exemplul 2 (pachete diferite, clasa de bază nepubli că)
package person; class Person {
private String name; private String address; private int age; private void setName(String name){
this.name = name;
}private String getName(){
return name;
}protected void setAddress(String address){
this.address = address;
}protected String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}int getAge(){
return age;
}
}package main; import person.Person; public class Main {
public static void main(String[] args) {
Person p = new Person(); //Eroare!
}
}

47 Limbajul Java – crearea claselor (4)
Exemplul 3 (pachete diferite, clasa de bază publică )
package person; public class Person {
private String name; private String address; private int age; private void setName(String name){
this.name = name;
}private String getName(){
return name;
}protected void setAddress(String address){
this.address = address;
}protected String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}int getAge(){
return age;
}
}package main; import person.Person; public class Main {
public static void main(String[] args) {
Person p = new Person();
p.name = "Popescu"; //Eroare!
p.setName("Popescu"); //Eroare!
p.setAddress("Str. N. Balcescu, Nr. 5"); //Eroare!
p.setAge(103);
System.out.println("Numele: " + p.getName()); //Eroare!
System.out.println("Adresa: " + p.getAddress()); //Eroare!
System.out.println("Varsta: " + p.getAge()); //Eroare!
}
}

48 Limbajul Java – crearea claselor (5)
Exemplul 4 (o variantă corectă)
package person; public class Person {
private String name; private String address; private int age; public void setName(String name){
this.name = name;
}public String getName(){
return name;
}public void setAddress(String address){
this.address = address;
}public String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}public int getAge(){
return age;
}
}package person; public class Main {
public static void main(String[] args) {
Person p = new Person(); p.setName("Popescu"); p.setAddress("Str. N. Balcescu, Nr. 5"); p.setAge(103); System.out.println("Numele: " + p.getName()); System.out.println("Adresa: " + p.getAddress()); System.out.println("Varsta: " + p.getAge());
}
}

49 Limbajul Java – constructori (1)
/square6Este o metodă publică fără tip, având același nume cu cel al clasei;
/square6Principalul rol al constructorului este acela de a inițializa obiectul pentru care sSa apelat;
/square6Dacă întrSo clasă nu se declară un constructor, atu nci
compilatorul generează unul implicit, fără parametr i;
/square6ÎntrSo clasă pot coexista mai mulți constructori cu
parametri diferiți (tip, număr);
/square6La instanțierea unui obiect se apelează constructor ul
corespunzător parametrilor de apel;
/square6În Java nu există destructori. Sistemul apelează periodic mecanismul garbage collector .

50 Limbajul Java – constructori (2)
Exemplu
public class Person {
private String name; private String address; private int age; public Person(String name, String address, int age) {
this.name = name; this.address = address; this.age = age;
}public void setName(String name){
this.name = name;
}public String getName(){
return name;
}public void setAddress(String address){
this.address = address;
}public String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}public int getAge(){
return age;
}
}public class Main {
public static void main(String[] args) {
Person p = new Person("Pop", "Sibiu", 103); System.out.println("Numele: " + p.getName()); //Pop System.out.println("Adresa: " + p.getAddress()); //S ibiu
System.out.println("Varsta: " + p.getAge()); //103 p.setName("Rus"); p.setAddress("Avrig"); p.setAge(98); System.out.println("Numele: " + p.getName()); //Rus System.out.println("Adresa: " + p.getAddress()); //A vrig
System.out.println("Varsta: " + p.getAge()); //98
}
}

51 /square6Unul dintre marile avantaje ale programării orienta teSobiect (POO) constă în
reutilizarea codului;
/square6Toate clasele Java, cu excepția interfețelor, sunt subclase ale clasei rădăcină
Object ;
/square6Procesul prin care o clasă nouă refolosește o clasă veche se numește moștenire;
/square6O clasă, numită clasă derivată, poate moșteni varia bilele și metodele unei alte
clase, numită clasă de bază;
/square6Dacă apare aceeași metodă cu aceiași parametri atât în clasa de bază cât și în
cea derivată (prin redefinire) și se apelează metod a instanței clasei derivate, se
execută metoda clasei derivate;
/square6Derivarea unei clase în Java se face prin cuvântul cheie extends urmat de
numele clasei de bază;
/square6O clasă declarată final nu poate fi derivată;
/square6Java nu permite moștenire multiplă: o clasă poate d eriva o singură clasă de
bază. Moștenirea multiplă este permisă doar folosin d interfețele (vor fi
prezentate);
/square6Constructorii clasei derivate pot folosi printrSun apel super constructorii clasei
de bază pentru inițializarea variabilelor moștenite ;
/square6În exemplul prezentat în continuare, clasele Studen t și Teacher moștenesc clasa
Person; Limbajul Java – moștenirea (1)

52 Limbajul Java – moștenirea (2)
Exemplu
public class Person {
private String name; private String address; private int age; public Person(String name, String address, int age) {
this.name = name; this.address = address; this.age = age;
}public void setName(String name){
this.name = name;
}public String getName(){
return name;
}public void setAddress(String address){
this.address = address;
}public String getAddress(){
return address;
}public void setAge(int age){
this.age = age;
}public int getAge(){
return age;
}
}public class Student extends Person {
private int grade; //medie public Student(String name, String address, int age , int grade) {
super(name, address, age);
//trebuie sa fie prima instructiune!
this.grade = grade;
}public void setGrade(int grade){
this.grade = grade;
}public int getGrade(){
return grade;
}
} public class Teacher extends Person {
private int courses; //nr. cursuri public Teacher(String name, String address, int age, int courses) {
super(name, address, age);
//trebuie sa fie prima instructiune!
this.courses = courses;
}public void setCourses(int courses){
this.courses = courses;
}public int getCourses(){
return courses;
}
} public class Main {
public static void main(String[] args) {
Student s = new Student("Rus", "Avrig", 98, 4); System.out.println(s.getAge()); //98
}
}

53 /square6Dacă un constructor al clasei derivate nu apelează prin super un
constructor al clasei de bază, compilatorul va apel a implicit
constructorul fără parametri al clasei de bază. Dac ă însă clasa de bază
are doar constructori cu parametri, compilatorul nu va genera
constructorul implicit. În acest caz, în clasa de b ază trebuie declarat și
un constructor fără parametri.
/square6Exemplu:
public class Base {
public Base(){
}
public Base(int p) { }
} public class Sub extends Base{
public Sub() { }
}Limbajul Java – moștenirea (3)

54 Supraîncărcarea metodelor
public class Base {
public void method(int i) {
System.out.println("Base integer is " + i);
}
public void method(String s){
System.out.println("Base string is " + s);
}
} public class Sub extends Base {
public void method(int j){
System.out.println("Sub integer is " + j);
}
public static void main(String[] args) {
Base b1 = new Base(); Base b2 = new Sub(); Sub s = new Sub(); b1.method(1); //"Base integer is 1" b2.method(2); //"Sub integer is 2"
s.method(3); //"Sub integer is 3" s.method("4"); //"Base string is 4"
}
}Limbajul Java – moștenirea (4)

55 Aplicații
1. Să se implementeze o aplicație care să permită in troducerea de la
tastatură a numărului de studenți din semigrupă urm at de datele lor
(întrSun tablou) și a numărului de profesori din ac est semestru urmat de
datele lor (întrSun alt tablou). Căutați și afișați studentul cu media cea
mai mare respectiv profesorul cu cele mai multe cur suri.
2. Definiți clasa Employee (angajat) derivată din clasa Person prezentată,
având câmpul suplimentar salary . Introduceți de la tastatură 5 obiecte
de tip Employee întrSun tablou. Căutați și afișați angajatul cu sal ariul cel
mai mare.
3. Definiți clasa Product cu câmpul price (preț). Definiți clasa Book
(carte) derivată din clasa Product având câmpurile suplimentare title ,
author și publisher (editor). Introduceți de la tastatură 5 obiecte de tip
Book întrSun tablou. Căutați și afișați cartea cu prețul cel mai mic.
4. Definiți clasa Book (carte) cu câmpurile title , author și publisher
(editor). Definiți clasa LibraryCard (fișă de bibliotecă) derivată din clasa
Book având câmpul suplimentar copies (nr. exemplare). Introduceți de
la tastatură 5 obiecte de tip LibraryCard întrSun tablou. Căutați și afișați
cartea cu numărul cel mai mare de exemplare.
5. Definiți clasa Vehicle cu câmpul manufacturer (fabricant). Definiți
clasa Car derivată din clasa Vehicle având câmpurile suplimentare
model , length (lungime), maxSpeed (viteză maximă), price (preț).
Introduceți de la tastatură 5 obiecte de tip Car întrSun tablou. Căutați și
afișați mașina cu prețul cel mai mic. Limbajul Java – moștenirea (5)

56 Limbajul Java – clase abstracte
/square6O clasă trebuie declarată abstractă dacă conține ce l puțin o metodă abstractă.
/square6Metodele abstracte sunt declarate fără implementare urmând ca ele să fie
implementate în clasele derivate. O clasă abstractă nu poate fi instanțiată.
/square6Exemplu:
public abstract class Product {
private double price; public Product(double price) {
this.price = price;
}public abstract double computeFinalPrice(); public void setPrice(double price){
this.price = price;
}public double getPrice(){
return price;
}
} public class Book extends Product {
public Book(double price) {
super(price);
}public double computeFinalPrice(){ //TVA=9%
return getPrice() + (9*getPrice())/100;
}
}public class Car extends Product{
public Car(double price) {
super(price);
}public double computeFinalPrice(){ //TVA=19%
return getPrice() + (19*getPrice())/100;
}
} public class Main {
public static void main(String[] args) {
Product p = new Product(10); //Eroare!
Book b = new Book(100); System.out.println(b.computeFinalPrice()); Car c = new Car(100000); System.out.println(c.computeFinalPrice());
}
}

57 /square6Interfețele oferă avantajele moștenirii multiple, e vitând complicațiile
acesteia.
/square6Toate metodele dintrSo interfață sunt implicit publ ice și abstracte. O
interfață furnizează numele metodelor fără implemen tarea lor. P
interfață care conține o singură metodă se numește funcțională.
/square6Interfețele nu pot fi instanțiate.
/square6Clasa care folosește o interfață trebuie să impleme nteze toate
metodele acesteia.
/square6Se poate deriva o interfață din alte interfețe prin același mecanism
care a fost prezentat la clase (v. moștenirea).
/square6În continuare vor fi prezentate câteva exemple:
/square6O interfață Price folosită de clasele Product , Book și Car .
/square6Folosirea interfețelor Comparator sau Comparable pentru sortarea unui
tablou de obiecte prin metoda sort din clasa Arrays . În cazul interfeței
Comparator trebuie implementată metoda compare .
/square6Interfața Serializable pentru serializarea obiectelor. Limbajul Java – interfețe (1)

58 Limbajul Java – interfețe (2)
Exemplul 1 (interfața Price , implementare computeFinalPrice )
public interface Price {
public double computeFinalPrice();
} public abstract class Product implements Price{
private double price; public Product(double price) {
this.price = price;
}public void setPrice(double price){
this.price = price;
}public double getPrice(){
return price;
}
} public class Book extends Product {
public Book(double price) {
super(price);
}public double computeFinalPrice(){ //TVA=9%
return getPrice() + (9*getPrice())/100;
}
}public class Car extends Product{
public Car(double price) {
super(price);
}public double computeFinalPrice(){ //TVA=19%
return getPrice() + (19*getPrice())/100;
}
} public class Main {
public static void main(String[] args) {
Product p = new Product(10); //Eroare!
Book b = new Book(100); System.out.println(b.computeFinalPrice()); Car c = new Car(100000); System.out.println(c.computeFinalPrice());
}
}

59 Limbajul Java – interfețe (3)
Exemplul 2 (interfața Comparator , implementare compare )
public class Item {
String str; int num; Item(String str, int num) {
this.str = str; this.num = num;
}
}public class Main {
public static void main(String[] args) {
Item t[] = new Item[5]; t[0] = new Item("c", 2); t[1] = new Item("a", 1); t[2] = new Item("e", 4); t[3] = new Item("b", 5); t[4] = new Item("d", 3);
//Sortare dupa campul num
java.util.Arrays.sort(t, new Comparator() {
public int compare(Object o1, Object o2) {
//return ((Item)o1).numS((Item)o2).num;
if(((Item)o1).num<((Item)o2).num) return S1; if(((Item)o1).num>((Item)o2).num) return 1; return 0;
}
});
//Sortare dupa campul str
java.util.Arrays.sort(t, new Comparator() {
public int compare(Object o1, Object o2) {
return ((Item)o1).str.compareTo(((Item)o2).str);
}
});
}
}

60 Limbajul Java – interfețe (4)
Exemplul 3 (interfața Comparator , implementare compare )
public class Item implements Comparator {
String str; int num; Item() {} Item(String str, int num) {
this.str = str; this.num = num;
}public int compare(Object o1, Object o2) {
return ((Item)o1).numâ((Item)o2).num;
}
}public class Main {
public static void main(String[] args) {
Item t[] = new Item[5]; t[0] = new Item("c", 2); t[1] = new Item("a", 1); t[2] = new Item("e", 4); t[3] = new Item("b", 5); t[4] = new Item("d", 3);
//Sortare dupa campul num
java.util.Arrays.sort(t, new Item());
//Afisare for (int i=0; i<t.length; i++)
System.out.println(t[i].str + " â " + t[i].num);
//Sortare dupa campul str
java.util.Arrays.sort(t, new Comparator() {
public int compare(Object o1, Object o2) {
return ((Item)o1).str.compareTo(((Item)o2).str);
}
});
//Afisare
for (int i=0; i<t.length; i++)
System.out.println(t[i].str + " â " + t[i].num);
}
}

61 Limbajul Java – interfețe (5)
Exemplul 4 (interfața Comparable , implementare compareTo )
public class Item implements Comparable {
String str; int num; Item(String str, int num) {
this.str = str; this.num = num;
}public int compareTo(Object o) {
return numâ((Item)o).num; //return str.compareTo(((Item)o).str);
}
}public class Main {
public static void main(String[] args) {
Item t[] = new Item[5]; t[0] = new Item("c", 2); t[1] = new Item("a", 1); t[2] = new Item("e", 4); t[3] = new Item("b", 5); t[4] = new Item("d", 3);
//Sortare dupa campul num
java.util.Arrays.sort(t);
//Afisare for (int i=0; i<t.length; i++)
System.out.println(t[i].str + " â " + t[i].num);
//Sortare dupa campul str
java.util.Arrays.sort(t, new Comparator() {
public int compare(Object o1, Object o2) {
return ((Item)o1).str.compareTo(((Item)o2).str);
}
});
//Afisare
for (int i=0; i<t.length; i++)
System.out.println(t[i].str + " â " + t[i].num);
}
}

62 Limbajul Java – interfețe (6)
Exemplul 5 (interfața Serializable – permite serializarea obiectelor)
public class Item implements Serializable {
String str; int num; Item(String str, int num) {
this.str = str; this.num = num;
}
} public class Main {
public static void main(String[] args) {
FileOutputStream fos = null; FileInputStream fis = null; ObjectOutputStream oos = null; ObjectInputStream ois = null; try{
fos = new FileOutputStream("data.txt"); fis = new FileInputStream("data.txt");
}
catch(FileNotFoundException e){
e.printStackTrace();
}try{
oos = new ObjectOutputStream(fos); ois = new ObjectInputStream(fis);
}
catch(IOException e){
e.printStackTrace();
}try{
oos. writeObject (new Item("c", 2)); //Scrierea obiectului in fisi er
oos.close(); fos.close();
}
catch(IOException e){
e.printStackTrace();
}try{
Item item=(Item)ois. readObject (); //Citirea obiectului din fisier
System.out.println(item.str + " S " + item.num); ois.close(); fis.close();
}
catch(IOException e){
e.printStackTrace();
}
catch(ClassNotFoundException e){
e.printStackTrace();
}
}
}

Expresii lambda
/square6Disponibile din JDK 1.8, expresiile lambda pot fi f olosite pentru a
crea instanțe ale unor interfețe funcționale [Blo17] .
/square6Pentru expresiile lambda sSa introdus noul operator S> în Java.
/square6Expresiile lambda sunt compuse din două părți. Part ea din
stânga operatorului S> specifică lista parametrilor separați prin
virgulă, iar partea din dreapta este corpul lambda care conține
operațiile efectuate de expresia lambda. Spre exemp lu, expresia
lambda
(a,b)S>a+b
/square6calculează suma parametrilor a și b. În cazul în ca re în partea
dreaptă a expresiei lambda este un bloc de instrucț iuni, acesta
trebuie furnizat între acolade:
(a,b)S>{return a+b;} Limbajul Java – interfețe (7)

Exemplul 1 (interfața Arithmetic , aplicare operații aritmetice)
public interface Arithmetic {
int operation(int a, int b);
} public class Main {
public static void main(String[] args) {
// TODO code application logic here Arithmetic addition = (a,b)S>a+b;
System.out.println(addition.operation(6,2)); //8
Arithmetic substraction = (a,b)S>aSb;
System.out.println(substraction.operation(6,2)); // 4
Arithmetic multiplication = (a,b)S>a*b;
System.out.println(multiplication.operation(6,2));/ /12
Arithmetic division = (a,b)S>a/b;
System.out.println(division.operation(6,2)); //3
}
}Limbajul Java – interfețe (8)

Exemplul 2 (interfața Comparator , sortare folosind expresii lambda)
public class Item {
String str;
int num; Item(String str, int num) {
this.str = str; this.num = num;
}
}public class Comparisons {
public int compareByStr(Item a, Item b){
return a.str.compareTo(b.str);
}public int compareByNum(Item a, Item b){
return a.numSb.num;
}
}public class Main {
public static void main(String[] args) {
Item t[] = new Item[5]; Comparisons c = new Comparis ons();
t[0] = new Item("c", 2); t[1] = new Item("a", 1); t[2] = new Item("e", 4); t[3] = new Item("b", 5); t[4 ] = new Item("d", 3);
java.util.Arrays.sort(t,(o1,o2) S> c.compareByNum(o 1, o2)); //Sortare dupa campul num
java.util.Arrays.sort(t,(o1,o2) S> c.compareByStr(o 1, o2)); //Sortare dupa campul str
}
}Limbajul Java – interfețe (9)

Exemplul 3 (Intarfața Comparator , fără clasa Comparisons din exemplul 2)
public class Item {
String str;
int num; Item(String str, int num) {
this.str = str; this.num = num;
}
}public class Main {
public static void main(String[] args) {
Item t[] = new Item[5]; t[0] = new Item("c", 2); t[1] = new Item("a", 1); t[2] = new Item("e", 4); t[3] = new Item("b", 5); t[4 ] = new Item("d", 3);
//Sortare dupa campul num
java.util.Arrays.sort(t,(o1,o2) S> {return o1.numâo2.num;} );
//Sortare dupa campul str
java.util.Arrays.sort(t,(o1,o2) S> {return o1.str.compareTo(o2.str);} );
}
}
Afișarea se poate face cu ajutorul buclei:
for(Item i:t)
System.out.println(i.str + " " + i.num); Limbajul Java – interfețe (10)

67 Aplicații
1. Definiți clasa Person cu câmpurile name , address și age . Definiți clasa Student
derivată din clasa Person având câmpul suplimentar grade (medie). Introduceți
dintrSun fișier student.txt numărul de studenți din semigrupă urmat de datele lor,
întrSun tablou. Sortați și afișați studenții în ord inea crescătoare a mediei.
2. Definiți clasa Person cu câmpurile name , address și age . Definiți clasa Teacher
derivată din clasa Person având câmpul suplimentar courses (nr. cursuri).
Introduceți dintrSun fișier teacher.txt numărul de profesori din acest semestru
urmat de datele lor, întrSun tablou. Sortați și afi șați profesorii în ordinea crescătoare
a numărului de cursuri predate.
3. Definiți clasa Person cu câmpurile name , address și age . Definiți clasa
Employee (angajat) derivată din clasa Person având câmpul suplimentar salary
(salariu). Introduceți dintrSun fișier employee.txt numărul de angajați urmat de
datele lor, întrSun tablou. Sortați și afișați anga jații în ordinea crescătoare a
salariilor.
4. Definiți clasa Product cu câmpul price (preț). Definiți clasa Book (carte) derivată
din clasa Product având câmpurile suplimentare title , author și publisher
(editor). Introduceți dintrSun fișier book.txt numărul de cărți urmat de datele lor,
întrSun tablou. Sortați și afișați cărțile în ordin ea crescătoare a prețului.
5. Definiți clasa Book (carte) cu câmpurile title , author și publisher (editor).
Definiți clasa LibraryCard (fișă de bibliotecă) derivată din clasa Book având
câmpul suplimentar copies (nr. exemplare). Introduceți dintrSun fișier
librarycard.txt numărul de fișe urmat de datele acestora, întrSun tablou. Sortați și
afișați cărțile în ordinea crescătoare a numărului de exemplare disponibile.
6. Definiți clasa Vehicle cu câmpul manufacturer (fabricant). Definiți clasa Car
derivată din clasa Vehicle având câmpurile suplimentare model , length
(lungime), maxSpeed (viteză maximă), price (preț). Introduceți dintrSun fișier
car.txt numărul de mașini, urmat de datele lor, întrSun ta blou. Sortați și afișați
mașinile în ordinea crescătoare a prețului. Limbajul Java – interfețe (11)

68 Limbajul Java – partajarea datelor (1)
/square6Partajarea datelor de către obiectele unei clase po ate fi realizată prin intermediul membrilor
statici ai clasei respective.
/square6În timp ce variabilele obișnuite (nonSstatice) apar țin instanțelor clasei (obiectelor),
variabilele declarate statice aparțin clasei și sun t partajate de către toate obiectele acesteia.
/square6Unei variabile statice i se alocă memorie o singură dată, la prima instanțiere a clasei. La
următoarele instanțieri ale clasei variabilei stati ce nu i se mai alocă memorie, dar toate
obiectele clasei pot accesa aceeași variabilă stati că, alocată la prima instanțiere.
/square6Metodele statice pot fi apelate fără instanțierea c lasei.
/square6Metodele statice nu pot utiliza variabile și metode nonSstatice.
/square6Un exemplu de utilizare a unei variabile statice es te contorizarea obiectelor instanțiate
dintrSo clasă:
public class Person {
private String name; static int counter; public Person(String name) {
this.name = name; counter++; System.out.println(counter + " persoane.");
}public void setName(String name){
this.name = name;
}public String getName(){
return name;
}
}public class Main {
public static void main(String[] args) {
Person p1 = new Person("Popescu"); //"1 persoane." Person p2 = new Person("Ionescu"); //"2 persoane."
}
}

69 Exemple de folosire a metodelor statice:
public class Person {
private String name; private int age; static int counter; public Person(String name, int age) {
this.name = name; this.age = age; increaseCounter();
}public static void increaseCounter(){
counter++; System.out.println(counter + " persoane.");
}public static void increaseAge(){
age++; //Eroare!
}public void setName(String name){
this.name = name;
}public String getName(){
return name;
}public void setAge(int age){
this.age = age;
}public int getAge(){
return age;
}
}Limbajul Java – partajarea datelor (2)
public class Main {
public static void main(String[] args) {
Person p1 = new Person("Popescu", 61); //"1 persoane ."
Person p2 = new Person("Ionescu", 72); //"2 persoane ."
Person.increaseCounter(); //"3 persoane." p1 = new Person("Petrescu", 53); //"4 persoane."
}
}

70 Alte exemple de folosire a variabilelor și metodelo r statice:
public class Person {
private String name; private int age; static int counter; public Person(String name, int age) {
this.name = name; this.age = age; increaseCounter();
}public static void increaseCounter(){
counter++; System.out.println(counter + " persoane.");
}
public void printCounter(){
System.out.println(counter);
}
public void setName(String name){
this.name = name;
}public String getName(){
return name;
}public void setAge(int age){
this.age = age;
}public int getAge(){
return age;
}Limbajul Java – partajarea datelor (3)
public static void main(String[] args) {
Person p1 = new Person("Popescu", 61); //"1 persoane ."
Person p2 = new Person("Ionescu", 72); //"2 persoane ."
Person.increaseCounter() ; //"3 persoane." p1 = new Person("Petrescu", 53); //"4 persoane.“
printCounter(); //Eroare!
p2.printCounter(); //”4”
}
}

71 Limbajul Java – atribuire vs. clonare (1)
Folosirea operatorului de atribuire
În cazul obiectelor operatorul de atribuire determi nă atribuirea referințelor (adreselor)
public class Person {
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
}public void setName(String name) {
this.name = name;
}public String getName() {
return name;
}public void setAge(int age) {
this.age = age;
}public int getAge() {
return age;
}
}public class Main {
public static void main(String[] args) {
Person p1 = new Person("Pop", 61); Person p2 = p1; System.out.println(p1.getName() + ", " + p1.getAge( )); //"Pop, 61"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Pop, 61"
p1.setAge(p1.getAge() + 1); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Pop, 62"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Pop, 62"
p2.setName("Rus"); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Rus, 62"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Rus, 62"
p1 = new Person("Lup", 53); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Lup, 53"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Rus, 62"
p1.setAge(p1.getAge() + 1); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Lup, 54"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Rus, 62"
}
}

72 Limbajul Java – atribuire vs. clonare (2)
Clonarea obiectelor
public class Person implements Cloneable {
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
}public Object clone() { //protected in Object
Object obj = null; try {
obj = super.clone();
}catch (CloneNotSupportedException ex) { }return obj;
}public void setName(String name) {
this.name = name;
}public String getName() {
return name;
}public void setAge(int age) {
this.age = age;
}public int getAge() {
return age;
}
}public class Main {
public static void main(String[] args) {
Person p1 = new Person("Pop", 61); Person p2 = (Person)p1.clone(); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Pop, 61"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Pop, 61"
p1.setAge(p1.getAge() + 1); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Pop, 62"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Pop, 61"
p2.setName("Rus"); System.out.println(p1.getName() + ", " + p1.getAge( )); //"Pop, 62"
System.out.println(p2.getName() + ", " + p2.getAge( )); //"Rus, 61"
}
}

73 Limbajul Java – interfață grafică (1)
/square6O componentă foarte importantă a aplicațiilor moderne este interfața grafică prin care acestea comunică cu utilizatorul: se citesc datele și se afișează rezultatele.
/square6Mediile de dezvoltare Java oferă numeroase pachete cu diverse componente vizuale.
/square6În următoarea aplicație vom folosi componente din pachetul AWT (Advanced Windowing Toolkit) pentru citirea studenților întrSo listă
/square6Fereastra neredimensionabilă a aplicației este prezentată pe pagina următoare.

74 /square6Numele studentului se introduce printrSun TextField ;
/square6Acționarea butonului Add determină adăugarea textului din
TextField în componenta List respectiv ștergerea din TextField ;
/square6Adăugarea în componenta List determină apariția unui scroll
atunci când numărul de linii introduse trece de lim ita de
vizualizare. Limbajul Java – interfață grafică (2)
Fereastra aplicației

75 Codul sursă al aplicației
public class StudentFrame extends Frame {
private List studentList = new List(); private TextField studentTextField = new TextField( );
private Button addButton = new Button(); public StudentFrame() {
try {
jbInit();
}catch(Exception e) {
e.printStackTrace();
}show();
}public static void main(String[] args) {
StudentFrame studentFrame = new StudentFrame();
}private void jbInit() throws Exception {
this.addWindowListener(new java.awt.event.WindowAda pter() {
public void windowClosing(WindowEvent e) {
this_windowClosing(e);
}
}); studentList.setBounds(new Rectangle(210, 60, 160, 1 40));
studentTextField.setBounds(new Rectangle(25, 60, 16 0, 30));
addButton.setLabel("Add"); addButton.setBounds(new Rectangle(70, 120, 80, 25)) ; Limbajul Java – interfață grafică (3)
addButton.addActionListener(new java.awt.event.Acti onListener() {
public void actionPerformed(ActionEvent e) {
addButton_actionPerformed(e);
}
}); this.setSize(400, 220); this.setResizable(false); this.setLayout(null); //componentele pot fi asezat e cu mouseSul
this.setTitle("Students"); this.setBackground(new Color(240, 240, 240)); this.add(addButton, null); this.add(studentTextField, null); this.add(studentList, null);
} void this_windowClosing(WindowEvent e) {
System.exit(0); //inchiderea aplicatiei
} void addButton_actionPerformed(ActionEvent e) {
studentList.add(studentTextField.getText()); studentTextField.setText(""); //stergere
}
}

76 Limbajul Java – interfață grafică (4)
Tratarea evenimentelor
/square6Evenimentele sunt generate de acțiunile utilizatoru lui asupra
componentelor interfeței grafice.
/square6Pentru tratarea unui anumit eveniment întrSo clasă, trebuie
implementată interfața Listener corespunzătoare care să prelucreze
evenimentul respectiv. De exemplu, pentru tratarea evenimentelor
ActionEvent , se implementează interfața ActionListener .
/square6Astfel, evenimentele sunt recepționate de obiecte d e tip Listener care
apelează metode de tratare a evenimentelor.
/square6Aplicația anterioară tratează evenimentele de închi dere a ferestrei și de
click pe butonul Add .
/square6În continuare vom extinde aplicația astfel încât să răspundă la
apăsarea tastei ENTER, tratând evenimentul KeyEvent. Pentru asta se
poate folosi interfața KeyListener implementând toate metodele
(keyPressed , keyReleased , keyTyped ) sau clasa abstractă KeyAdapter
care ne permite să implementăm doar metodele necesa re (în cazul
nostru keyPressed ).

77 public class StudentFrame extends Frame {
private List studentList = new List(); private TextField studentTextField = new TextField(); private Button addButton = new Button(); public StudentFrame() {
try {
jbInit();
}catch(Exception e) {
e.printStackTrace();
}show(); studentTextField.requestFocus();
} public static void main(String[] args) {
StudentFrame studentFrame = new StudentFrame();
} private void jbInit() throws Exception {
this.addWindowListener(new java.awt.event.WindowAdapter () {
public void windowClosing(WindowEvent e) {
this_windowClosing(e);
}
}); studentList.setBounds(new Rectangle(210, 60, 160, 140 ));
studentTextField.setBounds(new Rectangle(25, 60, 160, 30));
studentTextField.addKeyListener(new java.awt.event. KeyAdapter() {
public void keyPressed(KeyEvent e) {
studentTextField_keyPressed(e);
}
});
addButton.setLabel("Add"); addButton.setBounds(new Rectangle(70, 120, 80, 25));Limbajul Java – interfață grafică (5)
addButton.addActionListener(new java.awt.event.ActionL istener() {
public void actionPerformed(ActionEvent e) {
addButton_actionPerformed(e);
}
}); this.setSize(400, 220); this.setResizable(false); this.setLayout(null); //componentele pot fi asezate cu mouseSul
this.setTitle("Students"); this.setBackground(new Color(240, 240, 240)); this.add(addButton, null); this.add(studentTextField, null); this.add(studentList, null);
} void this_windowClosing(WindowEvent e) {
System.exit(0); //inchiderea aplicatiei
} void addButton_actionPerformed(ActionEvent e) {
studentList.add(studentTextField.getText()); studentTextField.setText(""); //stergere studentTextField.requestFocus();
} void studentTextField_keyPressed(KeyEvent e) {
if(e.getKeyCode()==e.VK_ENTER)
addButton_actionPerformed(new ActionEvent(this, 0, null));
}
}

78 Layout manager (aranjarea componentelor)
/square6Toate obiectele grafice de tip container ( Frame ,
Panel , etc.) au o proprietate layout prin care se
specifică cum să fie așezate și dimensionate componentele: null , XYLayout , BorderLayout ,
FlowLayout , GridLayout , GridBagLayout , etc.
/square6Un layout null (folosit și în aplicația prezentată) sau
XYLayout păstrează pozițiile și dimensiunile originale
ale componentelor. Se pot folosi în cazul containerelor neredimensionabile.
/square6BorderLayout , FlowLayout , GridLayout și
GridBagLayout repoziționează și/sau rescalează
obiectele în cazul redimensionării containerului.Limbajul Java – interfață grafică (6)

79 BorderLayout permite aranjarea componentelor din
container în 5 zone: nord, sud, est, vest și centru .
Componentele din nord și sud își păstrează înălțime a
originală și sunt scalate la lățimea containerului.
Componentele din est și vest își păstrează lățimea originală
și sunt scalate vertical astfel încât să acopere sp ațiul dintre
nord și sud. Componenta din centru se expandează pe ntru
acoperirea întreg spațiului rămas. Constructori:BorderLayout() – fără distanță între componente;BorderLayout(int hgap, int vgap) – primește ca param etri
distanțele orizontale și verticale dintre component e.Limbajul Java – interfață grafică (7)
public class BorderFrame extends Frame {
private BorderLayout bLayout = new BorderLayout(); private Button northButton = new Button("North Button ");
private Button southButton = new Button("South Button ");
private Button westButton = new Button("West Button") ;
private Button eastButton = new Button("East Button") ;
private Button centerButton = new Button("Center Butt on");
public BorderFrame() {
this.setSize(400, 220); this.setTitle("BorderLayout"); this.setLayout(bLayout); this.setBackground(new Color(240, 240, 240)); this.add(northButton, BorderLayout.NORTH); this.add(southButton, BorderLayout.SOUTH); this.add(westButton, BorderLayout.WEST); this.add(eastButton, BorderLayout.EAST); this.add(centerButton, BorderLayout.CENTER); this.show();
} public static void main(String[] args) {
new BorderFrame();
}
}

80 public class FlowFrame extends Frame {
private FlowLayout fLayout = new FlowLayout(); private Button firstButton = new Button("First Button ");
private Button secondButton = new Button("Second Butt on");
private Button thirdButton = new Button("Third Button ");
private Button fourthButton = new Button("Fourth Butt on");
private Button fifthButton = new Button("Fifth Button ");
private Button lastButton = new Button("Last Button") ;
public FlowFrame() {
this.setSize(400, 220); this.setTitle("FlowLayout"); this.setLayout(fLayout); this.setBackground(new Color(240, 240, 240)); this.add(firstButton); this.add(secondButton); this.add(thirdButton); this.add(fourthButton); this.add(fifthButton); this.add(lastButton); this.show();
} public static void main(String[] args) {
new FlowFrame();
}
}FlowLayout aranjează componentele pe linii păstrând
dimensiunile. Aliniază componentele care încap într So linie
și dacă e nevoie continuă pe linia următoare. Se fo losește
de obicei pentru aranjarea butoanelor întrSun Panel .
Constructori:FlowLayout() – aliniere centrată și distanță implicit ă de 5
între componente atât pe orizontală cât și pe verti cală;
FlowLayout(int align) – primește ca parametru tipul de
aliniere (LEFT, RIGHT, CENTER din FlowLayout), dista nța
dintre componente fiind implicit 5;FlowLayout(int align, int hgap, int vgap) – primește ca
parametri tipul de aliniere (LEFT, RIGHT, CENTER di n
FlowLayout) și distanțele orizontale și verticale d intre
componente.
Limbajul Java – interfață grafică (8)

81 GridLayout împarte containerul în linii și coloane și
păstrează componentele în celulele astfel obținute. Toate
celulele au aceeași dimensiune. Fiecare componentă este
expandată la dimensiunea celulei. În cazul unor inte rfețe
complexe, se pot introduce în celule containere Panel cu
subcomponente aranjate tot prin GridLayout . Pentru
obținerea unor spații libere se pot introduce compo nente
Panel goale în celulele corespunzătoare.
Constructori:GridLayout() – creează o singură linie cu câte o col oană
pentru fiecare componentă adăugată, fără distanță î ntre
componente;GridLayout(int rows, int cols) – primește ca paramet ri
numărul de linii și coloane;GridLayout(int rows, int cols, int hgap, int vgap) –
primește ca parametri numărul de linii și coloane respectiv distanțele orizontale și verticale dintre
componente.Limbajul Java – interfață grafică (9)
public class GridFrame extends Frame {
private GridLayout gLayout = new GridLayout(2, 3, 50, 100);
private Button firstButton = new Button("First Button ");
private Button secondButton = new Button("Second Butt on");
private Button thirdButton = new Button("Third Button ");
private Button fourthButton = new Button("Fourth Butt on");
private Button fifthButton = new Button("Fifth Button ");
private Panel emptyPanel = new Panel(); public GridFrame() {
this.setSize(400, 220); this.setTitle("GridLayout"); this.setLayout(gLayout); this.setBackground(new Color(240, 240, 240)); this.add(firstButton); this.add(secondButton); this.add(thirdButton); this.add(fourthButton); this.add(emptyPanel); this.add(fifthButton); show();
} public static void main(String[] args) {
new GridFrame();
}
}

82 GridBagLayout împarte containerul în celule care
pot avea dimensiuni diferite. O componentă poate ocupa mai multe celule. Exemplu:
Alinierea componentelor:
First Button:
gridy = 0, gridx = 0 (celula [0,0]) gridwidth = 2, gridheight = 1 (două coloane, o lini e)
weightx = 0.6 (0.6 din extraspațiul orizontal)weighty = 0.0 (0.0 din extraspațiul vertical)
Second Button:
gridy = 0, gridx = 2 (celula [0,2]) gridwidth = 2, gridheight = 1 (două coloane, o lini e)
weightx = 0.3 (0.3 din extraspațiul orizontal)weighty = 0.0 (0.0 din extraspațiul vertical)
Third Button:
gridy = 1, gridx = 0 (celula [1,0]) gridwidth = 4, gridheight = 1 (patru coloane, o li nie)
weightx = 0.0 (0.0 din extraspațiul orizontal) weighty = 0.3 (0.3 din extraspațiul vertical)
Fourth Button:
gridy = 2, gridx = 0 (celula [2,0]) gridwidth = 1, gridheight = 3 (o coloană, trei linii )
weightx = 0.0 (0.0 din extraspațiul orizontal) weighty = 0.3 (0.3 din extraspațiul vertical)
Fifth Button:
gridy = 2, gridx = 1 (celula [2,1]) gridwidth = 3, gridheight = 2 (trei coloane, două lini i)
weightx = 0.6 (0.6 din extraspațiul orizontal)weighty = 0.6 (0.6 din extraspațiul vertical)
Last Button:
gridy = 4, gridx = 1 (celula [4,1]) gridwidth = 3, gridheight = 1 (trei coloane, o linie) weightx = 0.6 (0.6 din extraspațiul orizontal)weighty = 0.3 (0.3 din extraspațiul vertical)Limbajul Java – interfață grafică (10)
First Button [0,0] Second Button [0,2]
Third Button [1,0]
Fifth Button [2,1]
Last Button [4,1] Fourth
Button
[2,0]

83 Limbajul Java – interfață grafică (11)
GridBagLayout – codul sursă
public class GridBagFrame extends Frame {
private GridBagLayout gbLayout = new GridBagLayout( );
private GridBagConstraints gbc = new GridBagConstra ints();
private Button firstButton = new Button("First Butt on");
private Button secondButton = new Button("Second Bu tton");
private Button thirdButton = new Button("Third Butt on");
private Button fourthButton = new Button("Fourth Bu tton");
private Button fifthButton = new Button("Fifth Butt on");
private Button lastButton = new Button("Last Button ");
public GridBagFrame() {
this.setSize(400, 220); this.setTitle("GridBagLayout"); this.setLayout(gbLayout); this.setBackground(new Color(240, 240, 240)); gbc.fill = GridBagConstraints.BOTH; //directii de e xtindere
gbc.insets = new Insets(5, 5, 5, 5); //dist. fata d e marginile celulei
gbc.gridy = 0; //linia 0 gbc.gridx = 0; //coloana 0 gbc.gridwidth = 2; //ocupa doua coloane gbc.weightx = 0.6; //0.6 din extraspatiul orizontalgbLayout.setConstraints(firstButton, gbc); this.add(firstButton); gbc.gridy = 0; //linia 0 gbc.gridx = 2; //coloana 2 gbc.weightx = 0.3; //0.3 din extraspatiul orizontalgbLayout.setConstraints(secondButton, gbc); this.add(secondButton); gbc.gridy = 1; //linia 1 gbc.gridx = 0; //coloana 0 gbc.gridwidth = 4; //ocupa 4 coloane gbc.weightx = 0.0; //resetare gbc.weighty = 0.3; //0.3 din extraspatiul vertical gbLayout.setConstraints(thirdButton, gbc); this.add(thirdButton); gbc.gridy = 2; //linia 2 gbc.gridx = 0; //coloana 0 gbc.gridwidth = 1; //resetare gbc.gridheight = 3; //ocupa trei linii gbLayout.setConstraints(fourthButton, gbc); this.add(fourthButton); gbc.gridy = 2; //linia 2 gbc.gridx = 1; //coloana 1 gbc.gridwidth = 3; //ocupa trei coloane gbc.gridheight = 2; //ocupa doua linii gbc.weighty = 0.6; //0.6 din extraspatiul vertical gbc.weightx = 0.6; //0.6 din extraspatiul orizontalgbLayout.setConstraints(fifthButton, gbc); this.add(fifthButton); gbc.gridy = 4; //linia 4 gbc.gridx = 1; //coloana 1 gbc.gridheight = 1; //resetare gbc.weighty = 0.3; //0.3 din extraspatiul vertical gbLayout.setConstraints(lastButton, gbc); this.add(lastButton); show();
} public static void main(String[] args) {
new GridBagFrame();
}
}

84 Crearea tabelelor
/square6O clasă care permite crearea tabelelor este JTable ;
/square6Gestionarea componentelor JTable se poate face prin clasa
DefaultTableModel ;
/square6Pentru o funcționare corectă cu scroll, obiectul JTable trebuie
adăugat pe un JScrollPane și nu pe ScrollPane !
/square6Aplicația următoare folosește două tabele, unul pre încărcat, iar
celălalt cu încărcare dinamică a datelor:Limbajul Java – interfață grafică (12)

85 Codul sursă al aplicației cu tabele
public class TableFrame extends Frame {
private GridLayout gLayout = new GridLayout(1, 2, 1 0, 10);
private JScrollPane leftScrollPane = new JScrollPan e();
private JScrollPane rightScrollPane = new JScrollPa ne();
private String leftTableColumns[] = {"Name", "Age"} ; //header
private Object leftTableData[][] = {{"Popescu", "10 3"}, {"Ionescu", "98"}}; //continut
private JTable leftTable = new JTable(leftTableData , leftTableColumns); //tabel cu date preincarcate
private JTable rightTable = new JTable(); //tabel g ol
private String rightTableColumns[] = {"Column 1", " Column 2"}; //header
private DefaultTableModel rightTableModel = new Def aultTableModel(rightTableColumns, 0);
public TableFrame() {
this.setSize(400, 150); this.setLayout(gLayout); this.setTitle("Tables"); this.setBackground(new Color(240, 240, 240)); this.add(leftScrollPane); this.add(rightScrollPane); leftScrollPane.getViewport().add(leftTable, null); rightScrollPane.getViewport().add(rightTable, null) ;
rightTable.setModel(rightTableModel); for(int i=1; i<=10; i++){
String row[] = {"Row" + i + ", Col 1", "Row" + i + ", Col 2"};
rightTableModel.addRow(row);
}show();
} public static void main(String[] args) {
new TableFrame();
}
}Limbajul Java – interfață grafică (13)

86 Aplicații
1. Introduceți în fereastra aplicației care gestione ază lista de
studenți un buton Clear care să permită ștergerea conținutului
listei. Ștergerea conținutului componentei List (din pachetul
AWT) se poate face prin metodele clear sau removeAll .
2. Modificați funcția de adăugare în listă astfel în cât aceasta să
păstreze lista sortată la introducerea unui nou stu dent. Preluarea
conținutului componentei List (din AWT) întrSun tablou de tip
String se poate efectua prin metoda getItems , iar preluarea liniei
de pe o anumită poziție se poate face prin metoda getItem cu un
parametru de tip int , reprezentând poziția în listă. Inserarea pe o
poziție în listă se poate efectua prin metoda add cu un
parametru String și unul de tip int , reprezentând poziția. De
asemenea, getItemCount returnează numărul de linii din listă.
3. Înlocuiți lista din aplicația prezentată cu un ta bel.
4. Dezvoltați aplicația astfel încât, pe lângă nume, să se introducă
în tabel adresa, vârsta și media studentului.
5. Rearanjați componentele pe fereastră prin GridLayout sau
GridBagLayout și setați fereastra redimensionabilă.Limbajul Java – interfață grafică (14)

87 Limbajul Java – fire de execuție (1)
/square6Un fir de execuție ( thread ) este o secvență de instrucțiuni executată de un
program.
/square6Firul de execuție primar este metoda main și atunci când acesta se termină, se
încheie și programul.
/square6Un program poate utiliza fire multiple care sunt ex ecutate concurențial.
/square6Utilizarea firelor multiple este utilă în cazul pro gramelor complexe care
efectuează seturi de activități multiple.
/square6Fiecare fir de execuție are o prioritate care poate lua valori de la 1 (prioritate
mică) la 10 (prioritate maximă). Firele cu priorita te mare sunt avantajate la
comutare, ele primesc mai des controlul procesorulu i.
/square6Pentru implementarea unui fir de execuție în Java, se po ate extinde clasa
Thread . Deoarece Java nu acceptă moștenirea multiplă, în cazul în care a fost
deja extinsă o clasă, pentru crearea unui fir de execuți e trebuie implementată
interfațaRunnable . Indiferent de metoda utilizată, se suprascrie metodarun
care trebuie să conțină instrucțiunile firului.
/square6Aplicația următoare pornește două fire de execuție: unu l pentru afișarea
numerelor și celălalt pentru afișarea literelor. Pentru a observa diferențele dintre
cele două metode de implementare, firul de execuție Numbers extinde clasa
Thread , în timp ce Letters implementează interfațaRunnable .

88 Afișare concurențială de numere și litere:
public class Numbers extends Thread { //extinde clas a Thread
public void run(){
for(int i=0; i<1000; i++){
System.out.println(i);
}
}
} public class Letters implements Runnable { //implemen teaza interfata Runnable
char a = 'a'; public void run(){
for(int i=0; i<1000; i++){
int c = a + i%26; System.out.println((char)c);
}
}
} public class Main {
public static void main(String[] args) {
Numbers numbers = new Numbers();
Thread letters = new Thread(new Letters());
letters.start(); numbers.start();
}
}Limbajul Java – fire de execuție (2)

89 /square6Principalele operații care pot fi efectuate după crearea unui fir de execuție:
/square6start – pornește firul de execuție
/square6setPriority – setează prioritatea firului de execuție (valoare
între 1 și 10)
/square6getPriority – returnează prioritatea firului de execuție
(valoare între 1 și 10)
/square6sleep – suspendă execuția unui fir pentru o perioadă
precizată în milisecunde.
/square6yield – suspendă temporar execuția firului curent în
favoarea altor fire de execuție.
/square6Se recomandă oprirea firului prin încheierea execuț iei
metodei run .
/square6Următoarea aplicație folosește un fir de execuție pentru deplasarea unei mingi pe orizontală.Limbajul Java – fire de execuție (3)

90 public class Ball extends Thread {
private int px = 0; //pozitia x private int py = 0; //pozitia y private int size = 0; private Color color = null; private MyFrame parent = null; public Ball(MyFrame parent, int px, int py, int size, Colo r color) {
this.parent = parent; //referinta la fereastra this.px = px; this.py = py; this.size = size; this.color = color;
} public int getPX(){
return px;
} public int getPY(){
return py;
} public int getSize(){
return size;
} public Color getColor(){
return color;
} public void run(){
while(px < parent.getSize().width){ //iesire din fereastra
px++; parent.paint();
}
}
}Limbajul Java – fire de execuție (4)

91 public class MyFrame extends Frame {
Ball ball = null; Image buffer = null; public MyFrame() {
this.setSize(new Dimension(400, 300)); this.setTitle("Balls"); this.addWindowListener(new java.awt.event.WindowAdapt er() { //detectia evenimentului de inchidere a ferestrei
public void windowClosing(WindowEvent e) {
this_windowClosing(e);
}
}); setVisible(true); buffer = createImage(getSize().width, getSize().height) ;
ball = new Ball(this, 20, 50, 20, Color.red); ball.start();
}void paint(){
Graphics gbuffer = buffer.getGraphics();
//se deseneaza mai intai in buffer (tehnica Double Buffe ring)
gbuffer.setColor(Color.white); gbuffer.fillRect(0, 0, getSize().width, getSize().height);gbuffer.setColor(ball.getColor()); gbuffer.fillOval(ball.getPX(), ball.getPY(), ball.getSize(), b all.getSize());
paint(gbuffer);
//se copiaza imaginea din buffer pe fereastra (tehnica D ouble Buffering)
Graphics g = getGraphics(); g.drawImage(buffer, 0, 0, getSize().width, getSize(). height, 0, 0, getSize().width, getSize().height, this);
}void this_windowClosing(WindowEvent e) { //evenimentul de inc hidere a ferestrei
System.exit(0);
}public static void main(String[] args){
new MyFrame();
}
}Limbajul Java – fire de execuție (5)

92 Sincronizarea firelor de execuție
/square6Dacă în cadrul unui program Java există un fir de execuție care creează (produce) date și un al doilea fir de execuție care le prelucrează (consumă), de regulă se declară un bloc synchronized , ceea ce
permite ca un singur fir să aibă acces la resurse (metode, date) la un moment dat.
/square6Atunci când un fir de execuție apelează wait în cadrul
unui bloc de cod synchronized , alt fir poate accesa
codul.
/square6Iar atunci când un fir de execuție încheie procesarea codului synchronized , el apelează metoda notify
pentru a anunța alte fire de execuție să înceteze așteptarea.
/square6Reluăm în continuare aplicația care afișează numere
și litere sincronizând cele două fire de execuție. Limbajul Java – fire de execuție (6)

93 public class Numbers extends Thread {
Main m; public Numbers(Main m){
this.m = m;
}public void run(){
m.numbers();
}
} public class Letters implements Runnable {
Main m; public Letters(Main m){
this.m = m;
}public void run(){
m.letters();
}
} public class Main {
public Main(){
Numbers numbers = new Numbers(this);
Thread letters = new Thread(new Letters(this));
letters.start(); numbers.start();
}Limbajul Java – fire de execuție (7)
public synchronized void numbers(){
for(int i=0; i<1000; i++){
if(i%26==0){ try {
this.notify(); this.wait();
}
catch (InterruptedException ex) { }
}System.out.println(i);
}this.notify();
}
public synchronized void letters(){
char a = 'a'; for(int i=0; i<1000; i++){
if(i%26==0){
try {
this.notify(); this.wait();
}
catch (InterruptedException ex) { }
}int c = a + i%26; System.out.println((char)c);
}
this.notify();
} public static void main(String[] args) {
new Main();
}
}

94 Aplicații propuse:
1. Introducerea unei întârzieri de 10 ms în algoritm ul de mișcare a bilei din aplicația prezentată.
2. Modificarea aplicației astfel încât să permită po rnirea mai multor mingi simultan.
3. Să se înlocuiască algoritmul de deplasare a mingi i pe orizontală cu următorul algoritm de mișcare:
dx = 1; dy = 1; while (true){
px += dx; py += dy; if((px <= 0) || (px >= frame_width))
dx = Sdx;
if((py <= 0) || (py >= frame_height))
dy = Sdy;
paint();
}
Un alt algoritm de mișcare:
gravy = 1; speed = S30 speedy = S30; speedx = 0; while(true){
speedy += gravy; py += speedy; px += speedx;if(py > frameheight){
speedy = speed; speed += 3;
}if(speed == 0) break; paint();
}Limbajul Java – fire de execuție (8)

95 O colecție grupează date întrSun singur obiect și p ermite manipularea acestora.
Clasele Vector și ArrayList
/square6Permit implementarea listelor redimensionabile cu e lemente referință de orice
tip, inclusiv null .
/square6O diferență importantă: Vector este sincronizat, iar ArrayList este nesincronizat,
ceea ceSl face mai rapid. Dacă un ArrayList este accesat și modificat de mai
multe fire de execuție concurențial, necesită sincr onizare externă (a obiectului
care încapsulează lista). O altă soluție constă în crearea unei instanțe
sincronizate, prevenind astfel eventualele accese n esincronizate:
List list = Collections.synchronizedList(new ArrayL ist(…));
/square6Clasa Vector sSa păstrat pentru compatibilitate cu versiuni JDK mai vechi de 1.2.
/square6Exemple
Vector vector = new Vector(); //vector gol
vector.addElement(new Integer(1)); //vector = {1} vector.add(new Integer(3)); //vector = {1, 3} vector.insertElementAt(new Integer(5), 1); //vector = {1, 5, 3}
vector.setElementAt(new Integer(2), 1); //vector = {1, 2, 3}
ArrayList list = new ArrayList(); //lista goala
list.add(new Integer(1)); //list = {1} list.add(new Integer(3)); //list = {1, 3} list.add(1, new Integer(5)); //list = {1, 5, 3} list.set(1, new Integer(2)); //list = {1, 2, 3} Limbajul Java – colecții (1)

/square6Începând cu versiunea JDK 1.8, listele au metodă sort . În exemplul următor
criteriul de sortare este furnizat printrSo expresie lamb da. Afișarea poate fi și ea
realizată cu ajutorul unei expresii lambda, apelând meto da forEach a listei,
disponibilă tot de la JDK 1.8.
public class Person{
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
}
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add(new Person("Popescu", 103)); list.add(new Person("Ionescu", 98)); list.add(new Person("Petrescu", 49));
list.sort((o1,o2)S>((Person)o1).name.compareTo(((Pe rson)o2).name));
//{IonescuS98, PetrescuS49, PopescuS103}
list.forEach((o)S>System.out.println(((Person)o).na me+" "+((Person)o).age));
}
}Limbajul Java – colecții (2)

/square6Pentru evitarea conversiei repetate din Object în Person, la crearea colecției se
poate preciza tipul componentelor. Astfel, exemplul anterior sSar rescrie în felul
următor:
public class Person{
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
}
public static void main(String[] args) {
ArrayList<Person> list = new ArrayList(); //ArrayList<Person> list = new ArrayList<Person>();
list.add(new Person("Popescu", 103)); list.add(new Person("Ionescu", 98)); list.add(new Person("Petrescu", 49)); list.sort((o1,o2)S>o1.name.compareTo(o2.name));
//{IonescuS98, PetrescuS49, PopescuS103}
list.forEach((o)S>System.out.println(o.name+" "+o.a ge));
}
}Limbajul Java – colecții (3)

98 Clasa Stack
/square6Permite implementarea sincronizată a stivelor
/square6Extinde clasa Vector cu operațiile specifice stivei :
/square6push – introduce un element în vârful stivei;
/square6pop – scoate elementul din vârful stivei;
/square6peek – preia (citește) elementul din vârful stivei, fără săSl scoată;
/square6empty – verifică dacă stiva e goală;
/square6search – returnează poziția unui obiect din stivă f ață de vârf.
/square6Exemple:
Stack stack = new Stack(); //stiva goala System.out.println(stack.empty()); //true
stack.push(new Integer(1)); //stack = {1} stack.push(new Integer(2)); //stack = {1, 2} stack.push(new Integer(3)); //stack = {1, 2, 3}
System.out.println(stack.search(new Integer(3))); //1System.out.println(stack.search(new Integer(2))); //2System.out.println(stack.empty()); //false System.out.println(stack.pop()); //3, stack = {1, 2 }
System.out.println(stack.peek()); //2, stack = {1, 2}
System.out.println(stack.pop()); //2, stack = {1} System.out.println(stack.pop()); //1, stiva goala System.out.println(stack.empty()); //true Limbajul Java – colecții (4)

99 Clasa LinkedList
/square6Permite implementarea stivelor și a cozilor.
/square6Diferența față de Stack: LinkedList este nesincroni zat (deci mai rapid). Nefiind
sincronizat, LinkedList necesită sincronizare exter nă în caz de accesare
concurențială multifir.
/square6Exemple:
LinkedList stack = new LinkedList(); //stiva goala stack.addLast(new Integer(1)); //stack = {1} stack.addLast(new Integer(2)); //stack = {1, 2} stack.addLast(new Integer(3)); //stack = {1, 2, 3}
System.out.println(stack.removeLast()); //3, stack = {1, 2}
System.out.println(stack.getLast()); //2, stack = { 1, 2}
System.out.println(stack.removeLast()); //2, stack = {1}
System.out.println(stack.removeLast()); //1, stiva goala
LinkedList queue = new LinkedList(); //coada goala
queue.addFirst(new Integer (1)); //queue = {1} queue.addFirst(new Integer(2)); //queue = {2, 1} queue.addFirst(new Integer(3)); //queue = {3, 2, 1} System.out.println(queue.removeLast()); //1, queue = {3, 2}
System.out.println(queue.removeLast()); //2, queue = {3}
System.out.println(queue.removeLast()); //3, coada goala Limbajul Java – colecții (5)

100 Clasele HashSet, TreeSet și LinkedHashSet
/square6Interfața Set permite folosirea mulțimilor – colecți i de date în care elementele
sunt unice.
/square6Clasa HashSet păstrează elementele adăugate în ordinea stabilită de o funcție
de dispersie, asigurând astfel operații de introduc ere și preluare a unui element
rapide, de complexitate O(1). Funcția de dispersie poate fi schimbată prin
redefinirea metodei hashCode() .
/square6Clasa TreeSet păstrează elementele sortate în ordine crescătoare , ceea ce
determină operații de introducere și preluare a unu i element mai lente, de
complexitate O(log n).
/square6Clasa LinkedHashSet (disponibilă începând cu versiunea JDK 1.4) păstre ază
elementele în ordinea în care au fost introduse asi gurând operații de accesare a
unui element de complexitate O(1).
/square6Exemple
/square6HashSet hs = new HashSet(); //hs = {}
/square6hs.add(new Integer(1)); //hs = {1}
/square6hs.add(new Integer(2)); //hs = {2, 1}
/square6hs.add(new Integer(4)); //hs = {2, 4, 1}
/square6hs.add(new Integer(2)); //hs = {2, 4, 1}
/square6TreeSet ts = new TreeSet(hs); //ts = {1, 2, 4}
/square6ts.add(new Integer(3)); //ts = {1, 2, 3, 4}
/square6LinkedHashSet lhs = new LinkedHashSet(); //lhs = { }
/square6lhs.add(new Integer(1)); //lhs = {1}
/square6lhs.add(new Integer(2)); //lhs = {1, 2}
/square6lhs.add(new Integer(4)); //lhs = {1, 2, 4}
/square6lhs.add(new Integer(3)); //lhs = {1, 2, 4, 3} Limbajul Java – colecții (6)

101 Implementarea interfeței Comparable pentru
obiectele încărcate în TreeSet
/square6Obiectele încărcate în TreeSet sunt sortate prin in termediul funcției compareTo. De
aceea, clasa obiectelor încărcate trebuie să implem enteze interfața Comparable.
/square6Proprietatea de set (mulțime) se aplică câmpului du pă care se face comparația în
compareTo . Dacă valoarea acelui câmp este aceeași în două ob iecte, chiar dacă celelalte
câmpuri diferă, în set rămâne doar unul din obiecte . De aceea, dacă în compareTo
valorile câmpului comparat sunt egale se poate ține cont de celelalte câmpuri, aplicând
astfel proprietatea de set pe întregul obiect.
/square6Exemplu:
public class Person implements Comparable{
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
} public int compareTo(Object p){
return this.name.compareTo(((Person)p).name);
}public static void main(String[] args) {
TreeSet ts = new TreeSet();
ts.add(new Person("Popescu", 103));
//{PopescuS103}
ts.add(new Person("Ionescu", 98));
//{IonescuS98, PopescuS103}
ts.add(new Person("Petrescu", 49));
//{IonescuS98, PetrescuS49, PopescuS103}
}
}Limbajul Java – colecții (7)

/square6Criteriul de comparație poate fi furnizat și printrSo exp resie lambda, caz
în care clasa Person nu mai trebuie să implementeze interf ața
Comparable :
public class Person{
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
}public static Comparator alphabeticNames = (p1,p2) S> {
return ((Person)p1).name.compareTo(((Person)p2).nam e);
}; public static void main(String[] args) {
TreeSet ts = new TreeSet(Person.alphabeticNames);
ts.add(new Person("Popescu", 103)); ts.add(new Person("Ionescu", 98)); ts.add(new Person("Petrescu", 49));
}
}Limbajul Java – colecții (8)

/square6Conținutul colecției ts de tip TreeSet din aplicația prezentată mai sus,
se poate afișa printrSo buclă for îmbunătățită, disponibilă începând cu
JDK 1.5:
TreeSet<Person> ts = new TreeSet(Person.alphabeticN ames);
ts.add(new Person("Popescu", 103)); ts.add(new Person("Ionescu", 98)); ts.add(new Person("Petrescu", 49));
//{IonescuS98, PetrescuS49, PopescuS103}
for(Person o: ts)
System.out.println(o.name + " " + o.age);
/square6O altă variantă de afișare a conținutului colecției cons tă în apelul
metodei forEach (disponibilă începând cu JDK 1.8), cu o expresie
lambda:
TreeSet<Person> ts = new TreeSet(Person.alphabeticN ames);
ts.add(new Person("Popescu", 103)); ts.add(new Person("Ionescu", 98)); ts.add(new Person("Petrescu", 49));
//{IonescuS98, PetrescuS49, PopescuS103}
ts.forEach((o)S>System.out.println(o.name + " " + o. age)); Limbajul Java – colecții (9)

Iteratori
/square6Iteratorii permit traversarea în ordine a colecțiil or de date.
/square6Exemplul 1 (aplicația anterioară):
TreeSet<Person> ts = new TreeSet(Person.alphabeticN ames);
ts.add(new Person("Popescu", 103)); ts.add(new Person("Ionescu", 98)); ts.add(new Person("Petrescu", 49));
//{IonescuS98, PetrescuS49, PopescuS103}
Iterator<Person> i = ts.iterator(); while(i.hasNext()){
Person o = i.next();
System.out.println(o.name + " " + o.age);
}
/square6Exemplul 2 (colecție de tip String):
TreeSet ts = new TreeSet();
ts.add("Romania"); ts.add("Anglia"); ts.add("Germania"); ts.add("Franta"); Iterator i = ts.iterator(); while(i.hasNext()) System.out.println(i.next()); //{A nglia, Franta, Germania, Romania} Limbajul Java – colecții (10)

105 Clasele HashMap, TreeMap și LinkedHashMap
/square6Interfața Map permite păstrarea de perechi cheieSva loare, ambele de tip
referință, cu chei unice. Principalele operații:
/square6put(k, v) – asociază cheii k valoarea v. Dacă exist ă deja cheia k atunci
vechea valoare se înlocuiește cu v.
/square6get(k) – returnează valoarea corespunzătoare cheii k.
/square6Clasa HashMap păstrează cheile în ordinea stabilită de o funcție de dispersie
asigurând astfel accesări rapide, de complexitate O (1).
/square6Clasa TreeMap păstrează cheile ordonate crescător, accesarea fii nd astfel mai
lentă, de complexitate O(log n).
/square6Clasa LinkedHashMap (disponibilă începând cu JDK 1.4) păstrează cheile în
ordinea în care au fost introduse asigurând accesăr i de complexitate O(1).
/square6Exemple
/square6HashMap hm = new HashMap();
/square6hm.put("Romania", "Bucuresti");
/square6hm.put("Franta", "Paris");
/square6hm.put("Germania", "Bonn");
/square6hm.put("Germania", "Berlin");
/square6System.out.println(hm); //{Romania=Bucuresti, Germa nia=Berlin, Franta=Paris}
/square6System.out.println(hm.get("Germania")); //Berlin
/square6TreeMap tm = new TreeMap(hm);
/square6System.out.println(tm); //{Franta=Paris, Germania=B erlin, Romania=Bucuresti}
/square6LinkedHashMap lhm = new LinkedHashMap();
/square6lhm.put("Romania", "Bucuresti");
/square6lhm.put("Franta", "Paris");
/square6lhm.put("Germania", "Berlin");
/square6System.out.println(lhm); //{Romania=Bucuresti, Fran ta=Paris, Germania=Berlin} Limbajul Java – colecții (11)

106 Implementarea interfeței Comparable pentru
cheile încărcate în TreeMap
/square6Perechile cheieSvaloare încărcate în TreeMap sunt s ortate în ordinea crescătoare a cheilor,
prin intermediul funcției compareTo. De aceea, clasa obiectelor cheie trebuie să
implementeze interfața Comparable. Exemplu:
public class Person implements Comparable{
private String name; private int age; public Person(String name, int age) {
this.name = name; this.age = age;
} public int compareTo(Object p){
return this.name.compareTo(((Person)p).name);
} public static void main(String[] args) {
TreeMap tm = new TreeMap();
tm.put(new Person("Pop", 54), "Romania"); //tm={PopS 54SRomania}
tm.put(new Person("Brown", 98), "Anglia"); //tm={BrownS98SAnglia, PopS54SRomania}
tm.put(new Person("Schmitt", 49), "Germania"); //tm={BrownS98SAnglia, PopS54SRomania, SchmittS49SG ermania}
}
}Limbajul Java – colecții (12)

/square6Pentru evitarea conversiei repetate a cheilor din Object în Person respectiv a
valorilor din Object în String, la crearea colecției se poate preciza tipul cheilor și
a valorilor. Astfel, exemplul anterior, cu afișarea inclusă, sSar rescrie în felul
următor:
TreeMap<Person, String> tm = new TreeMap(); //TreeMap<Person, String> tm = new TreeMap<Person, String>();
Person p = new Person("Pop", 54); tm.put(p, "Romania");
//tm={PopS54SRomania}
Person q = new Person("Brown", 98); tm.put(q, "Anglia");
//tm={BrownS98SAnglia, PopS54SRomania}
Person r = new Person("Schmitt", 49); tm.put(r, "Germania");
//tm={BrownS98SAnglia, PopS54SRomania, SchmittS49SGe rmania}
for(Map.Entry<Person,String> entry : tm.entrySet()) {
Person k = entry.getKey(); String v = entry.getValue(); System.out.println(k.getName()+ "S" +k.getAge()+ "S " +v);
}Limbajul Java – colecții (13)

108 Aplicații propuse
1. Să se modifice programele prezentate la TreeSet ș i TreeMap astfel încât sortarea
persoanelor să se facă după vârstă în cazul în care au același nume.
2. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișați cursul cu cel mai mic număr de credite.
3. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișați cursul cu cel mai mare număr de credite.
4. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișațiSle în ordinea descrescătoare a numărului de c redite.
5. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișațiSle în ordinea crescătoare a anului de studiu .
6. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișațiSle în ordinea alfabetică a titlului.
7. Definiți clasa Course cu câmpurile title , teacher (profesor), credits (nr. credite) și
year (an de studiu). Introduceți de la tastatură cinci obie cte de tip Course întrSun
TreeSet și afișațiSle în ordinea alfabetică a profesorului.Limbajul Java – colecții (14)

109 Test (T) susținut la laborator din aplicațiile
propuse la laborator în cadrul capitolului Limbajul Java – se va implementa și rula pe
calculator o aplicație care implică o moștenire respectiv folosirea unor colecții de date. Limbajul Java – test

Partea II
Analiza algoritmilor

111 Analiza algoritmilor
/square6Algoritmul este o secvență de operații care transformă mulțimea datelor de intrare în datele de
ieșire.
/square6Analiza algoritmului se referă la evaluarea
performanțelor acestuia (timp de execuție, spațiu d e
memorie). Scopul este acela de a găsi algoritmul ce l
mai eficient pentru o anumită problemă.
/square6La analiza algoritmilor trebuie avut în vedere mode lul
de implementare (secvențială, paralelă) și arhitect ura
mașinii de calcul (superscalar, multithreading, multicore) respectiv dacă aceasta permite sau nu execuția speculativă a instrucțiunilor.

112 /square6Conjectura ChurchSTuring postulează că pentru orice algoritm
există o mașină Turing echivalentă. Cu alte cuvinte , nicio
procedură de calcul nu este algoritm dacă nu poate fi executată
de o mașină Turing. În esență, mașina Turing reprez intă ceea
ce astăzi numim algoritm. Așadar, o mașină Turing e ste
echivalentă cu noțiunea de algoritm.
/square6O mașină Turing constă din:
/square6O bandă împărțită în celule, fiecare conținând un s imbol (inclusiv
cel vid) dintrSun alfabet finit.
/square6Un cap care poate scrie și citi și care se poate de plasa la stânga
sau la dreapta.
/square6Un registru de stare care stochează starea mașinii Turing. Numărul
stărilor este finit și există o stare inițială.
/square6O funcție de tranziție (tabelă de acțiuni) care, în funcție de starea
curentă și simbolul citit, determină ce simbol să s e scrie, cum să se
deplaseze capul (la stânga sau la dreapta) și care va fi noua stare.
/square6Mașina Turing se oprește dacă se ajunge întrSo star e finală sau
dacă nu există combinația de simbolSstare în tabela de acțiuni. Analiza algoritmilor – mașina Turing

113 /square6Complexitatea unui algoritm, exprimată în funcție d e dimensiunea
datelor de intrare ( n), are următoarele componente:
/square6Complexitate temporală – numărul de operații necesa re pentru rezolvarea
unei probleme
/square6Complexitate spațială – spațiul de memorie utilizat
/square6Complexitatea temporală este indicatorul principal al performanței unui
algoritm.
/square6Complexitatea temporală a unui algoritm poate fi de terminată
experimental (prin măsurarea timpului de rulare) sa u prin analiză
teoretică (prin aproximarea numărului de operații p rimitive).
/square6Complexitatea unui algoritm este de regulă exprimat ă (aproximată) prin
notații asimptotice [Cor00] care rețin doar termenul dominant al
expresiei, ceilalți termeni devenind neglijabili pe ntru valori mari ale lui n.
Exemple:
/square6Dacă execuția unui algoritm necesită 2n+n 5+8 operații, atunci complexitatea
temporală este 2n;
/square6Un algoritm cu 7n 4+10n 2+1000n operații elementare are complexitate n 4.Analiza algoritmilor – complexitate (1)

114 Analiza algoritmilor – complexitate (2)
Θânotația
}),()()(0. .0,,)({))((0 2 1 021 nn ngc nf ngc î a ncc nf ng ≥∀ ⋅≤ ≤ ⋅≤ > ∃ = Θ
ΘSnotația delimitează o funcție asimptotic inferior și
superior, g(n) este o margine asimptotic tare pentr u f(n). nf(n) c2g(n)
c1g(n)
n0

115 OSnotația delimitează o funcție asimptotic superior ,
g(n) este o margine asimptotică superioară.Analiza algoritmilor – complexitate (3)
Oânotația
nf(n) c g(n)
n0}),()(0 . .0,)({))((0 0 nn ngcnf î a nc nf ngO ≥∀ ⋅≤ ≤ > ∃ =

116 ΩSnotația delimitează o funcție asimptotic inferior ,
g(n) este o margine asimptotică inferioară.Analiza algoritmilor – complexitate (4)
Ωânotația
}),()(0. .0,)({))((0 0 nn nf ngc î a nc nf ng ≥∀ ≤ ⋅≤ > ∃ = Ω
nn0f(n)
c g(n)

117 /square6oânotația: Delimitarea asimptotică superioară dată de notația O
poate sau nu să fie o delimitare asimptotic strânsă . De exemplu,
2n 2=O(n 2) este o delimitare asimptotic strânsă, pe când 2n 2=O(n 3)
nu este. Vom folosi oSnotația pentru a desemna o de limitare
superioară care nu este asimptotic strânsă: 2n 2=o(n 3).
/square6ωânotația desemnează o delimitare asimptotică inferioară car e nu
este asimptotic strânsă: 2n 2=ω(n).
/square6Teoremă: Pentru orice două funcții f(n) și g(n), avem f(n)= Θ(g(n))
dacă și numai dacă f(n)=O(g(n)) și f(n)=Ω(g(n)).
/square6Convenție: În orice ecuație în care se folosesc notații asimpt otice
membrul drept oferă un nivel de detaliu mai scăzut decât membrul
stâng. Exemplu: 2n 2+3n+1 = 2n 2+Θ(n) = Θ(n 2). Putem scrie
2n 2+3n+1 = Θ(n 2), dar nu scriem niciodată Θ(n 2) = 2n 2+3n+1 .Analiza algoritmilor – complexitate (5)
}),()(0. .0, 0)({))((0 0 nn ngcnf î a n c nf ngo ≥∀ ⋅< ≤ >∃>∀ =
}),()(0. .0, 0)({))((0 0 nn nf ngc î a n c nf ng ≥∀ < ⋅≤ >∃>∀ =
ω

118 Alte exemple [Knu00]
/square6Știm că
/square6Rezultă că
/square6Ecuația (2) este destul de nerafinată, dar nu incor ectă; ecuația
(3) este mai puternică, iar ecuația (4) și mai pute rnică.Analiza algoritmilor – complexitate (6)
) 1 (61
21
31
6) 12)(1(…2123 2 22n n nn nnn + + =+ += ++ +
) 4 ( )(31…21) 3 ( )(…21) 2 ( )(…21
232 2232 2242 22
nO n nnO nnO n
+ = ++ += ++ += ++ +

119 Analiza algoritmilor – complexitate (7)
Ordinul de complexitate
Constantă O(1) Logaritmică O(log n) Liniară O(n) Liniar logaritmică O(n log n) Pătratică O(n
2)
Polinomială (p>2) O(n p)
Exponențială O(a n)

120 Exprimați următoarele complexități cu ajutorul notației Θ:Analiza algoritmilor – complexitate (8)
2 223 332 22222 3
) 12 (…31)10) 1(…3221) 9…21) 8…21) 7…21) 6ln ) 5ln2) 424) 3352) 2100) 1
− ++ ++⋅++⋅+⋅++ +++ ++++⋅ ++⋅+⋅⋅++ ++
nnnnnnn nn nn n nnnn n
k knn
n

121 /square6Vom utiliza următoarele notații:
/square6Deoarece schimbarea bazei unui logaritm de la o constantă la alta schimbă valoarea logaritmului doa r
printrSun factor constant, vom folosi notația lgn
atunci când factorii constanți nu vor fi importanți . Analiza algoritmilor – logaritmi (1)
)lg(lglglg)(lglgloglnloglg2
n nn nn nn n
k ke
====

122 Pentru orice numere reale a>0, b>0, c>0 și n, Analiza algoritmilor – logaritmi (2)
a nb bb b bc b ba babcc
bbn
bc c ca
b bb
n aaaa caca c ab ababaaa n ab a abba
log loglog
log1logloglogloglogloglog1logloglog1loglogloglogloglogloglog)(log
=−=− =⋅ == ⋅===+ ==

123 O recurență este o ecuație care descrie o funcție e xprimând valoarea sa pentru
argumente mai mici. Când un algoritm conține o apel are recursivă la el însuși,
timpul său de execuție poate fi descris printrSo re curență. Recurențele pot fi
rezolvate prin metoda substituției, metoda iterație i sau metoda master [Cor00].
Metoda master oferă o soluție simplă pentru rezolvarea recurențe lor de forma:
unde a≥1, b>1, iar f(n) este o funcție dată.Teorema master. Fie a≥1 și b>1 constante, f(n) o funcție și T(n) de finită pe
întregii nenegativi prin recurența atunci T(n) poate fi delimitată asimptotic după cum urmează:Analiza algoritmilor – recurențe (1)
)( )( nfbnTa nT +⋅=
)( )( nfbnTa nT +⋅=
)).(()( 1),( 0),()(. 3)lg()()()(. 2)()(0),()(. 1
loglog loglog log
nf nT maride suficientnși cncfbnafși n nf dacăn n nT n nf dacăn nT nO nf dacă
aa aa a
bb bb b
Θ= ⇒ < ≤> Ω=Θ= ⇒ Θ=Θ= ⇒> =
+−ε ε
ε ε

124 Exemplu de utilizare a metodei master
Să considerăm Pentru această recurență a=9, b=3, f(n)=n, astfel Deoarece aplicând cazul 1 al teoremei master, Analiza algoritmilor – recurențe (2)
nnT nT +⋅=39)(
29log log3n n nab= =
, 1),()()(9log3= = =−ε
εnO nO nf
)()()(2 9log3n n nT Θ= Θ=

125 Exemplu de neaplicabilitate a metodei master
Să considerăm următoarea recurență: Pentru această recurență a=2, b=2, f(n)=nlgn. Astfe l,
Se poate observa că niciunul din cazurile teoremei master
nu se poate aplica:
Vom folosi în continuare metoda iterației pentru re zolvarea
acestei recurențe. Analiza algoritmilor – recurențe (3)
nn nT nT lg) 2 /(2)( + =
)lg,01. 0.(0),(lg. 3)(lg. 20),(lg. 1
01. 1 11
nn n ex n nnn nnnOnn
> = >∀ Ω≠Θ≠>∀ ≠
+−ε
ε ε
ε εn n n nab= = =12log log2

126 Rezolvare prin metoda iterației a recurenței
Iterăm recurența după cum urmează: Considerând condiția la limită T(1)=Θ(1), recurența se termină pentru Analiza algoritmilor – recurențe (4)
nn nT nT lg) 2 /(2)( + =
1 112 33
2232
2222
2lg22222lg222lg2222222lg222lg2222222lg22)(
− −−+=+=
+=+=
 
 
+
 
 
=+=
q qq
qq nnnTnTnnnTn n nTnTnnnTnnn
TnTnnnT nT
n q nnq
qlg 212= ⇒= ⇒=

127 Am arătat că la limita T(1)=Θ(1), q=lg n. Obținem: Analiza algoritmilor – recurențe (5)
( )
( ) nn nTn n nnnn nTn nknnkk nn n n nTnn n n n nTn n nTnn T nT
n
kn
kn
kn
kkn
kk nn
kkn
221lg
01
01lg
02 11lg
02lg1lg
0lg1lg
0lg
lg)(2) 1(lglglg)(2) 1(lglg
2) 1(lg) 1 ()(2lglglg) 1 ()(2lglg) 1 (2)(2lg) 1 (2)(
Θ= − ⋅ ⋅− + Θ=− ⋅= ⇒−=− ⋅+ Θ⋅ =− ⋅ ⋅+ Θ =− + Θ =+ =
∑ ∑∑∑∑∑
−
=−
=−
=−
=−
=−
=

128 Exerciții. Dați o delimitare asimptotică strânsă
pentru următoarele recurențe:
1) T(n) = T(2n/3) + 1 2) T(n) = 3T(n/4) + n lg n 3) T(n) = 3T(n/3) + n/2 4) T(n) = 2T(n/2) + n 5) T(n) = 16T(n/4) + n 6) T(n) = 4T(n/2) + n
2
7) T(n) = 4T(n/2) + n 3Analiza algoritmilor – recurențe (6)

129 /square6Principalele tipuri de analiză
/square6Analiza cazului cel mai favorabil – cel mai scurt
timp de execuție posibil pe date de intrare de dimensiune constantă n;
/square6Analiza cazului cel mai defavorabil – cel mai mare
timp de execuție posibil relativ la orice date de intrare de dimensiune constantă n;
/square6Analiza cazului mediu – timpul mediu de execuție
al unui algoritm considerând toate datele de intrare de dimensiune constantă n. Există însă
probleme la care nu e prea clar care sunt datele de intrare de complexitate medie.
/square6Urmează câteva exemple de analiză a unor algoritmi: căutare, sortare, etc. Analiza algoritmilor – tipuri de analiză

130 Analiza algoritmilor – căutarea maximului (1)
Se dă un tablou X de n elemente. Să se găsească mastfel încât
m = max 1≤k≤nX[k], considerând cel mai mare indice k care
satisface această relație. 1. k /barb2leftnS1, m /barb2leftX[n].
2. Dacă k=0, algoritmul se încheie.
3. Dacă X[k]≤m, mergeți la pasul 5.
4. m /barb2leftX[k].
5. Decrementați k cu 1 și reveniți la pasul 2.
Pentru ca analiza să fie completă trebuie să determinăm mărimea A, care reprezintă numărul de modificări ale valorii maxime curente. Pasul Cost Nr. execuții 1. c1 12. c2 n3. c3 nS14. c4 A5. c5 nS1

131 Analiza algoritmilor – căutarea maximului (2)
Determinarea mărimii A
/square6Cazul cel mai favorabil: A=0, se obține atunci când
maximul este X[n];
/square6Cazul cel mai defavorabil: A=nS1, se obține atunci când maximul este X[1];
/square6Cazul mediu: presupunând că cele n valori sunt distincte, contează doar ordinea lor relativă. Dacă
n=3, există următoarele posibilități echiprobabile:
Situație AX[1]>X[2]>X[3] 2X[1]>X[3]>X[2] 1X[2]>X[1]>X[3] 1X[2]>X[3]>X[1] 1X[3]>X[1]>X[2] 0X[3]>X[2]>X[1] 0

132 Determinarea valorii A pentru cazul mediu
/square6Probabilitatea ca A să aibă valoarea kva fi
pnk =(nr. situații în care A=k )/n!
/square6În exemplul anterior p 30 =1/3, p 31 =1/2, p 32 =1/6
/square6Valoarea medie a lui A este definită astfel: An reprezintă de fapt media ponderată a valorilor lui A.
/square6În exemplul anterior valoarea medie a lui Apentru n=3
va fi 5/6. Knuth arată că pentru nmare An=ln n.Analiza algoritmilor – căutarea maximului (3)
∑ ⋅ =
knk n pk A

133 Determinarea complexității
/square6Cazul cel mai favorabil: c
1+ c 2n + c 3(nS1) + 0 + c 5(nS1) =
(c 2+c 3+c 5)n + (c 1Sc3Sc5) = an+b = Θ(n)
/square6Cazul cel mai defavorabil: c
1+ c 2n + c 3(nS1) + c 4(nS1) + c 5(nS1) =
(c 2+c 3+c 4+c 5)n + (c 1Sc3Sc4Sc5) = an+b = Θ(n)
/square6Cazul mediu: c
1+ c 2n + c 3(nS1) + c 4ln n + c 5(nS1) =
(c 2+c 3+c 5)n + c 4ln n + (c 1Sc3Sc5) = an + b ln n + c = Θ(n) Analiza algoritmilor – căutarea maximului (4)

134 Punând problema mai simplu,
Cost Execuții
m /barb2leftX[n] c1 1
for k /barb2leftnS1 downto 1 do c2 n
if X[k]>m then m /barb2leftX[k] c3 nS1
considerând operație elementară fiecare iterație a ciclului, e
ușor de observat că bucla este parcursă în întregim e, deci
algoritmul are aceeași complexitate
(c 2+c 3)n + (c 1Sc3) = an+b = Θ(n)
indiferent de ordinea relativă a celor nvalori. Analiza algoritmilor – căutarea maximului (5)

135 Se dă un tablou X de n elemente. Se parcurge secven țial tabloul X până la primul element care
are valoarea k.
Cost Execuții
1. i /barb2left1. c1 1
2. Dacă X[i] = k, algoritmul se încheie cu succes. c2 C
3. i /barb2lefti+1. c3 CSS
4. Dacă i≤n se revine la pasul 2. c4 CSS
În caz contrar, algoritmul se încheie fără succes.
unde C este numărul de comparații de chei și S este 1 în caz de succes respectiv 0 în caz de
căutare fără succes. Complexitatea algoritmului est e:
c1+ c 2C + c 3(CSS) + c 4(CSS)
În cazul în care valoarea nu este găsită, avem C=n, S=0, cu o complexitate
(c 2+c 3+c 4)n + c 1= an+b = Θ(n)
În caz de succes, cu X[i]=k, avem C=i, S=1, cu o co mplexitate
(c 2+c 3+c 4)i + (c 1Sc3Sc4)
Considerând că valorile din tablou sunt distincte ș i echiprobabile, valoarea medie a lui C este
deci complexitatea în cazul mediu este tot Θ(n). Analiza algoritmilor – căutarea secvențială (1)
21…21 +=+++ n
nn

/square6Punând problema mai simplu, algoritmul arată în fel ul
următor:
CAUTARE_SECV(X, k)
for i /barb2left1 to n do
if x[i] = k then
return i
return 0
/square6Algoritmul constă în execuția unei bucle: o singura iterație în cazul cel mai favorabil, niterații în cazul cel
mai defavorabil, respectiv (1+2+…+n)/n = (n+1)/2
iterații în cazul mediu. Așadar, complexitatea este Θ(1) în cazul cel mai favorabil, Θ(n) în cazul cel mai defavorabil și tot Θ(n) în cazul mediu. Analiza algoritmilor – căutarea secvențială (2)

137 Se dă un tablou X de n elemente ordonate crescător. Valoarea căutată k
se compară cu elementul din mijlocul tabloului, iar rezultatul acestei
comparații ne arată în care jumătate trebuie contin uată căutarea.
Cost Execuții
1. s /barb2left1, d /barb2leftn c1 1
2. Dacă d<s alg. se încheie fără succes. c2 C+1SS
Altfel, i /barb2left(s+d)/2.
3. Dacă k<X[i] se trece la pasul 4. c3 C
Dacă k>X[i] se trece la pasul 5.
Dacă k=X[i] alg. se încheie cu succes. 4. d /barb2leftiS1 și se revine la pasul 2. c
45 CSS
5. s /barb2lefti+1 și se revine la pasul 2.
unde C este numărul de comparații de chei și S este 1 în caz de succes
respectiv 0 în caz de căutare fără succes. Complexi tatea algoritmului
este:
c1+ c 2(C+1SS) + c 3C + c 45 (CSS) Analiza algoritmilor – căutarea binară (1)

Rescris întrSo formă mai apropiată de limbajele de nivel î nalt, algoritmul
arată în felul următor:
CAUTARE_BINARA(X, k) Cost Execuții
st /barb2left1 c1 1
dr /barb2leftX.size c2 1
while st≤dr do c3 C
i /barb2left(st+dr)/2
if k=X[i] then
return i
if k<X[i] then
dr /barb2leftiS1
if k>X[i] then
st /barb2lefti+1
return 0 c4 1SS
Complexitatea algoritmului este:
c1 + c2 + c3C + c4(1SS)
Complexitatea temporală a algoritmului de căutare b inară depinde
astfel doar de numărul de comparații C. Analiza algoritmilor – căutarea binară (2)

139 Determinarea valorii C pentru cazul cel mai favorab il
Valoarea căutată este găsită la prima comparație, astfe l C=1, deci
complexitatea temporală este Θ(1).
Determinarea valorii C pentru cazul cel mai defavor abil
Valoarea maximă a lui C (numărul comparațiilor de c hei) poate fi
exprimată prin următoarea recurență care descrie înjumătățirea recurentă a spațiului de căutare cu un cost
constant Θ(1).
Aplicând terorema master, avem a=1 (căutarea se con tinuă pe o
singură ramură st./dr.), b=2 (spațiul de căutare se reduce la jumătate)
și f(n)=Θ(1). Astfel, deci putem aplica cazul 2 al teoremei master. Prin urmare,
Astfel, în cazul cel mai defavorabil, C=Θ(lg n) iar complexitatea
temporală este Θ(lg n). Analiza algoritmilor – căutarea binară (3)
) 1 (2)( Θ+=nTnT
101log log2= = = n n nab)(lg)lg()lg()(0 logn n n n n nTabΘ= Θ= Θ=

140 Determinarea valorii C pentru cazul mediu
Considerând că valorile din tablou sunt distincte ș i echiprobabile,
în cazul mediu valoarea căutată este găsită la jumă tatea
procesului de căutare, ceea ce în număr de iterații este echivalent
cu parcurgere totală dar divizarea recurentă a spaț iului de căutare
la un sfert:
Aplicând teorema master, avem a=1, b=4 și f(n)=Θ(1) . Astfel,
deci putem aplica cazul 2 al teoremei master. Prin urmare,
Astfel, în cazul mediu, la fel ca în cazul cel mai defavorabil,
C=Θ(lg n), deci complexitatea temporală este tot Θ(lg n). Analiza algoritmilor – căutarea binară (4)
) 1 (4)( Θ+=nT nT
101log log4= = = n n nab
)(lg)lg()lg()(0 logn n n n n nTabΘ= Θ= Θ=

141 Se dă un tablou X de n elemente. Se consideră pe râ nd vectorii formați
din primele 2, 3, …, n elemente din tablou, ordon ate prin aducerea noului
element (al 2Slea, al 3Slea, …, al nSlea) pe pozi ția corespunzătoare valorii
sale. Aceasta presupune deplasarea la dreapta a ele mentelor cu valori
mai mari, astfel încât noul element să poată fi ins erat înaintea lor:
Cost Execuții
for j /barb2left2 to n do c1 n
k /barb2leftX[j] c2 nS1
i /barb2leftjS1 c3 nS1
while i>0 and X[i]>k do c4
X[i+1] /barb2leftX[i] c5
i /barb2leftiS1 c6
X[i+1] /barb2leftk c7 nS1
unde am notat cu t j numărul de execuții ale testului while Analiza algoritmilor – sortare prin inserție (1)
sortat nesortat 1 n k
∑
=n
jjt
2
∑
=−n
jjt
2) 1(
∑
=−n
jjt
2) 1(

142 Determinarea complexității în cazul cel mai favorab il
/square6Vectorul de intrare este deja sortat, deci bucla while nu
se execută niciodată (se verifică doar condițiile o singură
dată în fiecare iterație for ), astfel t j=1, rezultă:
/square6 /square6
/square6Analiza algoritmilor – sortare prin inserție (2)
∑
=−=n
jjnt
21
0) 1(
2=−∑
=n
jjt
)( ) () () 1() 1() 1() 1(
7432743217 4 3 21
n ban ccccncccccnc nc nc ncnc
Θ=+ = +++ − ++++=− +− +− +− +

143 Determinarea complexității în cazul cel mai defavor abil
/square6Vectorul de intrare este sortat în ordine inversă, deci bucla while se
execută de 1, 2, …, nS1 ori (condițiile fiind ver ificate de 2, 3, …, n ori)
pentru j=2, 3, …,n, astfel t j=j,
/square6 /square6
/square6Analiza algoritmilor – sortare prin inserție (3)
∑ ∑
= =−+= =n
jn
jjnnj t
2 212) 1(
2) 1() 1(12) 1() 1(
2−=−−−+=−∑
=nnnnntn
jj
)() (222 222) 1(2) 1(
2) 1(12) 1() 1() 1(
2 27432 7654
32126547 6 5 4 3 21
n c bn anccccncc c cccc nc c cncnncnncnnc nc ncnc
Θ=+ += +++ −+ − − +++ ++ +=− +−⋅+−⋅+−++− +− +

144 Determinarea complexității în cazul mediu
/square6Să presupunem că alegem la întâmplare n numere dist incte și aplicăm
sortarea prin inserție.
/square6Câte iterații sunt necesare pentru inserarea elemen tului X[j] în
subvectorul X[1…jS1]? În medie jumătate din eleme ntele subvectorului
X[1…jS1] sunt mai mici decât X[j] și jumătate sun t mai mari. Prin
urmare, în medie, trebuie verificate jumătate din e lementele
subvectorului X[1…jS1], deci t j=j/2,
/square6 /square6
/square6Astfel, complexitatea în cazul mediu va fi tot Θ(n 2), la fel ca în cazul cel
mai defavorabil. Analiza algoritmilor – sortare prin inserție (4)
∑ ∑
= =−+=−+= ⋅=
n
jn
jjn n nnj t
22
2 4212) 1(
21
21
423) 1(42) 1(2 2
2+ −=−−−+=−∑
=n nnn ntn
jj

145 Se dă un tablou X de n elemente. Se consideră pe râ nd
subtablourile formate din elementele i, …, n (cu i=1, 2, …, n) și
se aduce prin interschimbare elementul minim al fie cărui
subtablou pe poziția i:
SELSORT1(X)
for i /barb2left1 to nS1 do
min /barb2lefti
for j /barb2lefti+1 to n do
if X[j] < X[min] then
min /barb2leftj
X[i] /barb2left/barb2right X[min] Analiza algoritmilor – sortare prin selecție (1)
sortat nesortat 1 n imin

146 Analiza algoritmilor – sortare prin selecție (2)
O altă variantă a sortării prin selecție: SELSORT2(X)
for i /barb2left1 to nS1 do
for j /barb2lefti+1 to n do
if X[j] < X[i] then
X[i] /barb2left/barb2right X[j]
Complexitatea algoritmului este:
)(2) 1(1…) 2() 1(2nnnn n C Θ=−=++−+− =

147 Se dă un tablou X de n elemente. Algoritmul Bubbles ort parcurge
repetat tabloul X interschimbând dacă e cazul eleme ntele
consecutive: BUBBLESORT1(X)
n /barb2leftX.size
for i /barb2left1 to n do
for j /barb2left1 to nS1 do
if X[j] > X[j+1] then
X[j] /barb2left/barb2right X[j+1]
Complexitatea algoritmului este: Analiza algoritmilor – Bubblesort (1)
)() 1(2n nnC Θ=− =

148 Elementul de pe ultima poziție a iterației curente poate fi exclus
din iterația următoare: BUBBLESORT2(X)
n /barb2leftX.size
for i /barb2left1 to nS1 do
for j /barb2left1 to nSi do
if X[j] > X[j+1] then
X[j] /barb2left/barb2right X[j+1]
Complexitatea algoritmului este: Analiza algoritmilor – Bubblesort (2)
)(2) 1(1…) 2() 1(2nnnn n C Θ=−=++−+− =

149 O altă variantă în care elementul de pe prima poziț ie a iterației curente
poate fi exclus din iterația următoare: BUBBLESORT3(X)
n /barb2leftX.size
for i /barb2left1 to nS1 do
for j /barb2leftnS1 downto i do
if X[j] > X[j+1] then
X[j] /barb2left/barb2right X[j+1]
Complexitatea algoritmului este: Analiza algoritmilor – Bubblesort (3)
)(2) 1(1…) 2() 1(2nnnn n C Θ=−=++−+− =

150 Algoritmul poate fi îmbunătățit reducând numărul de iterații de la n la câte sunt
necesare până la obținerea tabloului sortat. Și în acest caz elementul de pe ultima
poziție a iterației curente poate fi exclus din ite rația următoare:
BUBBLESORT4(X)
sortat /barb2leftfalse
n /barb2leftX.sizeS1
while not sortat do
sortat /barb2lefttrue
for i /barb2left1 to n do
if X[i] > X[i+1] then
X[i] /barb2left/barb2right X[i+1]
sortat /barb2leftfalse
n/barb2leftnS1
Complexitatea algoritmului în cazul cel mai favorab il (o singură parcurgere) este
Θ(n) iar în cazul cel mai defavorabil rămâne:Analiza algoritmilor – Bubblesort (4)
)(2) 1(1…) 2() 1(2nnnn n C Θ=−=++−+− =

151 Algoritmul de sortare rapidă se bazează pe paradigm a divide et impera . Tabloul
este rearanjat în două subtablouri astfel încât fie care element al primului
subtablou este mai mic sau egal cu orice element di n al doilea subtablou. Cele
două subtablouri sunt sortate prin apeluri recursiv e ale algoritmului de sortare
rapidă. QUICKSORT(X, primul, ultimul)
i /barb2leftprimul
j /barb2leftultimul
pivot /barb2leftX[primul]
while i<j do
while X[i]<pivot do
i /barb2lefti+1
while X[j]>pivot do
j /barb2leftjS1
if i<j then
X[i] /barb2left/barb2right X[j]
if i≤j then
i /barb2lefti+1
j /barb2leftjS1
if primul<j then QUICKSORT(X, primul, j) if i<ultimul then QUICKSORT(X, i, ultimul) Analiza algoritmilor – Quicksort (1)

152 Analiza cazului cel mai defavorabil
/square6Cazul cel mai defavorabil este acela în care toate partiționările sunt total dezechilibrate: un subtab lou
de un element și unul de nS1 elemente. Astfel, cazu l
cel mai defavorabil poate fi descris prin următoare a
recurență:
/square6Unde Θ(n) este timpul de partiționare. Deoarece
T(1)=Θ(1), se ajunge la recurența
/square6Apoi, iterând recurența, obținem: Analiza algoritmilor – Quicksort (2)
)() 1() 1 ()( n nT T nT Θ+− + =
)() 1()( n nT nT Θ+− =
∑ ∑
= =Θ= +Θ=Θ= Θ =
n
kn
knnnk k nT
12
1)(2) 1()()(

153 Analiza cazului cel mai favorabil
/square6Atunci când partițiile sunt aproximativ egale se aj unge la
următoarea recurență:
/square6Folosind teorema master avem a=2 (sortarea se conti nuă pe
ambele partiții), b=2 (vectorul de sortat se înjumă tățește) și
f(n)=Θ(n) (timpul de partiționare). Astfel,
/square6Deci putem aplica cazul 2 al teoremei master. Prin urmare,
avem: Analiza algoritmilor – Quicksort (3)
)(22)( nnT nT Θ+=
n n n nab= = =12log log2
)lg()lg()lg()(2log log2nn n n n n nTabΘ= Θ= Θ=

154 Analiza cazului mediu
/square6Atunci când partiționările echilibrate și dezechili brate alternează,
combinarea unei partiționări defavorabile și a unei a favorabile produce
trei subvectori de dimensiuni 1, (nS1)/2 și (nS1)/2 cu un cost total:
n + nS1 = 2nS1 = Θ(n)
/square6Se poate observa că o partiționare defavorabilă de un cost Θ(n) poate
fi absorbită de o partiționare echilibrată de cost Θ(n), și partiționarea
rezultată este favorabilă.
/square6Astfel, complexitatea medie este aceeași ca în cazu l cel mai favorabil,
O(nlgn), doar constanta din notația Oeste mai mare. Alternanța
partiționărilor dezechilibrate cu cele echilibrate poate fi descrisă prin
recurența
/square6unde T(1)=Θ(1), iar Θ(n)+Θ(1)+Θ(n)=Θ(n), deci obțin em recurențaAnaliza algoritmilor – Quicksort (4)
−+−+ Θ+ + Θ=− + + Θ=21
21)() 1 ()() 1() 1 ()()(nTnTn Tn nT Tn nT
)(212)( nnT nT Θ+−=

155 Rezolvarea recurenței cazului mediu
Metoda master nu e aplicabilă pentru recurența Prin urmare, vom folosi metoda iterației: Analiza algoritmilor – Quicksort (5)
)(212)( nnT nT Θ+−=

 + −Θ +
 + −=
 + −−Θ+−=
 
 
−Θ+
 
 −−
=−−Θ+−=
 
 
−Θ+
 
 −−
=−Θ+−=
−−
−
−−
−
11
1
11
122
33
222
2211
22
21222122212223227223
2123
22232212
23221
2121
22212)(212)(
qq
q
qq
q
qq
q n nTnTn nTnn
TnTn nTnn
TnTnnT nT

156 Considerând condiția la limită T(1)=Θ(1), recurența se termină pentru
Astfel, obținem: 1) 1lg() 1lg(11212121−+ = ⇒ + =+ ⇒+= ⇒=+ −+n q n q nnq
qqAnaliza algoritmilor – Quicksort (6)
( )
( )
)lg()() 1lg()()(1) 1lg()()()() 1 (2)(2122) 1 (2)(
1) 1lg(
11) 1lg(1) 1lg(
111
1 1) 1lg(
nn nTn nnn nTn n n nTn nTnT nT
n
knn
kkk
k n
Θ=−+ +Θ=Θ⋅−+ + Θ=Θ + Θ =


 + −Θ + =
∑∑
−+
=−+−+
=−−
− −+

/square6Algoritmul de sortare prin interclasare (Mergesort ),
bazat pe paradigma divide et impera , a fost introdus
de John von Neumann în 1945.
/square6Funcția principală a algoritmului, MERGESORT ,
realizează următoarele operații:
/square6determină mijlocul tabloului;
/square6sortează prin câte un autoapel (recursiv) cele două subtablouri;
/square6apelează funcția MERGE care interclasează cele două
subtablouri (sortate), obținând astfel tabloul sortat.
/square6Divizarea are loc recursiv până se ajunge la subtablouri formate dintrSun singur element, considerate deci sortate.
/square6Urmează în continuare pseudocodul algoritmului.Analiza algoritmilor – Mergesort (1)

158 MERGESORT(X, primul, ultimul)
if primul<ultimul then
pivot /barb2left(primul+ultimul)/2
MERGESORT(X, primul, pivot) MERGESORT(X, pivot+1, ultimul) MERGE(X, primul, pivot, ultimul) Analiza algoritmilor – Mergesort (2)
MERGE(X, primul, pivot, ultimul)
k /barb2leftprimul
i /barb2leftprimul
j /barb2leftpivot+1;
while i≤pivot and j≤ultimul do
if X[i]<X[j] then
T[k] /barb2leftX[i]
k /barb2leftk+1
i /barb2lefti+1
else
T[k] /barb2leftX[j]
k /barb2leftk+1
j /barb2leftj+1
if j>ultimul then
for j /barb2lefti to pivot do
T[k] /barb2leftX[j]
k /barb2leftk+1
if i>pivot then
for i /barb2leftj to ultimul do
T[k] /barb2leftX[i]
k /barb2leftk+1
for i /barb2leftprimul to ultimul do
X[i] /barb2leftT[i] Având în vedere divizarea în două
subtablouri de aproximativ aceeașidimensiune și apoi interclasarea, complexitatea temporală a algoritmului poate fi descrisă prin recurența: rezolvată la Quicksort, cu soluția Θ(n lg n).
)(22)( nnT nT Θ+=

159 Aplicații
1. Să se rezolve recurența aferentă cazului cel mai defavorabil al
algoritmului de căutare binară folosind metoda iter ației.
2. Să se rezolve recurența care descrie complexitatea tem porală
a algoritmului Mergesort folosind metoda iterației.
3. Să se implementeze algoritmii de sortare prezenta ți.
4. Comparați algoritmii de sortare, pe un tablou mar e, măsurând
timpii de execuție. Analiza algoritmilor – căutare și sortare

160 Analiza algoritmilor – tabele de dispersie (1)
Funcții de dispersie
Mapează o cheie k întrSuna din cele m locații ale t abelei de dispersie
/square6Metoda diviziunii
/square6Metoda înmulțirii
/square6Dispersia universală unde cheia k sSa descompus în r+1 octeți, astfel în cât
k= {k0, k 1, …, k r}, k i<m
a= {a0, a 1, …, a r}valori alese aleator din mulțimea {0, 1, …, m-1} m k khmod)(=
 10, ) 1mod()( << = A kAm kh
,mod)(
0∑
==r
iii m ka kh

161 Rezolvarea coliziunilor prin înlănțuire
/square6Elementele care se dispersează în aceeași locație s e încarcă întrSo listă
înlănțuită.
/square6Locația j conține un pointer către capul listei ele mentelor care se
dispersează în locația j, sau NULL dacă nu există a stfel de elemente.
/square6Operația de căutare, în cazul cel mai defavorabil ( când toate cele n
chei se dispersează în aceeași locație), este Θ(n).Analiza algoritmilor – tabele de dispersie (2)
K (chei) k1T
k1
k2
k3k2 k3
k4
k4

162 Rezolvarea coliziunilor prin adresare deschisă
/square6Toate elementele sunt memorate în interiorul tabele i de dispersie.
/square6Locația j conține elementul dispersat în locația j sau NULL dacă
nu există un astfel de element.
/square6Pentru inserare se examinează succesiv tabela de di spersie,
începând cu locația indexată, până la găsirea unei locații libere.
/square6Pentru căutarea unei chei se examinează secvența de locații
folosită de algoritmul de inserare. Căutarea se ter mină cu succes
dacă se găsește cheia k sau fără succes dacă se înt âlnește o
locație liberă.
/square6La ștergerea unei chei nu poate fi marcată locația ca fiind liberă
pentru că ar face imposibilă accesarea cheilor a că ror inserare a
găsit această locație ocupată. Prin urmare, locația se marchează
cu o valoare specială (ȘTERS, S1, etc.). Evident că la inserare
locațiile marcate astfel se consideră libere. Analiza algoritmilor – tabele de dispersie (3)

163 Verificarea liniară
/square6Fiind dată o funcție de dispersie h’, metoda verifi cării liniare
folosește funcția de dispersie pentru i= 0, 1, …, mN1.
/square6În cazul accesării tabelei de dispersie cu o cheie k, secvența
locațiilor examinate este:
T[h’(k)], T[h’(k)+1], …, T[mS1], T[0], T[1], …, T[h’(k)S1].
/square6Verificarea liniară poate genera grupări primare (ș iruri lungi de
locații ocupate care tind să se lungească) crescând timpul mediu
de căutare.Analiza algoritmilor – tabele de dispersie (4)
( ) m ikh ikh mod)() ,( +′=

164 Verificarea pătratică
/square6Fiind dată funcția de dispersie h’, verificarea păt ratică folosește
o funcție de dispersie de forma unde c
1, c 2 ≠ 0 sunt constante auxiliare și i= 0, 1, …, mN1.
/square6Locația verificată inițial este T[h’(k)], următoare le locații
examinate depinzând întrSo manieră pătratică de i.
/square6Dacă două chei au aceeași poziție de start a verifi cării, atunci
secvențele locațiilor verificate coincid:
Această situație poate conduce la o formă mai ușoar ă de
grupare, numită grupare secundară.Analiza algoritmilor – tabele de dispersie (5)
( ),mod )() ,(2
21 m icickh ikh + +′=
) ,() ,() 0 ,() 0 ,(2 1 2 1 ikhikh kh kh = ⇒ =

165 Dispersia dublă
/square6Se folosește o funcție de dispersie de forma: unde h’și h’’ sunt funcții de dispersie auxiliare
/square6Spre deosebire de verificarea liniară sau pătratică , secvența
locațiilor examinate depinde prin două funcții de d ispersie de
cheia k.
/square6În cazul dispersiei duble, când cheia variază, pozi ția inițială a
verificării h’(k) și decalajul h’’(k) pot varia ind ependent,
evitând astfel grupările primare și secundare. Analiza algoritmilor – tabele de dispersie (6)
( ),mod)()() ,( m khikh ikh ′′⋅+′=

166 Exerciții [Cor00]
1. Se consideră o tabelă de dispersie de dimensiune m=1000 și
funcția de dispersie Calculați locațiile în care se pun cheile 61, 62, 6 3, 64 și 65.
2. Se consideră că se inserează cheile 10, 22, 31, 4 , 15, 28, 17,
88, 59 întrSo tabelă de dispersie cu m=11 locații f olosind
adresarea deschisă cu funcția primară de dispersie h’=k mod
m. Ilustrați rezultatul inserării acestor chei folos ind verificarea
liniară, verificarea pătratică cu c 1=1 și c 2=3 respectiv
dispersia dublă cu h’’ (k)=1+( kmod ( m S1)). Analiza algoritmilor – tabele de dispersie (7)
 215, ) 1mod()(−= = A kAm kh

167 /square6Arborele este o particularizare a unei structuri de date mai generale,
graful, care va fi prezentat în capitolul următor.
/square6Utilizarea unei structuri arborescente binare face posibilă inserarea
și ștergerea rapidă, precum și căutarea eficientă a datelor.
/square6Dacă orice nod din arbore poate avea cel mult doi f ii, atunci arborele se
numește arbore binar .
/square6Pe lângă un câmp cheie și date adiționale, fiecare nod al arborelui binar
conține câmpurile st , dr și p– referințe spre nodurile corespunzătoare
fiului stâng, fiului drept și părintelui.
/square6ÎntrSun arbore binar de căutare cheile sunt întotdeauna astfel
memorate încât ele satisfac următoarea proprietate:
Fie x un nod dintrSun arbore binar de căutare. Dacă y este un nod din
subarborele stâng al lui x, atunci y.cheie≤x.cheie. Dacă y este un nod din
subarborele drept al lui x, atunci y.cheie≥x.cheie.
/square6Exemplu: Analiza algoritmilor – arbori binari de căutare (1)
6
3
2 57
8

168 Implementarea clasei Node în Java
public class Node {
int key; //cheia float data; //alte informatii Node leftChild; //fiul stang Node rightChild; //fiul drept Node parent; //parintele public Node(int k){ //constructorul
key = k; //initializarea cheii
}
}Analiza algoritmilor – arbori binari de căutare (2)

169 Inserarea – constă în inserarea nodului zpe poziția corespunzătoare în
arborele binar de căutare cu rădăcina r.
INSEREAZA(z)
y /barb2leftNULL
x /barb2leftr
while x≠NULL do
y /barb2leftx
if z.cheie<x.cheie then
x /barb2leftx.st
else
x /barb2leftx.dr
z.p /barb2lefty
if y=NULL then
r /barb2leftz
else if z.cheie<y.cheie then
y.st /barb2leftz
else
y.dr /barb2leftzAnaliza algoritmilor – arbori binari de căutare (3)
6
3
2 57
8
6
3
2 57
8
4Inserarea nodului 4:

170 Implementarea inserării în Java
public class BinaryTree {
Node root = null; //nodul radacina public BinaryTree() {
insert(new Node(7)); //inserarea unui nod cu cheia 7insert(new Node(1)); //inserarea unui nod cu cheia 1insert(new Node(5)); //inserarea unui nod cu cheia 5
} public void insert(Node z){
Node y = null; //parintele nodului curent x Node x = root; //nodul curent while(x!=null){ //deplasarea in jos in arbore
y=x; if(z.key<x.key) x=x.leftChild; //deplasarea in jos p e subarborele stang
else x=x.rightChild; //deplasarea in jos pe subarbor ele drept
}
z.parent=y; //x==null, z este inserat pe aceasta poz itie null, cu y parinte
if(y==null) root=z; //daca parintele este null, z de vine radacina arborelui
else if(z.key<y.key) y.leftChild=z; //setarea nodulu i z ca fiu stang al lui y
else y.rightChild=z; //setarea nodului z ca fiu drep t al lui y
}
public static void main(String[] args) {
BinaryTree binaryTree1 = new BinaryTree();
}
}Analiza algoritmilor – arbori binari de căutare (4)

171 /square6Traversarea arborelui în inordine – vizitează nodurile în ordinea crescătoare
a cheilor. Rădăcina se vizitează între nodurile din subarborele său stâng și cele
din subarborele său drept. În exemplul anterior: 2, 3, 5, 6, 7, 8.
INORDINE(x)
if x≠NULL then
INORDINE(x.st)
AFISEAZA(x.cheie)
INORDINE(x.dr)
/square6Traversarea arborelui în preordine – vizitează rădăcina înaintea nodurilor
din subarbori. În exemplul anterior: 6, 3, 2, 5, 7, 8.
PREORDINE(x)
if x≠NULL then
AFISEAZA(x.cheie)
PREORDINE(x.st) PREORDINE(x.dr)
/square6Traversarea arborelui în postordine – vizitează rădăcina după nodurile din
subarbori. În exemplul anterior: 2, 5, 3, 8, 7, 6. POSTORDINE(x)
if x≠NULL then
POSTORDINE(x.st) POSTORDINE(x.dr)
AFISEAZA(x.cheie) Analiza algoritmilor – arbori binari de căutare (5)

172 Căutarea unei chei
/square6Căutarea returnează nodul având cheia k dacă există sau NULL în caz contrar.
/square6Căutarea recursivă CAUTA_REC(x, k)
if x=NULL or k=x.cheie then
return x
if k<x.cheie then
return CAUTA_REC(x.st, k)
else
return CAUTA_REC(x.dr, k)
/square6Căutarea iterativă (de obicei mai eficientă decât varianta recursivă)
CAUTA_IT(x, k)
while x≠NULL and k≠x.cheie do
if k<x.cheie then
x /barb2leftx.st
else
x /barb2leftx.dr
return x Analiza algoritmilor – arbori binari de căutare (6)

173 /square6Minimul – determinarea nodului cu cheia minimă dintrSun
arbore binar de căutare se realizează prin deplasar e în jos pe
subarborele stâng până când se ajunge la un nod fru nză.
MINIM(x)
while x.st≠NULL do
x /barb2leftx.st
return x
/square6Maximul – este nodul cu cheia maximă și se determină prin
deplasare în jos pe subarborele drept până când se ajunge la un
nod frunză.MAXIM(x)
while x.dr≠NULL do
x /barb2leftx.dr
return x Analiza algoritmilor – arbori binari de căutare (7)
6
3
2 57
8
6
3
2 57
8

174 Succesorul unui nod x este nodul având cea mai mică cheie mai mare
decât cheia lui x, sau NULL, dacă xare cea mai mare cheie din arborele
binar de căutare. Trebuie tratate două alternative:
/square6Dacă xare subarbore drept, atunci succesorul lui x este nodul cu cheia
minimă din acest subarbore. În exemplul anterior, s uccesorul lui 3 este 5.
/square6Dacă xnu are fiu drept, atunci succesorul lui x se determină traversând
arborele binar de căutare de la xîn sus până când se întâlnește un nod
care este fiu stâng, părintele acelui nod fiind suc cesorul lui x. În exemplul
anterior, succesorul lui 5 este 6.
SUCCESOR(x)
if x.dr≠NULL then
return MINIM(x.dr)
y /barb2leftx.p
while y≠NULL and x=y.dr do
x /barb2lefty
y /barb2lefty.p
return y Analiza algoritmilor – arbori binari de căutare (8)
6
3
2 57
8Succesorul lui 3 este 5 Succesorul lui 5 este 6

175 /square6Ștergerea unui nod z constă în tratarea următoarelor trei
situații:
/square6Dacă z nu are fii, se va modifica părintele său pentru a Si înlocui fiul
z cu NULL.
/square6Dacă zare un fiu, z va fi eliminat prin setarea unei legături de la
părintele lui zla fiul lui z.
/square6Dacă zare doi fii, se va elimina din arbore succesorul yal lui zși
apoi se vor înlocui cheia și informațiile adițional e ale lui zcu cele
ale lui y.
/square6Exemplu în care zare doi fii: Analiza algoritmilor – arbori binari de căutare (9)
15
5
3 12 16
20
13 10
6
718 23 z
y15
6
3 12 16
20
13 10
718 23

176 /square6Exemplu în care zare un singur fiu:
/square6Exemplu în care znu are fii: Analiza algoritmilor – arbori binari de căutare (10)
15
5
3 12 16
20
13 10
6
718 23
z15
5
3 12 16
20
13 10
618 23 15
5
3 12 16
20
13 10
6
718 23
z15
5
3 12 16
20
13 10
718 23

STERGE(z)
if z.st=NULL and z.dr=NULL then
y /barb2leftz
if y.p=NULL then
radacina /barb2leftNULL
else if y=y.p.st then
y.p.st /barb2leftNULL
else
y.p.dr /barb2leftNULL
else if z.st=NULL or z.dr=NULL then
y /barb2leftz
if y.st≠NULL then
x /barb2lefty.st
else
x /barb2lefty.dr
if x≠NULL then
x.p /barb2lefty.p
if y.p=NULL then
radacina /barb2leftx
else if y=y.p.st then
y.p.st /barb2leftx
else
y.p.dr /barb2leftxelse
y /barb2leftSUCCESOR(z)
if y.st≠NULL then
x /barb2lefty.st
else
x /barb2lefty.dr
if x≠NULL then
x.p /barb2lefty.p
if y.p=NULL then
radacina /barb2leftx
else if y=y.p.st then
y.p.st /barb2leftx
else
y.p.dr /barb2leftx
if y≠z then
z.cheie /barb2lefty.cheie Analiza algoritmilor – arbori binari de căutare (11)

178 În continuare este prezentată o variantă de ștergere care
organizează compact cele trei situații. Algoritmul d etermină
nodul y care se șterge și reface legăturile (în al 3Slea caz chiar și
cheia) nodurilor implicate.
STERGE(z)
if z.st=NULL or z.dr=NULL then
y /barb2leftz
else
y /barb2leftSUCCESOR(z)
if y.st≠NULL then
x /barb2lefty.st
else
x /barb2lefty.dr
if x≠NULL then
x.p /barb2lefty.p
if y.p=NULL then
radacina /barb2leftx
else if y=y.p.st then
y.p.st /barb2leftx
else
y.p.dr /barb2leftx
if y≠z then
z.cheie /barb2lefty.cheie
return y Analiza algoritmilor – arbori binari de căutare (12)

179 Complexitatea operațiilor
/square6Operațiile de bază pe arborii binari INSEREAZA, CAU TA, MINIM,
MAXIM, SUCCESOR și STERGE consumă un timp proporțio nal cu
înălțimea arborelui.
/square6Pentru un arbore binar relativ echilibrat cu n nodu ri, aceste operații se
execută în cazul cel mai defavorabil întrSun timp Θ (lg n). În acest caz,
complexitatea temporală poate fi exprimată prin rec urența
rezolvată deja pentru algoritmul de căutare binară.
/square6Dacă arborele binar este degenerat (ex. lanț liniar de n noduri), atunci
timpul consumat în cazul cel mai defavorabil este Θ (n).
/square6Operațiile INORDINE, PREORDINE și POSTORDINE au nev oie de un
timp Θ(n) pentru traversarea unui arbore binar de c ăutare cu n noduri.) 1 (2)( Θ+=nTnTAnaliza algoritmilor – arbori binari de căutare (13)

180 Aplicații
1. Fie secvența de valori: 4, 7, 2, 5, 3, 1, 6.
a) Reprezentați grafic arborele binar de căutare cons truit prin inserarea secvenței de valori
de mai sus.
b) În ce ordine se afișează valorile printrSo traver sare în preordine? Dar printrSo traversare în
postordine?
c) Care este succesorul nodului cu cheia 4? Dar succ esorul nodului cu cheia 6?
d) Reprezentați grafic arborele binar de căutare obț inut după ștergerea nodului 4.
2. Să se completeze clasa BinaryTree prezentată cu t raversarea arborelui binar de căutare în
inordine, preordine și postordine.
3. Să se implementeze în Java (în clasa BinaryTree) căutarea recursivă și căutarea iterativă a unei
chei în arborele binar de căutare.
4. Să se introducă în clasa BinaryTree metode pentru determinarea cheii minime și maxime în
arborele binar de căutare.
5. Să se implementeze în clasa BinaryTree o metodă c are să identifice succesorul unui nod în
arborele binar de căutare.
6. Să se implementeze în clasa BinaryTree algoritmul de ștergere a unui nod din arborele binar de
căutare.
7. Să se modifice clasa Node și operațiile implement ate în clasa BinaryTree astfel încât cheia să
fie numele studentului.
8. Să se rezolve prin metoda iterației recurența afe rentă operațiilor de bază (inserare, căutare,
minim, maxim, succesor și ștergere) pe un arbore bi nar de căutare echilibrat cu nnoduri. Analiza algoritmilor – arbori binari de căutare (14)

181 /square6HeapSul (movila) este un arbore binar complet (până la ultimul nivel) cu
următoarea proprietate:
/square6orice nod dintrSun heap minimizant trebuie să aibă o cheie mai mică (sau egală)
decât oricare dintre fiii săi.
/square6orice nod dintrSun heap maximizant trebuie să aibă o cheie mai mare (sau egală)
decât oricare dintre fiii săi.
/square6Reprezentarea heapSurilor se face prin tablouri. În trSun tablou indexat de la 1, fiii
nodului k au indicii 2k și 2k+1, iar părintele nodu lui k are indicele k/2. ÎntrSun
tablou indexat de la 0 (ca în Java), fiii nodului k au indicii 2k+1 și 2k+2, iar
părintele nodului k are indicele (kS1)/2. Exemplu d e heap minimizant:
/square6HeapSul permite selecția rapidă a elementului cu ch eie minimă sau maximă (care
este chiar rădăcina), operație realizată în O(1).
/square6HeapSul binar este slab ordonat în raport cu arbore le binar de căutare, de aceea,
traversarea nodurilor în ordine este dificilă.
/square6Pentru o structură heap A notăm cu A.size dimensiunea totală a tabloului
respectiv A.heapsize dimensiunea heapSului. Analiza algoritmilor – heapSuri (1)
5
34 27
49 53 42 1
2 3
4 5 65
34 27 42 53 49 123
456

182 Inserarea unui nod
/square6Constă în două operații:
/square6Adăugarea nodului pe ultimul nivel, sau pe un nou n ivel dacă arborele este
complet. În cazul reprezentării prin tablouri, noul element se adaugă în prima
poziție disponibilă.
/square6Propagarea în sus (spre rădăcină) a nodului inserat până la îndeplinirea condiției
de heap.
/square6Exemplu de inserare a valorii 3 întrSun heap minimi zant Analiza algoritmilor – heapSuri (2)
5
34 27
49 53 42 1
2 3
4 5 63
75
34 27
49 53 42 1
2 3
4 5 6
5
34 3
49 53 42 1
2 3
4 5 627
73
34 5
49 53 42 1
2 3
4 5 627
7

183 Determinarea părintelui sau fiilor nodului cu indic ele iîntrSun heap reprezentat prin tablou.
PARINTE(i)
return i/2
STANGA(i)
return 2i
DREAPTA(i)
return 2i+1
Inserarea nodului z în heapSul minimizant A:
INSEREAZA(A, z)
A.heapsize /barb2leftA.heapsize+1
i /barb2leftA.heapsize
while i>1 and A[PARINTE(i)]>z do
A[i] /barb2leftA[PARINTE(i)]
i /barb2leftPARINTE(i)
A[i] /barb2leftzAnaliza algoritmilor – heapSuri (3)

184 Extragerea rădăcinii
/square6Constă în două operații:
/square6Copierea ultimului nod în rădăcină.
/square6Propagarea în jos a rădăcinii temporare până la înd eplinirea condiției de
heap (reconstituirea proprietății de heap). Propaga rea se face spre fiul cu
cheia cea mai mică întrSun heap minimizant respecti v spre fiul cu cheia
mai mare întrSun heap maximizant.
/square6Exemplu de extragere a rădăcinii dintrSun heap mini mizant Analiza algoritmilor – heapSuri (4)
3
34 5
49 53 42 1
2 3
4 5 627
727
34 5
49 53 42 1
2 3
4 5 65
34 27
49 53 42 1
2 3
4 5 6

185 La reconstituirea heapSului se consideră că subarbo rii care au ca rădăcină
STANGA(i) respectiv DREAPTA (i) sunt heapSuri.
RECONSTITUIE(A, i)
s /barb2leftSTANGA(i)
d /barb2leftDREAPTA(i)
if s≤A.heapsize and A[s]<A[i] then
min /barb2lefts
else
min /barb2lefti
if d≤A.heapsize and A[d]<A[min] then
min /barb2leftd
if min≠i then
A[i] /barb2left/barb2right A[min]
RECONSTITUIE(A, min)
EXTRAGE(A)
min /barb2leftA[1]
A[1] /barb2leftA[A.heapsize]
A.heapsize /barb2leftA.heapsizeS1
RECONSTITUIE(A, 1)
return min Analiza algoritmilor – heapSuri (5)

186 Construcția heapâurilor
/square6Prin reconstituirea recursivă a proprietății de hea p de la nodul n/2 în
jos – nodurile n/2+1…n sunt frunze și îndeplinesc condiția de heap:
CONSTRUIESTE(A)
A.heapsize /barb2leftA.size
for i /barb2leftA.size/2 downto 1 do
RECONSTITUIE(A, i)
/square6Prin inserare repetată în heap considerând că primu l element al
tabloului formează deja un heap: CONSTRUIESTE(A)
A.heapsize /barb2left1
for i /barb2left2 to A.size do
INSEREAZA(A, A[i]) Analiza algoritmilor – heapSuri (6)

187 Heapsort
Algoritmul heapsort începe cu apelul procedurii CON STRUIESTE
prin care transformă vectorul de intrare A în heap. Sortarea se
face prin interschimbarea repetată a rădăcinii cu u ltimul element
din heap urmată de excluderea lui din heap. Sortare a este
descrescătoare cu un heap minimizant respectiv cres cătoare cu
heap maximizant. HEAPSORT(A)
CONSTRUIESTE(A) for i /barb2leftA.size downto 2 do
A[1] /barb2left/barb2right A[i]
A.heapsize /barb2leftA.heapsizeS1
RECONSTITUIE(A, 1) Analiza algoritmilor – heapSuri (7)

188 Complexitatea operațiilor în heap
/square6Operațiile INSEREAZA, EXTRAGE și RECONSTITUIE sunt de complexitate O(lgn), la fel
ca operațiile întrSun arbore binar de căutare (v. c apitolul precedent).
/square6Operația de construire prin inserare repetată apele ază de O(n) ori INSEREAZA de
complexitate O(lgn), deci, timpul total de execuție este O(nlgn).
/square6În cazul operației de construire prin reconstituire recursivă se observă că nodurile de pe
ultimul nivel (aproximativ jumătate) îndeplinesc co ndiția de heap, deci nu sunt
propagate deloc. Nodurile de pe nivelul deasupra fr unzelor (aproximativ un sfert) sunt
propagate cel mult un nivel. Nodul aflat în rădăcin ă este propagat cel mult hS1 nivele,
(lg nrotunjit în jos). Astfel, numărul de propagări este
Știm că pentru orice xsubunitar
Astfel rezultă că
/square6Timpul de execuție al algoritmului heapsort este O( nlgn) deoarece CONSTRUIESTE se
execută în O(n) iar operația RECONSTITUIE de O(lgn) este apelată de nS1 ori. Analiza algoritmilor – heapSuri (8)
( )∑∞
= −=⋅
021 kk
xxxk   
∑ ∑
= =+ + + 
= ⋅ =⋅ ++⋅+⋅+⋅
n
kn
kk k kknO kOnkn n n nlg
0lg
01 1 12)(
22…281402
 
)(
21121
221
222
0lg
01nOnO knOknOk
kn
kk=
 
 
−⋅ =

⋅ ⋅ =

∑ ∑∞
= =+

189 Aplicații
1. Ilustrați modul de funcționare al procedurii CONS TRUIESTE, prin reconstituire
heap minimizant, pentru vectorul A={5,3,17,10,84,19 ,6,22,9}.
2. Ilustrați modul de funcționare al procedurii CONS TRUIESTE, prin inserare în
heap minimizant, pentru vectorul A={5,3,17,10,84,19 ,6,22,9}.
3. Ilustrați modul de funcționare al procedurii CONS TRUIESTE, prin reconstituire
heap maximizant, pentru vectorul A={5,3,17,10,84,19 ,6,22,9}.
4. Ilustrați modul de funcționare al procedurii CONS TRUIESTE, prin inserare în
heap maximizant, pentru vectorul A={5,3,17,10,84,19 ,6,22,9}.
5. Ilustrați modul de funcționare al procedurii HEAP SORT pentru vectorul
A={5,3,17,10,84,19,6,22,9}.
6. Să se implementeze în Java operațiile de construi re, inserare, extragere și
reconstituire.
7. Să se implementeze în Java algoritmul heapsort. 8. Să se rescrie funcția RECONSTITUIE pentru un heap maximizant.
9. Să se implementeze în Java algoritmul heapsort fo losind un heap maximizant,
astfel încât sortarea să se facă în ordine crescăto are.
10. Să se adapteze și să se reutilizeze clasa Node d e la arbori binari de căutare (cu
informație suplimentară nume student) pentru heapSu ri. Analiza algoritmilor – heapSuri (9)

190 /square6Grafurile au o formă determinată de o problemă conc retă.
/square6Nodurile grafului se numesc vârfuri și ele pot fi conectate prin muchii . Notăm
un graf G=(V,E), unde V este mulțimea vârfurilor și E este mulțimea muchiilor.
Notăm cu |V| numărul vârfurilor și cu |E| numărul m uchiilor.
/square6Fiecare vârf conține câmpurile i (index), c (color) , d (distance/discovered), p
(predecessor), f (finalized).
/square6Două vârfuri se numesc adiacente dacă sunt conectate direct printrSo muchie.
/square6Un drum reprezintă o secvență de muchii.
/square6Un graf se numește conex dacă există cel puțin un drum între toate vârfuril e.
/square6Un graf în care muchiile nu au o direcție (deplasar ea se poate face în orice sens)
se numește neorientat . Un graf în care muchiile au o singură direcție (m arcată
prin săgeată) se numește orientat .
/square6Un graf în care muchiile au asociate ponderi (costu l drumurilor dintre vârfuri) se
numește ponderat .
/square6Complexitatea unui algoritm pe un graf G=(V,E) se exprimă în fun cție de
dimensiunea intrării descrisă prin doi parametri: n umărul de vârfuri |V| și
numărul de muchii |E|. În cadrul notației asimptoti ce simbolul V înseamnă |V|,
iar simbolul E înseamnă |E|. Analiza algoritmilor – grafuri (1)

191 Podurile din Königsberg Analiza algoritmilor – grafuri (2)
BAC
D
abcd
e
fg
AC
BD
abcd
e
fgUnul dintre primii matematicieni care a studiat grafurile a fost Leonhard Euler , în
secolul al XVIIISlea. El a rezolvat celebra problemă a podurilor din Königsberg, demonstrând că nu există un drum care să cuprindă toate cele șapte poduri, fără a traversa de două ori același pod.

192 Implementarea clasei Vertex în Java
ÎntrSo implementare abstractă vârfurile pot fi valo ri întregi. În majoritatea aplicațiilor însă
pentru fiecare vârf trebuie păstrate mai multe info rmații, ca în clasa Vertex de mai jos:
package graphs; import java.awt.*; public class Vertex {
Color color;
Vertex predecessor;
int distance; int discovered; //for DFS int finalized; //for DFS char label; int index; static int infinite = 100;
public Vertex(int i) {
index = i; color = Color.white;
distance = infinite; predecessor = null;
}
}Analiza algoritmilor – grafuri (3)

193 Reprezentarea grafurilor prin matrice de adiacență
/square6Matricea de adiacență este un tablou bidimensional, în care elementele indică
prezența unei muchii între două vârfuri. Dacă grafu l are |V| vârfuri, numerotate
cu 1,2,…,|V| în mod arbitrar, matricea de adiacen ță este un tablou A=(a ij ) cu
|V|x|V| elemente, unde
/square6Matricea de adiacență poate fi folosită și pentru g rafuri ponderate. În acest caz,
costul w(i,j) al unei muchii (i,j) ϵ E este memorat ca element din linia iși
coloana ja matricei de adiacență:
/square6Avantajul constă în verificarea rapidă a adiacențel or. Dezavantajul constă în
faptul că necesarul de memorie pentru matricea de a diacență a unui graf este
Θ(V 2) și nu depinde de numărul de muchii. Astfel, repre zentarea prin matrice de
adiacență este indicată în cazul grafurilor cu un n umăr relativ mic de vârfuri sau
atunci când graful este dens (|E| aproximativ egal cu |V| 2). Analiza algoritmilor – grafuri (4)
 ∈=.0,), (1
altfelEji dacăaij
 ∈=.0,), (), (
altfelEji dacăjiwaij

194 Implementarea în Java a unui graf neponderat reprez entat prin matrice de adiacență
package graphs; import java.awt.*; import java.util.*; public class Graph {
int maxVerts = 20; int nVerts = 0;
ArrayList<Vertex> vertexList = new ArrayList();
int A[][] = new int[maxVerts][maxVerts]; public Graph() {
for(int i=0; i<maxVerts; i++)
for(int j=0; j<maxVerts; j++)
A[i][j] = 0;
} public void addVertex(){
vertexList.add(new Vertex(nVerts++));
} public void addEdge(int v1, int v2){
A[v1][v2] = 1; A[v2][v1] = 1;
}Analiza algoritmilor – grafuri (5)
public static void main(String[] args) {
Graph graph = new Graph(); graph.addVertex(); //0 graph.addVertex(); //1 graph.addVertex(); //2 graph.addVertex(); //3 graph.addEdge(0, 1); graph.addEdge(1, 2); graph.addEdge(0, 3);
}
}
1 2
30

195 Reprezentarea grafurilor prin liste de adiacență
/square6Se folosește un tablou A cu |V| liste, câte una pen tru fiecare
vârf din V. Pentru fiecare i ϵ V, lista de adiacență A[i] conține
toate vârfurile j pentru care există o muchie (i,j) ϵ E.
/square6Dacă graful este orientat, suma lungimilor tuturor listelor de
adiacență este |E|. Dacă graful este neorientat, lu ngimea totală
a listelor de adiacență este 2|E| deoarece, dacă (i ,j) este o
muchie, atunci iapare în lista de adiacență a lui j dar și j apare
în lista de adiacență a lui i.
/square6Dacă graful este ponderat, costul w(i,j) al muchiei (i,j) ϵ E este
memorat împreună cu vârful j în lista de adiacență a lui i.
/square6Avantajul constă în necesarul de memorie O(max(V,E) ).
Reprezentarea prin liste de adiacență este preferat ă pentru că
oferă un mod compact de reprezentare a grafurilor r are (cu |E|
mult mai mic decât |V| 2). Dezavantajul constă în faptul că
verificarea adiacențelor implică operații de căutar e în liste. Analiza algoritmilor – grafuri (6)

196 Analiza algoritmilor – grafuri (7)
Reprezentarea grafurilor neponderate. Exemple
Graf neorientat Listele de adiacență Matricea de adia cență
Graf orientat Listele de adiacență Matricea de adiace nță1 2
3
4 5
1 2
3
4 51 /barb2right2 /barb2right5
2 /barb2right1 /barb2right3 /barb2right4 /barb2right5
3 /barb2right2 /barb2right4
4 /barb2right2 /barb2right3 /barb2right5
5 /barb2right1 /barb2right2 /barb2right4
1 /barb2right2 /barb2right5
2 /barb2right3 /barb2right4
3 /barb2right4
4 /barb2right5
5 /barb2right21 2 3 4 5
10 1 0 0 1
21 0 1 1 1
30 1 0 1 0
40 1 1 0 1
51 1 0 1 0
1 2 3 4 5
10 1 0 0 1
20 0 1 1 0
30 0 0 1 0
40 0 0 0 1
50 1 0 0 0

197 Analiza algoritmilor – grafuri (8)
Reprezentarea grafurilor ponderate. Exemple
Graf neorientat Listele de adiacență Matricea de adia cență
Graf orientat Listele de adiacență Matricea de adiace nță1 2 3 4 5
10 12 0 0 15
212 0 26 18 17
30 26 0 29 0
40 18 29 0 21
515 17 0 21 01 /barb2right2/12 /barb2right5/15
2 /barb2right1/12 /barb2right3/26 /barb2right4/18 /barb2right5/17
3 /barb2right2/26 /barb2right4/29
4 /barb2right2/18 /barb2right3/29 /barb2right5/21
5 /barb2right1/15 /barb2right2/17 /barb2right4/21
1 /barb2right2/12 /barb2right5/15
2 /barb2right3/26 /barb2right4/18
3 /barb2right4/29
4 /barb2right5/21
5 /barb2right2/17 1 2
3
4 512
15 17 18
21 26
29
1 2
3
4 512
15 17 18
21 26
29 1 2 3 4 5
10 12 0 0 15
20 0 26 18 0
30 0 0 29 0
40 0 0 0 21
50 17 0 0 0

198 Parcurgerea grafurilor în lățime (breadthâfirst sea rch)
/square6Parcurgerea în lățime a unui graf G=(V,E) pornește de la un vârf sursă
sși explorează sistematic graful descoperind toate v ârfurile accesibile
din s. Algoritmul calculează distanța de la sla toate aceste vârfuri
accesibile.
/square6Parcurgerea în lățime lărgește uniform frontiera di ntre vârfurile
descoperite și cele nedescoperite. Astfel, algoritm ul descoperă toate
vârfurile aflate la distanța k față de s înainte de cele aflate la distanța
k+1.
/square6Acest algoritm este implementat cu ajutorul unei co zi Q.
/square6Pentru a ține evidența avansării, parcurgerea în lă țime colorează fiecare
vârf cu alb (nedescoperit), gri (descoperit, cu lis ta de adiacență în curs
de explorare) sau negru (descoperit, cu lista de ad iacență explorată).
/square6Algoritmul păstrează pentru fiecare vârf v ϵ V culoa rea în v.c,
predecesorul în v.p și distanța de la sursa s în câ mpul v.d.
/square6Complexitatea algoritmului constă în operațiile efe ctuate cu coada
(fiecare vârf este inserat și scos o singură dată) cu un cost O(V) și în
examinarea listelor de adiacență cu un cost O(E), a stfel timpul total de
execuție este O(V+E). Analiza algoritmilor – grafuri (9)

199 BFS(G, s)
foreach u ϵ V do
u.c /barb2leftALB
u.d /barb2left∞
u.p /barb2leftNULL
s.c /barb2leftGRI
s.d /barb2left0
Q.INSERT(s) while Q≠Ø do
u /barb2leftQ.HEAD
PRINT(u.i) foreach v ϵ A[u] do
if v.c=ALB then
v.c /barb2leftGRI
v.d /barb2leftu.d+1
v.p /barb2leftu
Q.INSERT(v)
Q.DELETE(Q.HEAD) u.c /barb2leftNEGRU Analiza algoritmilor – grafuri (10)

200 Implementarea în Java a parcurgerii grafurilor în l ățime
public void BFS(int s){
for(int u=0; u<nVerts; u++){
vertexList.get(u).color = Color.white; vertexList.get(u).distance = Vertex.infinite; vertexList.get(u).predecessor = null;
}vertexList.get(s).color = Color.gray; vertexList.get(s).distance = 0; LinkedList<Vertex> queue = new LinkedList();
queue.addFirst(vertexList.get(s)); while(!queue.isEmpty()){
Vertex u = queue.getLast();
System.out.println(u.index);
for(int v=0; v<nVerts; v++)
if(A[v][u.index]==1 && vertexList.get(v).color==Col or.white){
vertexList.get(v).color = Color.gray; vertexList.get(v).distance = u.distance+1; vertexList.get(v).predecessor = u;
queue.addFirst(vertexList.get(v));
}
queue.removeLast(); u.color = Color.black;
}
}Analiza algoritmilor – grafuri (11)

201 Parcurgerea grafurilor în adâncime (depthâfirst sea rch)
/square6Algoritmul explorează în adâncime subgraful succeso r al celui mai recent
descoperit vârf v dintrSun graf G=(V,E). Când toate muchiile care p leacă din v
au fost explorate, algoritmul revine pentru explora rea următoarelor muchii care
pleacă din predecesorul lui v.
/square6Parcurgerea în adâncime se implementează cu ajutoru l stivei, fiind astfel naturală
o abordare recursivă.
/square6Pentru a ține evidența avansării, parcurgerea în ad âncime colorează fiecare vârf
v ϵ V cu alb (nedescoperit), gri (descoperit, cu zon a de graf accesibilă din vîn
curs de explorare) sau negru (descoperit, cu zona d e graf accesibilă din v
explorată).
/square6Algoritmul păstrează pentru fiecare vârf v ϵ V culoa rea în v.c și predecesorul în
v.p. De asemenea, algoritmul folosește un ceas tal parcurgerii care crește
atunci când un nod își schimbă culoarea. Algoritmul creează marcaje de timp
pentru fiecare vârf v ϵ V: momentul când v este des coperit (devine gri) este
păstrat în v.d, iar momentul în care explorarea zo nei grafului accesibilă din v a
fost finalizată este păstrat în v.f.
/square6Marcajele de timp precum și predecesorii se pot fol osi pentru o serie extinsă de
prelucrări.
/square6Complexitatea algoritmului constă în explorarea vâr furilor Θ(V) și în examinarea
listelor de adiacență Θ(E), astfel timpul total de execuție este Θ(V+E). Analiza algoritmilor – grafuri (12)

202 DFS(G)
foreach u ϵ V do
u.c /barb2leftALB
u.p /barb2leftNULL
t /barb2left0
foreach u ϵ V do
if u.c=ALB then
EXPLOREAZA(u)
EXPLOREAZA(u)
u.c /barb2leftGRI
PRINT(u.i) u.d /barb2leftt /barb2leftt+1
foreach v ϵ A[u] do
if v.c=ALB then
v.p /barb2leftu
EXPLOREAZA(v)
u.c /barb2leftNEGRU
u.f /barb2leftt /barb2leftt+1 Analiza algoritmilor – grafuri (13)

203 Drumuri minime. Algoritmul Dijkstra
/square6Algoritmul de căutare în lățime determină drumurile minime în grafuri
neponderate. Algoritmul Dijkstra permite determinar ea drumurilor
minime de la vârful sursă s către toate vârfurile unui graf ponderat cu
costuri nenegative. Astfel, vom presupune că w(u,v) ≥0 pentru fiecare
muchie (u,v) ϵ E.
/square6Pentru fiecare vârf v ϵ V algoritmul păstrează în v .d estimarea drumului
minim față de s, iar în v.p păstrează predecesorul. Algoritmul folo sește
o coadă de priorități Q inițializată cu V (conține toate vârfurile grafului).
/square6La fiecare iterație while , se extrage din Q vârful ucu drumul minim.
Pentru fiecare vârf vadiacent cu u se reactualizează v.d și v.p în cazul
în care drumul minim către v poate fi ameliorat dacă trece prin u
(operație de relaxare a muchiilor).
/square6Complexitatea algoritmului constă în extragerea min imului (operație
O(V) efectuată de |V| ori) cu un cost O(V 2) și în examinarea listelor de
adiacență (fiecare muchie este examinată o singură dată) cu un cost
O(E), astfel timpul total de execuție este O(V 2+E)=O(V 2). Analiza algoritmilor – grafuri (14)

204 DIJKSTRA(G, w, s)
foreach u ϵ V do
u.d /barb2left∞
u.p /barb2leftNULL
s.d /barb2left0
Q /barb2leftV
while Q≠Ø do
u /barb2leftMIN(Q, d)
Q /barb2leftQS{u}
foreach v ϵ A[u] do
if v.d>u.d+w(u,v) then
v.d /barb2leftu.d+w(u,v)
v.p /barb2leftuAnaliza algoritmilor – grafuri (15)

Căutare în spațiul stărilor: algoritmul A*
/square6Algoritmul A*, introdus în 1968 de Hart, Nilsson și
Raphael, este o extensie și în același timp o variantă îmbunătățită a algoritmului Dijkstra care permite căutarea unei căi eficiente între două vârfuri ale unui graf.
/square6Pe lângă estimarea drumului minim față de vârful sursă salgoritmul folosește și o funcție euristică
pentru estimarea distanței față de vârful țintă t.
/square6La fiecare iterație algoritmul extrage din coada de priorități Q vârful uestimat cu distanțasSuSt minimă. Analiza algoritmilor – grafuri (16)

206 A*(G, w, s, t) s=sursă, t=țintă/target
foreach u ϵ V do
u.d /barb2left∞
u.h /barb2left∞
u.f /barb2left∞
u.p /barb2leftNULL
s.d /barb2left0
s.h /barb2leftH(s, t) H=heuristic
s.f /barb2lefts.h
Q /barb2left{s} Q=openset
C /barb2leftØ C=closedset
while Q≠Ø do
u /barb2leftMIN(Q, f)
if u=t then return true Q /barb2leftQ S {u}
C /barb2leftC
U{u}
foreach v ϵ A[u] do
if v ϵ C then continue if v Q then Q /barb2leftQ
U{v}
if v.d>u.d+w(u,v) then
v.d /barb2leftu.d+w(u,v)
v.h /barb2leftH(v, t)
v.f /barb2leftv.d+v.h
v.p /barb2leftu
return false Analiza algoritmilor – grafuri (17)
∉

Algoritmul Kruskal
/square6Algoritml Kruskal este folosit pentru determinarea
arborelui parțial de cost minim G*=(V, Q) dintrSun graf conex ponderat G=(V,E), adică arborele care să
conțină toate vârfurile și care să fie minimizat di n
punct de vedere al ponderilor.
/square6Inițial Q este vid.
/square6Muchiile din E sunt sortate crescător după ponderi.
/square6Aceste muchii sunt adăugate apoi în Q, cu condiția să
nu formeze un ciclu.
/square6La final se returnează Q conținând muchiile arborel ui
parțial de cost minim. Analiza algoritmilor – grafuri (18)

KRUSKAL(G)
Q /barb2leftØ
foreach u ∈V do
CREEAZA_MULTIME(v)
SORTEAZA(E) foreach (u,v) ∈E do
if GASESTE(u) ≠ GASESTE(v) then
Q /barb2leftQ ∪(u,v)
REUNESTE(u, v)
return Q Analiza algoritmilor – grafuri (19)
Etapa cea mai costisitoare din algoritm este sortarea setu lui de muchii E.
Astfel, complexitatea algoritmului este O(E log E).

Algoritmul Prim
/square6Algoritmul Prim determină arborele parțial de cost
minim G*=(V, Q) dintrSun graf ponderat G=(V,E) pornind de la un vârf sursă s, care este adăugat în U.
/square6Și în acest algoritm Q este inițial vid.
/square6Se formează două seturi de vârfuri: U conținând vârfurile vizitate și VSU cu vârfurile nevizitate.
/square6Vârfurile se mută pe rând din VSU în U considerând
muchiile cu cost minim, care sunt și ele adăugate înQ. Analiza algoritmilor – grafuri (20)

PRIM(G, s)
Q /barb2leftØ
U /barb2left{s}
while U ≠ V
GASESTE_MIN(u, v), u ∈U, v ∈VSU
Q /barb2leftQ ∪(u,v)
U /barb2leftU ∪{v}
return Q Analiza algoritmilor – grafuri (21)
ÎntrSo implementare cu matrice de adiacență, complexit atea algoritmului
constă în parcurgerea vârfurilor și, pentru fiecare din e le, găsirea acelui
vârf cu care muchia este de cost minim, așadar implică O (V 2) operații.

211 Aplicații
1. Să se modifice clasa Graph, inclusiv metoda BFS, astfel încât
grafurile să fie reprezentate prin liste de adiacen ță în loc de
matrice de adiacență.
2. Să se implementeze în clasa Graph algoritmul de p arcurgere a
grafurilor în adâncime.
3. Să se implementeze în clasa Graph algoritmul Dijk stra care să
afișeze drumurile minime întrSun graf ponderat. Pon derile notate
cu w(u,v) pot fi păstrate în matricea de adiacență A(u,v) –
pentru asta e necesară adăugarea unei noi metode addEdge în
clasa Graph.
4. Să se implementeze în clasa Graph algoritmul Krus kal.
5. Să se implementeze în clasa Graph algoritmul Prim.
6. Să se implementeze un algoritm de colorare a graf urilor Analiza algoritmilor – grafuri (22)

Partea III
Proiectarea algoritmilor

213 /square6Divide et impera este o metodă de construire a algoritmilor.
Rezolvarea unei probleme prin această metodă constă în:
/square6împărțirea problemei în două sau mai multe subprobl eme de dimensiune
mai mică.
/square6rezolvarea subproblemelor.
/square6combinarea rezultatelor pentru obținerea soluției p roblemei inițiale.
/square6Divizarea problemei se poate face recursiv până cân d subproblemele
devin elementare și pot fi rezolvate direct.
/square6Forma generală a algoritmului de rezolvare a proble mei P de
dimensiune ncu soluția S:
DIVIZARE(P, n, S)
if n≤n0then
SOLUTIE(P, n, S)
else
SEPARARE (P, n) în (P 1, n 1), …, (P k, n k)
DIVIZARE(P 1, n 1, S 1)
… DIVIZARE(P
k, n k, S k)
COMBINARE (S 1, …, S k) în S Proiectarea algoritmilor – divide et impera (1)

214 Turnurile din Hanoi
/square6Problema turnurilor din Hanoi a fost introdusă în 1 883 de
matematicianul francez Édouard Lucas. Problema are la bază o
legendă hindusă conform căreia zeul Brahma a așezat în templul
din Benares o stivă de 64 de discuri din aur cu dia metre diferite,
pe o tijă, în ordinea descrescătoare a diametrelor. C ălugării
templului au sarcina de a muta toate discurile pe o altă tijă,
folosind și o tijă intermediară, astfel încât:
/square6La un moment dat doar un disc, aflat în vârful unei tije, poate fi
mutat pe o altă tijă;
/square6Nu este permisă așezarea unui disc de dimensiune ma i mare peste
un disc de dimensiune mai mică.
/square6Conform legendei, lumea se va sfârși atunci când că lugării își
vor termina treaba. Proiectarea algoritmilor – divide et impera (2)

215 Algoritmul HANOI
Algoritmul mută n discuri de pe tija A pe tija C fo losind tija B.
Pentru asta, trebuie mutate nS1 discuri de pe A pe B prin C,
ultimul disc de pe A pe C și apoi nS1 discuri de pe B pe C prin A.
HANOI(n, A, C, B)
if n≥1 then
HANOI(nS1, A, B, C) PRINT(A /barb2rightC)
HANOI(nS1, B, C, A) Proiectarea algoritmilor – divide et impera (3)
A B C A B C

216 Exemplu (n=2) Proiectarea algoritmilor – divide et impera (4)
A B C
A B C
A B C
A B CA /barb2rightB
A /barb2rightC
B /barb2rightC

217 Complexitatea algoritmului HANOI
Numărul de mutări poate fi descris prin recurența
Aplicăm metoda iterației:
Considerând condiția la limită T(0)=0, recurența se termină
pentru Proiectarea algoritmilor – divide et impera (5)
1) 1(2) 1(1) 1()( +− =− ++− = nT nT nT nT
( )
( )
1 12 3 2 21 20 1
2)(2) 1(22) 3(21) 3(22) 2(22) 2(21) 2(22) 1(22) 1(2)(
− −+− ⋅ =+− ⋅+− ⋅ =+− ⋅ =− ⋅+− ⋅ =+− ⋅=−+− ⋅=
q q qqnT qnTnT nT nTnT nT nTnT nT
nq qn = ⇒=−0

218 Am arătat că la limită T(0)=0, q=n. Obținem
Știm că Rezultă astfel că Complexitatea algoritmului este O(2
n), deci călugării mai au
mult de lucru… ∑ ∑∑
−
=−
=−
=
= +⋅ =+ ⋅ =
1
01
01
0
2202)(2) 0 (2)(
n
kkn
kk nn
kk n
nTT nT
∑
=+
−−=n
kn
k
xxx
01
11
121212)( − =−−=nn
nTProiectarea algoritmilor – divide et impera (6)

219 Aplicații
1. Care din algoritmii prezentați anterior au la baz ă metoda
divide et impera?
2. Să se implementeze în Java algoritmul de rezolvar e a
problemei turnurilor din Hanoi.
3. Să se implementeze în Java varianta problemei tur nurilor din
Hanoi cu 4 tije.
4. Se dă un tablou de valori întregi. Să se determin e cel mai
mare divizor comun al valorilor din tablou prin met oda divide
et impera. Este evident că putem calcula separat ce l mai
mare divizor comun pentru cele două jumătăți ale ta bloului,
iar soluția este cel mai mare divizor comun al celo r două.
Procesul de divizare continuă până când se ajunge l a
subtablouri de un element. Proiectarea algoritmilor – divide et impera (7)

220 Algoritmii greedy aleg la fiecare moment cel mai bu n candidat
posibil. Metoda greedy face optimizări locale, cu s peranța că
acestea vor conduce la un optim global. Acești algo ritmi sunt de
obicei rapizi și furnizează o soluție relativ bună, dar nu
întotdeauna cea mai bună. Forma generală a unui alg oritm
greedy: GREEDY(C)
S /barb2leftØ
while C≠Ø do
x /barb2leftBEST(C)
C /barb2leftCS{x}
if FEASIBLE(S
U {x}) then
S /barb2leftS U {x} Proiectarea algoritmilor – greedy (1)

221 Problema fracționară a rucsacului
Se consideră că dispunem de un rucsac cu o anumită capacitate G (greutate maximă) și de nobiecte, definite prin
greutate gși prețp. Să se umple rucsacul cu obiecte, astfel
încât valoarea totală să fie maximă. Pot fi introdu se și
fracțiuni din obiecte. Proiectarea algoritmilor – greedy (2)

222 /square6Algoritmul greedy pentru rezolvarea problemei fracț ionare a
rucsacului constă în următorii pași: 1. v[i] /barb2left p[i]/g[i], ;
2. sortează vectorii v, p, g în ordinea descrescăto are a valorilor din v;
3. caută k astfel încât
soluția fiind
/square6Timpul de execuție al algoritmului este O(nlgn), de oarece sortarea
se execută în O(nlgn), iar complexitatea operației de căutare din
pasul 3 este O(n). Proiectarea algoritmilor – greedy (3)
∑ ∑
=+ =
<≤k
ik
jj i g G g
11
1n i, 1=

+ −=
∑
=k
iii
k pentrug Gk i pentrug
11,, 1 ,

223 Proiectarea algoritmilor – greedy (4)
Coduri Huffman
/square6Codificarea Huffman este o tehnică foarte utilă pen tru compactarea datelor.
Algoritmul greedy propus de David Albert Huffman of eră o modalitate optimă de
reprezentare a caracterelor prin coduri binare unic e.
/square6Fie un fișier cu 100 de caractere care conține doar literele aSf, cu următoarele
frecvențe:
/square6Dacă folosim un cod binar de lungime fixă, avem nev oie de trei biți pentru a
reprezenta șase caractere (a=000, b=001, …, f=101 ). Această metodă necesită
300 de biți pentru codificarea celor 100 de caracte re din fișier.
/square6O codificare cu lungime variabilă, care atribuie co duri scurte caracterelor frecvente
și coduri lungi caracterelor cu frecvență redusă, p oate codifica fișierul prin 224 de
biți (45×1+13×3+12×3+16×3+9×4+5×4), economisind 25% din spațiu.
/square6O codificare optimă pentru un fișier este reprezent ată printrSun arbore binar
complet. Caracter a b c d e fFrecvență 45 13 12 16 9 5Cod cu lungime fixă 000 001 010 011 100 101 Cod cu lungime variabilă 0 101 100 111 1101 1100

224 Decodificarea
/square6Codurile și lungimile acestora se generează de algo ritm astfel
încât distincția simbolurilor este asigurată.
/square6În exemplul anterior
/square6a = 0
/square6b = 101
/square6c = 100
/square6d = 111
/square6e = 1101
/square6f = 1100
/square6Astfel, dacă un cod începe cu 0 e format dintrSun s ingur bit și
este “a”. Dacă începe cu 1, sigur e format din cel puțin trei biți,
iar dacă primii trei biți sunt 110 înseamnă că exis tă și un al
patrulea bit, etc.
/square6De exemplu, decodificând pas cu pas secvența binară
1000110011010, veți obține cuvântul “cafea”. Proiectarea algoritmilor – greedy (5)

225 Construcția unui cod Huffman
/square6Algoritmul Huffman pornește de la |C| frunze, fieca re
reprezentând câte un caracter c ϵ C cu o frecvență d ată f[c].
/square6Se realizează |CS1| operații de fuzionare, până la obținerea
arborelui final.
/square6La fiecare pas, se aleg doi arbori (inițial frunze) cu frecvența cea
mai redusă și se înlocuiesc cu arborele obținut pri n fuzionarea
lor. Frecvența noului arbore este suma frecvențelor celor doi
arbori care au fuzionat.
/square6Prin fuzionarea a doi arbori A 1și A 2se obține un nou arbore
binar, în care arborii A 1și A 2 sunt fii stâng respectiv drept al
rădăcinii.
/square6În arborele final frunzele sunt caracterele și inte rpretăm codul
binar pentru un caracter ca fiind drumul de la răda cină până la
frunza corespunzătoare, unde o deplasare pe fiul st âng este
reprezentată prin 0, iar o deplasare pe fiul drept prin 1. Proiectarea algoritmilor – greedy (6)

226 Construcția unui cod Huffman Proiectarea algoritmilor – greedy (7)
f:5 c:12 b:13 d:16 e:9 a:45 c:12 b:13 d:16
f:5 e:9 a:45 14
0 1
c:12 b:13 d:16
f:5 e:9 a:45 14
0 125
0 1
c:12 b:13 d:16
f:5 e:9 a:45
14
0 125
0 130
0 1
c:12 b:13 d:16
f:5 e:9 a:45
14
0 125
0 130
0 155
0 1
c:12 b:13 d:16
f:5 e:9 a:45
14
0 125
0 130
0 155
0 1100
0 1

227 Algoritmul lui Huffman
HUFFMAN(C)
n /barb2left|C|
Q /barb2leftC
for i /barb2left1 to nS1 do
z /barb2leftCREATENODE()
x /barb2leftz.st /barb2leftMIN(Q)
Q /barb2leftQS{x}
y /barb2leftz.dr /barb2leftMIN(Q)
Q /barb2leftQS{y}
z.cheie /barb2leftx.cheie + y.cheie
Q.INSERT(z)
return MIN(Q) Proiectarea algoritmilor – greedy (8)

228 Complexitatea algoritmului Huffman
/square6Presupunem implementarea structurii Q sub forma unui heap binar.
/square6Astfel, construirea lui Q prin reconstituire
heap, poate fi realizată în O(n).
/square6Bucla for are nS1 iterații în care apelează operații heap de complexitate O(lgn).
/square6Rezultă un timp total de execuție, pe o mulțime de n caractere, de O(nlgn). Proiectarea algoritmilor – greedy (9)

229 Aplicații
1. Să se ilustreze construcția arborelui Huffman pe ntru
următoarele caractere și frecvențe: C={p:100, q:17, r:2, x:58, y:80, z:5} Decodificați apoi secvența binară 1111011001.
2. Stabiliți o codificare Huffman pentru următoarea secvență de
frecvențe formată din primele numere ale șirului Fi bonacci:
C={a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21}
3. Desenați arborele Huffman pentru cuvântul ABRACAD ABRA.
4. Care din algoritmii prezentați anterior au la baz ă strategia
greedy?
5. Implementați în Java algoritmul Huffman. 6. Implementați în Java problema fracționară a rucsa cului.Proiectarea algoritmilor – greedy (10)

230 /square6Conceptul de programare dinamică a fost introdus în
1957 de matematicianul american Richard Bellman.
/square6Programarea dinamică, asemenea metodei divide et impera, rezolvă probleme combinând soluțiile unor subprobleme.
/square6Programarea dinamică este aplicabilă atunci când subproblemele au în comun subSsubprobleme.
/square6Spre deosebire de metoda divide et impera, un algoritm bazat pe programare dinamică rezolvă fiecare subSsubproblemă o singură dată, memorează soluția, evitând astfel recalcularea. Proiectarea algoritmilor – programare dinamică (1)

231 Un prim exemplu: șirul lui Fibonacci
/square6Șirul lui Fibonacci este definit astfel:
/square6Arborele recursiv pentru calculul F(5) este următor ul:
/square6În cazul implementării recursive, termenii sunt det erminați de mai multe ori: F(2)
de trei ori și F(3) de două ori, pentru calculul F( 5). Astfel, varianta recursivă are
complexitate exponențială: O(2 n).
/square6Varianta iterativă memorează tot timpul rezultatele , deci are la bază programarea
dinamică. Calculând o singură dată termenii, comple xitatea este liniară: O(n). Proiectarea algoritmilor – programare dinamică (2)

> − +−==
=
1),2() 1(1, 10, 0
)(
n nF nFnn
nF
F(5)
F(4) F(3)
F(3) F(2) F(2) F(1)
F(2) F(1) F(1) F(0) F(0) F(1)
F(1) F(0)

/square6Pseudocodul algoritmului iterativ:
FIBONACCI(n)
if n≤1 then
return n
a /barb2left0
b /barb2left1
for i /barb2left2 to n do
f /barb2lefta + b
a /barb2leftb
b /barb2leftf
return f
/square6Există o variantă de calcul și mai rapidă, care cal culează direct un
anumit termen al șirului lui Fibonacci (deci cu o c omplexitate constantă
O(1)), introdusă de Binet în 1843: unde Φ este secțiunea de aur, având valoarea: Proiectarea algoritmilor – programare dinamică (3)
5)(n n
nF−Φ−−Φ=
251+=Φ

233 Cel mai lung subșir crescător
/square6Fie A un șir de nnumere întregi. Se cere
determinarea subșirului crescător de lungime maximă, nu neapărat contiguu, în șirul A.
/square6Pentru rezolvarea problemei construim vectorii:
/square6L[i] = lungimea subșirului crescător care începe pe poziția i
și are ca prim element A[i].
/square6S[i] = k, succesorul elementului A[i] în subșirul c rescător, cu
L[k]=max{L[j]| j>i și A[j]>A[i]}, iar S[i]=S1 dacă nu există
un astfel de succesor.
/square6Cel mai lung subșir crescător va începe pe acea poziție i în A pentru care L[i] este maxim, iar afi șarea
se poate face cu ajutorul vectorului S. Proiectarea algoritmilor – programare dinamică (4)

234 Algoritmul de determinare a subșirului crescător ma ximal
CMLSC(A)
imax /barb2leftn
for i /barb2leftn downto 1 do
S[i] /barb2leftS1
L[i] /barb2left1
for j /barb2lefti+1 to n do
if A[j]>A[i] and L[j]+1>L[i] then
L[i] /barb2leftL[j]+1
S[i] /barb2leftj
if L[i]>L[imax] then
imax /barb2lefti
i /barb2leftimax
while i≠S1 do
PRINT(A[i]) i /barb2leftS[i] Proiectarea algoritmilor – programare dinamică (5)

235 Proiectarea algoritmilor – programare dinamică (6)
Exemplu:
/square6Fie șirul de întregi:
A=3, 5, 76, 1, 45, 2, 68, 52, 90, 0, 4, 15
/square6Aplicând algoritmul CMLSC, obținem
/square6Astfel, cel mai lung subșir crescător este:
3, 5, 45, 68, 90 A 3 5 76 1 45 2 68 52 90 0 4 15 L54 2 4 3 3 2 2 1 3 2 1
S 2 5 9 5 7 7 9 9 S1 11 12 S11 2 3 4 5 6 7 8 9 10 11 12

236 Complexitatea algoritmului CMLSC
/square6Operațiile din bucla for exterioară, de cost c 1, sunt
apelate de n ori.
/square6Numărul de apeluri ale operațiilor din bucla for interioară,
de cost c 2, este
/square6Operațiile din bucla while , de cost c 3, sunt executate de
cel mult n ori.
/square6Astfel, complexitatea algoritmului este Proiectarea algoritmilor – programare dinamică (7)
2) 1(1…211
1−= =−+++ ∑−
=nnk nn
k
)(2) 1(2 2
3 21 nOc bn anncnncnc =+ + = +−+

237 Proiectarea algoritmilor – programare dinamică (8)
Aplicații propuse
1. Se consideră un triunghi de numere, reprezentat î ntrSo matrice A, ca
în exemplul de mai jos: și o bilă care cade în jos sau spre dreaptaSjos. Să se determine
drumul prin care bila ar strânge numărul maxim de p uncte. Se va
folosi o matrice P de predecesori (S1=nu există, 1= pas în jos, 0=pas
spre dreaptaSjos) și o matrice S pentru sumele maxi me.
2. Se dau pozițiile de start și de final respectiv d imensiunea tablei de
șah. Se cere determinarea celui mai scurt drum al u nui cal între cele
două poziții. Se va folosi o matrice L care să păst reze lungimea
minimă din fiecare poziție a tablei de șah și un ta blou P de
predecesori. 10 82 81
4 6 10
2 14 35 7
41 3 52 26 15
32 90 11 87 56 23
54 65 89 32 71 9 31

238 /square6Backtracking este o metodă de căutare sistematică c u încercări repetate și
reveniri în caz de nereușită.
/square6Soluția este construită în mod progresiv, prin adău garea câte unei componente
Sk+1 la o soluție parțială (S 1,S 2,…,S k) care reprezintă o selecție din primele k
oferte din totalul celor n, astfel încât (S 1,S 2,…S k,S k+1 ) formează o nouă soluție
parțială.
/square6Soluția finală se obține în momentul în care selecț ia cuprinde toate cele n oferte,
deci k=n.
/square6Metoda backtracking este în general ineficientă, av ând complexitate
exponențială. De aceea, se folosește doar atunci câ nd nu există metode mai
eficiente de rezolvare a problemei.
/square6Forma generală a algoritmului backtracking recursiv :
BACKTRACKING(k)
for i /barb2left1 to n do
if ACCEPT(k, i) then
S[k] /barb2lefti
if FINAL(k) then
return S
else BACKTRACKING(k+1) Proiectarea algoritmilor – backtracking (1)

239 Problema celor n regine
/square6Fie o tablă de șah de dimensiune n x n. Determinați toate
posibilitățile de a amplasa n regine pe această tab lă, astfel încât
ele să nu se atace reciproc. Două regine se atacă r eciproc dacă se
află pe aceeași linie, coloană sau diagonală.
/square6Prima observație este că pe fiecare linie poate fi amplasată o
singură regină. Astfel, pentru o tablă de șah de di mensiune n x n,
problema celor n regine poate fi reprezentată print rSun tablou de n
elemente, unde S[k]=i semnifică o regină amplasată pe poziția
(k,i) a tablei de șah.
/square6Condiția ca două regine i și j să nu fie pe aceeași coloană este
S[i]≠S[j].
/square6Condiția ca două regine i și j să nu fie pe aceeași diagonală este
|jSi|≠|S[j]SS[i]|.
/square6Pentru n=2 și 3 nu există soluții, pentru n=4 sunt două soluții, etc. Proiectarea algoritmilor – backtracking (2)

240 QUEENS(k)
for i /barb2left1 to n do
if ACCEPT(k, i) then
S[k] /barb2lefti
if k=n then
PRINT(S)
else QUEENS(k+1)
ACCEPT(k, i)
for j /barb2left1 to kS1 do
if S[j]=i then
return FALSE
if ABS(jSk)=ABS(S[j]Si) then
return FALSE
return TRUE Proiectarea algoritmilor – backtracking (3)

241 Aplicații propuse
1. Să se implementeze în Java algoritmul prezentat
pentru rezolvarea problemei celor n regine.
2. Fie o tablă de șah de dimensiune n x n. Determina ți
toate posibilitățile de a amplasa n ture pe această
tablă, astfel încât ele să nu se atace reciproc. Do uă
ture se atacă reciproc dacă se află pe aceeași lini e
sau coloană.
3. Fie o tablă de șah de dimensiune n x n și poziția de
start a calului. Să se determine toate drumurile calului care să acopere toată tabla de șah și să treacă o singură dată prin toate pozițiile. Proiectarea algoritmilor – backtracking (4)

242 /square6Un algoritm genetic este o procedură iterativă de c ăutare globală.
/square6Algoritmul procesează o populație de soluții potenț iale (cromozomi) distribuite
peste întreg spațiul de căutare.
/square6Pentru rezolvarea unei probleme folosind un algorit m genetic este necesară
definirea unei funcții F care să evalueze performan ța fiecărui cromozom.
/square6În fiecare iterație se creează o nouă populație P, numită generație. Toate
generațiile au același număr de indivizi. În genera l, noua generație constă din
indivizi mai performanți.
/square6Evoluția spre optimul global este asigurată prin re combinarea (încrucișarea) și
modificarea (mutația) cromozomilor.
/square6Condiția de oprire se referă, de regulă, la atinger ea unui anumit număr de
generații ng.
/square6Forma generală a algoritmului genetic fundamental: P
1/barb2leftRANDOM()
for t /barb2left1 to ng do
EVALUARE(P t)
P = SELECTIE(P t)
P’/barb2leftRECOMBINARE(P)
Pt+1 /barb2leftMODIFICARE(P’)Proiectarea algoritmilor – algoritmi genetici (1)

243 /square6Evaluarea populației de cromozomi
/square6Selecția
/square6Se calculează suma valorilor obținute în urma evalu ării
/square6Se determină probabilitățile cumulative de selecție
/square6Pentru selecția noii populații se generează aleator n cvalori
subunitare. Fiecare valoare r i generată aleator va selecta acel
cromozom c kpentru care r iϵ [p k, p k+1 ].
/square6Recombinarea a doi cromozomi constă în interschimba rea unor
gene (biți).
/square6Modificarea unui cromozom constă în inversarea unor gene (biți). Proiectarea algoritmilor – algoritmi genetici (2)
c i i n i cFv , 1),( = =
∑
==cn
iiv S
1
1,, 1,
1= = =∑
=cn cj
ii
j p n jSvp

244 Determinarea maximului unei funcții
/square6Se va determina maximul unei funcții F(x), definită în exemplul nostru SIN(x).
Maximul se caută în intervalul [li, ls], deci xϵ[li , ls].
/square6Funcția X(v) normalizează valoarea v, aducândSo în intervalul [li, ls].
/square6Funcțiile GETBIT(v, i), SETBIT(v, i) și RESETBIT(v, i) preiau, setează respectiv
resetează bitul de pe poziția i din v.
/square6Funcția INCRUCISARE(C, p1, p2) recombină biții crom ozomilor p1 și p2.
/square6Funcția MUTATIE(C, p) modifică cromozomul p.
/square6Funcția INITIALIZARE inițializează populația de cro mozomi cu valori generate aleator.
/square6Funcția SELECTIE evaluează populația de cromozomi ș i generează o populație nouă
păstrând doar cromozomii performanți.
/square6Funcția RECOMBINARE realizează o selecție în vedere a încrucișării.
/square6Funcția MODIFICARE realizează operația de mutație a populației de cromozomi.
/square6Funcția MAX reprezintă algoritmul genetic în sine, care determină maximul funcției
F(x), cu xϵ[li, ls]. Funcția folosește o populație C de nc cromozomi. Căutarea se
termină după ng=50 de generații. Proiectarea algoritmilor – algoritmi genetici (3)

245 li /barb2left0
ls /barb2left2
nc /barb2left500
ng /barb2left50
pincrucisare /barb2left0.3
pmutatie /barb2left0.1
X(v)
return li+v/65535*(lsSli)
F(x)
return SIN(x)
GETBIT(v, i)
return v>>i&1
SETBIT(v, i)
return v|(1<<i)
RESETBIT(v, i)
return v&~(1<<i) Proiectarea algoritmilor – algoritmi genetici (4)

246 INCRUCISARE(C, p1, p2)
v1 /barb2leftC[p1]
v2 /barb2leftC[p2]
r /barb2leftRANDOM(0, 16)
for j /barb2leftr to 16 do
if GETBIT(v2, j)=1 then
SETBIT(C[p1], j)
else RESETBIT(C[p1], j)
if GETBIT(v1, j)=1 then
SETBIT(C[p2], j)
else RESETBIT(C[p2], j)
MUTATIE(C, p)
cp /barb2leftC[p]
for j /barb2left1 to 16 do
if pmutatie>RANDOM(0, 1) then
if GETBIT(cp, j)=1 then
RESETBIT(cp, j)
else SETBIT(cp, j)
if F(X(cp))>F(X(C[p])) then
C[p] /barb2leftcp Proiectarea algoritmilor – algoritmi genetici (5)

247 INITIALIZARE(C)
for i /barb2left1 to nc do
C[i] /barb2leftRANDOM(0, 65536)
xmax /barb2leftX(C[1])
fmax /barb2leftF(xmax)
SELECTIE(C)
s /barb2left0
for i /barb2left1 to nc do
V[i] /barb2leftF(X(C[i]))
s /barb2lefts+V[i]
P[1] /barb2leftV[1]/s
for i /barb2left2 to nc do
P[i] /barb2leftP[iS1]+V[i]/s
for i /barb2left1 to nc do
r /barb2leftRANDOM(0, 1)
for j /barb2left1 to nc do
if r>P[j] and r≤P[j+1] then
C’[i] /barb2leftC[j]
for i /barb2left1 to nc do
C[i] /barb2leftC’[i] Proiectarea algoritmilor – algoritmi genetici (6)

248 RECOMBINARE(C)
primul /barb2leftTRUE
for i /barb2left1 to nc do
if RANDOM(0, 1)<pincrucisare then
if primul then
primul /barb2leftFALSE
p1 /barb2lefti
else
primul /barb2leftTRUE
p2 /barb2lefti
INCRUCISARE(C, p1, p2)
MODIFICARE(C)
for i /barb2left1 to nc do
MUTATIE(C, i) Proiectarea algoritmilor – algoritmi genetici (7)

249 MAX(ng)
INITIALIZARE(C) for t /barb2left1 to ng do
SELECTIE(C) RECOMBINARE(C) MODIFICARE(C) maxiteri /barb2left1
maxiterf /barb2leftF(X(C[1]))
for i /barb2left2 to nc do
if F(X(C[i]))>maxiterf then
maxiteri /barb2lefti
maxiterf /barb2leftF(X(C[i]))
if maxiterf>fmax then
fmax /barb2leftmaxiterf
xmax /barb2leftX(C[maxiteri])
PRINT(xmax, fmax) Proiectarea algoritmilor – algoritmi genetici (8)

250 Aplicații propuse
1. Să se implementeze în Java algoritmul genetic pre zentat.
2. Să se modifice algoritmul genetic prezentat astfe l încât să
determine minimul unei funcții. Să se implementeze algoritmul modificat în Java.
3. Să se implementeze un algoritm genetic pentru rez olvarea
problemei comisSvoiajorului ( traveling salesman problem ). Se
consideră n orașe și se cunosc distanțele dintre or icare două
orașe. Un comisSvoiajor trebuie să treacă prin toat e cele n
orașe. Se cere să se determine drumul minim care să
pornească dintrSun oraș oarecare, să treacă o singu ră dată
prin toate orașele celelalte și să revină în orașul inițial. Proiectarea algoritmilor – algoritmi genetici (9)

251 /square6Rețelele neuronale sunt folosite pentru rezolvarea unor
probleme dificile, cum sunt cele de estimare, ident ificare și
predicție.
/square6Există probleme practice de mare complexitate pentr u care
elaborarea unui algoritm este dificilă sau chiar im posibilă.
/square6Pornind de la o mulțime de exemple, rețelele neuron ale sunt
capabile să sintetizeze un model al problemei. Un m are avantaj
al rețelelor neuronale constă în capacitatea lor de a învăța din
exemple și apoi să trateze cazuri similare.
/square6Rețelele neuronale sunt formate dintrSo multitudine de neuroni,
elemente simple de calcul care operează în paralel.
/square6Modelul de neuron a fost propus de McCulloch și Pit ts în 1943.
Hebb a introdus în 1949 un mecanism de învățare pri n
modificarea conexiunilor sinaptice dintre neuroni. Rosenblatt a
propus apoi în 1957 primul model de rețea neuronală numită
perceptron, care interconectează o mulțime de neuro ni. Proiectarea algoritmilor – rețele neuronale (1)

252 Perceptronul multistrat
/square6Structura perceptronului multistrat cu un singur st rat ascuns este
prezentată în figura următoare:
/square6Fiecare intrare x iîntrSun neuron are asociată o pondere w i. Ieșirea
neuronului se obține prin însumarea ponderată a int rărilor,
asupra căreia se aplică o funcție de activare. Proiectarea algoritmilor – rețele neuronale (2)
VIN VHID
VOUT x1
xNo1
oP
∑
=⋅ =n
ii ixw y
1

253 Proiectarea algoritmilor – rețele neuronale (3)
Funcții de activare
/square6Funcția de activare are rolul de a restrânge domeni ul de variație al
ieșirii neuronului. Cele mai uzuale funcții de acti vare sunt următoarele:
/square6Vom folosi în continuare funcția de activare
care restrânge ieșirea neuronului la intervalul (S1 , 1). yeyf−+=11)(
yyyy
eeyf−−
+−=
11)(
11
-1
yy
eeyf−−
+−=
11)(

254 Algoritmul de învățare backpropagation [Mit97]
/square6Algoritmul backpropagation ajustează ponderile rețelei neuronale astfel
încât eroarea să scadă
/square6Algoritmul de învățare backpropagation, cu funcția de activare
și intrări codificate cu S1 și 1, constă în următor ii pași:
1. Se creează o rețea neuronală cu N intrări, M unită ți ascunse și P
unități de ieșire.
2. Se inițializează ponderile
cu valori aleatoare mici [Mit97] din intervalul (S0 .05, 0.05). Proiectarea algoritmilor – rețele neuronale (4)
yy
eeyf−−
+−=11)(
P kM j wM jN iw
jkij
, 1;, 1;, 1;, 1;
21
= == =

255 3. Cât timp repetă
3.1. Se aplică rețelei intrarea și se calculează ieșirea
3.2. Pentru fiecare neuron din stratul de ieșire
se calculează eroarea față de valoarea corec tă tkProiectarea algoritmilor – rețele neuronale (5)
1X2O
P k netf oP k x w netM j netf o xM j xw net
k kM
jj jk kj j jN
ii ij j
…,, 1),(…,, 1,…,, 1),(…,, 1,
2 2122 21 12111 1
= == ⋅ == = == ⋅ =
∑∑
==
P k k, 1, =
2
kδ
( ) ( )( )222 22 2121)(k k k k k k k k oo ot netf ot ⋅ −⋅ −⋅= ′⋅ − =
δ( ) ( ) T ot WEP
kk k > − ⋅=∑
=122
21

256 3.3. Pentru fiecare neuron din stratul ascuns
se calculează eroarea
3.4. Se actualizează toate ponderile rețelei neuronale
unde este rata de învățare. Proiectarea algoritmilor – rețele neuronale (6)
M jj, 1,=
1
jδ
( )∑ ∑
= =⋅ ⋅⋅ −⋅= ′⋅ ⋅ =P
kjk k j jP
kj jk k j w oo netf w
12211
11221121)(δ
δ
δ
M j N i x w wP k M j x w w
i j ij ijj k jk jk
, 1,, 1,, 1,, 1,
11 1122 22
= = ⋅⋅+ == = ⋅⋅+ =δ
αδ
α
α

/square6În continuare este prezentat pseudocodul algoritmul ui
backpropagation, considerând N intrări, M unități a scunse și P
ieșiri.
/square6Am notat cu:
/square6alpha S rata de învățare
/square6input S vectorul de intrare (cu valorile codificate cu S 1 și 1)
/square6neth S vectorul cu valorile stratului ascuns înainte de ac tivare
/square6whin S matricea ponderilor dintre stratul ascuns și de int rare
/square6bhin S vectorul bias aferent stratului ascuns
/square6hidd S vectorul cu valorile stratului ascuns după activare
/square6neto S vectorul cu valorile de ieșire înainte de activare
/square6wohi S matricea ponderilor dintre stratul de ieșire și asc uns
/square6bohi S vectorul bias aferent stratului de ieșire
/square6out S vectorul cu valorile de ieșire după activare
/square6deltaout S vectorul de erori aferent stratului de ieșire
/square6deltain S vectorul de erori aferent stratului ascuns
/square6target S vectorul cu ieșirile corecte (folosit în etapa de învățare). Proiectarea algoritmilor – rețele neuronale (7)

alpha /barb2left0.3
input[N] neth[M] whin[M,N] bhin[M] hidd[M] neto[P] wohi[P,M] bohi[P] out[P] deltaout[P] deltain[M] GENERARE_PONDERI()
wi /barb2left4.0/N
hwi /barb2left2.0/N
for i /barb2left1 to M do
bhin[i] /barb2left(RANDOM(0, 10000) % FLOOR(wi*100))/100.0Shwi
for j /barb2left1 to N do
whin[i,j] /barb2left(RANDOM(0, 10000) % FLOOR(wi*100))/100.0Shwi
for i /barb2left1 to P do
bohi[i] /barb2left(RANDOM(0, 10000) % FLOOR(wi*100))/100.0Shwi
for(j /barb2left1 to M do
wohi[i,j] /barb2left(RANDOM(0, 10000) % FLOOR(wi*100))/100.0Shwi
F(x)
return (1SEXP(S1*x))/(1+EXP(S1*x)) Proiectarea algoritmilor – rețele neuronale (8)

dF(x)
return (1S(F(x)*F(x)))/2
FORWARD(input[])
for i /barb2left1 to M do
neth[i] /barb2leftbhin[i]
for j /barb2left1 to N do
neth[i] /barb2leftneth[i] + whin[i,j]*input[j]
hidd[i] /barb2leftF(neth[i])
for i /barb2left1 to P do
neto[i] /barb2leftbohi[i]
for j /barb2left1 to M do
neto[i] /barb2leftneo[i] + wohi[i,j]*hidd[j]
out[i] /barb2leftF(neto[i])
BACKWARD(target[], input[])
for i /barb2left1 to P do
for j /barb2left1 to M do
deltaout[i] /barb2left(target[i]Sout[i]) * dF(neto[i])
wohi[i,j] /barb2leftwohi[i,j] + alpha*deltaout[i]*hidd[j]
bohi[i] /barb2leftbohi[i] + alpha*deltaout[i]
for i /barb2left1 to M do
for j /barb2left1 to N do
deltain[i] /barb2left0
for k /barb2left1 to P do
deltain[i] /barb2leftdeltain[i]+deltaout[k]*wohi[k,i]*dF(neth[i])
whin[i,j] /barb2leftwhin[i,j] + alpha*deltain[i]*input[j]
bhin[i] /barb2leftbhin[i] + alpha*deltain[i]Proiectarea algoritmilor – rețele neuronale (9)

260 Aplicații propuse
1. Să se rescrie algoritmul backpropagation pentru funcția de
activare
2. Să se implementeze în Java o rețea neuronală cu u n strat
ascuns care, pe baza algoritmului backpropagation prezentat, să
învețe cifrele 0S9.
3. Să se implementeze în Java o rețea neuronală cu un str at
ascuns care, folosind algoritmul backpropagation , să învețe
literele alfabetului limbii engleze.Proiectarea algoritmilor – rețele neuronale (10 )
yeyf−+=11)(

261 Nota finală
Nota laborator (NL) = 0,5*T + 0,5*C Nota finală = 0,4*NL + 0,6*E
/square6T = Test susținut la laborator din aplicațiile prop use la laborator
în cadrul capitolului Limbajul Java ;
/square6C = Colocviu de laborator din aplicațiile propuse l a laborator în
cadrul capitolelor Analiza algoritmilor respectiv Proiectarea
algoritmilor ;
/square6E = Examen susținut din capitolele Analiza algoritmilor și
Proiectarea algoritmilor .

262 Bibliografie
Algoritmi
[Knu00] Knuth D., Arta programării calculatoarelor , Vol. 1 –Algoritmi fundamentali , Teora, 2000.
[Knu02] Knuth D., Arta programării calculatoarelor , Vol. 3 –Sortare și căutare , Teora, 2002.
[Cor00] Cormen T., Leiserson C., Rivest R., Introducere în algoritmi , Agora, 2000.
[Giu04] Giumale C., Introducere în analiza algoritmilor , Polirom, 2004.
[Log07] Logofătu D., Algoritmi fundamentali în Java , Polirom, 2007.
[Wai01] Waite M., Lafore R., Structuri de date și algoritmi în Java , Teora, 2001.
[Cri98] Cristea V., Athanasiu I., Kalisz E., Iorga V ., Tehnici de programare , Teora 1998.
[Mit97] Mitchell T., Machine Learning , McGrawSHill, 1997.
Programare în Java
[Blo17] Bloch J., Effective Java, Third Edition, Ad disonSWesley Professional, 2017.
[Rob00] Roberts S., Heller P., Ernest M., Complete Java 2 Certification , Second Edition, SYBEX, USA, 2000.
[Cha01] Chan M., Griffith S., Iasi A., Java 1001 secrete pentru programatori , Teora, 2000.
[Tan07] Tanasă Ș., Andrei Ș., Olaru C., Java de la 0 la expert , Polirom, 2007.
[Hun01] Hunter J., Crawford W., Java Servlet Programming , Second Edition, O’Reilly, USA, 2001.
[Gea01] Geary D., Advanced JavaServer Pages , Prentice Hall, USA, 2001.
[Gor98] Gordon R., Java Native Interface , Prentice Hall, USA, 1998.

263 Webliografie
[Web01] http://java.sun.com/docs/codeconv/html/CodeConvTOC. doc.html
[Web02] http://www.javapassion.com/javaintro/
[Web03] http://thor.info.uaic.ro/~acf/java/curs/cursuri.htm l
[Web04] http://labs.cs.utt.ro/labs/sdaa/html/LabSDA.html
[Web05] http://www.personal.kent.edu/~rmuhamma/Algorithms/a lgorithm.html