Post on 15-Sep-2015
description
Proiectarea Algoritmilor
I CA: Stefan Trausan-Matu stefan.trausan@cs.pub.ro
I CB: Traian Rebedea traian.rebedea@cs.pub.ro
I CC: Costin Chiru costin.chiru@cs.pub.ro
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
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;
Proiectarea Algoritmilor 2015
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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!
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 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.
Proiectarea Algoritmilor 2015
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!
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
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
Laboratoare:/Seminarii: 4.51 / 6
Materialele puse la dispozitie sunt suficiente pentru
intelegerea?
Cursuri: 4.33 / 6
Laboratoare:/Seminarii: 4.42 / 6
Numarul si dificultatea temelor au fost adecvate? 3.76 / 6
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
Feedback 2014 (1)
Cadrul didactic a fost bine pregatit pentru sustinerea?
Cursuri: 4.65 / 6
Laboratoare:/Seminarii: 4.86 / 6
Pot fi obtinute explicatii suplimentare in afara orelor de?
Cursuri: 4.13 / 6
Laboratoare:/Seminarii: 4.48 / 6
Materialele puse la dispozitie sunt suficiente pentru intelegerea?
Cursuri: 4.03 / 6
Laboratoare:/Seminarii: 4.31 / 6
Numarul si dificultatea temelor au fost adecvate? 3.42 / 6
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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).
Proiectarea Algoritmilor 2015
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.
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
Exemplu funcionare Merge Sort
Exemplu funcionare [Wikipedia]:
Proiectarea Algoritmilor 2015
Merge Sort - Complexitate
T(n) =
complexitatea interclasrii
numr de subprobleme dimensiunea subproblemelor
=> (din T. Master) T(n) = (n * logn)
(n) 2 * T(n/2) +
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
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)
Proiectarea Algoritmilor 2015
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
Proiectarea Algoritmilor 2015
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!
Divide et Impera Tem de gndire (2)
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!
Proiectarea Algoritmilor 2015
Divide et Impera Tem de gndire (3)
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
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?
Proiectarea Algoritmilor 2015