ESTRUCTURES DE DADES I ALGORISMES

 

 

Professora coordinadora: Lina Juan (lina@eupmt.cat)

 

Tipus d’assignatura: Troncal

 

Nivell: 2A

 

Càrrega lectiva: 6 crèdits (4.5 de teoria/aplicació i 1.5 de laboratori) / 5 crèdits ECTS

 

Recomanacions: Haver cursat i superat  l’assignatura “Metodologia de la Programació”.

 

Organització de la docència:

Teoria/aplicació: 3 hores/setmana x 12 setmanes

Laboratori: 2 hores/quinzena x 12 setmanes

 

Descripció

En aquesta assignatura s’aprèn a especificar, dissenyar, implementar estructures de dades i fer-ne ús mitjançant el disseny d’algorismes d’aplicació.

 

Objectius

En finalitzar el curs, l’estudiant serà capaç de:

·          Descriure les seqüències enllaçades com a eina en la implementació d’estructures de dades.

·          Manipular seqüències enllaçades. Exposar i defendre determinats tractaments.

·          Explicar la tècnica del disseny recursiu. Aplicar la tècnica en la resolució de problemes.

·          Exposar, argumentar i discutir la correcta aplicació de la tècnica recursiva.

·          Enumerar, definir i comparar les diferents estructures de dades. Implementar-les.

·          Diferenciar el treball amb estructures de dades en funció de, si agafem el rol de programador del contenidor ó bé usuari de l’estructura de dades.

·          Utilitzar les seqüències enllaçades en la implementació de les estructures de dades lineals.

·          Aplicar la tècnica recursiva en la implementació d’alguns dels mètodes característics dels arbres.

·          Argumentar l’eficiència d’una implementació d’una estructura de dades.

·          Justificar l’ús d’una estructura de dades o una altra en la resolució d’exercicis. Escollir les estructures  més adients, en funció de l’ús que en cal fer i de les especificacions establertes en l’enunciat.

 

Competències transversals

En aquesta assignatura es treballen les següents competències transversals:

·          Comunicar de forma efectiva.

·          Dirigir i col·laborar en equips de treball.

·          Gestionar el treball personal.

 

Bibliografia bàsica

·          Estructures de Dades i Algorismes. Dossiers de Teoria i Problemes. L. Juan; Publicacions de l’EUPMt

·          Estructuras de datos con Java. Diseño de  estructuras y algoritmos. J. Lewis, J. Chase. Ed. Addison Wesley, 2ª edición, 2006

 

Bibliografia complementària

·          Estructuras de datos y métodos algorítmicos. Ejercicios resueltos. N. Martí, Y. Ortega, J.A. Verdejo. Ed. Prentice Hall, 2003

·          Estructuras de datos en Java. Mark Allen Weiss. ED. Addison Wesley, 2000

 

Criteris d’avaluació i mètode de qualificació

·          Prova parcial dels temes 1 a 3 (30%) + Prova final amb tota la matèria de l’assignatura (41%) + Pràctiques (17%) + dos treballs dirigits (12%).

·          La nota corresponent a les dues proves serà sempre la màxima entre la que surt a partir de la ponderació anterior i la que s’obtindria sense tenir en compte el primer parcial, considerant tota la ponderació sobre la prova final.  

·          Totes les proves de l’assignatura es poden realitzar, a criteri del propi estudiant,  amb un esquema guia  dels conceptes avaluats.

·          Les pràctiques s’avaluen a partir de les memòries i fitxers lliurats.

·          Al llarg del quadrimestre els estudiants, per grups, resoldran a classe de teoria, problemes que seran lliurats al professor al finalitzar aquesta.  Aquesta tasca desenvolupada pels estudiants té un reconeixement màxim de 1 punt a afegir sobre la nota final obtinguda per l’estudiant.  

Programa de teoria

 

Tema 1. Variable dinàmica

1.1. Tipus de variables. Variable dinàmica (en Java, variables referencials)

1.2. Característiques de les variables referencials: domini i operadors

1.3. Concepte de seqüència enllaçada

1.4. Algorismes pel tractament de seqüències enllaçades:

1.4.1. Creació, cerca, recorregut i esborrament  

                1.4.2. Concepte de node capçalera

1.5. Aplicació de les seqüències enllaçades: la classe Conjunt

 

Tema 2. Disseny recursiu

2.1.   El mecanisme de la recursivitat

2.2.   Com i quan usar la recursivitat

2.3.   Transformació d’un algorisme recursiu a iteratiu

 

Tema 3. Estructures de dades lineals

                3.1. Introducció.

3.2.Tècniques d’emmagatzematge

                3.2.1. Tècnica seqüencial

                3.2.2. Tècnica enllaçada

                3.2.3. Tècnica del hashing.Concepte.Problema de les col·lisions: hashing obert i hashing tancat

                3.3. La classe Pila. Declaració i implementacions

                3.4. La classe Cua. Declaració i implementacions

                3.5. La classe Llista associativa. Declaració i implementacions

                3.6. Exercicis d’aplicació

 

Tema 4. Estructures de dades no lineals: els arbres

                4.1. Introducció. Definicions

                4.2. Recorregut d’arbres: en fondària i en amplada

                4.3. La classe Arbre binari: Declaració i implementació dinàmica

                4.4. La classe Arbre de Cerca Binaria: Declaració i implementació dinàmica

                4.5. Arbres equilibrats. La classe A.V.L.

4.6. La classe Arbre Turó. Ordenació segons un turó: Heapsort

                4.7. Arbres de grau N

 

Programa de pràctiques

1.- POO en Java. L’API de Java. Classes i herència. Redefinició de mètodes de la classe Object.

2.- Declaració i implementació d’una estructura de dades lineal senzilla.

3.- Declaració i implementació d’una estructura de dades lineal més complexa.

4.- Declaració i implementació d’una estructura de dades no lineal: un arbre.

5.- Síntesi. Ús de les implementacions treballades en les sessions anteriors.

 

Metodologia docent

El treball a l’aula es basa en classes on el professor explica els conceptes de teoria i els aplica en la resolució de problemes,  alguns d’ells realitzats pel professor i d’altres pels propis alumnes.

Les metodologies que es seguiran a l’aula per a resolució d’exercicis seran molt variades, sempre depenent de la temàtica a treballar i dels estudiants assistents a l’aula i principalment, de l’objectiu que es pretén assolir amb la resolució de l’exercici.  Amb aquestes resolucions es pretén treballar els elements bàsics d’aprenentatge cooperatiu, demanant que els estudiants s’involucrin més en l’assignatura i, desenvolupin les habilitats interpersonals, per això les activitats es faran en grups d’estudiants, amb o sense defensa de la resolució proposada pel grup a la resta de companys d’assignatura i al professor. Aquestes activitats seran avaluades pel professor i/o companys i per tant, serà una qualificació més a tenir en compte en el càlcul de la nota final de l’assignatura. És molt important l’assistència a les classes de l’assignatura per l’assoliment de les competències transversals de l’assignatura.

 

Les activitats programades fora de l’aula son:

-          Realització de 2 treballs dirigits.

Treball 1: Codificació a Java d’un disseny de classes proporcionat pel professor. L’objectiu bàsic és el de refrescar els conceptes treballats en les assignatures de programació dels cursos 1A i 1B. Aquest treball es realitza a l’inici del quadrimestre.

Treball 2:  Cal continuar el treball 1 afegint  classes i/o mètodes, en aquest cas els conceptes que es treballen són conceptes propis d’aquesta assignatura.

-         

by Bitlonia