Teaching Guides Query



Academic Year: 2019/20

30213 - Data Structures and Algorithms


Teaching Plan Information

Academic Year:
2019/20
Subject:
30213 - Data Structures and Algorithms
Faculty / School:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Degree:
439 - Bachelor's Degree in Informatics Engineering
443 - Bachelor's Degree in Informatics Engineering
ECTS:
6.0
Year:
2
Semester:
First semester
Subject Type:
Compulsory
Module:
---

1. General information

2. Learning goals

3. Assessment (1st and 2nd call)

4. Methodology, learning tasks, syllabus and resources

4.1. Methodological overview

The methodology followed in this course is oriented towards the achievement of the learning objectives. The learning process that is designed for this subject is based on the following:

  • The study and work continued since the first day of class.
  • Learning concepts and methodologies for the design and implementation of correct, reusable and efficient Abstract Data Types (ADTs) through lectures, in which student participation will be encouraged.
  • The application of such knowledge to the design and analysis of algorithms and programs in the classes of problems. In these classes, students will play an active role in the discussion and resolution of problems.
  • Labs in which the student will implement several programming projects, applying the concepts and techniques explained in the lectures.
  • Teamwork whose result will be reflected in the delivery of suitably designed and documented resulting programs, as well as the explanation and justification of the design and decisions adopted.
  • A continued work combining concepts and analysis understanding, problem-solving sessions using "pencil and paper", and the set-up of (small or medium size) programming projects.

4.2. Learning tasks

The course includes the following learning tasks: 

Classes of problems to apply the concepts and techniques previously presented.
The practice sessions take place in a computer lab. In these sessions, students will work in teams and perform a number of programming jobs directly related to the topics studied in the course. A series of works or programming exercises will be proposed to be developed either in the laboratory or at home. The result of this work will be delivered within fixed deadlines.

4.3. Syllabus

The course will address the following topics: 

  1. Programming with Abstract Data Types (ADTs).
  2. Linear ADTs.
  3. Tree ADTs.
  4. Dictionaries and hash tables.
  5. Introduction to algorithmic schemes.
  6. Introduction to graphs.

4.4. Course planning and calendar

Classroom:

  • Theoretical classes (2 hours per week)
  • Classes of problems (1 hour weekly)

Labs:

There will be a first face two-hour session in the laboratory. In the rest of the (off-site) practices, students will work in teams, tutored by a teacher. Programming projects will be performed and presented as specified for each of them, and within deadlines to be announced.

Student Work:

The dedication of the student to achieve the learning outcomes in this subject is estimated at 157 hours distributed as follows:

  • 47 hours, approximately, of classroom activities (lectures, problems and laboratory face practices)
  • 42 hours of programming teamwork
  • 62 hours of effective personal study
  • 6 hours for exams

4.5. Bibliography and recommended resources

Zaragoza:

Basic Bibliography:

  • Weiss, M.A.: Data Structures and Algorithm Analysis in C++, 4th Edition, Pearson/Addison Wesley, 2014.
  • Hernández, Z.J. y otros: Fundamentos de Estructuras de Datos. Soluciones en Ada, Java y C++, Thomson, 2005.
  • Shaffer, Clifford A.: Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications, 2013. (En línea.)

Exercises:

  • Martí Oliet, N., Ortega Mallén, Y., Verdejo López, J.A.: Estructuras de datos y métodos algorítmicos: 213 ejercicios resueltos. 2ª Edición, Ed. Garceta, 2013.
  • Joyanes, L., Zahonero, I., Fernández, M. y Sánchez, L.: Estructura de datos. Libro de problemas, McGraw Hill, 1999.

Bibliography on C++:

  • Stroustrup, B.: The C++ Programming Language, 4th Edition, Addison-Wesley, 2013.

Complementary Bibliography:

  • Campos Laclaustra, J.: Estructuras de Datos y Algoritmos, Prensas Universitarias de Zaragoza, Colección Textos Docentes, 1995.
  • Franch Gutiérrez, X.: Estructuras de Datos. Especificación, Diseño e Implementación, 3ª edición, Ed. Edicions UPC, 2001.
  • Mehta, D.P. y Sahni, S.: Handbook of Data Structures and Applications, Chapman & Hall/CRC, 2005.

