Programación y Algorítmica II

Créditos
6
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Segunda parte del curso de Introducción a la Programación para los alumnos del grado de IA (formado por PA1+PA2). En este curso nos centraremos esencialmente en la abstracción con datos, definiendo nuevas estructuras de datos (pilas, colas, listas, árboles, grafos, heaps) o viendo cómo se implementan estructuras de datos conocidas (conjuntos y diccionarios). Al final de la asignatura se verá la continuación del tema de complejidad, que comenzó al final de PA1

Profesorado

Responsable

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

Otros

  • Caroline König (caroline.leonore.konig@upc.edu)
  • Jose Luis Balcázar Navarro (jose.luis.balcazar@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.

    • 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. Conocer nuevas estructuras de datos: Pilas, Colas, Listas, Árboles y Grafos y los algoritmos asociados a las operaciones necesarias sobre estas estructuras.
      Competencias relacionadas: CG2, CG4, CT6, CE03, CE04, CE12,
    2. Conocer diferentes implementaciones de estructuras de datos: Implementaciones utilizando estructuras de datos más simples proporcionadas por el lenguaje de programación, e implementaciones dinámicas.
      Competencias relacionadas: CG2, CG4, CE02, CE03, CE04, CE12,
    3. Conocer los principios básicos de la orientación a objetos: Conceptos de clase, instancia, método, herencia (simple y múltiple), etc.
      Competencias relacionadas: CG2, CG4, CT6, CE03, CE04, CE10,
    4. Ampliación de Complejidad Computacional: Big O, Big Omega, Master Theorems
      Competencias relacionadas: CG2, CG4, CT6, CE02, CE12, CE13,
    5. Resolver en grupo un problema de tamaño pequeño-medio aplicando lo aprendido sobre orientación a objetos
      Competencias relacionadas: CG2, CG4, CG8, CT4, CE03, CE04, CE10,

    Contenidos

    1. Árboles y Grafos
      Comenzaremos el curso utilizando las estructuras de datos que el lenguaje de programación nos proporciona para implementar los Árboles y los Grafs. Veremos algoritmos de recorrido para las dos estructuras, y otros algoritmos importantes relacionados con éstas, como por ejemplo el algoritmo de Dijkstra.
    2. Objetos y Clases
      Se introducen los conceptos fundamentales de orientación a objetos: Clase, objeto, instancia, delegación, herencia, etc. y otras particularidades de la implementación de la orientación a objetos propias del lenguaje de programación con que trabajamos.
    3. Estructuras dinámicas de datos
      Se estudia cómo implementar estructuras de datos conocidas utilizando el concepto de referencia a un objeto. Se reimplementarán de este modo estructuras de datos que el lenguaje de programación proporciona por defecto, y estructuras de datos nuevas que ya hemos visto implementadas de forma más sencilla.
    4. Conjuntos y Diccionarios: Implementación
      Veremos diferentes formas de implementar conjuntos y diccionarios: Tablas Hash y árboles binarios de búsqueda (BSTs). Se estudiarán las propiedades de estas estructuras, sus ventajas e inconvenientes.
    5. Ampliación de Complejidad Algorítmica
      En PA1 se empezó a ver el concepto de complejidad de un programa, un algoritmo y un problema, e introdujimos la notación asintótica, concretamente la definición de Theta(f). Este tema quiere ser una continuación, donde veremos la Big O, la Big Omega, etc, y los Master Theorems.

    Actividades

    Actividad Acto evaluativo


    Construyendo Abstracciones con Datos. Árboles y Grafos

    Es necesario que el estudiante esté atento en clase y realice los ejercicios propuestos.
    Objetivos: 1 2
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    5h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Construyendo Abstracciones con Funciones: Objetos y Clases

    Es necesario que el estudiante esté atento en clase y realice los ejercicios propuestos.
    Objetivos: 2 3
    Contenidos:
    Teoría
    8h
    Problemas
    0h
    Laboratorio
    8h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    Construyendo Abstracciones con Datos: Estructuras Dinámicas de Datos

    Es necesario que el estudiante esté atento en clase y realice los ejercicios propuestos.
    Objetivos: 1 2
    Contenidos:
    Teoría
    6h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Conjuntos y Diccionarios: Implementación

    Es necesario que el estudiante esté atento en clase y realice los ejercicios propuestos.
    Objetivos: 2 3
    Contenidos:
    Teoría
    4h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Ampliación de Complejidad Algorítmica

    Es necesario que el estudiante esté atento en clase y realice los ejercicios propuestos.
    Objetivos: 4
    Contenidos:
    Teoría
    6h
    Problemas
    0h
    Laboratorio
    6h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8h

    Trabajo Práctico

    Los estudiantes harán una práctica en parejas relacionada con un problema de tamaño pequeño-medio.
    Objetivos: 1 2 3 5
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Examen Parcial


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

    Examen Final


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

    Metodología docente

    La docencia de la asignatura está estructurada en clases de teoría y clases de laboratorio.

    En las clases de teoría los profesores presentan los contenidos esenciales de la asignatura. En las clases de laboratorio se practican los contenidos de la asignatura (los presentados en clase y los adquiridos autónomamente) mediante la realización de problemas prácticos. Las clases de laboratorio serán una continuación de las clases teóricas, donde los conceptos nuevos se implementarán a medida que vayan apareciendo.

    Método de evaluación

    El método de evaluación de la asignatura consistirá en dos pruebas de carácter teórico (T1 y T2), una a mediados de curso y otra al final y una práctica de tamaño pequeño-medio (Practica).

    Entonces, el método de evaluación sería:
    0.8 * Teoría + 0.2 * Practica
    donde:
    Teoría: MAX(T2, 0.5 * T1 + 0.5 * T2)

    Reevaluación: sólo se pueden presentar a la reevaluación aquellas personas que, habiéndose presentado en el examen final, hayan suspendido la teoría. La nota máxima que se puede obtener en la reevaluación es un 7.

    Competencia transversal "Trabajo en equipo":

    Se evalúa usando una rúbrica simple en que el tutor de cada grupo puntúa los
    diferentes aspectos del trabajo en equipo de cada miembro de los grupos.

    Bibliografía

    Básico

    Complementario

    • Python pocket reference - Lutz, Mark, O'Reilly Media, 2014. ISBN: 9781449356941

    Web links

    • Aquest és el text PRINCIPAL de l'assignatura, la font d'informació primària per a tot allò que expliquem a classe. Tot i això, a PA2 hi ha temes que no apareixen en aquest text. http://composingprograms.com/
    • La principal referència del llenguatge de programació que fem servir: Python. No és un lloc on aprendre a programar, és un lloc on consultar detalls de les construccions i llibreries del llenguatge https://docs.python.org/3/reference/index.html

    Capacidades previas

    Curso PA1, o equivalente