Denominación de la asignatura |
Diseño Avanzado de Algoritmos |
Grado al que pertenece |
Grado en Ingeniería Informática |
Créditos ECTS |
6 |
Curso y cuatrimestre en el que se imparte |
Primer cuatrimestre |
Carácter de la asignatura | Optativa |
Esta es una asignatura práctica en la que se van a aplicar a multitud de problemas de todo tipo las técnicas de diseño de algoritmos más utilizadas. Asimismo se aprenderá a verificar de forma certera si un programa en efecto cumple sus especificaciones.
El profundo cambio que ha supuesto en nuestro modo de vivir, no solamente en la informática y el tratamiento de la información, los algoritmos en los que se basa Google, basta para hacerse una idea de la importancia fundamental que tiene una asignatura como ésta.
En esta asignatura se va a profundizar en las técnicas de diseño de algoritmos, o si se quiere en las técnicas de resolución de problemas. No se va a centrar en un lenguaje de programación en concreto, aunque la posibilidad de implementar un algoritmo en una aplicación que pueda ser ejecutada en un ordenador, es fundamental para entender el funcionamiento y la eficiencia de los algoritmos que veamos.
Hablando de eficiencia, es un concepto fundamental a la hora de juzgar la bondad de los algoritmos. Evidentemente se pide que un algoritmo resuelve un problema dado, pero también se le pide que lo haga con los recursos adecuados de los que disponemos o de los que podemos disponer razonablemente. La tecnología de nuestros computadores avanza al parecer exponencialmente, pero al mismo tiempo la cantidad de datos que deseamos, no, que necesitamos procesar en el mismo tiempo crece a un ritmo siempre mayor.Competencias
Generales
Específicas
Tema 1. Principios de computabilidad
Máquinas de Turing
Tesis de Church-Turing
NP-Completitud
Tema 2. Tratamiento de la NP-Completitud
Búsqueda inteligente: vuelta atrás
Ramificación y poda
Tema 3. Análisis de algoritmos recursivos
Planteamiento y resolución de ecuaciones de recurrencia homogéneas e inhomogéneas.
Ejemplos de ecuaciones de recurrencia
Tema 4. Análisis amortizado
El análisis agregado
El método de contabilidad
El método del potencial
Tema 5. Verificación formal de programas
Especificación de abstracciones funcionales
El lenguaje de la lógica de primer orden
El sistema formal de Hoare
Tema 6. Verificación de programas iterativos
Reglas del sistema formal de Hoare
Concepto de invariante de iteraciones
Tema 7. Algoritmo: divide y vence
Introducción
Ejemplos de algoritmos: divide y vence.
Tema 8. Algoritmo voraces
Introducción
Ejemplos de algoritmos voraces
Tema 9. Programación dinámica
Introducción
Ejemplos de algoritmos de programación dinámica
Tema 10. Optimización combinatoria
Introducción
Ejemplos de búsqueda de soluciones
Tema 11. Algoritmos de aleatorización
Introducción
Ejemplos de algoritmos de aleatorización
Tema 12. Algoritmos paralelos
Introducción
Ejemplos de algoritmos paralelos
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
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 algunos temas deberás estudiar el siguiente manual de la asignatura:
Brassard, P. B. & Bratley, T. (1997). Fundamentos de algoritmia. Madrid: Pearson.
Díaz de Ilarraza, A. y Lucio, F. (1990). Verificación de programas y metodología de la programación. Bilbao: Universidad del País Vasco.
Guerequeta, R. & Vallecillo, A. (1998). Técnicas de diseño de algoritmos. Málaga: Universidad de Málaga.
Navarro, G. (2012). Teoría de la computación. Chile: Universidad de Chile.
Vargas, L. E. (2010). Problemas y algoritmos. Autoedición: Etnassoft.
Bibliografía complementaria
Kaldewaij, A. (1990). Programming: the derivation of algorithms. New Jersey: Prentice Hall.
Horowitz, E. & Sahni, S. (1984). Fundamentals of computer algorithms. Nueva Delhi: Galgotia Publications.
Knuth, D. E. (1980). Algoritmos fundamentales. Barcelona: Reverté.
Knuth, D. E. (1986). Seminuméricos. Barcelona: Reverté.
Knuth, D. E. (1987). Algoritmos combinatorios. Barcelona: Reverté.
Knuth, D. E. (1987). Clasificación y búsqueda. Barcelona: Reverté.
Sedgewick, R. (1995). Algoritmos en C++. Madrid: Ediciones Díaz de Santos.
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 (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…
|