Programación y Algorítmica Avanzada

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Web
https://www.cs.upc.edu/~balqui/paa.html
Se estudian los fundamentos de la computación y técnicas para el eficiente diseño de algoritmos. Se repasan las técnicas básicas algorítmicas y su análisis, y se explican técnicas adicionales de diseño de algoritmos. Seguidamente, se estudian los límites de la computación, como consecuencia del estudio de modelos formales de cálculo,
y se realiza una introducción a la complejidad computacional.

Profesorado

Responsable

  • Jose Luis Balcázar Navarro (jose.luis.balcazar@upc.edu)

Otros

  • Jordi Delgado Pin (jdelgado@cs.upc.edu)

Horas semanales

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

Competencias

Competencias Transversales

Transversales

  • CT4 [Avaluable] - 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.
  • CT6 [Avaluable] - 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.

    • Básicas

  • CB1 - Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
  • CB2 - Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.

    • Competencias Técnicas

    Específicas

  • CE02 - 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.
  • CE03 - Identificar i aplicar els procediments algorítmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algorismes proposats.
  • CE04 - Diseñar y utilizar de forma eficiente los tipos y estructuras de datos más adecuados a la resolución de un problema.
  • CE10 - Analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, eligiendo el paradigma y los lenguajes de programación más adecuados.
  • CE12 - Dominar los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la inteligencia artificial.
  • CE13 - Evaluar la complejidad computacional de un problema, identificar estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG2 - Utilizar los conocimientos fundamentales y metodologías de trabajo sólidas adquiridos durante los estudios para adaptarse a los nuevos escenarios tecnológicos del futuro.
  • CG4 - Razonar, analizando la realidad y diseñando algoritmos y formulaciones que la modelen. Identificar problemas y construir soluciones algorítmicas o matemáticas válidas, eventualmente nuevas, integrando el conocimiento multidisciplinar necesario, valorando distintas alternativas con espíritu crítico, justificando las decisiones tomadas, interpretando y sintetizando los resultados en el contexto del dominio de aplicación y estableciendo generalizaciones metodológicas a partir de aplicaciones concretas.
  • CG8 - Observar un ejercicio ético de la profesión en todas sus facetas, aplicando criterios éticos en el diseño de sistemas,algoritmos, experimentos, utilización de datos, de acuerdo con los sistemas éticos recomendados por los organismos nacionales e internacionales, con especial énfasis en seguridad, robustez, privacidad, transparencia, trazabilidad, prevención de sesgos (de raza, género, religión, territorio, etc.) y respeto a los derechos humanos.

    • Objetivos

    1. Aprender a analizar algoritmos y conocer las notaciones asintóticas.
      Competencias relacionadas: CG2, CG4, CE02, CE03, CE12,
    2. -
      Competencias relacionadas: CG4, CG8, CT4, CT6, CB2, CE02, CE03, CE12, CE13,
    3. -
      Competencias relacionadas: CG4, CT6, CB2, CE02, CE03, CE04, CE10, CE13,
    4. -
      Competencias relacionadas: CG4, CT4, CB1, CB2, CE02, CE13,

    Contenidos

    1. -
      -
    2. --
      -
    3. -
      -
    4. -
      -

    Actividades

    Actividad Acto evaluativo


    -

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

    -

    -
    • Teoría: Planificación de tareas. Algoritmos para caminos mínimos. Algoritmos de Kruskal y Prim para árboles de expansión mínimos. Particiones (Union-find). Códigos de Huffman.
    Objetivos: 3
    Contenidos:
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    2h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    -

    -
    • Teoría: Concepto, ejemplos y características de los algoritmos de programación dinàmica. Principio de optimalidad. Memoización. Árboles binarios de búsqueda óptimos. Algoritmo de Floyd-Warshall para caminos mínimos. Problema de la mochila. Otros ejemplos.
    Objetivos: 3
    Contenidos:
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    -

    -
    Objetivos: 4
    Contenidos:
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    6h

    -

    -
    Objetivos: 4
    Contenidos:
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    -

    -
    Objetivos: 1 3 4
    Semana: 8
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    -

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

    -

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

    -

    -
    Objetivos: 2 4
    Contenidos:
    Teoría
    5h
    Problemas
    0h
    Laboratorio
    8h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    -

    -
    Objetivos: 2 4
    Contenidos:
    Teoría
    6h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Metodología docente

    -

    Método de evaluación

    Parte de la sección de Algorítmica (inicial del curso) requerirá para su evaluación una práctica de dimensión modesta que se presentará al principio del tema Programación Dinámica y se evaluará en su entrega (nota P).

    Adicionalmente habrá la nota del parcial (E) y la del examen final (nota F). La nota del curso se obtendrá mediante el siguiente criterio:

    max(F*0.8, (E*0.3 + F*0.5)) + P*0.2

    Reevaluación
    Sólo se pueden presentar en el examen de reevaluación quien previamente se haya presentado en el examen final y lo haya suspendido. La nota máxima de reevaluación es un 7.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    -