Denominación de la asignatura |
Algoritmia y Complejidad |
Grado al que pertenece |
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 | Básico |
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:
Competencias básicas
Competencias generales
Competencias específicas
Competencias transversales
Tema 1. Introducción a las estrategias de diseño de algoritmos
Introducción y objetivos.
Recursividad.
Divide y conquista.
Otras estrategias.
Tema 2. Eficiencia de los algoritmos
Introducción y objetivos.
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
Introducción y objetivos.
Notación asintónica.
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
Introducción y objetivos.
Concepto de ordenación.
Ordenación de la burbuja.
Ordenación por selección.
Ordenación por inserción.
Ordenación por mezcla (merge_sort).
Ordenación rápida (quick_sort).
Tema 5. Algoritmos con árboles
Introducción y objetivos.
Concepto de árbol.
Árboles binarios.
Recorridos de árbol.
Representar expresiones.
Tema 6. Algoritmos con árboles ordenados y balanceados
Introducción y objetivos.
Árboles binarios ordenados.
Árboles binarios balanceados.
Tema 7. Algoritmos con heaps
Introducción y objetivos.
Los heaps.
El algoritmo heapsort.
Las colas de prioridad.
Tema 8. Algoritmos con grafos
Introducción y objetivos.
Representación.
Recorrido en anchura.
Recorrido en profundidad.
Ordenación topológica.
Tema 9. Algoritmos greedy
Introducción y objetivos.
La estrategia greedy.
Elementos de la estrategia greedy.
Cambio de monedas.
Problema del viajante.
Problema de la mochila.
Tema 10. Búsqueda de caminos mínimos
Introducción y objetivos.
El problema del camino mínimo.
Arcos negativos y ciclos.
Algoritmo de Dijkstra.
Tema 11. Algoritmos greedy sobre grafos
Introducción y objetivos.
El árbol de recubrimiento mínimo.
El algoritmo de Prim.
El algoritmo de Kruskal.
Análisis de complejidad.
Tema 12. Backtracking
Introducción y objetivos.
El backtracking.
Técnicas alternativas.
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:
Las horas de dedicación a cada actividad se detallan en la siguiente tabla:
ACTIVIDADES FORMATIVAS |
HORAS |
% PRESENCIAL |
Sesiones presenciales virtuales | 15 |
100% |
Lecciones magistrales | 6 |
0 |
Estudio del material básico | 50 |
0 |
Lectura del material complementario | 25 |
0 |
Trabajos, casos prácticos, test | 17 |
0 |
Prácticas de laboratorios virtuales | 12 |
16,7% |
Tutorías | 16 |
30% |
Trabajo colaborativo | 7 |
0 |
Realización de examen final presencial | 2 |
100% |
Total | 150 |
Recuerda que la bibliografía básica es imprescindible para el estudio de la asignatura. Cuando se indica que no está disponible en el aula virtual, tendrás que obtenerla por otros medios: librería UNIR, biblioteca...
Los textos necesarios para el estudio de la asignatura han sido elaborados por UNIR y están disponibles en formato digital para consulta, descarga e impresión en el aula virtual.
Además, en estos temas deberás estudiar la siguiente bibliografía:
Tema 1
Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.
Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.
Temas 2 a 8
Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.
Tema 9
Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.
Tema 10
Joyanes, L. et al. (2005). Estructuras de datos en C. Madrid: McGraw-Hill.
Disponible en la Biblioteca Virtual de UNIR.
Temas 11 y 12
Guerequeta, R. y Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones de la Universidad de Málaga.
Disponible a través del aula virtual.
Aho, A. V. y Ullman, J. D. (1983). Data Structures and Algorithms. Massachusetts: Addison-Wesley.
Arova, S. y Barak B. (2009). Computational Complexity. A Modern Approach. Cambridge: Cambridge University Press.
Cairó, O. y Guardati, S. (2006). Estructuras de datos, 3.ª edición. Madrid: McGraw Hill.
Horowitz, E. y Sahni, S. (1984). Fundamentals of computer algorithms. Nueva Delhi: Galgotia Publications.
Kaldewaij, A. (1990). Programming: the derivation of algorithms. New Jersey: Prentice Hall.
Knuth, D. E. (1980). Algoritmos fundamentales. Barcelona: Reverté.
Knuth, D. E. (1986). Seminuméricos. Barcelona: Reverté.
Knuth, D. E. (1987). Clasificación y búsqueda. Barcelona: Reverté.
Knuth, D. E. (1987). Algoritmos combinatorios. Barcelona: Reverté.
Leiserson, C., Rivest, R. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Massachusetts: MIT Press.
Levitin A. (2011). Introduction to the Design and Analysis of Algorithms, 3.ª edición. Addison-Wesley.
Necaise, R. D. (2010). Data Structures and Algorithms Using Python. Nueva York: John Wiley & Sons.
Sedgewick, R. (1995). Algoritmos en C++. Madrid: Ediciones Díaz de Santos.
West, D. (2000). Introduction to Graph Theory. Pearson.
Wirth, N. (1986). Algoritmos + estructuras de datos. México: Ediciones Castillo.
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 y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO.
La evaluación continua supone el 40% de la calificación final. 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 permite que realices las que prefieras hasta conseguir el máximo puntuable mencionado en la programación semanal. En ella se detalla la calificación máxima de cada actividad o evento concreto puntuables.
Para aprobar la asignatura será necesario aprobar cada una de las partes.
El sistema de evaluación de la asignatura es el siguiente:
SISTEMA DE EVALUACIÓN |
PONDERACIÓN MIN. |
PONDERACIÓN MÁX. |
Prueba de evaluación final presencial | 60% |
60% |
Evaluación de prácticas de laboratorios virtuales | 0% |
40% |
Resolución de trabajos, proyectos y casos | 0% |
40% |
Participación en foros y otros medios participativos | 0% |
40% |
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:
Recuerda que en el aula virtual de Lo que necesitas saber antes de empezar puedes consultar el funcionamiento de las distintas herramientas del aula virtual: Correo, Foro, Sesiones presenciales virtuales, Envío de actividades, etc.
Ten en cuenta estos consejos…
|