PROGRAMA DE LA ASIGNATURA
0. ESPECIFICACION, DERIVACION Y RECURSION.
0.1. ESPECIFICACIONES
0.2. RAZONAMIENTO Y DISEÑO RECURSIVO.
0.3. CORRECCION DE LOS PROGRAMAS RECURSIVOS
0.4. INMERSIONES. OBTENCION DE RECURSIVIDAD LINEAL FINAL Y TRANSFORMACION DEL PARADIGMA RECURSIVO EN ITERATIVO.
0.5. ANALISIS DEL COSTE DE ALGORITMOS RECURSIVOS.
1. DIVIDE Y VENCERAS
1.1. DESCRIPCION DEL ESQUEMA Y ANALISIS DE SU COSTE COMPUTACIONAL.
1.2. EJEMPLOS ARITMETICOS.
1.3. EJEMPLOS NUMËRICOS.
1.4. EJEMPLOS COMBINATORIOS.
2. GRAFOS
2.1. ESPECIFICACION ALGEBRAICA Y DEFINICIONES
2.1.1. ESPECIFICACION
2.1.2. DEFINICIONES
2.1.2.1. Adyacencias
2.1.2.2. Caminos
2.1.2.3. Conectividad
2.1.2.4. Algunos grafos particulares
2.2. IMPLEMENTACIONES. ANALISIS DEL COSTE DE LAS OPERACIONES
2.2.1. MATRICES DE ADYACENCIA
2.2.2. LISTAS Y MULTILISTAS DE ADYACENCIA
2.2.3. EL PROBLEMA DE LA CELEBRIDAD
2.3. ALGORITMOS SOBRE GRAFOS
2.3.1. RECORRIDO EN PROFUNDIDAD
2.3.1.1. Conectividad
2.3.1.2. Numerar vértices
2.3.1.3. Arbol asociado al Recorrido en profundidad
2.3.1.4. Test de ciclicidad
2.3.1.5. Un TAD útil : MFSets
2.3.2. RECORRIDO EN ANCHURA
2.3.3. ORDENACION TOPOLOGICA
3. ALGORITMOS VORACES
3.1. CARACTERIZACION Y ESQUEMA
3.3. EJEMPLOS DE OPTIMIZACION LINEAL DISCRETA.
3.4. ARBOLES DE EXPANSION MINIMA
3.4.1. KRUSKAL
3.4.2. PRIM
4. VUELTA ATRAS
4.1. CARACTERIZACION
4.2. TERMINOLOGÍA Y ESQUEMAS
4.2.1. UNA SOLUCION
4.2.2. TODAS LAS SOLUCIONES
4.2.3. LA MEJOR SOLUCION
4.2.4. EJEMPLOS DE OPTIMIZACION LINEAL DISCRETA.
5. RAMIFICACION Y PODA
5.1. CARACTERIZACION Y DEFINICIONE
5.2. EL ESQUEMA Y SU EFICIENCIA
5.3. EJEMPLOS DE OPTIMIZACION LINEAL DISCRETA.
6. COMPUTACION EN PARALELO
6.1. MODELOS DE COMPUTO EN PAPALELO.
6.2 PARALELISMO Y CLASES DE COMPLEJIDAD.
6.3. PARALELIZACION DE LA ESTRATEGIA DIVIDE Y VENCERAS.
7. ESTRATEGIAS PARA PROBLEMAS COMPUTACIONALMENTE DIFICILES
7.1 ALGORITMOS APROXIMADOS.
7.2. ALGORITMOS PROBABILISTAS.
7.3. ALGORITMOS HEURÏSTICOS.
7.4. MAQUINAS CUANTICAS.
Asignaturas que se recomienda al alumno haber cursado o estar cursando. Se recomienda poseer conocimientos básicos sobre el diseño y análisis de algoritmos. En el caso de alumnos de Ingeniería Informática las asignaturas relacionadas con la programación: Programación I, Prácticas de Programación y Estructuras de datos proporcionan dichos conocimientos. En el caso de alumnos de la titulación de Matemáticas es preciso, al menos, haber cursado y superado la asignatura Informática
OBJETIVOS GENERALES DE LA ASIGNATURA
Ampliar el abanico de técnicas algorítmicas y profundizar en sus fundamentos teóricos. Profundizar en el diseño y evaluación de los algoritmos. Profundizar en los esquemas algorítmicos como herramienta de diseño. Presentar herramientas algorítmicas para el tratamiento de problemas computacionalmente difíciles como los algoritmos de aproximación y los algoritmos probabillísticos. Presentar la ingeniería algorítmica como selección de las estructuras de datos y de las técnicas algorítmicas más adecuadas para la resolución de un problema concreto.
OBJETIVOS ESPECIFICOS: APTITUDES/DESTREZAS
Conocimientos
1. Análisis de algoritmos: Eficiencia, costes, notación asintótica. Recurrencias. Análisis en caso medio.
2. Fundamentos teóricos de los esquemas algorítmicos.
3. Algoritmos fundamentales avanzados: ordenación, grafos.
4. Algoritmos probabilistas: Tipos, técnicas elementales de diseño. Primalidad. Técnicas de análisis.
5. Algoritmos de aproximación: Concepto de aproximación. Eficiencia versus calidad. Técnicas de análisis y de diseño.
Habilidades
1. Ser capaz de usar técnicas avanzadas de diseño y análisis de algoritmos.
2. Saber razonar sobre la corrección y la eficiencia de algoritmos.
3. Conocer algunos algoritmos clásicos para problemas fundamentales.
4. Saber identificar los componentes más relevantes de un problema y seleccionar la técnica algorítmica más adecuada.
5. Ser capaz de escoger los tipos de datos más adecuados para mejorar la eficiencia de una solución algorítmica.
Competencias
1. Capacidad para el razonamiento crítico y lógico-matemático.
2. Capacidad para resolver problemas aplicando los métodos de la ciencia y la ingeniería.
Capacidad para diseñar sistemas, componentes o procesos que se ajusten a unas necesidades, usando los métodos, técnicas y herramientas más adecuadas en cada caso.
4. Capacidad de abstracción. Capacidad para enfrentarse a problemas nuevos recurriendo conscientemente a estrategias que han resultado útiles en problemas resueltos anteriormente.
5. Capacidad para estudiar de diversas fuentes, identificando cuándo la información recibida en clase no es suficiente y buscando información complementaria.
6. Capacidad para relacionar y estructurar información de diversas fuentes, para integrar ideas y conocimientos.
7. Capacidad para transmitir ideas efectivamente de forma escrita.
8. Disposición y capacidad para actualizarse a lo largo de la carrera profesional, respecto a conocimientos, procedimientos y técnicas.
BIBLIOGRAFÍA Básica.
-CORMEN, Thomas H. et alt. Introduction to algorithms. 2nd edition, MIT Press y McGraw-Hill, 2001.
-Brassar, G. Bradley, P. Fundamentos de Algoritmia. 1977. Prentice-Hall.
-KLEINBERG, Jon i TARDOS, Eva Algorithm design, Pearson/Addison Wesley, 2006.
-MITZENMACHER, Michael i UPFAL, Eli Probability and Computing. Randomized algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
-VAZIRANI, Vijay V. Approximation Algorithms, Springer, 2001.
-MICHALEWICZ, Z. i FOGEL, D.B. How to solve it: Modern Heuristics, Springer, 2000. Complementaria
-MOTWANI, R. i RAGHAVAN, P. Randomized Algorithms, Cambridge University Press, 1995.
-SKIENA, Steven The algorithm design manual, Springer Verlag, 1998.
-GAREY, M. R. i JHONSON, D. S. Computers and intractability. A guide to the NP-completeness. , W.H. Freema, 1979.
ACTIVIDADES A DESARROLLAR EN LA ASIGNATURA
Se desarrollarán prácticas y ejercicios relacionados con cada uno de los bloques temáticos en número a determinar.
MÉTODO DE EVALUACIÓN
CRITERIO DE EVALUACION %
PROCEDIMIENTO ORDINARIO:
-trabajo continuo
- 40% prácticas + 20% ejercicios obligatorios 60%
-Examen (teoría y problemas). La duración del examen es de aproximadamente 4
horas 40%
TOTAL 100%
Examen Final
PROCEDIMIENTO EXTRAORDINARIO (hay que solicitarlo al profesor)
-Entrega de los informes de las prácticas y ejercicios obligatorios de la asignatura
(esto es obligatorio tanto en junio como en Septiembre, si bien, la entrega de
junio es válida para septiembre)
-Examen único de tres partes (añadiendo al examen del procedimiento ordinario
una parte más de prácticas, con una duración aproximada de 2 horas)
- Cuestiones (25%)
- Problemas (25%)
- Prácticas (50%)
100%
CRITERIOS DE EVALUACION DE LAS PRACTICAS
-Especificación y diseño: Precisión de la especificación; corrección y nivel del diseño.
Escala: Destaca (4), Bien (3), Suficiente (2), Debe mejorar (1), Insuficiente (0).
-Grado de resolución: Grado de resolución de la práctica alcanzado durante las horas en el laboratorio (con mejoras, resolución básica, no finalizado).
Escala: Con mejoras sustanciales (4), con mejoras simples (3), básico (2), no finalizado (1).
-Estilo: Estilo de programación, claridad del código, documentación del código.
Escala: Destaca (4), Bien (3), Suficiente (2), Debe mejorar (1), Insuficiente (0).
-Organización: Organización del informe, claridad en la exposición. Escala: Destaca (4), Bien (3), Suficiente (2), Debe mejorar (1), Insuficiente (0).
Observaciones: Los ejercicios se evaluarán siguiendo los mismos criterios que las prácticas
Print this page