Dades generals

Curs acadèmic:
2017
Descripció:
Estructures de dades: punters, estructures lineals, arbres, diccionaris de dades, grafs. Esquemes algorítmics: divideix i venç, mètode voraç, backtracking.
Crèdits ECTS:
9

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:
MIQUEL BOFILL ARASA  / JORDI REGINCOS ISERN  / JOAN SURRELL SAURI
Idioma de les classes:
Català (100%)

Competències

  • CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
  • CB01 - Analitzar situacions complexes i dissenyar estratègies per resoldre-les.
  • CB03 - Aplicar criteris de qualitat a les propostes i / o projectes.
  • CB05 - Prendre decisions per a la resolució de situacions diverses
  • CCI6 Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzar la idoneïtat i complexitat dels algorísmics proposats
  • CCI7 Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema.
  • CCI8 Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, elegint el paradigma i els llenguatges de programació més adequats
  • CE17 - Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes , analitzant la idoneïtat i complexitat dels algorismes proposats
  • CE18 - Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema
  • CE19 - Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats

Continguts

1. Introducció

          1.1. Classes i abstracció de dades

          1.2. Programació utilitzant classes

          1.3. Memòria dinàmica i estructures enllaçades

          1.4. Genèrics

          1.5. Esquemes algorítmics

2. Estructures de dades lineals

          2.1. Introducció

          2.2. Piles

          2.3. Cues

          2.4. Llistes amb punt d'interés

          2.5. Iteradors

3. Arbres

          3.1. Introducció. Recursivitat.

          3.2. Arbres binaris

          3.3. Algoritmes sobre arbres

          3.4. Arbres n-aris

          3.5. Monticles i cues de prioritat

          3.6. Particions

4. Diccionaris de dades

          4.1. Introducció

          4.2. Conjunts, EDFs, fitxers directes

          4.3. Representacions lineals

          4.4. Representacions ordenades

          4.5. Arbres de cerca

          4.6. Tècniques de dispersió

          4.7. Fitxers relatius i directes

5. Grafs i estructures compostes

          5.1. Concepte

          5.2. Representació de grafs

          5.3. Algoritmes bàsics sobre grafs

          5.4. Relacions

          5.5. Estructures compostes

6. Algoritmes voraços

          6.1. Introducció

          6.2. L'esquema voraç

          6.3. Exemples de l'esquema voraç

          6.4. Algoritmes quasi-òptims

          6.5. Algoritmes voraços sobre grafs

7. Algoritmes de divideix i venç

          7.1. Introducció

          7.2. L'esquema de divideix i venç

          7.3. Eficiència i llindar d'un algoritme

          7.4. Exemples d'algoritmes de divideix i venç

8. Backtracking

          8.1. Introducció

          8.2. Concepte de backtracking

          8.3. Variants de l'esquema

          8.4. Exemples de backtracking

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Total
Classes participatives 30 35 65
Elaboració de treballs 14 34 48
Prova d'avaluació 4 10 14
Resolució d'exercicis 42 56 98
Total 90 135 225

Bibliografia

  • Franch Gutiérrez, Xavier (1999 ). Estructures de dades : especificació, disseny i implementació (4ª ed.). Barcelona: Edicions UPC. Catàleg
  • Stroustrup, Bjarne (cop. 2002 ). El Lenguaje de programación C++ (Ed. especial.). Madrid [etc.]: Addison Wesley. Catàleg
  • Brassard, Gilles (cop. 1996 ). Fundamentals of algorithmics . Englewood Clifs, N.J.: Prentice-Hall International. Catàleg
  • Horowitz, Ellis (cop. 2007 ). Fundamentals of data structures in C++ (2nd ed.). Summit: Silicon Press. Catàleg
  • Horowitz, Ellis (cop. 2008 ). Computer algorithms (2nd ed.). Summit: Silicon Press. Catàleg
  • Preiss, Bruno R (cop. 1999 ). Data structures and algorithms : with object-oriented design patterns in C++ . New York [etc.]: John Wiley and Sons. Catàleg
  • Gonzalo Arroyo, Julio (1997 ). Esquemas algorítmicos : enfoque metodológico y problemas resueltos . Madrid: Universidad Nacional de Educación a Distancia. Catàleg
  • Wirth, Niklaus (cop. 1987 ). Algoritmos y estructuras de datos . México, D.F. [etc.]: Prentice-Hall Hispanoamericana. Catàleg
  • Stroustrup, Bjarne (cop. 2013 ). The C++ programming language (4th ed.). Upper Saddle River, NJ: Addison-Wesley. Catàleg

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Avaluació continuada, problemes i laboratori Problemes de teoria i exercicis de laboratori.

• S'avaluaran un conjunt de problemes proposats, resolts a classe i a casa.

• També s'avaluaran alguns exercicis implementats a les sessions de laboratori.
25
Pràctiques de l'assignatura S'avaluarà la implementació de pràctiques relacionades amb els temes de l'assignatura (1 d'estructures de dades i 1 d'algorítmica).

Aquesta activitat es desenvoluparà principalment fora de classe i és obligatòria.
25
Examen - qüestions Exercicis breus sobre la matèria.
Aquesta activitat és obligatòria i es podrà recuperar.
25
Examen - problemes Problemes de l'assignatura.
Aquesta activitat és obligatòria i es podrà recuperar.
25

Qualificació

• En l'avaluació es tindran en compte les activitats segons els pesos indicats: avaluació continuada, pràctiques de laboratori, qüestions i problemes.
• La nota d'avaluació continuada només es tindrà en compte en els alumnes que demostrin treure profit de les sessions, mentre que la resta d'alumnes tindran un sistema alternatiu que no té en compte aquesta nota.
• L'examen és obligatori i cal treure una nota mínima de les dues parts (qüestions i problemes).
• Hi haurà recuperació de l'examen. Com posa la normativa EPS, per poder optar a la recuperació cal haver-se presentat a l'examen normal i tenir una nota superior a 3.
• Les pràctiques són obligatòries i no tenen recuperació.
• A la Guia Docent que es presenta el primer dia de classe hi ha una explicació més detallada de l'avaluació.
• Els professors de l'assignatura decidiran sobre qualsevol interpretació no contemplada en els criteris d'avaluació.

Criteris específics de la nota «No Presentat»:
Per a la qualificació de NP només es tindrà en compte l'examen final (qüestions i problemes).

Observacions

A l'inici de l'assignatura no hi haurà laboratori presencial i es faran classes addicionals de teoria.

Segons el pla d'estudis oficial, cal tenir aprovada Metodologia i Tecnologia de la Programació II per matricular-se d'aquesta assignatura.

Assignatures recomanades

  • Lògica i matemàtica discreta
  • Metodologia i tecnologia de la programació II