curs 1 - di

Proiectarea Algoritmilor

I CA: Stefan Trausan-Matu [email protected]

I CB: Traian Rebedea [email protected]

I CC: Costin Chiru [email protected]

Proiectarea Algoritmilor 2015


Obiectivele cursului (I)

Cunoaterea unui set important de algoritmi i metode de rezolvare a problemelor de

algoritmic curs

Dezvoltarea abilitilor de adaptare a unui algoritm la o problem din viaa real. laborator/teme/proiect

Dezvoltarea abilitilor de lucru n echip. proiect


Obiectivele cursului (II)

Utilizarea teoriei predate la curs pentru proiectarea algoritmilor de rezolvare pentru probleme tipice ntlnite n practica dezvoltrii sistemelor de programe.

Discutarea relaiei dintre caracteristicile problemelor, modul de rezolvare i calitatea soluiilor.

Compararea variantelor unor algoritmi pentru rezolvarea problemelor dificile.

De ce s nv PA?

Exemple de utilizri ale PA-ului in diferite meserii:

web developer web social, teoria grafurilor, data mining, clustering;

game dev cutri, grafuri, inteligen artificial;

project manager fluxuri, grafuri de activiti;

dezvoltator de sisteme de operare structuri de date avansate, scheme de algoritmi;

programator tot ce tine de algoritmi, in special complexitate si eficien;

tester tot ce tine de algoritmi, in special complexitate, eficien si debugging;



Planul cursului (I)

Scheme de algoritmi Caracteristici ale problemelor i tehnici asociate de

rezolvare: divide & impera (Merge Sort, puterea unui numr), rezolvare lacom (arbori Hufmann, problema rucsacului continu), programare dinamic (nmulirea matricelor, AOC, problema rucsacului discret). Backtracking cu optimizri. Propagarea restriciilor.

Algoritmi pentru jocuri Minimax i -.

Algoritmi pentru grafuri Algoritmi pentru grafuri: parcurgeri, sortare topologic,

componente tare conexe, articulaii, puni, arbori minimi de acoperire, drumuri de cost minim, fluxuri.


Planul cursului (II)

Rezolvarea problemelor prin cutare euristic

Rezolvarea problemelor prin cutarea euristic A*. Completitudine i optimalitate, caracteristici ale euristicilor.

Algoritmi aleatorii

Algoritmi aleatori. Las Vegas i Monte Carlo, aproximare probabilistic.


Evaluarea

Citii documentul Regulament Proiectarea Algoritmilor 2015 de pe site! http://ocw.cs.pub.ro/courses/pa/regulament-general

Examen 4 p

Laborator 6 p 3p teme (3 teme punctate egal) // incepnd de anul acesta, nu mai exist tem de recuperare

2p laborator (1p activitate laborator, 1p test practic)

2p proiect

Activitate tiinific maxim 0,5 1 p bonus (n funcie de realizri)

Obs. 1 - Nu se copiaz in facultate!

Obs. 2 - Prima tem copiat se puncteaz cu minus valoarea maxim a temei. La a doua tema copiat, se repet materia!


Proiect PA

Tema proiectului: TBA (To Be Announced)

Obiective:

Rezolvarea unei probleme interesante din viaa real;

Gsirea si aplicarea unor euristici pentru aceast problem;

Dezvoltarea abilitilor de lucru n echip;

Dezvoltarea spiritului competitiv.


Proiect PA (2)

Etape:

1. Formarea echipelor.

2. Familiarizarea cu frameworkul cu care se va lucra (micarea furnicilor pe hart, acumularea de hran i nmulirea lor).

3. Lupta cu un bot extrem de slab pe diverse plane.

4. Lupta cu un bot ceva mai inteligent pe diverse plane.

5. Finalizare proiectului i concursul pentru stabilirea celei mai bune colonii de furnici din an.

Mai multe informaii n Regulament Proiect PA 2015


Feedback 2008, 2009

