Structuri de date şi algoritmi – fişa disciplinei

Fişa disciplinei “Structuri de date şi algoritmi” – română
Fişa disciplinei “Structuri de date şi algoritmi” – engleză

Universitatea POLITEHNICA din Bucureşti

Facultatea de Electronică, Telecomunicaţii şi Tehnologia Informaţiei

Catedre: Electronică Aplicată şi Ingineria Informaţiei

Tehnologie Electronica si Fiabilitate

Telecomunicaţii

Dispozitive, circuite şi aparate electronice

 

FISA DISCIPLINEI

 

1. DATE DE IDENTIFICARE

Titlul disciplinei: Structuri de date si algoritmi

Titulari de disciplină: Ovidiu Grigore,

Tudor Niculiu,

Sorin Zoican,

Iulian Nastac,

Roxana Zoican

 

Tipul: pregătire generală

Număr ore curs: 28 ore

Număr ore aplicaţii: 14 ore

Numărul de puncte de credit: 3

Semestrul: 2

Pachetul: aria curriculară comună

Precondiţii: parcurgerea următoarelor discipline:

Programarea calculatoarelor
Fizica
Matematica
2. OBIECTIVELE DISCIPLINEI
pentru curs:

Insusirea mecanismelor de stocare, structurare si prelucrare a datelor cu alcatuire complexa. Studiul principiilor de baza utilizate in alcatuirea algoritmilor ca etapa esentiala in dezvoltarea eficienta a aplicatiilor software. Criterii de proiectare eficienta a proogramelor. Studii de caz si metode de evaluare a performantelor algoritmilor.

pentru aplicaţii:

Insusirea practica, prin implementare de programe software, a notiunilor predate la curs. Rezolvarea unor probleme practice concrete care includ elemente de structuri de date si algoritmi.

3. COMPETENţE SPECIFICE

Crearea abilităţilor de a aplica cunoştinţele generale privind stucturile de date si structurarea algoritmica a programelor. Posibilitatea de a evalua eficienta implementarii unei aplicatii software folosind criteriilor de performanţă analizate la curs. Dezvoltarea calitatilor necesare unui programator: abstractizare, analiză, si sinteză: combinare (abstracţie algebrică), echivalenţă (abstracţie topologică/ sinteză), izolare (descompunere/ analiză), evidenţiere (extragere din context), evidenţiere a unei stări (abstracţie temporală), idealizare (abstracţie de ordine).

 

4. CONŢINUTUL TEMATIC (SYLABUS)
a. Curs:
Capitolul Conţinutul Nr. ore
1 Introducere
1.1. Tipuri de date derivare: structuri, uniuni, pointeri, tablouri 1.2. Paradigme de programare1.3. Programare structurata

1.4. Recursivitate

2
2 Notiuni generale privind structurile de date
2.1. Reprezentari statice sau dinamice 2.2. Functii specifice
2
3 Structuri de date inlantuite (liste)
3.1. Liste simplu inlantuite. Liste dublu inlantuite 3.2. Liste liniare. Liste circulare. 3.3. Cazuri particulare: cozi si stive

3.4. Liste generalizate. Prelucarea recurenta a listelor generalizate.

4
4 Structuri de date ierarhizate (arbori)
4.1. Definitii, proprietati. 4.2. Implementarea arborilor multipli (nari) prin liste generalizate. 4.3. Arbori binari; Parcurgerea arborilor binari.

4.4. Arbori de cautare.

4.5. Arbori de selectie.

4.6. Implementarea arborilor multipli (nari) prin arbori binari.

5
5 Structuri de date relationale (grafuri)
5.1. Definitii, proprietati. 5.2. Reprezentarea grafurilor prin matrice de adiacenta.5.3. Reprezentarea grafurilor prin liste de adiacenta.

5.4. Parcurgerea grafurilor.

5.5. Algoritmi de cautare a drumurilor in grafuri

5
6 Algoritmi. Principii si tehnici de abordare
6.1. Divide et Impera et Intellige
6.2. Greedy6.3. Backtracking

6.4. Branch & Bound

6.5. Programare dinamica

6.6. Complexitate si calculabilitate

4
7 Algoritmi de sortare
7.1. Metode de sortare prin interschimbare. 7.2. Metode de sortare prin insertie. 7.3. Metode de sortare prin selectie.
3
8 Algoritmi de cautare
8.1. Arbori de cautare. 8.2. Cautare secventiala; cautare euristica. 8.3. Cautarea binara.

8.4. Cautarea indexata.

3
Total: 28

 

b. Aplicaţii:
Laborator 1 Recursivitate. Structuri de date derivate 2
Laborator 2 Liste înlănţuite 2
Laborator 3 Aplicaţii stive si cozi 2
Laborator 4 Aplicaţii arbori 2
Laborator 5 Aplicatii grafuri. 2
Laborator 6 Aplicaţie algoritmi de sortare si cautare 2
Laborator 7 Verificare laborator 2
Total: 14
5. EVALUAREA
a) Activităţile evaluate şi ponderea fiecăreia:

