Denominación de la asignatura |
Algoritmia y Complejidad |
Grado al que pertenece |
Grado en Ingeniería Informática |
Créditos ECTS |
6 |
Curso y cuatrimestre en el que se imparte |
Primer curso, segundo cuatrimestre |
Carácter de la asignatura | Obligatoria |
Existen múltiples ramas de la ingeniería informática para las que el ingeniero necesita identificar un algoritmo o estructura de datos que resuelva de forma eficaz el problema que pretende abordar. Un ingeniero familiarizado con los algoritmos clásicos tendrá mayor probabilidad de éxito a la hora de encontrar un algoritmo novedoso para el problema donde intenta innovar, ya que le resultará más fácil diseñar una modificación de uno o más de los principios e ideas en los que se basan estos algoritmos.
Por ello, es necesario familiarizar desde el primer curso al estudiante con las técnicas generales de diseño de algoritmos. En esta asignatura se introducen los principales algoritmos y estructuras de datos que existen en la literatura específica y sirve como base para posteriores asignaturas donde se profundiza en conocer técnicas más modernas y avanzadas.
No solo es necesario que el estudiante sepa reconocer algoritmos eficaces, sino que también sepa elegir los algoritmos más eficientes para cada situación. Esto implica el saber analizar y medir la complejidad de un algoritmo, saber identificar posibles cuellos de botella y prevenir congestiones que retarden la ejecución de su programa. Para ello, la asignatura también enseña a determinar la cantidad de recursos (temporales y de memoria) necesarios para ejecutar un algoritmo, así como a clasificar los algoritmos de acuerdo a su complejidad computacional.
A continuación se enumeran las competencias que adquirirás al cursar esta asignatura:
Tema 1. Estrategias de diseño de algoritmos
Estrategias de diseño de algoritmos
Recursividad
Divide y conquista
Programación dinámica
Algoritmos ávidos (greedy algorithms)
Método del retroceso (backtracking)
Ramificación y poda (branch and bound)
Tema 2. Eficiencia de algoritmos
Medidas de eficiencia
Medir el tamaño de la entrada
Medir el tiempo de ejecución
Caso peor, mejor y medio
Tema 3. Análisis de algoritmos
Notación asintótica
Análisis matemático de algoritmos no recursivos
Análisis matemático de algoritmos recursivos
Análisis empírico de algoritmos
Tema 4. Algoritmos de ordenación
Concepto de ordenación
Ordenación de la burbuja
Ordenación por selección
Ordenación por inserción
Ordenación por mezcla (mergesort)
Ordenación rápida (quicksort)
Tema 5. Listas enlazadas
Estructuras de datos dinámicas
Punteros
Listas enlazadas
Listas enlazadas ordenadas
Tema 6. Pilas y colas
Tipos abstractos de datos
Pilas
Colas
Tema 7. Árboles
Concepto de árbol
Árboles binarios
Árboles binarios de búsqueda
Árboles binarios balanceados
Tema 8. Heaps
y colas de prioridad
Heaps
Heapsort
Colas de prioridad
Tema 9. Grafos
Representación
Recorrido en anchura
Recorrido en profundidad
Ordenación topológica
Tema 10. Búsqueda de caminos mínimos
El problema del camino mínimo
Arcos negativos y ciclos
Algoritmo de Dijkstra
Tema 11. Tablas hash
Introducción
Prueba lineal
Funciones hash y clustering
Encadenamiento separado
Tema 12.Problemas NP
Problemas P
Problemas NP
Problemas NP-completos
Las actividades formativas de la asignatura se han elaborado con el objetivo de adaptar el proceso de aprendizaje a las diferentes capacidades, necesidades e intereses de los alumnos.
Las actividades formativas de esta asignatura son las siguientes:
En la programación semanal puedes consultar cuáles son las actividades concretas que tienes que realizar en esta asignatura.
Estas actividades formativas prácticas se completan, por supuesto, con estas otras:
Para la correcta participación de los alumnos en las diferentes actividades propuestas en la asignatura se recomienda disponer de un ordenador con las siguientes especificaciones mínimas recomendadas:
Bibliografía básica
Tema 1
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 57-94. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 2
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 15-17. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 3
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 17-31. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 4
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 97-119. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 5
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 171-199. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 6
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 221-249. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 7
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 287-324. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 8
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 243-249. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 9
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 369-374. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 10
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 397-401. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 11
Joyanes, L. et al. (2005). Estructuras de datos en C, pp. 271-274. Madrid: McGraw-Hill.
El libro está disponible en la Biblioteca Virtual de UNIR.
Tema 12
Ziviani, N. (2007). Diseño de algoritmos con Implementaciones en Pascal y C, pp. 341-366. Madrid: Thomson.
El intervalo está disponible en el aula virtual de la UNIR (bajo licencia CEDRO*).
* Esta obra está protegida por el derecho de autor y su reproducción y comunicación pública, en la modalidad puesta a disposición, se han realizado con autorización de CEDRO. Queda prohibida su posterior reproducción, distribución, transformación y comunicación pública en cualquier medio y de cualquier forma, con excepción de una única reproducción mediante impresora por cada usuario autorizado.
Bibliografía complementaria
Aho, A. V. & Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
Andrej Bogdanov, L. T. (2006). Average-Case Complexity. Now Publishers Inc.
Arova, S. & Barak B. (2009) Computational Complexity. A Modern Approach. Cambridge: Cambridge Press.
Cairó, O. y Guardati, S. (2006). Estructuras de datos, 3ª edición. Madrid: McGraw Hill.
Edosomwan, J. (2012). Sorting Algorithm: Analysis and Comparison Performance. LAP LAMBERT Academic Publishing.
Fortnow Lance. (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Nueva Jersey: Princeton University Press.
Leiserson, C., Rivest, R. & Stein, C. (2009). Introduction to Algorithms, 3rd edition. Massachusetts: MIT Press.
Levitin A. (2011). Introduction to the Design and Analysis of Algorithms, 3rd edition. Addison-Wesley.
Necaise, R. D. (2010). Data Structures and Algorithms Using Python. Wiley.
West, D. (2000). Introduction to Graph Theory. Pearson.
Zhang, X. (2011). Expected Lengths of Minimum Spanning Trees. Cambridge: ProQuest, UMI Dissertation Publishing.
El sistema de calificación se basa en la siguiente escala numérica:
0 - 4, 9 |
Suspenso |
(SS) |
5,0 - 6,9 |
Aprobado |
(AP) |
7,0 - 8,9 |
Notable |
(NT) |
9,0 - 10 |
Sobresaliente |
(SB) |
La calificación se compone de dos partes principales:
El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL y OBLIGATORIO. Supone el 60% de la calificación final (6 puntos sobre 10) y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO (es decir, obtener 3 puntos de los 6 totales del examen).
La evaluación continua supone el 40% de la calificación final (es decir, 4 puntos de los 10 máximos). Este 40% de la nota final se compone de las calificaciones obtenidas en las diferentes actividades formativas llevadas a cabo durante el cuatrimestre.
Ten en cuenta que la suma de las puntuaciones de las actividades de la evaluación continua es de 15 puntos. Así, puedes hacer las que prefieras hasta conseguir un máximo de 10 puntos (que es la calificación máxima que se puede obtener en la evaluación continua). En la programación semanal de la asignatura, se detalla la calificación máxima de cada actividad o evento concreto puntuables.
Obviamente, al tratarse de formación on-line puedes organizar tu tiempo de estudio como desees, siempre y cuando vayas cumpliendo las fechas de entrega de actividades, trabajos y exámenes. Nosotros, para ayudarte, te proponemos los siguientes pasos:
Ten en cuenta estos consejos…
|