Idei preluate din feedback 2008: Schimbarea modului de organizare al proiectului (etape, mod

de lucru in echip).

Schimbarea orientrii temelor (variante mai uoare, notare parial).

Subliniat importana bibliografiei.

Idei preluate din feedback 2009: Eliminare restricii echipa proiect la nivel de grup.

Publicare teme pe infoarena / checker teme.

Fr net n laboratoare.

Laboratoare mai bune, teme mai atent elaborate, organizare mai bun.

Evitat ora 8 dimineaa pentru curs.


Feedback 2010 (1)

Curs:

Prea puine 2 ore. (nu avem ce face, aa e in program)

Evitat ora 8 dimineaa pentru curs. (Am reuit!!!)

Pseudocod uniform - romn sau englez. (Am trecut totul n romn)

Evitarea greelilor din cursuri. (mi cer scuze de pe acum pentru eventualitatea in care mai apar)

Laborator:

Prea grele. (am ncercat s le uurm prin introducerea de schelete de cod)

Furnizare de rezolvri. (am nceput anul trecut sperm s fie ok anul acesta)

Laboratoare mai clare si mai uniforme din punctul de vedere al scheletului de

cod. (dou persoane vor scrie codul de la laboratoare C++/Java)

Preri mprite referitoare la absena internetului din laborator. (niciodat nu vom putea s mpcm pe toat lumea!)

Feedback 2010 (2)

Teme:

Mai puine (3 in loc de 4) si mai utile. (vor fi 3 teme)

Corectate mai repede si uniform pe serii. (fiecare tem va fi corectat de ctre o singur persoan pe serie)

Tem de recuperare peste var. (va fi disponibil o astfel de tem)

Proiect:

Schimbarea ahului. (F1- ants)

Interesant competiia final. (ne bucurm!, am pstrat-o)

E bine c este pe grupe abiliti de lucru in echip. (asta ne i dorim!)

Punctai si cei care nu intr n grupe. (ncercm s schimbm punctarea se va face un clasament general deoarece vom ncerca s facem meciuri fiecare cu fiecare)

Examen:

Timp prea scurt. (deja am dublat timpul fata de acum doi ani, mai mult de att nu vi se va

pune la dispoziie!)

Examen greu!


Feedback 2011 (1)

Curs:

Demonstraii prea multe/puine n curs s se dea mai multe demonstraii la examen! (prerile sunt mprite!)

Introducere de flashuri pentru a demonstra algoritmii (anul acesta nu avem cum,

dar sperm s le introducem la anul! Dac vei gsi astfel de flash-uri sau tool-uri, va rog s m anunai i pe mine ca s le pun la bibliografia cursurilor i s le poat folosi i ceilali colegi de-ai votri)

Timp prea puin la curs (2 ore) fiind necesare 3 ore cel puin, prea muli algoritmi (nu avem ce face, aa e in program)

Bazat pe crile lui Cormen i Giumale (Aa este! Este necesar citirea capitolelor din aceste cri! Vezi slide 22!)

Laborator

Introducere de schelete de cod n Java pentru laborator (sperm c vei fi mulumii de ele)

Toi studenii s aib timp sa vad din timp problemele de laborator (vor fi disponibile din timp i v ncurajm s v uitai peste probleme i peste laborator nainte de a face laboratorul)


Feedback 2011 (2)

Teme

Teme bine alese, care reflect probleme reale i sunt n concordan cu materia predat (vom ncerca i anul acesta s dm teme cel puin la fel de interesante)

Proiect

Acordare premii pentru ctigtorii concursului de la proiect (ncercm s gsim sponsori pentru o astfel de iniiativ)

Erori in serverul de proiect (au fost eliminate astfel de erori ntruct anul acesta am

schimbat proiectul i vom folosi o platform care deja i-a demonstrat valoarea ntr-un concurs internaional)

Overall

Entuziasm din partea echipei (ne pare bine c a fost remarcat acest aspect! Sperm s avei parte de acelai entuziasm)


