Algoritmia y Programación II

Créditos
7.5
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Web
http://www.cs.upc.edu/~jordicf/Teaching/AP2
Se introduce el análisis matemático de los algoritmos y se presentan las herramientas para calcular su coste. Estas bases se utilizan para estudiar y analizar el diseño y las diferentes implementaciones de varios algoritmos y estructuras de datos fundamentales (pilas, colas, listas, colas de prioridad, árboles, árboles binarios de búsqueda, árboles equilibrados, tablas de hash y grafos) . Asimismo, se introducen las herramientas necesarias para poder implementar estas estructuras de datos y sus algoritmos asociados y se profundiza en la orientación a objetos y el uso de librerías externas.

Profesorado

Responsable

Otros

Horas semanales

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

Competencias

Competencias Técnicas

Competencias técnicas

  • CE2 - Ser capaz de programar soluciones a problemas de ingeniería: Diseñar soluciones algorítmicas eficientes a un problema computacional dado, implementarlas en forma de Programa robusto, estructurado y mantenible, y comprobar la validez de la solución.

    • Competencias Transversales

    Transversales

  • CT4 - Trabajo en equipo. Ser capaz de trabajar como miembro de un equipo interdisciplinar, 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.
  • CT5 [Avaluable] - Uso solvente de los recursos de información. Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información en el ámbito de especialidad y valorar de forma crítica los resultados de dicha gestión.
  • CT6 - Aprendizaje autónomo. Detectar deficiencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar dicho conocimiento.
  • CT7 - Tercera lengua. Conocer una tercera lengua, preferentemente el inglés, con un nivel adecuado oral y escrito y en consonancia con las necesidades que tendrán los titulados y tituladas.

    • Básicas

  • CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Concebir sistemas computacionales que integren datos de procedencias y formas muy diversas, creen con ellos modelos matemáticos, razonen sobre dichos modelos y actúen en consecuencia, aprendiendo de la experiencia.
  • CG2 - Elegir y aplicar los métodos y técnicas más adecuados a un problema definido por datos que representen un reto por su volumen, velocidad, variedad o heterogeneidad, incluidos métodos informáticos, matemáticos, estadísticos y de procesado de la señal.
  • CG5 - Poder recurrir a conocimientos fundamentales y metodologías de trabajo sólidas adquiridos durante los estudios para adaptarse a los nuevos escenarios tecnológicos del futuro.

    • Objetivos

    1. Ser capaz de diseñar, analizar, implementar algoritmos que resuelvan problemas utilizando técnicas algorítmicas y de programación.
      Competencias relacionadas: CB5, CT4, CT5, CT6, CT7, CG1, CG2, CG5, CE2,

    Contenidos

    1. Tipos Abstractos de Datos.
      Especificación e implementación. Abstracción, descomposición funcional y por datos, ocultación y encapsulación de la información. Lenguajes orientados a objetos: clases y objetos, métodos privados y públicos, constructores y destructores. Genericidad. Ejemplos: punto, rectángulo, números racionales.
    2. Análisis de algoritmos.
      Coste en tiempo y espacio. Caso peor, mejor y medio. Notación asintótica. Análisis del coste de algoritmos iterativos y recursivos. Ejemplos: ordenación por inserción y selección, subsecuencia de suma máxima, envolvente convexa.
    3. Dividir y vencer.
      Principios: partición en subproblemas, recombinación de soluciones. Teorema Master. Ejemplos: búsqueda binaria, ordenación por fusión, ordenación y selección rápidas, cálculo de los dos puntos más cercanos en un plano. Transformada rápida de Fourier (FFT).
    4. Gestión de memoria.
      Representación de los datos en memoria. Punteros y referencias. Gestión dinámica de memoria (clase vector). Estructura de la memoria de un programa (código, pila, heap).
    5. Contenedores básicos.
      Operaciones, usos e implementaciones de pilas, colas, colas de prioridades y listas.
    6. Grafos.
      Representaciones: matrices de adyacencia, listas de adyacencia y representación implícita. Búsqueda en profundidad (DFS). Búsqueda en anchura (BFS). Ordenación topológica. Algoritmos por caminos mínimos (Dijsktra, Bellman-Ford). Algoritmos para árboles de expansión mínimos (Prim y Kruskal). Algoritmos para flujos máximos (Ford-Fulkerson).
    7. Conjuntos y diccionarios.
      Árboles y su representación. Árboles binarios y recorridos (pre-orden, post-orden, in-orden y por niveles). Árboles de búsqueda binarios y árboles balanceados: operaciones e implementación. Tablas de dispersión.

    Actividades

    Actividad Acto evaluativo


    Desarrollo del contenido 1


    Objetivos: 1
    Contenidos:
    Teoría
    5h
    Problemas
    0h
    Laboratorio
    3h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    9h

    Examen parcial (con ordenador)


    Objetivos: 1
    Semana: 7 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen final (sobre papel)



    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen final (sobre ordenador)



    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Entrega de la práctica



    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Desarrollo del contenido 2


    Objetivos: 1
    Contenidos:
    Teoría
    5h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Desarrollo del contenido 3


    Objetivos: 1
    Contenidos:
    Teoría
    7h
    Problemas
    0h
    Laboratorio
    5h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    20h

    Desarrollo del contenido 4


    Objetivos: 1
    Contenidos:
    Teoría
    3h
    Problemas
    0h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    7.5h

    Desarrollo del contenido 5


    Objetivos: 1
    Contenidos:
    Teoría
    7h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    Desarrollo del contenido 6


    Objetivos: 1
    Contenidos:
    Teoría
    9h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    21h

    Desarrollo del contenido 7



    Contenidos:
    Teoría
    7h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    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 todos los conceptos y técnicas necesarios, los cuales se ponen en práctica en las clases de problemas y de laboratorio mediante una colección de problemas y ejercicios en un juez automático.

    Cada semana se hacen dos horas de clase de teoría, una hora de problemas y dos horas de laboratorio.

    El curso utiliza los lenguajes de programación C++ y Python.

    Método de evaluación

    La nota final de la asignatura tiene en cuenta los siguientes actos de evaluación:
    * P1: proyecto de programación individual a entregar a mediados de curso
    * P2: proyecto de programación en pareja a entregar a final de curso
    * PL: examen parcial de laboratorio (con ordenador)
    * FL: examen final de laboratorio (con ordenador)
    * FT: examen final de teoría (con papel)

    La nota de proyectos se calcula como: P = (P1 + P2)/2
    La nota de exámenes se calcula como: X = max (0.3 PL + 0.4 FT + 0.3 FL, 0.5 FT + 0.5 FL)

    La nota final N se calcula como:
    * N = max(0.3 P + 0.7 X, 0.15 P + 0.85 X), si X >= 4
    * N = 0.15 P + 0.85 X, si X < 4

    Los alumnos que suspendan la asignatura podrán hacer los exámenes de reevaluación RL (laboratorio) y RT (teoría). Las nota de estos exámenes sustituirán FL y FT, respectivamente, en la fórmula de cálculo de la nota final.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    Las del curso AP1-GCED.