Algorítmica

Usted está aquí

Inicio » Estudios » Grados » Grado en Ingeniería Informática » Plan de estudios » Asignaturas » Algorítmica
Créditos
6
Tipos
Obligatoria de especialidad (Computación)
Requisitos
  • Prerrequisito: EDA
  • Precorrequisito: PE
  • Correquisito: PROP
Departamento
CS;BSC;ENTEL
Web
http://www.cs.upc.edu/~mjserna/docencia/grauA/alg-GEI.html
Mail
La algorítmica estudia los algoritmos, sus propiedades y su eficiencia. El algorítmica tiene como objetivo el desarrollo de métodos y técnicas para el diseño de algoritmos y estructuras de datos (EDs) eficientes y su análisis, así como el desarrollo de algoritmos y EDs que resuelvan problemas concretos. Tras un breve repaso de conceptos y técnicas algorítmicas básicas ya conocidas, se estudian nuevas técnicas de diseño algorítmico como el método voraz (greedy method), la programación dinámica, los flujos sobre redes, la programación lineal y la aleatorización. Cada una de las técnicas de diseño y análisis estudiadas se ilustra con ejemplos concretos, muchos de ellos algoritmos y EDs de gran trascendencia práctica como el algoritmo de Dijkstra para el cálculo de caminos mínimos en un grafo, el algoritmo de cálculo de la distancia de edición entre dos strings, el test de primalidad de Rabin o el algoritmo de Ford-Fulkerson para encontrar el flujo óptimo sobre una red.

Profesorado

Responsable

  • Maria Jose Serna Iglesias ( )

Otros

  • Amalia Duch Brown ( )
  • Conrado Martínez Parra ( )
  • Maria Josep Blesa Aguilera ( )
  • Santiago Marco Sola ( )

Horas semanales

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

Competencias

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.2C - 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. CEFB1: Capacidad para la resolución de los problemas matemáticos que puedan plantarse en la ingeniería. Aptitud para aplicar los conocimientos sobre: algebra, cálculo diferencial e integral i métodos numéricos; estadística y optimización.
  • 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.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.

Competencias Transversales

Aprendizaje autónomo

  • G7 [Avaluable] - Detectar carencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento. Capacidad para el aprendizaje de nuevos métodos y tecnologías y versatilidad para adaptarse a nueves situaciones.
    • G7.3 - Aprendizaje autónomo: Capacidad de planificación y organización del trabajo personal. Aplicar los conocimientos adquiridos a la realización de una tarea en función de la pertenencia y la importancia, decidiendo la manera de llevarla a cabo y el tiempo que hay que dedicarle y seleccionando las fuentes de información más adecuadas. Identificar la importancia de establecer y mantener contactos con los compañeros de estudios, con el profesorado y con profesionales (networking). Identificar fórums de información sobre ingeniería TIC, sus avances y su impacto en la sociedad (IEEE, asociaciones, etc.).

Competencias Técnicas de cada especialidad

Especialidad de computación

  • CCO1 - Tener un conocimiento profundo de los principios fundamentales y de los 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 informática.
    • CCO1.1 - Evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución, y recomendar, desarrollar e implementar la que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
  • CCO2 - Desarrollar de forma efectiva y eficiente los algoritmos y el software apropiados para resolver problemas complejos de computación.
    • CCO2.5 - Implementar software de búsqueda de información (information retrieval).
  • CCO3 - Desarrollar las soluciones informáticas que, considerando el entorno de ejecución y la arquitectura del computador sobre el cual se ejecutan, consigan el mejor rendimiento.
    • CCO3.1 - Implementar código crítico siguiendo criterios de tiempo de ejecución, eficiencia y seguridad.
    • CCO3.2 - Programar considerando la arquitectura hardware, tanto en ensamblador como en alto nivel.