Feedback 2012 (1)

Curs Complexitatea materiei este cu mult peste numarul

alocat in orar (2 ore curs, 2 ore laborator).

Timpul dedicat cursului a fost prea putin si cateodata se mergea foarte repede, se explica rapid doar pentru a ne incadra in timp. trebuie sa acopar materia

mult mai mult de 3 ore; asa e in programa Daca nu se face de 3 ore sugerez sa se predea mai

succint totul, ramanand sa aprofundeze copiii acasa.. ca doar sunt la facultate nu la clasa a patra.

ar putea fi scoase multe din teoremele si demonstratiile din slide-urile de curs nu se poate

Putine probleme (aplicatii, exemple de probleme) discutate la curs. asta se face la laborator


Feedback 2012 (2)

Examen Timp mai mult la examene si mai putine subiecte, nu trebuie

sa fim presati de timp, in plus nu trebuie ca dupa fiecare subiect sa ni se ia foile. ne scuteste de facut politie + veti lucra mereu sub presiunea timpului, nu ar strica sa va obisnuiti

Laborator scheletul de cod ar fi bine sa fie pus pe site din timp.

notele de la teme si laborator apar cu intarziere (4-5 saptamani); sper ca nu vor mai fi probleme

unele exercitii sa fie mai usoare pentru ca 2 ore nu sunt suficiente pentru unii sa rezolve probleme propuse la laborator. am transmis asistentilor acest lucru

sa nu se mai suprapuna temele si proiectul ca deadline cu celelalte teme. problema mai complexa


Feedback 2013

Cadrul didactic a fost bine pregatit pentru sustinerea?

Cursuri: 4.76 / 6

Laboratoare:/Seminarii: 4.78 / 6

Pot fi obtinute explicatii suplimentare in afara orelor de?

Cursuri: 4.31 / 6


Materialele puse la dispozitie sunt suficiente pentru

intelegerea?

Cursuri: 4.33 / 6


Numarul si dificultatea temelor au fost adecvate? 3.76 / 6


Feedback 2013 (2)

Aspecte pozitive

Materia este frumoasa, importanta, bine predata, utila in multe

domenii nu neaparat programare

Exemple relevante la curs. Explicatii foarte bune atat la curs,

cat si la orele de laborator

Cunostintele invatate au aplicabilitate directa

Organizarea cursului, sistemul de notare, numarul de teme

Faptul ca nota maxima este 12 (incluzand tema de

recuperare)

Proiectul este o idee foarte buna, antreneaza si spiritul de

echipa

Echipa tanara, entuziasta, profesorul si asistentii sunt foarte

bine pregatiti


Feedback 2013 (3)

Aspecte negative

Cantitate mare de informatie (numar mare de algoritmi noi) in

timp scurt

Ar fi util o ora in plus atat pentru curs, cat si pentru laborator

Studentii vor sa ia un punctaj cat mai mare din laboratoare,

asa ca fac aceasta prin orice mijloace (corecte si incorecte)

Laboratoare dificile, dureaza mult intelegerea scheletului de

cod, necesita pregatirea (citirea, intelegerea) laboratorului de

acasa de multe ori

Temele un pic cam dificile si corectate tarziu

Deadline-uri suprapuse cu alte materii

Proiectul organizat cam prost (inclusiv probleme cu platforma

aleasa)


Feedback 2014 (1)

Cadrul didactic a fost bine pregatit pentru sustinerea?

Cursuri: 4.65 / 6


Pot fi obtinute explicatii suplimentare in afara orelor de?

Cursuri: 4.13 / 6


Materialele puse la dispozitie sunt suficiente pentru intelegerea?

Cursuri: 4.03 / 6


Numarul si dificultatea temelor au fost adecvate? 3.42 / 6


Feedback 2014 (2)

Aspecte:

Multe observaii similare cu cele din 2013, referitor la dificultate, numr mare de teme, etc. Este o materie dificil, nu o putem face mai uoar