Teruel:

 
BB Estructura de datos. Libro de problemas / Luis Joyanes Aguilar [et al.] Madrid [etc.] : McGraw-Hill, D.L.1999
BB Fundamentos de estructura de datos : soluciones en Ada, Java y C++ / Zenón José Hernández Figueroa ... [et al.] Madrid : Thomson, D.L. 2005
BB MARTÍ OLIET, N. Estructura de datos y algoritmos. Ejercicios y problemas resueltos / Nardiso Martí Oliet, Y. Ortega Mallén, J.A. Verdejo López,. Madrid : Prentice Hall, 2003
BB Weiss, Mark Allen. Data structures and algorithm analysis in Java / Mark Allen Weiss Reading, Massachusetts [etc.] : Addison-Wesley, cop. 1999
BB Weiss, Mark Allen. Estructuras de datos en Java : compatible con Java 2 / Mark Allen Weiss . - 1a ed. en español Madrid : Addison Wesley, cop. 2000
BC Martí Oliet, Narciso. Estructuras de datos y métodos algorítmicos : 213 ejercicios resueltos / Narciso Martí Oliet, Alberto Verdejo, Yolanda Ortega Mallén . - 2ª ed. Madrid : Garceta, 2013 [Ejercicios], 2013
BC Campos Laclaustra, Javier. Estructuras de datos y algoritmos / Javier Campos Lacaustra . - 1ª ed., 1ª reimp. Zaragoza : Prensas Universitarias de Zaragoza, 2001
BC Deitel, Paul J.. Java : cómo programar / P. J. Deitel, H. M. Deitel ; traducción Alfonso Vidal Romero Elizondo ; revisión técnica Gabriela Azucena Campos García, Roberto Martínez Román, Jorge Armando Aparicio Lemus. - 7ª ed. Naucalpan de Juárez (Estado de México) : Pearson Educación, 2008
BC Franch Gutiérrez, Xavier. Estructuras de datos : Especificación, diseño e implementación / Xavier Franch Gutiérrez . - 2a. ed. Barcelona : UPC, 1996
BC Handbook of data structures and applications / edited by Dinesh P. Mehta and Sartaj Sahni Boca Raton, Florida [etc.] : Chapman & Hall/CRC, cop. 2005

 


Curso Académico: 2019/20

30213 - Estructuras de datos y algoritmos


Información del Plan Docente

Año académico:
2019/20
Asignatura:
30213 - Estructuras de datos y algoritmos
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Titulación:
439 - Graduado en Ingeniería Informática
443 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
2
Periodo de impartición:
Primer semestre
Clase de asignatura:
Obligatoria
Materia:
---

1. Información Básica

1.1. Objetivos de la asignatura

La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

En esta asignatura el alumno mejorará su capacidad para diseñar y desarrollar programas de ordenador haciendo énfasis en la identificación, diseño y definición de Tipos Abstractos de Datos (TADs) independientemente de su implementación. El alumno aprenderá a diseñar e implementar TADs para que sean reutilizables, eficientes y robustos, y a implementarlos garantizando dichas propiedades. Se presentarán algunos de los TADs fundamentales de uso más frecuente, como: pilas, colas, listas, árboles de búsqueda, tablas, etc., para los que se estudiarán y compararán distintas alternativas de implementación. También se introducirán una serie de esquemas algorítmicos básicos (como dividir para vencer, búsqueda con retroceso, voracidad...) y el alumno aprenderá a reconocer los problemas que requieren este tipo de esquemas para su resolución y cómo aplicarlos.

1.2. Contexto y sentido de la asignatura en la titulación

Estructuras de Datos y Algoritmos (EDA) es una asignatura obligatoria englobada en la materia de formación común en Programación y Computación.

