Programación II

Usted está aquí

Créditos
7.5
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
En esta asignatura se introduce el diseño modular y el diseño basado en objetos, usando el lenguaje de programación C++; se estudian nuevas estructuras de datos lineales (pilas, colas, listas) y arborescentes (árboles binarios, n-arios, generales); se profundiza en el diseño iterativo y en el diseño recursivo, tanto en el razonamiento sobre la corrección de un diseño dado como en la detección y mejora de soluciones ineficientes; y se presentan implementaciones de estructuras de datos lineales y arborescentes usando tipos recursivos de datos.

Profesorado

Responsable

  • Borja Valles Fuente ( )
  • Guillem Godoy Balil ( )
  • Juan Luis Esteban Ángeles ( )

Otros

  • Albert Calvo Ibañez ( )
  • Alejandro Ivan Paz Ortiz ( )
  • Alfonso Valverde Ruiz ( )
  • Jorge Castro Rabal ( )
  • Jose Carmona Vargas ( )
  • M. Luisa Bonet Carbonell ( )
  • Maria Josefina Sierra Santibañez ( )
  • Pau Fernandez Duran ( )
  • Santiago Marco Sola ( )
  • Xavier Messeguer Peypoch ( )

Horas semanales

Teoría
2
Problemas
0
Laboratorio
3
Aprendizaje dirigido
0.3
Aprendizaje autónomo
7.2

Competencias

Competencias Transversales

Trabajo en equipo

  • G5 [Avaluable] - Ser capaz de trabajar como miembro de un equipo, ya sea como un miembro más, o realizando tareas de dirección con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.
    • G5.1 - Capacidad de colaborar en un entorno unidisciplinar. Identificar los objetivos del grupo y colaborar en el diseño de la estrategia a seguir y un plan de trabajo para conseguirlos. Identificar las responsabilidades de cada componente del grupo y asumir el compromiso personal de la tarea asignada. Evaluar y presentar los resultados propios. Identificar el valor de la cooperación e intercambiar información con los otros componentes del grupo. Intercambiar información sobre el progreso del grupo y proponer estrategias para mejorar su funcionamiento.

Competencias Técnicas

Competencias técnicas comunes

  • CT1 - Demostrar conocimiento y comprensión de hechos esenciales, conceptos, principios y teorías relativas a la informática y a sus disciplinas de referencia.
    • CT1.1A - Demostrar conocimiento y comprensión de los conceptos fundamentales de la programación y de la estructura básica de un computador. CEFB4. Conocimiento de los fundamentos del uso y programación de los computadores, los sistemas operativos, las bases de datos y, en general, los programas informáticos con aplicación en ingeniería.
    • CT1.1B - Interpretar, seleccionar y valorar conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática y su aplicación a partir de los fundamentos matemáticos, estadísticos y físicos necesarios. CEFB2. Capacidad para comprender y dominar los fundamentos físicos y tecnológicos de la informática: electromagnetismo, ondas, teoría de circuitos, electrónica y fotónica y su aplicación para la resolución de problemas propios de la ingeniería.
    • CT1.2B - Interpretar, seleccionar y valorar conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática y su aplicación a partir de los fundamentos matemáticos, estadísticos y físicos necesarios. CEFB3. Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para el tratamiento automático de la información por medio de sistemas computacionales y su aplicación para la resolución de problemas propios de la ingeniería.
  • CT3 - Demostrar conocimiento y comprensión del contexto organizativo, económico y legal en el que desarrolla su trabajo (Conocimiento adecuado del concepto de empresa, marco institucional y jurídico de la empresa, organización y gestión de empresas.)
    • CT3.6 - Demostrar conocimiento de la dimensión ética en la empresa: la responsabilidad social y corporativa en general y, en particular, las responsabilidades civiles y profesionales del ingeniero en informática.
  • CT4 - Demostrar conocimiento y capacidad de aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y la complejidad de los algoritmos
    • CT4.1 - Identificar las soluciones algorítmicas más adecuadas para resolver problemas de dificultad mediana.
    • CT4.2 - Razonar sobre la corrección y la eficiencia de una solución algorítmica.
  • CT5 - Analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, escogiendo el paradigma y los lenguajes de programación más adecuados.
    • CT5.1 - Escoger, combinar y explotar diferentes paradigmas de programación, en el momento de construir software, atendiendo a criterios como la facilidad de desarrollo, la eficiencia, la portabilidad y la mantenibilidad.
    • CT5.2 - Conocer, diseñar y utilizar de forma eficiente los tipos y las estructuras de datos más adecuados para la resolución de un problema.
    • CT5.3 - Diseñar, escribir, probar, depurar, documentar y mantener código en un lenguaje de alto nivel para resolver problemas de programación aplicando esquemas algorítmicos y usando estructuras de datos.
    • CT5.4 - Diseñar la arquitectura de los programas utilizando técnicas de orientación a objetos, de modularización y de especificación e implementación de tipos abstractos de datos.
  • CT8 - Planificar, concebir, desplegar y dirigir proyectos, servicios y sistemas informáticos en todos los ámbitos, liderando su puesta en marcha, su mejora continua y valorando su impacto económico y social
    • CT8.6 - Demostrar comprensión de la importancia de la negociación, de los hábitos de trabajo efectivos, del liderazgo y de las habilidades de comunicación en todos los entornos de desarrollo de software.

