Si el contenido no está traducido, puede usar la herramienta de traducción automática

Estudia en la UdG

Diseño de la asignatura




Estructuras de datos y algorítmica (3105G07010/2016)


Datos generales  
  • Curso académico : 2016
  • Descripción : Estructures de dades: punters, estructures lineals, arbres, diccionaris de dades, grafs.
    Esquemes algorítmics: divideix i venç, mètode voraç, backtracking.

  • Créditos ECTS : 9

Torna a l'inici / Vuelve al principio / Back to top

  Grupos
Grupo A

Duración : Semestral, 1r semestre

Profesorado : MIQUEL BOFILL ARASAJORDI REGINCOS ISERNJOAN SURRELL SAURI

Lengua de las clases : Català (100%)

Horarios :

Actividad Horario Grupo de clase Aula
Teoria1
Pràctiques d'aula1
Pràctiques d'aula informàtica1
Pràctiques d'aula informàtica2
Pràctiques d'aula informàtica3
Pràctiques d'aula informàtica4
Pràctiques d'aula informàtica5
Grupo B

Duración : Semestral, 1r semestre

Profesorado : MIQUEL BOFILL ARASAJORDI REGINCOS ISERNJOAN SURRELL SAURI

Lengua de las clases : Català (100%)

Horarios :

Actividad Horario Grupo de clase Aula
Teoria2
Pràctiques d'aula2
Pràctiques d'aula informàtica1
Pràctiques d'aula informàtica2
Pràctiques d'aula informàtica3
Pràctiques d'aula informàtica4
Pràctiques d'aula informàtica5

Torna a l'inici / Vuelve al principio / Back to top

  Competencias
  1. CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
  2. CB01 - Analitzar situacions complexes i dissenyar estratègies per resoldre-les.
  3. CB03 - Aplicar criteris de qualitat a les propostes i / o projectes.
  4. CB05 - Prendre decisions per a la resolució de situacions diverses
  5. 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
  6. CCI7 Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema.
  7. 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
  8. 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
  9. CE18 - Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema
  10. 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

Torna a l'inici / Vuelve al principio / Back to top

  Contenidos

  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
  Actividades
Tipo de actividad Horas con profesor Horas sin profesor Total
Classes participatives303565
Elaboració de treballs143448
Prova d'avaluació41014
Resolució d'exercicis 425698
Total 90135225

Torna a l'inici / Vuelve al principio / Back to top

  Bibliografía
  • Franch Gutiérrez, Xavier (1999 ). Estructures de dades : especificació, disseny i implementació (4ª ed.). Barcelona: Edicions UPC. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Stroustrup, Bjarne (cop. 2002 ). El Lenguaje de programación C++ (Ed. especial.). Madrid [etc.]: Addison Wesley. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Brassard, Gilles (cop. 1996 ). Fundamentals of algorithmics . Englewood Clifs, N.J.: Prentice-Hall International. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Horowitz, Ellis (cop. 2007 ). Fundamentals of data structures in C++ (2nd ed.). Summit: Silicon Press. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Horowitz, Ellis (cop. 2008 ). Computer algorithms (2nd ed.). Summit: Silicon Press. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • 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   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Gonzalo Arroyo, Julio (1997 ). Esquemas algorítmicos : enfoque metodológico y problemas resueltos . Madrid: Universidad Nacional de Educación a Distancia. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Wirth, Niklaus (cop. 1987 ). Algoritmos y estructuras de datos . México, D.F. [etc.]: Prentice-Hall Hispanoamericana. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
  • Stroustrup, Bjarne (cop. 2013 ). The C++ programming language (4th ed.). Upper Saddle River, NJ: Addison-Wesley. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova

Torna a l'inici / Vuelve al principio / Back to top

  Evaluación y calificación
Actividades de evaluación
Descripción de la actividad Evaluación de la actividad %
Avaluació continuada, problemes i laboratoriProblemes de teoria i exercicis de laboratori. S'avaluaran un conjunt de problemes proposats, resolts a classe i a casa. Alguns exercicis s'implementaran sobre ordinador a les sessions de laboratori.25
Pràctiques de l'assignaturaS'avaluarà la implementació de pràctiques relacionades amb els temes de l'assignatura (estructures de dades i algorítmica). Aquesta activitat es desenvoluparà principalment fora de classe (act. obligatòria)25
Examen - qüestionsExercicis curts sobre la matèria (act. obligatòria). Aquesta activitat es podrà recuperar.25
Examen - problemesProblemes de l'assignatura (act. obligatòria). Aquesta activitat es podrà recuperar.25

 

Calificación

- En l'avaluació es tindran en compte les activitats segons els pesos indicats.

- 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.

- Cal treure una nota mínima de l'examen (qüestions i problemes).

- L'examen és obligatori.

- Hi haurà recuperació de l'examen pels que s'han presentat a l'examen i tinguin una nota superior a 3 (segons normativa EPS).

- 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ó.

Criterios específicos de la nota «No Presentado» :

Per a la qualificació de NP es tindrà en compte l'examen (qüestions i problemes) i les pràctiques. Aquestes activitats són obligatòries.

Torna a l'inici / Vuelve al principio / Back to top

  Observaciones
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.

Torna a l'inici / Vuelve al principio / Back to top

  Asignaturas recomendadas
  1. Lògica i matemàtica discreta
  2. Metodologia i tecnologia de la programació II

Torna a l'inici / Vuelve al principio / Back to top