ASD Introducere PPT

7/24/2019 ASD Introducere PPT

1/10

Algoritmi si structuri de date -Introducere

1

ALGORITMI si STRUCTURI de

DATE

Curs:Daniela Zaharie

cab 046B (parter)

e-mail: [email protected]

web.info.uvt.ro/~dzaharie -> Fall 2015 -> Algorithms & Data

Structures (in Romanian) (materiale pentru curs)

moodle.e-uvt.ro -> Algoritmi si structuri de date

Activitate laborator:

Mdlina Eracu cab F109; [email protected]

Flavia Micota cab 050B; [email protected] Neagul cab 049; [email protected]

Liviu Mafteiu-Scai cab 049; [email protected]

Materiale pentru laborator: http://web.info.uvt.ro/wiki/Algoritmica


2/10


2

Motivaie

Aproape zilnic:

Folosim un motor de cutare (ex: Google)

Beneficiem de un filtru anti-spam i/sau un antivirus

Aflm informaii despre prieteni i colaboratori prin intermediul

unei reele de socializare (ex: Facebook, LinkedIn,ResearchGate)

Ce se aflin spatele acestor instrumente ?

Algoritmide cutare, potrivire dupcuvinte cheie, sortare,calcul frecvene de apariie, identificare corelaii, clasificareaplicai asupra unor volume mari de date organizate dupanumite reguli etc.

Exemple: PageRank (Google)

EdgeRank (Facebook)


3/10


3

Motivaie

PageRank algoritm folosit de ctremotoarele de cutare pentru ierarhizareapaginilor web [Page & Brin, 1997]

Idee:

rang(P0)=(1-d)+d*(rang(P1)/L1+rang(Pk)/Lk)

P0 pagina al crui rang se calculeaz

P1,, Pk pagini care conin link-uri ctre P0

Li - numrul de link-uri ce pleacdin Pid din (0,1) coeficient de damping

Web = graf

Criterii de ierarhizare = scor

probabilist

Calcul rang = prin algoritm

iterativ sau prin calculalgebric (rezolvarea unui

sistem liniar)

http://www.google.com/insidesearch/howsearchworks/algorithms.html


4/10


4

MotivaieEdgeRank algoritm folosit iniial de ctre

Facebook pentru a realiza selecianoutilor postate pe wall (News Feed)

- la ora actual sunt folosiialgoritmi care iau n calcul un numr foartemare de factori

Idee:

Interaciunea dintre un utilizator i unobiect din News Feed definete o muchie(edge)

Fiecare muchie (e) este caracterizatprin3 factori care determinimportana sa:afinitate(a), pondere(w), vechime(d)

Cu ct importana unei muchii e mai marecu att e mai probabil saparin News


5/10


5

Despre ce este acest curs ?

Scop: proiectarea i analizaalgoritmilor

identificarea structurilor de date, descrierea si analizaprelucrarilor efectuate asupra lor

Implic:

gndire abstract abiliti de rezolvare a problemelor

Acest curs nu este:

Despre un limbaj de programare

(totui algoritmii vor fi implementai limbajul de programare

folosit este: Python - http://www.python.org/ ) Un curs de matematic

(totui sunt necesare unele cunotine de matematic: noiunifundamentale: mulime, funcie, ir, matrice etc.

metode de demonstrare: reducere la absurd, inducie

matematic)


6/10


6

Structura1. Introducere n rezolvarea algoritmica problemelor si utilizarea structurilor

de date fundamentale (sem 1: C1)

2. Descrierea algoritmilor. Pseudocod/Python (sem 1: C2)

3. Analiza algoritmilor: verificarea corectitudinii, analiza eficienei(sem 1: C3-5)

4. Structuri liniare de date (tablouri i liste nlnuite). Stive. Cozi. (sem 1: C6-

C8)5. Algoritmi de cutare i sortare (sem 1: C9)

6. Tehnici de rezolvare algoritmica problemelor:

reducere si divizare (recursivitate, quicksort, mergesort) (sem 1: C10-C12)

alegere local optimal(greedy) (sem 1: C13)

cutare sistematicn spaiul soluiilor (backtracking) (sem 2) programare dinamic (sem 2)

7. Structuri arborescente. Structuri eficiente de stocare i cutare(arboribinari de cutare, cozi cu prioriti, heaps, tabele de dispersie etc) (sem 2)

8. Structuri de date i algoritmi specifici unor probleme (ex: procesare texte)(sem 2)


7/10


7

Bibliografie

1. M.T. Goodrich, R. Tamassia, M.H. Goldwasser Data Structures & Algorithms

in Python, Wiley 2013

2. S. Skiena The Algorithm Design Manual, second edition, 2008

3. T.H. Cormen, C.E. Leiserson, R.R. Rivest Introducere in algoritmi, trad. Ed.

Teora

4. D. Lucanu, M. Craus Proiectarea algoritmilor, Ed. Polirom, 2008

5. V. Cretu Structuri de date si algoritmi, Ed. Orizonturi universitare, 2000

6. D. Zaharie Introducere n proiectarea i analiza algoritmilor, Ed. Eubeea,2008

Alte resurse:

(Leiserson) http://ocw.mit.edu/courses/electrical-engineering-and-computer-

science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

(Skiena) http://www.cs.sunysb.edu/~algorith/video-lectures/

http://www.coursera.org


8/10


8

Evaluare

Examen final (scris + probpractic) 50%

Test laborator (scris + practic) 30%

(in cadrul laboratorului 10)

Activitate individual(teme de casa + activitate la laborator +activitate curs) (10%+5%+5%)

Submitere teme:

http://moodle.e-uvt.ro


9/10


9

Reguli

Termen de predare teme: 2 sptmnide la data enunrii temei

Intrzierile n predarea temelor sunt penalizate cu 0.5 pcte /sptmn

Temele se pot rezolva n echipe de cte 2 studeni (echipele seformeazn primele dousptmni i se anuncadrul didacticresponsabil cu activitatea de laborator)

Prezena curs: minim 50%

Prezena laborator: 100%

Absene de la laborator: maxim 2 absene nemotivate/semestru

Laboratoarele la care se absenteaz trebuie recuperate

Laboratorul poate fi recuperat doar mpreuncu una dintre celelaltesubgrupe

Cu condiia sanunai cadrul didactic i s obinei acordul acestuia


10/10


10

Alte informaii

Dac avei ntrebri/ neclariti:

Intrebai n timpul/ la sfritul cursului/laboratorului

Trimitei un e-mail cadrului didactic

Mergei la biroul cadrului didactic n orele de consultaii

Ore consultaii

Zaharie (cab 046B: LUNI 13:00-14:30

JOI 18:00-19:30

- Coordonatorii activitii de laborator: vezi avizier

ASD Introducere PPT

Documents

Transcript of ASD Introducere PPT