Source: https://guiae.uclm.es/vistaGuia/346/42344/2018-19
Timestamp: 2020-08-05 05:48:25+00:00

Document:
Profesor: FERNANDO CUARTERO GOMEZ - Grupo(s): 15
fernando.cuartero@uclm.es
Es recomendable haber cursado y aprobado las asignaturas "Metodología de la Programación" y "Estructuras de Datos" de segundo curso, ya que la asignatura está muy relacionada con ambas. También es importante haber cursado la asignatura "Cálculo y métodos numéricos", ya que la asignatura revisa y profundiza en el cálculo de complejidad algorítmica estudiado también en Metodología de la Programación de segundo.
Diseño de algoritmos constituye una extensión de "Metodología de la programación", que ha de cursarse en segundo. En esta asignatura se abordan aspectos relativos a la resolución de problemas mediante técnicas fundamentales de computación, tanto exactas como aproximadas. En particular, se profundiza en aspectos relativos a complejidad computacional y a técnicas algorítmicas, como programación dinámica, etc.
Otros temas relacionados con este grupo de asignaturas, como son los relativos a grafos o investigación operativa, serán tratados en las asignaturas correspondientes que se imparten también dentro de la intensificación en computación.
CM3 Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.
Saber evaluar la complejidad computacional de un problema y aplicar la estrategia más adecuada de diseño de algoritmos que lo resuelve.
Aplicar los principios de Programación Orientada a Objetos para la resolución de problemas.
Tema 1: Algoritmos sobre grafos
Tema 2: Divide y vencerás
Tema 3: Algoritmos voraces
Tema 4: Programación dinámica
Tema 5: Búsqueda con retroceso
Tema 6: Ramificación y poda
Tema 7: Algoritmos aleatorios
Tema 8: Metaheurísticas
Enseñanza presencial (Teoría) [PRESENCIAL] Método expositivo/Lección magistral CM3 INS4 SIS9 0.8 20 N N N Estas horas de teoría se dedicarán a la explicación de los diferentes temas.
Enseñanza presencial (Prácticas) [PRESENCIAL] Seminarios CM3 INS4 SIS9 0.24 6 N N N A lo largo del curso se impartirán tres seminarios relativos a programación en Python, estructuras de datos en Python, y a un ejemplo de resolución de problema práctico.
Prácticas de laboratorio [PRESENCIAL] CM3 INS4 SIS9 0.64 16 N N N Se dedicarán unas horas para la explicación y supervisión de cada uno de los trabajos prácticos.
Estudio o preparación de pruebas [AUTÓNOMA] CM3 SIS3 SIS9 1.68 42 N N N Este es el tiempo que se estima para la preparación de los dos examenes parciales, o en su defecto final. Se presupone un seguimiento continuo de las clases.
Elaboración de memorias de Prácticas [AUTÓNOMA] Trabajo dirigido o tutorizado CM3 INS4 SIS3 SIS9 1.92 48 S S S Además de las horas dedicadas al trabajo en laboratorio, se estima un trabajo de unas 12 horas para la realización de cada una de las prácticas. La entrega y defensa de las mismas es obligatoria.
Resolución de problemas o casos [PRESENCIAL] Método expositivo/Lección magistral CM3 INS4 SIS9 0.56 14 N N N Se dedicarán horas de clase y de laboratorio a la resolución de problemas.
Prueba final [PRESENCIAL] Pruebas de evaluación CM3 INS4 SIS9 0.16 4 S S S Se dedicarán dos horas de clase a la realización de sendos exámenes parciales.
Examen teórico 60.00% 0.00% (ESC) Es necesario aprobar el examen de teoría. En caso de aprobar los exámenes parciales, no es necesario presentarse al examen final.
Realización de prácticas en laboratorio 30.00% 0.00% (LAB) El desarrollo de cada una de las cuatro prácticas constituirá el 7.5% de la nota final.
Elaboración de memorias de prácticas 10.00% 0.00% (INF) La memoria de cada una de las cuatro prácticas constituirá el 2.5% de la nota.
- Es necesario aprobar de manera independiente tanto las prácticas como el examen final.
- Es necesario obtener una calificación mínima de 5 en cada una de las cuatro prácticas para superar la parte de prácticas. En caso de no superar las prácticas la máxima calificación será de Suspenso (4). Las prácticas suspensas tendrán posibilidad de recuperarse previo al examen ordinario, o extraordinario en su caso. En caso de no superar el examen la máxima calificación será de Suspenso (4). En ambos casos aún cuando la media sea superior a 5.
- Es necesario aprobar los dos examenes parciales de manera individual para aprobar la parte de teoría. Todo aquel que apruebe un solo parcial con una nota superior a 6 podrá optar a presentarse solamente a la parte pendiente en el examen ordinario.
- Se penalizará la entrega de las prácticas fuera de los plazos establecidos con un 20% de la nota.
- Si se aprueba sólo una parte, la teórica o la práctica, para la convocatoria extraordinaria sólo será necesario recuperar la otra parte.
Tema 1 (de 8): Algoritmos sobre grafos
Enseñanza presencial (Prácticas) [PRESENCIAL][Seminarios] 6
Inicio del tema: 28-01-2019 Fin del tema:
Comentario: Se dedicarán dos clases de teoría al estudio de algoritmos sobre grafos, y otra más a la resolución de problemas y ejercicios. Las cuatro primeras horas de prácticas se dedicarán a la impartición de dos seminarios de programación en Python. Se dará el guión de la primera práctica para que el alumno intente abordarla de manera autónoma antes de su expilcación, que tendrá lugar en la semana 4.
Tema 2 (de 8): Divide y vencerás
Estudio o preparación de pruebas [AUTÓNOMA][] 7
Tema 3 (de 8): Algoritmos voraces
Prácticas de laboratorio [PRESENCIAL][] 3
Estudio o preparación de pruebas [AUTÓNOMA][] 4
Elaboración de memorias de Prácticas [AUTÓNOMA][Trabajo dirigido o tutorizado] 12
Comentario: Debido a que los algoritmos voraces se vieron en la asignatura Metodología de la Programación, se dedicarán las primeras dos horas de teoría a su repaso, y otras dos a la corrección de ejercicios.
Tema 4 (de 8): Programación dinámica
Elaboración de memorias de Prácticas [AUTÓNOMA][Trabajo dirigido o tutorizado] 10
Comentario: Se dedicarán dos horas al repaso del tema Programación Dinámica"visto en la asignagura Metodología de la Programación. En la siguiente clase de teoría se corregirán los ejercicios propuestos.
Tema 5 (de 8): Búsqueda con retroceso
Comentario: Durante las semanas 8 y 9 se repasará el tema Búsqueda con Retroceso en teoría, y se corregirán los ejercicios en clase de prácticas.
Tema 6 (de 8): Ramificación y poda
Prácticas de laboratorio [PRESENCIAL][] 4
Comentario: Se dedicarán dos clases de teoría a explicar los algoritmos de ramificación y poda, y una a la resolución de ejercicios.
Tema 7 (de 8): Algoritmos aleatorios
Resolución de problemas o casos [PRESENCIAL][Método expositivo/Lección magistral] 8
Tema 8 (de 8): Metaheurísticas
Comentario: Durante las semanas 12 y 13 se abordará el tema relativo a metaheurísticas. En la primera clase de teoría se expondrá el tema, y en la segunda se resoverán ejercicios.
Comentarios generales sobre la planificación: Tanto la distribución del trabajo como, sobre todo, la planificación, son estimaciones orientativas. En cualquier caso, cualquier modificación se notificará con antelación en el espacio virtual de la asignatura. A lo largo del curso, y dependiendo de cómo se desarrolle éste, se irán modificando si es necesario para adaptarnos a las distintas eventualidades. En cualquier caso, se proporcionará una planificación semanal detallada en moodle. La asignatura se imparte en tres sesiones semanales de 1,5 horas.
Aho, A.V.; Hopcroft, J.E. y Ullman, J.D. The design and analysis of computer algoritms Addison-Wesley 1974
Cormen, T.; Leiserson, C. y Rivest, R. Introduction to Algorithms McGraw-Hill 1990
D. Goldberg Genetic algorithms in search, optimization, and machine learning Addison-Wesley Professional 1989
Donald E. Knuth The art of computer programming I-3 (2nd Edition) Addison-Wesley Professional 1998
Fred Glover and Gary A. Kochenberger Handbook of Metaheuristics Springer-Verlag 2003
G. Brassard and P. Bratley Fundamentos de algoritmia Prentice Hall 1997
Horowitz, Ellis; Sahni, Sartaj; Rajasekaran, Sanguthevar Computer Algorithms Computer Science Press 1998
Jon Kleimberg and Eva Tardos Algorithm Design Pearson 2006
Parberry I Problems on Algorithms Prentice Hall 1995

References: resolución 
 resolución 
 resolución 
 resolución 

Resolución 
 resolución 
 resolución 
 resolución 

Resolución