Studenii au reclamat ca laboratorul s-a transformat ntr-o alergtur dup puncte, sunt prea dificile, iar studenii nu sunt ateni la explicaii, au tendina s mai copieze de la colegi, etc.

Drept urmare:

Laboratorul valoreaz doar 1p n acest an

A fost introdus un test practic care va fi susinut aproximativ n sptmna a 10a valoreaz 1p



Bibliografie

Introducere in Analiza Algoritmilor de Cristian Giumale Ed. Polirom 2004

Introducere in Algoritmi de Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest Ed. Agora

Vedei i recomandrile din Regulament!

Meniune importanta slide-urile reprezint doar un suport pentru prezentare!

Proiectarea Algoritmilor

Curs 1 Scheme de algoritmi Divide et impera



Curs 1 Cuprins

Scheme de algoritmi

Divide et impera

Exemplificare folosind Merge sort

Alte exemple de algoritmi divide et impera

Greedy

Exemplificare folosind arbori Huffman

Demonstraia corectitudinii algoritmului Huffman

Curs 1 Bibliografie

Giumale Introducere in Analiza Algoritmilor cap 4.4

Cormen Introducere n Algoritmi cap. Algoritmi Greedy (17)

http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

http://www.cs.umass.edu/~barring/cs611/lecture/4.pdf

http://thor.info.uaic.ro/~dlucanu/cursuri/tpaa/resurse/Curs6.pps

http://www.math.fau.edu/locke/Greedy.htm

http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-SelectMasterThm.pdf



Scheme de algoritmi

Prin scheme de algoritmi nelegem tipare comune pe care le putem aplica n rezolvarea

unor probleme similare.

O gam larg de probleme se pot rezolva folosind un numr relativ mic de scheme.

=> Cunoaterea schemelor determin o rezolvare mai rapid i mai eficient a problemelor.


Divide et Impera (I)

Ideea (divide si cucerete) este atribuit lui Filip al II-lea, regele Macedoniei (382-336 i.e.n.), tatl lui Alexandru cel Mare i se refer la politica acestuia fa de statele greceti.

In CS Divide et impera se refer la o clas de algoritmi care au ca principale caracteristici faptul c mpart problema n subprobleme similare cu problema iniial dar mai mici ca dimensiune, rezolv problemele recursiv i apoi combin soluiile pentru a crea o soluie pentru problema original.


Divide et Impera (II)

Schema Divide et impera const n 3 pai la fiecare nivel al recurenei:

Divide problema dat ntr-un numr de subprobleme;

Impera (cucerete) subproblemele sunt rezolvate recursiv. Dac subproblemele sunt suficient de mici ca date de intrare se rezolv direct (ieirea din recuren);

Combin soluiile subproblemelor sunt combinate pentru a obine soluia problemei iniiale.


Divide et Impera Avantaje i Dezavantaje

Avantaje:

Produce algoritmi eficieni.

Descompunerea problemei n subprobleme

faciliteaz paralelizarea algoritmului n vederea execuiei sale pe mai multe procesoare.

Dezavantaje:

Se adaug un overhead datorat recursivitii (reinerea pe stiv a apelurilor funciilor).


Merge Sort (I)

Algoritmul Merge Sort este un exemplu clasic de rezolvare cu D&I.

Divide: Divide cele n elemente ce trebuie sortate n 2 secvene de lungime n/2.

Impera: Sorteaz secvenele recursiv folosind merge sort.

Combin: Secvenele sortate sunt asamblate pentru a obine vectorul sortat.

Recurena se oprete cnd secvena ce trebuie sortat are lungimea 1 (un vector cu un singur element este ntotdeauna sortat ) .

Operaia cheie este: asamblarea soluiilor pariale.


Merge Sort (II)

Algoritm [Cormen]

MERGE-SORT(A, p, r)

1 Dac p < r

2 Atunci q [(p + r)/2] // divide