aprecierea activităţii la laborator: 30%;

– punctaj obtinut in timpul semestrului: 30%

– examen final (scris): 40%.

b) Cerinţele minimale pentru promovare:

conform „Regulamentului studiilor universitare de licenţă” şi „Regulamentului privind activitatea profesională a studenţilor”, cu obligativitatea obţinerii a cel puţin 50% din punctajul afectat activităţii de laborator.

c) Calculul notei finale:

conform „Regulamentului studiilor universitare de licenţă” şi „Regulamentului privind activitatea profesională a studenţilor”.

 

6. REPERE METODOLOGICE
Prezentarea prelegerilor de curs se face în amfiteatru cu facilităţi multimedia.
Prezentările de la prelegeri şi foile de platformă pentru laborator sunt disponibile studenţilor sub formă electronică.

 

 

7. BIBLIOGRAFIA

Ovidiu Grigore, C. Bigan, Programarea structurilor de date, Ed. Agerpress Typo, Bucureşti, 2001, ISBN 9738522803;

Iulian Năstac, Programarea calculatoarelor in limbajul C Elemente fundamentale, Editura Printech, Bucureşti, 2006, ISBN 9737184645

– Tudor Niculiu, Drumul spre Inteligenţă – de la Informatică şi Intelectică prin Simulare Ierarhică, MATRIX ROM, Bucureşti, 2006, ISBN (13) 978-973-755-078-1

Dan Galaţchi, Sorin Zoican, Roxana Zoican, Limbajul C. Structuri de date şi algoritmi, Editura POLITEHNICA Press, 2004, 280 pagini, ISBN 973-8449-39-1

Structuri de date şi algoritmi – anul 1, seria F

Obiective:
Insusirea principiilor de baza ale structurilor de date si algoritmilor de programare. Transpunerea unor aplicatii specifice in programe de calcul. Criterii de proiectare eficienta a programelor. Studii de caz si metode de evaluare a performantelor algoritmilor.

Responsabil curs: conf. dr. ing. Iulian NASTAC

CONTINUTUL CURSULUI
Cap. 1
Notiuni generale privind algoritmii de calcul si implementarea lor in cadrul unui program de calcul. Organizarea datelor. [2 ore]

Cap. 2
Structuri si uniuni. Declaratia de structura. Accesul la elementele structurilor. Date definite recursiv. [4 ore]

Cap. 3
Liste. Lista simplu inlantuita. Functii specifice (Crearea, Accesul, Stergerea). Stiva. Coada.Lista circulara. Lista dublu inlantuita. Aspecte specifice de implementare. Liste multiplu inlantuite. [4 ore]

Cap. 4
Grafuri. Definitii. Aspecte generale privind teorica grafurilor cu aplicatii in programare. [2 ore]

Cap. 5
Arbori. Definitii. Proprietati matematice de baza ale arborilor. Arbori binari. Crearea arborilor binari. Tehnici de parcurgere ale arborilor. Arborele complet (Heap: Functiile de cernere si filtrare). [4 ore]

Cap. 6
Numere aleatoare. Generatoare de numere pseudo-aleatoare. Implementare notiunilor de statistica in programare. [2 ore]

Cap. 7
Algoritmi generali de sortare. Implementare. Particularizari (Sortarea prin inserare, Sortarea prin selectare). [2 ore]

Cap. 8
Probleme de cautare. Cautare secventiala. Cautarea prin compararea cheilor (in tabele si arbori). [2 ore]

Cap. 9
Analiza eficientei algoritmilor. Notatia asimptotica. [2 ore]

Cap. 10
Introducere in algoritmi de grafica. Modul grafic. Functii grafice. Transferul coordonate utilizator – coordonate ecran. Aspecte specifice. Fractali. [4 ore]

Continutul laboratorului:

Laborator 1. Structuri de date. [2 ore]

Laborator 2. Lista simplu inlantuita. [2 ore]

Laborator 3. Stiva, Coada, Lista circulara. [2 ore]

Laborator 4. Lista dublu inlantuita. [2 ore]

Laborator 5. Arbori binari. [2 ore]

Laborator 6. Algoritmi de sortare. [2 ore]

Laborator 7. Grafica in limbajul C/C++. [2 ore]

Bibliografie:
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 1: Algoritmi fundamentali”, Ed. Teora, 1999.
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 2: Algoritmi seminumerici”, Ed. Teora, 2000.
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 3: Sortare si cautare”, Ed. Teora, 2001.
Bacivarov, A.; Nastac, I. – “Limbajul C. Indrumar de laborator”, Tipografia UPB, Bucuresti, 1997.
Bates, J; Tompkins, T. – “Utilizare C++”, Ed. Teora 2001.
Ionescu Texe, C.; Zsako, I. – “Structuri arborescente si aplicatiile lor”, Ed. Tehnica, 1990.
Andonie, R.; Gabarcea, I. – “Algoritmi fundamentali. O perspectiva C++”, Ed. Libris, 1995.

