Algorítmica

Usted está aquí

Créditos
6
Tipos
Obligatoria de especialidad (Computación)
Requisitos
  • Correquisito: PROP
  • Prerrequisito: EDA
  • Precorrequisito: PE

Departamento
CS
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.

Profesores

Responsable

  • Maria Jose Serna Iglesias ( )

Otros

  • Josep Diaz Cort ( )
  • M. Jose Blesa Aguilera ( )
  • Maria Del Carme Alvarez Faura ( )

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 - 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.
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, 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
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, G7.3,
  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
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, G7.3,
  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 como quicksort aleatorizado, las skip lists, el test de primalidad de Rabin o el algoritmo de búsqueda de patrones de Karp-Rabin
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, 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
    Related competences: CCO2.5, CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, G7.3,
  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
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, CCO3.2, G7.3,
  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
    Related competences: 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
    Related competences: CT5.3, CT4.1, CT4.2, CT5.2, CT5.4, CCO3.1, CCO3.2, G7.3,

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. Hashing. 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 algunas de las siguientes estructuras de datos u otras juntamente con algoritmos asociados. Montículos de Fibonnacci. Cuckoo hashing. Filtros Bloom. Blockchains. Árboles mutidimensionales. Map Reduce. Grafos aleatorios.

Actividades

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.
Teoría
6
Problemas
6
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
10
  • Aprendizaje autónomo: - Estudio de la teoría y problemas vistos en clase - Resolución de los ejercicios propuestos con antelación

Contenidos:

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
Teoría
4
Problemas
4
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
6
  • 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:

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
Teoría
4
Problemas
6
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
10
  • 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:

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
Teoría
8
Problemas
8
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
10
  • 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:

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
Teoría
8
Problemas
6
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
7
  • 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:

Resolución de problemas

El objetivo es resolver los problemas propuestos por el profesor, con carácter individual. Se dispondrá de un mínimo de 4 días entre la fecha en la que el enunciado se asigna y la clase de problemas en la que se presentará la solución y una semana más para entregar por escrito la solución. A lo largo del curso se asignarán 2 o tres problemas a cada estudiante.
Teoría
0
Problemas
0
Laboratorio
0
Aprendizaje dirigido
3
Aprendizaje autónomo
11
Objetivos: 1 2 3 4 5 6 8
Contenidos:

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, a lo largo del curso se propondrán ejercicios de programación, en los que el estudiante habrá de diseñar y codificar programas en C++ que resuelvan los problemas planteados, p.e. implementar dos algoritmos que resuelven un mismo problema y llevar a cabo un experimento computacional que permita comparar la eficiencia de los dos algoritmos, y a su vez, comparar dichas eficiencias con las predicciones del análisis teórico. Cada estudiante deberá realizar una serie de ejercicios de progrmación de manera individual y otro en equipo (equipos de dos personas).
Éste último 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 de algorítmia (E), de ejercicios de programación (P), la nota de la prueba final escrita (F) y la nota del trabajo asociado al aprendizaje autónomo (A) según la fórmula

NF = 0.6 F + 0.1 E + 0.1 P + 0.2 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 A 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
A 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