Objetivos

  1. Diseñar una clase de datos con una clara independencia entre su especificación y su implementación. Justificar que la única forma de crear, consultar o modificar un objeto de una clase de datos sea a través de las operaciones de la especificación de la misma.
    Competencias relacionadas: CT5.4, CT5.3, CT1.1B, CT1.1A,
  2. Resolver en C++ cualquier ejercicio basado en la aplicación de un esquema algorítmico sencillo a un vector formado por objetos de una clase de datos.
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT5.4, CT5.3,
  3. Dada una implementación para una clase de datos sencilla, introducir mejoras en su representación y en sus operaciones.
    Competencias relacionadas: CT5.2, CT5.4, CT5.1, CT5.3, CT1.2B,
  4. Explicar las fases del diseño modular.
    Competencias relacionadas: CT5.4, CT5.1, CT5.3, CT1.1B, CT1.1A,
  5. Identificar en un enunciado textual de un problema las abstracciones de datos susceptibles de dar lugar a clases de datos que permitan resolver el problema. Comprobar si alguna de las abstracciones identificadas ya ha sido detectada en situaciones anteriores, para reutilizar la clase correspondiente.
    Competencias relacionadas: CT5.2, CT5.4, CT5.1, CT5.3,
  6. Diseñar de forma individual un programa modular en C++ a partir de las abstracciones de datos extraídas del enunciado de un problema. Modificar o añadir alguna funcionalidad a un programa modular dado escrito en C++.
    Competencias relacionadas: CT3.6, CT4.1, CT4.2, CT5.2, CT5.4, CT5.3, CT1.2B, CT1.1A,
  7. Implementar un programa modular en C++ con buen estilo y de forma que otros programadores sean capaces de entender qué hace y modificarlo. Redactar la documentación asociada a un programa modular en C++ de manera que favorezca el uso de dicho programa por parte de otros programadores.
    Competencias relacionadas: CT8.6, CT3.6, CT5.4, CT5.3,
  8. Preparar un programa en C++ que utilice tipos simples y clases C++ (algunas de ellas predefinidas y otras definidas por el propio alumno) para poder ser ejecutado. Esto se debe poder hacer de dos maneras: 1) compilando y enlazando manualmente con el comando g++; y 2) escribiendo un archivo makefile, y utilizándolo para compilar y enlazar el programa.
    Competencias relacionadas: CT1.1B, CT1.1A,
  9. Diseñar entre un grupo de estudiantes un programa modular en C++ y/o un conjunto de juegos de pruebas que traten todas las funcionalidades del mismo. Depurar sistemáticamente este programa, de forma que se puedan eliminar en un tiempo razonable pequeños errores de implementación.
    Competencias relacionadas: CT8.6, G5.1, CT3.6, CT5.3,
  10. Comocer los tipos de datos utilizados habitualmente para representar y manejar estructuras de datos lineales y su especificación. Diseñar algoritmos iterativos y recursivos para resolver problemas de búsqueda y recorrido en pilas, colas y listas, usando las operaciones del tipo de datos correspondiente e iteradores (cuando sea recomendable).
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT1.1A,
  11. Conocer tipos de datos utilizados para representar y manejar estructuras de datos arborescentes y su especificación. Diseñar algoritmos recursivos para resolver problemas de búsqueda y recorrido en árboles binarios, n-arios y generales usando las operaciones del tipo de datos correspondiente.
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT1.1A,
  12. Describir los principales pasos del diseño de algoritmos iterativos. Justificar la corrección de algoritmos iterativos relativamente sencillos.
    Competencias relacionadas: CT3.6, CT4.2, CT5.3, CT1.1A,
  13. Describir los principales pasos del diseño de algoritmos recursivos. Justificar la corrección de algoritmos recursivos relativamente sencillos.
    Competencias relacionadas: CT3.6, CT4.2, CT5.3, CT1.1A,
  14. Conocer el concepto de inmersión de una función, y saber explicar la diferencia entre inmersiones de especificación e inmersiones de eficiencia. Conocer los diferentes tipos de inmersiones de especificación y los distintos tipos de inmersiones de eficiencia.
    Competencias relacionadas: CT4.2, CT5.3, CT1.1A,
  15. Dado un algoritmo recursivo, determinar si existe una manera sencilla de obtener un algoritmo iterativo equivalente y, si es así, escribirlo.
    Competencias relacionadas: CT4.2, CT5.3, CT1.1A,
  16. Determinar si el coste de un algoritmo iterativo o recursivo sencillo dado que trabaje sobre vectores, pilas, colas, listas o árboles es lineal o si es cuadrático (suponiendo que el coste sea de uno de estos dos tipos).
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT1.1A,
  17. Determinar si se puede mejorar la eficiencia de un algoritmo recursivo sencillo dado y, en caso de que sea posible, diseñar un algoritmo recursivo alternativo más eficiente usando inmersiones de eficiencia.
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT1.1A,
  18. Determinar si se puede mejorar la eficiencia de un algoritmo iterativo sencillo dado y, en caso de que sea posible, diseñar un algoritmo iterativo alternativo más eficiente.
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT1.1A,
  19. Implementar una estructura de datos con requisitos específicos acerca de sus operaciones y/o la eficiencia de las mismas utilizando tipos de datos recursivos (o estructuras de datos enlazadas).
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
  20. Diseñar algoritmos iterativos y recursivos para resolver problemas de búsqueda y recorrido en estructuras de datos enlazadas utilizando directamente su representación.
    Competencias relacionadas: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
  21. Distignuir los roles de usuario, especificador e implementador de clases de datos. Conocer los elementos de la especificación de una clase de datos. Conocer los elementos de la implementación de una clase de datos.
    Competencias relacionadas: CT8.6, CT5.4, CT1.1B, CT1.1A,