Esta asignatura completa la formación recibida por el alumno en las asignaturas de Programación I y Programación II, y le prepara para abordar proyectos de programación de cada vez mayor tamaño y complejidad, y a hacerlo aplicando mejores técnicas y estrategias en el diseño e implementación, permitiendo además el reparto efectivo de la carga del trabajo de implementación y desarrollo de las diferentes partes del sistema a desarrollar. Esta línea de formación continuará ampliándose en las asignaturas de Tecnología de Programación, Programación de Sistemas Concurrentes y Distribuidos, e Ingeniería de Software, así como en otras asignaturas posteriores en el plan de estudios

Además, algunos de los TADs y algoritmos estudiados en EDA serán necesarios para diversas asignaturas que tienen a EDA como prerrequisito directo o indirecto, tales como Tecnología de Programación, Bases de Datos, e Inteligencia Artificial.

1.3. Recomendaciones para cursar la asignatura

El alumno que curse esta asignatura ha de contar con una formación en programación del nivel correspondiente al necesario para superar la asignatura de Programación II. Por otra parte una adecuada formación matemática del nivel de la asignatura Matemática Discreta resulta muy conveniente.

2. Competencias y resultados de aprendizaje

2.1. Competencias

Al superar la asignatura, el estudiante será más competente para...

Reconocer y aplicar los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.

Resolver problemas reconociendo o diseñando, y utilizando de forma eficiente, los tipos y estructuras de datos más adecuados a la resolución de un problema.

Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.

Aprender de forma continuada y desarrollar estrategias de aprendizaje autónomo.

2.2. Resultados de aprendizaje

El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

 Es capaz de identificar, diseñar y definir Tipos Abstractos de Datos (TADs) independientemente de su implementación.

Diseña e implementa TADs reutilizables y robustos en un lenguaje de programación modular o en un lenguaje orientado a objetos.

Diseña e implementa programas robustos de tamaño medio identificando, definiendo e implementando los Tipos Abstractos de Datos (TADs) necesarios.

Es capaz de identificar, utilizar e implementar algunos TADs fundamentales, como: pilas, colas, listas, árboles de búsqueda, tablas hash y grafos.

Es capaz de comparar distintas alternativas de implementación de TADs con respecto al tiempo de ejecución de algoritmos y al uso de la memoria, y de seleccionar la más adecuada en cada problema o contexto.

Conoce y aplica los esquemas algorítmicos básicos (como dividir para vencer, búsqueda con retroceso, voracidad...) a la resolución de problemas.

2.3. Importancia de los resultados de aprendizaje

Estructuras de Datos y Algoritmos constituirá una base sólida en la formación del alumno para el diseño y desarrollo de sistemas o proyectos de programación de cada vez mayor tamaño y complejidad, ya sean basados en el diseño modular o en el diseño orientado a objetos, buscando siempre la encapsulación, calidad, eficiencia y reutilización del software.

Se presentarán además un conjunto de TADs y algoritmos de uso frecuente, y que todo futuro Ingeniero Informático debe conocer y saber utilizar para poder diseñar soluciones en los nuevos contextos o problemas a los que se enfrente.

3. Evaluación

3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

Zaragoza:

 