3 MERGE-SORT(A, p, q) //impera

4 MERGE-SORT(A, q + 1, r)

5 MERGE(A, p, q, r) // combin // (interclasare)


Merge Sort (III) Algoritmul de interclasare

Algoritm [Cormen] MERGE(A, p, q, r) // p si r sunt capetele intervalului, q este mijlocul 1 n1 q - p + 1 // numrul de elemente din partea stnga 2 n2 r q // numrul de elemente din partea dreapta 3 creeaz vectorii S[1 -> n1 + 1] i D[1 -> n2 + 1] 4 Pentru i de la 1 la n1 5 S[i] A[p + i - 1] // se copiaz partea stnga n S 6 Pentru j de la 1 la n2 7 D[j] A[q + j] // si partea dreapta n D 8 S[n1 + 1] 9 D[n2 + 1] 10 i 1 11 j 1 12 Pentru k de la p la r // se copiaz napoi n vectorul de 13 Dac S[i] D[j] // sortat elementul mai mic din cei 14 Atunci A[k] S[i] // doi vectori sortai deja 15 i i + 1 16 Altfel A[k] D[j] 17 j j + 1


Exemplu funcionare Merge Sort

Exemplu funcionare [Wikipedia]:


Merge Sort - Complexitate

T(n) =

complexitatea interclasrii

numr de subprobleme dimensiunea subproblemelor

=> (din T. Master) T(n) = (n * logn)

(n) 2 * T(n/2) +


Divide et Impera alte exemple (I)

Calculul puterii unui numr: xn

Algoritm clasic: Pentru i de la 1 la n rez = rez * x;

ntoarce rez.

Complexitate: (n)

Algoritm Divide et Impera: Dac n este par

Atunci ntoarce xn/2 * xn/2

Altfel (n este impar) ntoarce x * x(n-1)/2 * x(n-1)/2

Complexitate: T(n) = T(n/2) + (1) = (logn)


Divide et Impera alte exemple (II)

Calculul celei mai scurte distane ntre 2 puncte din plan (http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf)

algoritmul naiv (n2)


Divide et Impera alte exemple (III)

Sorteaz punctele n ordinea cresctoare a coordonatei x ((nlog n));

mprim setul de puncte n 2 seturi de dimensiune egal i calculm recursiv distana minim n fiecare set (l = linia ce mparte cele 2 seturi, d = distana minim calculat n cele 2 seturi);

Elimin punctele care sunt plasate la distan

de l > d;

Sorteaz punctele rmase dup coordonata y;

Calculeaz distanele de la fiecare punct rmas

la cei 6 vecini (nu pot fi mai muli);

Dac gsete o distant < d, atunci actualizeaz d.

d d

d

d

d d

d

d

d d

d

d

l


Divide et Impera Tem de gndire (1)

Se d o mulime M de numere ntregi si un numr x. Se cere s se determine dac exist a,bM a.. a + b = x.

Algoritmul propus trebuie s aib complexitatea (nlogn).

Temele de la curs sunt facultative!


Cum sortm un vector fr interclasare sau alte operaii complexe n etapele de mprire a problemei i de combinare a soluiilor?

Hint: se folosesc trei apeluri recursive!

Observaie! Algoritmul este ineficient, dar este interesant!



Cum se gseste eficient elementul median al unui vector?

Problema mai general: cum se gsete al k-lea cel mai mic (sau cel mai mare)

element dintr-un vector?

Eficient nseamn (n)

http://www.cs.rit.edu/~ib/Classes/CS515

_Spring12-13/Slides/022-

SelectMasterThm.pdf Proiectarea Algoritmilor 2015


Divide et Impera Tem de gndire

Se d o mulime M de numere ntregi si un numr x. Se cere s se determine dac exist a,bM a.. a + b = x.

Algoritmul propus trebuie s aib complexitatea (nlogn).

Temele de la curs sunt facultative!

NTREBRI?


curs 1 - di

Documents