Contenidos

  1. Estructuras de datos lineales
    Pilas, colas, listas, maps y sets: especificación y uso (operaciones de búsqueda y recorrido). Iteradores: definición y uso.
  2. Estructuras de datos arborescents
    Árboles binarios.
  3. Corrección de programas iterativos
    Invariante de un bucle. Justificación de la corrección de algoritmos iterativos.
  4. Programación recursiva y corrección de algoritmos recursivos
    Diseño inductivo de algoritmos recursivos. Justificación de la corrección de algoritmos recursivos. Inmersión (o generalización) de una función. Inmersiones de especificación: por debilitamiento de la postcondición y por reforzamiento de la precondición. Relación entre algoritmos recursivos lineales finales y algoritmos iterativos.
  5. Mejoras de eficiencia en programas recursivos e iterativos
    Detección de la repetición de cálculos en programas recursivos e iterativos. Inmersiones de eficiencia: nuevos datos (parámetros de entrada) y/o resultados (valores de retorno o parámetros de salida) en operaciones recursivas para mejorar la eficiencia. Nuevas variables locales que utilizan sus valores en iteraciones anteriores para mejorar la eficiencia de operaciones iterativas.
  6. Diseño modular y diseño basado en objetos
    Abstracción y su necesidad. Descomposición funcional y por datos. Módulos. Ocultación de la información. Encapsulado. Fases del diseño modular: distinción entre especificación e implementación. Tipos de módulos y su uso. Bibliotecas.

    Principios básicos de diseño basado en objetos: clases y objetos; campos y métodos.

    Implementación de diseños modulares en C++. Compilación separada y montaje. Depuración, prueba y documentación de programas modulares.
  7. Tipo recursivos de datos
    Introducción al uso de tipo recursivos de datos. El constructor de tipos puntero y la gestión de memoria dinámica. Implementación de estructuras de datos enlazadas mediante tipos recursivos de datos. Algoritmos iterativos y recursivos para resolver problemas de búsqueda y recorrido en estructuras de datos enlazadas accediendo directamente a la representación basada en nodos y punteros a nodos.