A continuación se describen las actividades que contribuirán a la evaluación del estudiante y la prueba de evaluación global que se realizará en cada convocatoria para evaluar a los estudiantes de la asignatura.

  1. A lo largo del semestre se desarrollarán trabajos de prácticas de programación, para los que se formarán equipos integrados por un número de alumnos que se determinará al inicio del curso. Con los trabajos prácticos de programación se realizará un seguimiento del trabajo realizado por los alumnos durante el semestre y del progreso de su aprendizaje. Los trabajos presentados por el alumno se calificarán con una nota cuantitativa de 0 a 10. Para obtener dichas notas se valorará el funcionamiento de los programas según especificaciones, la calidad de su diseño y su presentación, la adecuada aplicación de los métodos de resolución, el tiempo empleado, así como la capacidad de los integrantes del equipo para explicar y justificar el diseño realizado.

    Los alumnos que hayan cumplido con los plazos de entrega fijados para los trabajos prácticos de programación, y hayan demostrado en ellos un nivel de aprovechamiento y calidad de resultados adecuados, obteniendo en la valoración de su trabajo práctico una nota de 5.0 como mínimo, serán exentos de la realización del examen práctico de programación en laboratorio. Para dichos alumnos, la calificación obtenida con sus prácticas se utilizará como nota de examen práctico de programación en laboratorio, salvo que el alumno decida presentarse a la prueba de examen práctico en laboratorio, en cuyo caso prevalecerá la nota obtenida en el examen práctico individual.
  2. Examen práctico e individual de programación, en laboratorio. En el examen práctico se le plantearán al alumno ejercicios de programación de naturaleza similar a los realizados en las prácticas o vistos en clase. Se calificará con una nota de 0 a 10, para la que se valorará el correcto funcionamiento y rendimiento de los programas según especificaciones, la calidad de su diseño, la adecuada aplicación de los métodos de resolución y el tiempo empleado. Para aquellos alumnos que resulten exentos de la realización de este examen y opten por presentarse al mismo prevalecerá la nota obtenida en el examen práctico individual. Será necesaria una calificación mínima de 5.0 puntos en el examen práctico para aprobar la asignatura y, en tal caso, la calificación obtenida pondera un 30% de la nota final de la asignatura.
  3. Examen escrito en el que se deberán resolver problemas de programación y, en su caso, responder preguntas conceptuales o resolver algún ejercicio. Se calificará con una nota de 0 a 10. En general, se valorará la calidad y claridad de las respuestas y soluciones propuestas, su adecuación a las especificaciones y restricciones planteadas, la calidad del diseño, la adecuada aplicación de los métodos de resolución y el tiempo empleado. Será necesario obtener una calificación mínima de 5.0 puntos en el examen escrito para aprobar la asignatura. En tal caso la calificación obtenida pondera un 70% de la nota final de la asignatura.

Evaluación global

La prueba global de evaluación de la asignatura consta de dos partes:

  • Examen práctico de programación en laboratorio e individual. En cada convocatoria se realizará un examen práctico de programación en laboratorio, en el que se le plantearán al alumno ejercicios de programación de naturaleza similar a los realizados en las prácticas o vistos en clase. Es necesario una calificación mínima de 5.0 puntos en el examen práctico para aprobar la asignatura. En tal caso la calificación obtenida pondera un 30% de la nota final de la asignatura.

    Los alumnos que hayan cumplido con los plazos de entrega fijados para los trabajos prácticos de programación, y hayan demostrado en ellos un nivel de aprovechamiento y calidad de resultados adecuados obteniendo una valoración de su trabajo práctico de como mínimo 5.0, serán exentos de la realización del examen práctico de programación en laboratorio convirtiéndose automáticamente la nota numérica obtenida en la evaluación de sus trabajos prácticos en su nota final de examen práctico de programación. No obstante, para los alumnos exentos del examen práctico que se presenten al mismo, en cualquier convocatoria, prevalecerá la nota obtenida en el examen práctico individual de programación.
  • Examen escrito en el que se deberán resolver problemas de programación y, en su caso, responder preguntas conceptuales o resolver algún ejercicio. Es necesaria una calificación mínima de 5.0 puntos en el examen escrito para aprobar la asignatura. En tal caso la calificación obtenida pondera un 70% de la nota final de la asignatura.

Si la calificación obtenida por el alumno en el examen escrito es igual o superior a 5.0 y su calificación en el examen práctico de programación es igual o superior a 5.0, entonces la calificación del alumno en la asignatura se obtendrá como la suma ponderada de las calificaciones del examen escrito con ponderación del 70%, y del examen práctico con ponderación del 30%. Si ambas calificaciones (examen escrito y examen práctico) son menores que 5.0, la calificación en la asignatura se obtendrá de igual forma (ponderando un 70% y un 30%, respectivamente). Si, por el contrario, la calificación obtenida por el alumno en una de las dos pruebas (examen práctico o examen escrito) es menor que 5.0, entonces la calificación del alumno en la asignatura será igual a esa nota que no alcanza el 5.0. Las calificaciones obtenidas en las dos partes en la primera convocatoria se guardan para la siguiente convocatoria del mismo curso académico en el caso de que el alumno no logre aprobar la asignatura.

 