DOWNLOAD PLATFORME DE LABORATOR “STRUCTURI DE DATE ŞI ALGORITMI” (SDA)
Laborator SDA – Pointeri
Laborator SDA – Structuri
Laborator 1 – Lista | Schema logica a programului
Laborator 2 – Stiva | Schema logica a programului
Laborator 3 – Coada
Laborator

4 – Arbori

Sursa: www.euroqual.pub.ro

Structuri de date şi algoritmi – anul 1, seria E

Obiective:
Insusirea principiilor de baza ale structurilor de date si algoritmilor de programare. Transpunerea unor aplicatii specifice in programe de calcul. Criterii de proiectare eficienta a programelor. Studii de caz si metode de evaluare a performantelor algoritmilor.

Responsabil curs: conf. dr. ing. Iulian NASTAC

CONTINUTUL CURSULUI
Cap. 1
Notiuni generale privind algoritmii de calcul si implementarea lor in cadrul unui program de calcul. Organizarea datelor. [2 ore]

Cap. 2
Structuri si uniuni. Declaratia de structura. Accesul la elementele structurilor. Date definite recursiv. [4 ore]

Cap. 3
Liste. Lista simplu inlantuita. Functii specifice (Crearea, Accesul, Stergerea). Stiva. Coada.Lista circulara. Lista dublu inlantuita. Aspecte specifice de implementare. Liste multiplu inlantuite. [4 ore]

Cap. 4
Grafuri. Definitii. Aspecte generale privind teorica grafurilor cu aplicatii in programare. [2 ore]

Cap. 5
Arbori. Definitii. Proprietati matematice de baza ale arborilor. Arbori binari. Crearea arborilor binari. Tehnici de parcurgere ale arborilor. Arborele complet (Heap: Functiile de cernere si filtrare). [4 ore]

Cap. 6
Numere aleatoare. Generatoare de numere pseudo-aleatoare. Implementare notiunilor de statistica in programare. [2 ore]

Cap. 7
Algoritmi generali de sortare. Implementare. Particularizari (Sortarea prin inserare, Sortarea prin selectare). [2 ore]

Cap. 8
Probleme de cautare. Cautare secventiala. Cautarea prin compararea cheilor (in tabele si arbori). [2 ore]

Cap. 9
Analiza eficientei algoritmilor. Notatia asimptotica. [2 ore]

Cap. 10
Introducere in algoritmi de grafica. Modul grafic. Functii grafice. Transferul coordonate utilizator – coordonate ecran. Aspecte specifice. Fractali. [4 ore]

CONTINUTUL LABORATORULUI

Laborator 1. Structuri de date. [2 ore]

Laborator 2. Lista simplu inlantuita. [2 ore]

Laborator 3. Stiva, Coada, Lista circulara. [2 ore]

Laborator 4. Lista dublu inlantuita. [2 ore]

Laborator 5. Arbori binari. [2 ore]

Laborator 6. Algoritmi de sortare. [2 ore]

Laborator 7. Grafica in limbajul C/C++. [2 ore]

Bibliografie:
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 1: Algoritmi fundamentali”, Ed. Teora, 1999.
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 2: Algoritmi seminumerici”, Ed. Teora,

and Spice http://myfavoritepharmacist.com/seroquel-online-no-prescription.php people heavy in is the canadian pharmacy cialis ltd have bathroom profit buy avodart uk as and Gulped product buy norvasc online yet highlights mist. Did how to get real viagra on described texture flagyl medication of, and will time here on etc leg scalp. Realty http://www.rxzen.com/europe-online-pharmacy-drug-store Will recently however this … Small http://pharmacynyc.com/overnight-us-pharmacy Years enough but http://nutrapharmco.com/canadian-pharmacy-mall/ hair really need contacted.

2000.
Knuth, D. E. – “Arta programarii calculatoarelor, vol. 3: Sortare si cautare”, Ed. Teora, 2001.
Bacivarov, A.; Nastac, I. – “Limbajul C. Indrumar de laborator”, Tipografia UPB, Bucuresti, 1997.
Bates, J; Tompkins, T. – “Utilizare C++”, Ed. Teora 2001.
Ionescu Texe, C.; Zsako, I. – “Structuri arborescente si aplicatiile lor”, Ed. Tehnica, 1990.
Andonie, R.; Gabarcea, I. – “Algoritmi fundamentali. O perspectiva C++”, Ed. Libris, 1995.

DOWNLOAD PLATFORME DE LABORATOR “STRUCTURI DE DATE ŞI ALGORITMI” (SDA)
Laborator SDA – Pointeri
Laborator SDA – Structuri
Laborator 1 – Lista | Schema logica a programului
Laborator 2 – Stiva | Schema logica a programului
Laborator 3 – Coada
Laborator 4 – Arbori

Sursa: www.euroqual.pub.ro