Algoritmia y Programación II

Usted está aquí

Créditos
7.5
Tipos
Obligatoria
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
CS
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.

Profesores

Responsable

  • Jordi Cortadella Fortuny ( )

Otros

  • Jordi Petit Silvestre ( )

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

  • CT5 - 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: CE2, CT5, CT6, CT7, CG1, CG2, CG5, CB5,

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
8h

Examen parcial (con ordenador)


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

Examen final (sobre papel)



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

Examen final (sobre ordenador)



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

Entrega de la práctica



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

Desarrollo del contenido 2


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

Desarrollo del contenido 3


Objetivos: 1
Contenidos:
Teoría
9h
Problemas
0h
Laboratorio
6h
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
6h

Desarrollo del contenido 5


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

Desarrollo del contenido 6


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

Desarrollo del contenido 7



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

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 del curso se calcula en función de una nota obtenida de dos proyectos de laboratorio (NL), un examen parcial realizado sobre ordenador (NP), y un examen final que consta de dos pruebas: una sobre papel (NF1) y la otra sobre ordenador (NF2).

La nota final es el máximo de:
   * 12:15 NL + 12:25 NP + 0.3 NF1 + 0.3 NF2
   * 12:15 NL + 0425 NF1 + 0425 NF2

Reevaluación:
En el examen de reevaluación se podrán presentar sólo aquellos estudiantes que se hayan presentado los actos de evaluación y no hayan aprobado el curso. Para el examen de reevaluación se realizan dos pruebas similares al examen final: una sobre papel (R1) y la otra sobre ordenador (R2). En caso de no presentarse a alguna de las pruebas, se mantendrá la nota correspondiente del examen final (NF1 o NF2).

En caso de reevaluación, la nota final del curso se calcula como el máximo de:
   * 0.5 R1 + 0.5 R2
   * 12:15 NL + 0425 R1 + 0425 R2

Bibliografía

Básica:

Complementaria:

Web links

Capacidades previas

Las del curso AP1-GCED.