Objetivos

  1. Conocer el esquema de los algoritmos voraces, identificar cuándo y cómo aplicarlo, conocer las técnicas más habituales de demostración de la corrección de estos algoritmos, y familiarizarse con algunos algoritmos voraces fundamentales, tales como el algoritmo de Dijkstra, el de Kruskal y el de Prim.
    Competencias relacionadas: CT1.2C, CT4.1, CT4.2, CT5.2, CCO1.1, G7.3,
  2. Conocer el esquema de programación dinámica, identificar cuándo se puede aplicar y cómo y familiarizarse con algunos algoritmos de programación dinámica fundamentales, por ejemplo, el algoritmo de Floyd o el cálculo de la distancia de edición
    Competencias relacionadas: G7.3, CT1.2C, CT4.1, CT4.2, CT5.2, CCO1.1,
  3. Conocer el problema básico de cálculo de flujos óptimos sobre redes, familiarizarse con un algoritmo básico (Ford-Fulkerson), entender el teorema de maxflow-mincut, reconocer cuándo un problema se puede formular en términos de un problema de flujos
    Competencias relacionadas: G7.3, CT1.2C, CT4.1, CT4.2, CCO1.1,
  4. Comprender la importancia del aleatorización en el diseño de algoritmos y estructuras de datos, familiarizarse con algunas técnicas elementales de análisis probabilístico necesarias para estudiar la eficiencia de los algoritmos aleatoritados y familiarizarse con algunos ejemplos clásicos.
    Competencias relacionadas: CT1.2C, CT4.1, CT4.2, CCO1.1, G7.3,
  5. Conocer algunos problemas computacionales específicos que surgen en ámbitos tan dispares como la búsqueda en bases de datos documentales, bases de datos proteínicas y genómicas, sistemas de información geográfica, recuperación de información basada en el contenido, compresión de datos, etc. y conocer algunas estructuras de datos avanzadas para dar respuesta a estas necesidades
    Competencias relacionadas: G7.3, CT1.2C, CT4.1, CT4.2, CT5.2, CCO1.1, CCO2.5, CCO3.1,
  6. Familiarizarse con el uso de los principios de diseño algorítmico para el diseño de estructuras de datos y conocer algunas técnicas esenciales para obtener implementaciones de éstas que garanticen la máxima eficiencia y saquen partido de las caracterísitcas específicas del hardware que debe soportar estas estructuras de datos
    Competencias relacionadas: G7.3, CT1.2C, CT4.1, CT4.2, CT5.2, CCO1.1, CCO3.1, CCO3.2,
  7. Desarrollar los hábitos, actitudes y habilidades necesarias para poder estudiar, de manera independiente o en equipo, un tema específico, haciendo uso de las fuentes de información disponibles (bibliografía, Web, ...) y conseguir el nivel de conocimiento y compresión del tema suficiente como para poder explicarlo a terceros, escribiendo un resumen y preparando un material audiovisual complementario
    Competencias relacionadas: G7.3,
  8. Conocer y comprender algunos principios básicos para el diseño de experimentos computacionales y aprender técnicas básicas de recogida de datos, validación y análisis estadístico de los datos recogidos y cómo sacar conclusiones; reconocer la necesidad, la utilidad y las limitaciones de los estudios experimentales en el diseño e implementación de algoritmos y estructuras de datos
    Competencias relacionadas: G7.3, CT4.1, CT4.2, CT5.2, CT5.3, CT5.4, CCO3.1, CCO3.2,

Contenidos

  1. Conceptos Algorítmicos Básicos
    Análisis de caso peor. Notación asintótica. Divide y vencerás. Análisis de algoritmos recursivos. Ordenación lineal. Algortmos para grafos. Aleatorització.
  2. Algoritmos Voraces
    Esquema voraz. Planificación de tareas. Algoritmos de Bellman-Ford y Johnson para caminos mínimos. Algoritmos de Kruskal y Prim para árboles de expansión mínimos. Particiones (Union-find). Códigos de Huffman.
  3. Programación Dinámica
    Principio de optimalidad. Memoización. Árboles binarios de búsqueda óptimos. Algoritmo de Floyd-Warshall para caminos mínimos. Problema del viajante de comercio. Problema de la mochila. Otros ejemplos.
  4. Flujos sobre Redes
    Conceptos básicos. Teorema de maxflow-mincut. Algoritmo de Ford-Fulkerson. Aplicaciones: matchings y caminos sin aristas en común. Dualidad.
  5. Estructuras de Datos y Algoritmos Avanzadoss
    Una selección de algunos de los siguientes algoritmos y/o estructuras de datos (o otros). Programación lineal. Montículos de Fibonnacci. Hashing. Filtros Bloom. Blockchains. Map Reduce. Grafos aleatorios. PageRank.

Actividades

Actividad Acto evaluativo


Conceptos Algorítmicos Básicos

Recordar conceptos fundamentales aprendidos en las asignaturas previas, y familiarizarse con la terminología y notación que se utilizará a lo largo del curso. Aprender otras técnicas algorítmicas básicas.
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación

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

Algoritmos voraces

Atender las clases de teoría y problemas dónde se desarrolla el tema y hacer los ejercicios propuestos por el profesor para hacer en casa o en clase
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación
Objetivos: 1
Contenidos:
Teoría
5h
Problemas
4h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
10h

Programación Dinámica

Atender las clases de teoría y problemas dónde se desarrolla el tema y hacer los ejercicios propuestos por el profesor para hacer en casa o en clase
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación
Objetivos: 2
Contenidos:
Teoría
7h
Problemas
10h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
15h