Teruel:

 

Igual que en Zaragoza salvo que es necesaria una calificación mínima de 4.0 puntos (en lugar de 5.0) en el examen escrito para aprobar la asignatura.

4. Metodología, actividades de aprendizaje, programa y recursos

4.1. Presentación metodológica general

El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

  1. El estudio y trabajo continuado desde el primer día de clase.
  2. El aprendizaje de conceptos y metodologías para el diseño e implementación de TADs correctos, reutilizables y eficientes a través de las clases magistrales, en las que se favorecerá la participación de los alumnos.
  3. La aplicación de tales conocimientos al diseño y análisis de algoritmos y programas en las clases de problemas. En estas clases los alumnos desempeñarán un papel activo en la discusión y resolución de los problemas.
  4. Las clases de prácticas en laboratorio en las que el alumno deberá poner en práctica la tecnología necesaria para desarrollar proyectos de programación de tamaño pequeño o medio, utilizando un lenguaje de programación determinado y aplicando los conceptos y técnicas estudiadas en esta asignatura.
  5. El trabajo en equipo desarrollado para resolver las prácticas de la asignatura y cuyo resultado se plasma en la entrega de programas resultantes convenientemente diseñados y documentados, así como en la explicación y justificación del diseño realizado y decisiones adoptadas, que se expondrán al profesor tutor de prácticas.
  6. Un trabajo continuado en el que se conjugue la comprensión de conceptos, el análisis y la resolución de problemas de programación utilizando “lápiz y papel” y la puesta a punto en computador de algunos proyectos de programación de tamaño pequeño o medio.

4.2. Actividades de aprendizaje

El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...

En las clases impartidas en el aula se desarrollará el temario de la asignatura.

En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura. Se propondrán problemas y ejercicios para ser resueltos antes de la clase de problemas en la que se presentarán y discutirán diferentes soluciones a dichos problemas. También se propondrán ejercicios durante la sesión de problemas para ser resueltos durante la misma, algunos de forma individual y otros para ser trabajados en grupo.

Las sesiones de prácticas de desarrollan en un laboratorio informático. En estas sesiones el alumno deberá trabajar en equipo y realizar una serie de trabajos de programación directamente relacionados con los temas estudiados en la asignatura. Para las prácticas de laboratorio se propondrán una serie de trabajos o ejercicios de programación para que el alumno los resuelva, desarrolle parte del trabajo en el laboratorio, los complete como trabajo en casa, y los entregue dentro de los plazos de tiempo que se fijen en cada caso.

4.3. Programa

  1. Programación con Tipos Abstractos de Datos.
  2. Tipos de datos lineales.
  3. Tipos de datos arborescentes.
  4. Tipos de datos funcionales.
  5. Introducción a los esquemas algorítmicos.
  6. Introducción a los grafos.

4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

La organización docente prevista de la asignatura es la siguiente.

  • Clases teóricas (2 horas semanales)
  • Clases de problemas (1 hora semanal)
  • Prácticas de la asignatura: Habrá una primera sesión presencial de dos horas en laboratorio. El resto de las prácticas consistirán en trabajos tutelados por un profesor, en las que participan los alumnos de cada uno de los subgrupos en los que se divide el grupo de clase.

Presentación de trabajos prácticos de programación:

Los trabajos de programación a desarrollar en las prácticas de la asignatura deberán ser realizados y presentados de acuerdo a lo especificado para cada uno de ellos, y dentro de las fechas límite que se anunciarán en el enunciado de cada uno de los trabajos propuestos o con suficiente antelación.

Trabajo del estudiante

La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 157 horas distribuidas del siguiente modo:

  • 47 horas, aproximadamente, de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
  • 62 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación de clases y prácticas)
  • 42 horas (cada estudiante) de trabajo en equipo para desarrollar los programas propuestos en las prácticas de programación
  • 6 horas de examen final de teoría escrito y de prácticas en laboratorio

 

El calendario de exámenes y las fechas de entrega de trabajos se anunciará con suficiente antelación.