X hits on this document

361 views

0 shares

0 downloads

0 comments

43 / 145

FACULTATEA: AUTOMATICĂ ŞI CALCULATOARE

DOMENIUL / SPECIALIZAREA: CALCULATOARE ŞI TEHNOLOGIA INFORMAŢIEI

Anul de studii: II

Semestrul: 2

Titularul cursului: prof. dr. ing. Vladimir-Ioan Creţu

Colaboratori: as. ing. Călin Jebelean, as. ing. Ciprian-Bogdan Chirilă, as. ing. Sebastian Gliţă

Numar de ore/saptamana/Verificarea/Credite

Curs

Seminar

Laborator

Proiect

Examinare

Credite

2

0

2

0

Examen scris

4

A. OBIECTIVELE CURSULUI

Disciplina prezinta aspectele legate de proiectarea şi analiza  performanţelor algoritmilor  în contextul structurilor de date avansate. Se prezintă  modalitatile de proiectare şi implementare a varietatilor de  algoritmi care implementează operatorii specifici, precum şi tipare de construcţie a algoritmilor, accentuand aspectele legate de analiza si performantele acestora. Are un important character formative fiind o disciplină fundamentală a domeniului.

B. SUBIECTELE CURSULUI

1.Arbori:  Arbori generalizaţi, Arbori binari, Arbori binari ordonaţi,  Arbori de regasire (“Trie Trees”), Arbori binari echilibraţi AVL, Arbori binari optimi, Arbori Huffmann, Arbori multicăi (Arbori-B, Arbori-B binary, Arbori 2-3

2. Mulţimi: Tipul de date abstract mulţime,  Implementarea structurii mulţime utilizând structuri de date fundamentale, Structuri de date derivate din structura multim, Implementarea structuri mulţime cu ajutorul structurilor de date avansate, Mulţimi pe care sunt definiţi operatorii UNIUNE şi CAUTĂ, Mulţimi pe care sunt definiţi operatorii UNIUNE, CAUTĂ şi   PARTIŢIONARE

3. Grafuri, Tipul de date abstract graf, Tehnici de implementare a tipului de date abstract graf, Algoritmi fundamentali de traversare a grafurilor, Aplicaţii ale traversării grafurilor (Arbori de acoperire ("Spanning Trees"), conexiuni

4. Grafuri ponderate ("Weighted Graphs"), Arbori de acoperirie minimi ("Minimum-Cost Spanning Trees") Algoritmi pentru determinarea arborilor de acoperirie minimi (Algoritmul lui Prim, Căutarea "bazată pe prioritata", Algoritmul lui Kruskal, Drumul minim ("Shortest Path")

5. Grafuri orientate, Problema drumurilor minim cu origine unică ("Single-Source Shortest Path Problem"), Algoritmul lui Dijkstra, Problema drumurilor minime corespunzătoare tuturor perechilor de noduri  ("All-Pairs Shortest Path Problem") Algoritmul lui Floyd, Închiderea tranzitivă, Algoritmul lui Warshal, Grafuri orientate aciclice, Componente puternic conectate, Algoritmul lui Kosaraju-Sharir, Algoritmul lui Tarjan,. Reţele de curgere ("Network-Flow") Algoritmul Ford-Fulkerson, Problema potrivirilor ("Matching")

6. Tehnici avansate de proiectare şi analiză: Programare dinamică, Algoritmi greedy, Analiza amortizată, NP-Completitudine

C. SUBIECTELE APLICATIILOR (laborator, seminar, proiect)

1. TDA arbore. Arbori binari ordonati (1,2)

2. Arbori binari echilibrati AVL

3. Arbori binari optimi

4. Arbori multicai

5. Implementarea TDA multime (1,2)

6. TDA graf. Implementare (1,2)

7. Grafuri orientate. Algoritmi specifici

8. Grafuri ponderate. Algoritmi specifici

9. Arbori de acoperire. Conexitate

D. BIBLIOGRAFIE  

1. V.Cretu: "Structuri de date si algoritmi. Structrui de date avansate.Vol.2", Editura “Orizonturi Universitare”, Timisoara, 2005.

2. A.V.Aho, J.H.Hopcroft, J.D.Ullman: "Data Structures and Algorithms", Addison Wesley Publishing Company, 1985 Company, 1988.

3. T.H.Cormen, C.E.Leiserson, R.L.Rivest: "Introduction to algorithms", MIT Press, 1992

E. PROCEDURA DE EVALUARE

Document info
Document views361
Page views361
Page last viewedThu Dec 08 18:59:12 UTC 2016
Pages145
Paragraphs4938
Words34649

Comments