Flujos sobre Redes

Atender las clases de teoría y problemas dónde se desarrolla el tema y hacer los ejercicios propuestos por el profesor para hacer en casa o en clase
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación
Objetivos: 3
Contenidos:
Teoría
7h
Problemas
10h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
15h

Estructuras de Datos Avanzadas

Atender las clases de teoría y problemas dónde se desarrolla el tema y hacer los ejercicios propuestos por el profesor para hacer en casa o en clase
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación
Objetivos: 5 6
Contenidos:
Teoría
2h
Problemas
2h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
4h

Proyecto de Aprendizaje Autónomo

El profesor asignará un proyecto de programación de mediana envergadura que involucra el estudio autónomo de un tema concreto incluyendo alguna componente que no se ha visto en clase. A final del curso podrá entrevistar al equipo para complementar la informacióde cara a la evaluación de esta actividad Los estudiantes formarán equipos de dos o tres personas para desarrollar un programa junto con la documentación escrita y material adicional.
Objetivos: 1 2 3 4 5 6 7 8
Semana: 6 (Fuera de horario lectivo)
Tipo: entrega
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
15h

Examen Final/Segundo parcial


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

Examen parcial

Examen parcial liberatorio fuera de horas de clase.
Objetivos: 1 2 5 6 7
Semana: 8
Tipo: examen de teoría
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Tutorización del proyecto

Resolver dudas, hacer el seguimiento de la actividad, etc
Objetivos: 6 7 8
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
6h
Aprendizaje autónomo
0h

Metodología docente

Las clases de teoria son de estilo magistral, con exposiciones teóricas por parte del profesor, intercaladas con numerosos ejemplos. Se espera que los estudiantes participen activamente con sus preguntas y comentarios a lo largo de estas clases. Cada semana se hacen dos horas y dos de problemas. En las clases de problemas se discutirán las soluciones propuestas por los estudiantes a los ejercicios planteados por el profesor con antelación (enunciados más complejos, con los que el estudiante ha podido trabajar durante una semana, autónomamente) o a los ejercicios cortos planteados en la propia clase, para trabajarlos en equipos de dos estudiantes o individualmente. Ocasionalmente, los estudiantes podrán ser requeridos para exponer su solución al resto de sus compañeros.

Complementado el estudio personal y la resolución de ejercicios prácticos en papel, se propondrá un proyecto de programación en el que el estudiante habrá de diseñar y codificar programas en C++ que resuelvan los problemas planteados, p.e. implementar dos (o más) algoritmos que resuelven un mismo problema y llevar a cabo experimentos que permitan comparar la eficiencia de los algoritmos, y a su vez, comparar dichas eficiencias con las predicciones del análisis teórico. El proyecto se desarrollará en equipo (equipos de dos o tres personas).
Él proyecto se usará para evaluar la competencia de aprendizaje autónomo, ya que requerirá estudiar un tema concreto, relacionado con los que se ven a lo largo del curso, pero no expuesto en clase de teoria.

Método de evaluación

La nota final (NF) se calcula a partir de la nota de la resolución de problemas algorítmicos (A), la de las pruebas escritas parcial (M) (materia correspondiente a las 6 -7 primeras semanas del curso) y examen final (F); y la nota del proyecto asociado al aprendizaje autónomo (P).

La nota final se calcula de acuerdo con la fórmula:

NF = 0.7 max(0.4 M + 0.6 F, F) + 0.2 P +0.1 A

El profesorado evaluará el grado de adquisición de la competencia de aprendizaje autónomo a partir de la nota obtenida en un ejercicio de programación que involucra un trabajo de aprendizaje autónomo por parte de los alumnos. La nota P se evaluarà en una escala numérica de 0 a 10.

La nota cualitativa de la competencia transversal se determina a partir de la nota numèrica
P según los siguientes tramos: [0,5) => D, [5,6.5) => C, [6.5,8.5) => B, [8.5,10] => A

Bibliografía

Básica:

Complementaria:

Capacidades previas

- Familiaridad con las técnicas básicas de programación y el lenguaje de programación C++: iteraciones, alternativas, funciones recursivas,
paso de parámetros, punteros, referencias, memoria dinámica, clases, objetos, métodos, ...

- Conocimiento de conceptos algorítmicos básicos: eficiencia de algoritmos, notación asintótica, grafos, recorridos de grafos, estructuras de datos (listas, árboles de búsqueda, hash, heaps, ...)

- Conocimientos básicos de matemática discreta, algebra lineal y cálculo

- Conocimientos básicos de teoría de probabilidad y estadística

- Conocimientos básicos de arquitectura de computadores y de la jerarquía de memoria