Actividades

Actividad Acto evaluativo


Ejercicios de repaso de C++.

Enlace con los contenidos de PRO1.
  • Laboratorio: Sesión laboratorio semana 1
Objetivos: 2 8
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Estructuras de datos lineales.

Desarrollo del tema correspondiente de la asignatura y ejercicios de laboratorio.
  • Teoría: Sesión teoría semana 3.
  • Laboratorio: Sesión laboratorio semana 6 y primera hora de la sesión semana 7
Objetivos: 10
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
9h

Programación recursiva

Desarrollo del tema correspondiente de la asignatura.
  • Teoría: Sesión teoría semana 6 y primera hora de la sesión semana 7.
Objetivos: 14 15 13
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Estructuras de datos arborescentes.

Desarrollo del tema correspondiente de la asignatura y ejercicios de laboratorio.
  • Teoría: Sesión teoría semana 4.
  • Laboratorio: Dos horas últimas de la sesión de laboratorio semana 7.
Objetivos: 11
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
9h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16h

Corrección de programas iterativos

Desarrollo del tema correspondiente de la asignatura.
  • Teoría: Sesión teoría semana 5
Objetivos: 12
Contenidos:
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
2h

Mejoras de eficiencia en programas recursivos e iterativos.

Desarrollo del tema correspondiente de la asignatura.
  • Teoría: Segunda hora de la sesión de teoría semana 7 y sesión semana 8.
Objetivos: 12 14 15 16 17 13 18
Contenidos:
Teoría
3h
Problemas
0h
Laboratorio
9h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12h

Introducción al diseño modular y el diseño basado en objetos.

Desarrollo del tema correspondiente de la asignatura.
  • Teoría: Sesiones teoría semanas 1 y 2.
Objetivos: 21 1 2 4
Contenidos:
Teoría
4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Especificación y uso de clases de objetos en C++.

Ejercicios del tema correspondiente de la asignatura.
  • Laboratorio: Sesiones laboratorio semanas 2 y 3.
Objetivos: 21 1 2
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Implementación de clases de objetos en C++.

Ejercicios del tema correspondiente de la asignatura.
  • Laboratorio: Sesión laboratorio semana 4.
Objetivos: 21 1 3
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
3h

Supervisión práctica

Supervisión del diseño e implementación de la práctica.
  • Laboratorio: Sesión laboratorio semana 11.
Objetivos: 3 5 6 7 8 10 11 16 17 21 1
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6h

Tipo recursivos de datos.

Desarrollo del tema correspondiente de la asignatura.
  • Teoría: Sesiones de teoría de las semanas 10, 11, 12 y 13
  • Laboratorio: Sesiones de laboratorio de las semanas 13 y 14
Objetivos: 16 17 19 20 1 3 18
Contenidos:
Teoría
7.5h
Problemas
0h
Laboratorio
9h
Aprendizaje dirigido
0h
Aprendizaje autónomo
16h

Repaso de teoría y problemas de exámenes.

Los alumnos podrán preguntar cuestiones concretas sobre los temas explicados en teoría.
  • Teoría: Sesión teoría semana 14.
  • Aprendizaje autónomo: Resolución de problemas de exámenes anteriores

Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
2h

EX_SIMUL1

Examen de simulacro para el Parcial 1
Objetivos: 10 11 16 17 19 20 2 3 5 6 7 8 18
Semana: 8 (Fuera de horario lectivo)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2h
Aprendizaje autónomo
2h

EX_PAR1_TP

Primer examen parcial de teoría y problemas.
Objetivos: 10 11 16 17 19 20 2 3 5 6 7 8 18
Semana: 9 (Fuera de horario lectivo)
Tipo: examen de teoría
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

CODI_DOC_PRAC

Entrega del código y la documentación de la práctica.
Objetivos: 10 11 12 14 16 17 21 1 5 6 7 8 9 13 18
Semana: 12 (Fuera de horario lectivo)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

EX_SIMUL2

Examen de simulacro para el Parcial 2
Objetivos: 10 11 16 17 19 20 2 3 5 6 7 8 18
Semana: 13 (Fuera de horario lectivo)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
2.5h
Aprendizaje autónomo
2.5h

EX_PAR2_TP

Segundo examen parcial de teoría y problemas.
Objetivos: 10 11 16 17 19 20 2 3 5 6 7 8 18
Semana: 15 (Fuera de horario lectivo)
Tipo: examen de teoría
Teoría
2.5h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6.5h

Metodología docente

El temario se expone de forma muy práctica a través de la presentación de muchos ejemplos.

Las clases de teoría introducen conocimientos, técnicas y conceptos que se ponen en práctica en las clases de laboratorio. También incluyen la presentanción y discusión de las soluciones de un conjunto de problemas.

Las dos horas de clases de teoría se imparten semanalmente. Las tres horas de las sesiones de laboratorio se imparten también semanalmente.

La programación de la práctica integra los conocimientos y las competencias de todo el curso, excepto tal vez el último tema (tipos recursivos de datos) que se evalúa en el segundo examen parcial de teoría.

Método de evaluación

La nota de las competencias técnicas (NCTEC) se calcula de la siguiente manera:

NCTEC = 0.3*EXAM1 + 0.3*EXAM2 + 0.25*PRAC + 0.15*DELIVERY

donde

* EXAM1 y EXAM2 son las notas del primer y del segundo exámenes parciales de teoría, respectivamente.

* PRAC es la nota de la práctica; podrá tener un componente obtenido de forma automática mediante la ejecución de juegos de prueba y un componente de corrección manual

* DELIVERY es la nota que se obtiene de las entregas por parte de los estudiantes de resolución de ejercicios a lo largo del curso.

No obstante NCTEC será NP si el peso de los actos de evaluación con nota NP es igual o superior al 70%.

La evaluación de la competencia transversal Trabajo en Equipo se obtiene de algunas de las entregas realizadas durante el curso (DELIVERY) que se harán en equipo.

Bibliografía

Básica:

Complementaria:

Web links

Capacidades previas

Tener formación sobre las técnicas de programación imperativa basada en:
- instrucciones básicas: asignación, alternativa, iteración
- acciones y funciones; paso de parámetros; recursividad
- vectores y tuplas; secuencias
- esquemas de recorrido y búsqueda
- algoritmos fundamentales: búsqueda binaria, ordenación de vectores, aritmética de matrices

Conocer bien al menos un lenguaje imperativo, preferentemente C++. Experiencia en la puesta en marcha de programas C++ en entorno Linux.

Capacidad para asimilar información a partir de un enunciado. Capacidad para argumentar sobre la corrección de un algoritmo y para comparar soluciones algorítmicas