Análisis y Diseño de Algoritmos

Análisis y Diseño de Algoritmos
Curso 2007/2008

Titulación	Curso	Cuatrimestre	Créditos
Ingeniería Técnica en Informática de Sistemas	2	primero	6.0

Profesorado

Objetivos

Proveer al alumno de las técnicas algorítmicas básicas que le permitirán abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales. Las técnicas básicas mencionadas incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.
Conocer mejor cómo es un lenguaje de programación, en particular un lenguaje orientado a objetos. Con este objetivo se estudiarán aspectos como son la estructura de control, el tipo de datos, la gestión de memoria y los mecanismos de abstracción de un lenguaje de estas características.
Conocer nuevas técnicas de programación.
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. Introducir herramientas de diseño de algoritmos y 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.
Profundizar en el aprendizaje de la programación estructurada. Introducir técnicas para diseñar programas de tamaño mediano. Proporcionar al alumno más experiencia en el campo de la programación mediante la realización de prácticas.
Ampliar el dominio de la recursividad como herramienta de construcción de programas.

Temario

Tema 1. Recursividad
Concepto. Tipos de recursividad. Funcionamiento interno. Recursividad e iteración.
Tema 2. Análisis de algoritmos
Recursos de computadora y complejidad. Estudio de la complejidad de un algoritmo. Medidas asintóticas. Órdenes de complejidad. Reglas prácticas para el cálculo de la eficiencia. Análisis de complejidad de algoritmos recursivos
Tema 3. Consideraciones sobre las técnicas de diseño de algoritmos
Planteamiento general. Programación por esquemas. Uso de patrones de diseño. El patrón Strategy. El patrón Template.
Tema 4. Algoritmos voraces
Características. Esquema general. Ejemplos de aplicación. Heurísticas voraces.
Tema 5. Divide y vencerás
Características. Cálculo de la eficiencia. Esquema general. Ejemplos de aplicación.
Tema 6. Programación dinámica
Introducción y esquema general de resolución. El Principio de Optimalidad. Ejemplos de aplicación.
Tema 7. Algoritmos de vuelta atrás
Ámbito de aplicación. Esquema general y sus variantes. Ejemplos de aplicación.

Metodología

Nuestro método de enseñanza se desarrolla en la forma que seguidamente detallamos, con el propósito de que el alumno mantenga un contacto continuo con la asignatura a lo largo del cuatrimestre:
Clases de teoría
Durante las semanas que dura el curso se impartirá el contenido teórico de la asignatura mediante el uso de presentaciones en ordenador y en formato tradicional, ilustrando con especial atención los problemas de relevancia con ejemplos clarificadores.
El material proporcionado a los alumnos, en forma de presentaciones elaboradas por los profesores de la asignatura, es un material de apoyo de gran valor para el seguimiento de la asignatura. Dichas presentaciones estarán accesibles tanto en papel (en la copistería del centro), como en Internet (en la página Web de la asignatura en el servidor del departamento).
Clases de problemas
Los alumnos tendrán a su disposición (tanto en versión papel, en copistería, como en formato electrónico en la web de la asignatura) un boletín de problemas donde se incluyen los enunciados de los problemas que los alumnos deben trabajar para cada uno de los bloques temáticos. Este boletín tiene ejercicios destinados a afianzar, profundizar y aplicar de forma práctica los conceptos y técnicas adquiridas en las sesiones teóricas. La dificultad de los problemas es incremental, de modo que se pueda realizar un estudio ordenado de cada uno de los contenidos de la asignatura. Los problemas de este boletín se actualizarán año tras año incorporando exámenes de convocatorias precedentes, además de otros ejercicios que los profesores estimen oportunos.
Algunas sesiones (según la temporización anterior) se dedicarán a la resolución por parte del profesor, y eventualmente del alumnado, de problemas de todos los bloques temáticos del citado boletín, o propuestos por el profesorado.
Prácticas de laboratorio
A lo largo del curso se reforzarán los contenidos de las clases teóricas y de problemas con clases de laboratorio, donde se presentará al alumno los contenidos necesarios para que puedan desarrollar problemas con un ordenador. Estas sesiones se realizan mediante el uso de presentaciones en ordenador, dejando al alumno un tiempo suficiente para la resolución de los problemas planteados con la asistencia del profesor. Además de estas presentaciones, se le proporcionará al alumno material en forma de código fuente, que deberá utilizar como punto de partida en la resolución de los ejercicios propuestos. Las presentaciones estarán accesibles tanto en papel (en la copistería del centro), como vía Internet (en la página web de la asignatura en el servidor del departamento), mientras que el código fuente únicamente estará disponible en la web de la asignatura.
Existirá un seguimiento y evaluación de las prácticas del laboratorio, donde el alumno podrá obtener un máximo de 1,5 que se sumará a la nota de prácticas.

Evaluación

Convocatorias ordinarias: Tanto la evaluación de la parte teórica como práctica se hará mediante un examen escrito que se realizará en las fechas que indique el Centro para cada una de las convocatorias oficiales.
Evaluación alternativa: El alumno también tendrá la posibilidad de aprobar la asignatura sin necesidad de presentarse al examen final mediante una evaluación alternativa. Esta evaluación alternativa consistirá en la superación de una serie de ejercicios escritos tanto teóricos como de programación, y la realización de un conjunto de problemas en clases de teoría y de prácticas de laboratorio. Para los ejercicios escritos se realizarán dos pruebas, que contendrán tanto aspectos teóricos como prácticos de la asignatura. En las sesiones de laboratorio se desarrollarán las diferentes prácticas y el profesor evaluará el trabajo realizado por el alumno. Se podrá obtener un máximo de 1.5 puntos con la realización de las prácticas en el laboratorio, que serán sumados a la nota final de prácticas siempre que se haya asistido al menos a un 60% de las prácticas de aula. Así mismo, se podrán obtener puntos adicionales en la nota de teoría por la realización de problemas.
Criterios de calificación:
- Convocatorias ordinarias: la nota final del alumno se calculará según el siguiente algoritmo. Sea T la nota del examen escrito de teoría y P la nota del examen escrito de práctica,
             si (T>=4 Y P >= 4):
                NotaFinal := 0.6 · T + 0.4 · P
             |otros:
                NotaFinal := mínimo (0.6 · T + 0.4 · P, 4)
             fsi
- Evaluación alternativa: a los alumnos se les calculará la nota media de los ejercicios de la misma forma que para las convocatorias oficiales. A la nota de prácticas, se le sumará la nota obtenida en la evaluación en aula de laboratorio siempre que el alumno haya asistido, al menos, al 60% de las prácticas.
Se considerará que un alumno ha superado la asignatura cuando la calificación que obtiene en el sistema de evaluación elegido sea igual o superior a 5.

Bibliografía

Aho, A.V., J.E. Hopcroft, J.D. Ullman, Estructuras de datos y algoritmos, Addison-Wesley, 1988.
Arnold, K., J. Gosling, D. Holmes, El Lenguaje de Programación Java, 3ª Ed., Addison-Wesley, 2001.
Arnow, D., G. Weiss, Introducción a la Programación con Java. Un enfoque Orientado a Objetos, Addison-Wesley, 2000.
Brassard, G., P. Bratley, Fundamentos de algoritmia, Prentice-Hall, 1997.
Cormen, T.H., C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Press, 1990.
Eckel, B., Piensa en Java. 2ª Edición, Prentice-Hall, 2002.
Gamma, E. et al, Design Patterns. Elements of Reusable Object Oriented Software, Addison-Wesley, 1995.
Gosling, A., El Lenguaje de Programación Java, Addison-Wesley, 1998.
Grand, M., Patterns in Java, Volume 1, John Wiley & Sons, 1998.
Guerequeta, R., A. Vallecillo, Técnicas de diseño de algoritmos, Universidad de Málaga / Manuales, 1997.
Martí, N., Y. Ortega, J. A. Verdejo, Estructuras de datos y métodos algorítmicos: Ejercicios resueltos, Prentice-Hall, 2003.
Peña, Ricardo, Diseño de programas. Formalismo y abstracción, Prentice-Hall, 1998.
Weiss, M.A., Estructuras de datos y algoritmos, Addison-Wesley, 1995.
Wirth, N., Algoritmos y Estructuras de Datos, Prentice-Hall Iberoamericana, 1987.

Noticias

Canal RSS de noticias de la asignatura

13/02/2008 - 12:21
Soluciones Examen Febrero
[fichero asociado]
30/01/2008 - 11:29
Soluciones Ev. Alternativa Enero
[fichero asociado]
14/01/2008 - 11:55
Soluciones Ev. Alternativa Diciembre
[fichero asociado]
24/10/2007 - 10:27
AVISO: ITIS - Clases de teoría en horario de prácticas
Para los tres grupos de ADA en ITIS, las dos próximas semanas (del 29/10 al 9/11) se impartirán clases de teoría en el horario de prácticas, en el aula de teoría.
01/10/2007 - 10:41
Evaluación alternativa y horarios prácticas
En el documento adjunto se aclaran aspectos sobre la evaluación alternativa y los horarios de los grupos de prácticas. [fichero asociado]
27/09/2007 - 09:34
Foro de Prácticas de ADA
Para acceder al foro, deberá identificarse en http://ev.us.es con su usuario y clave de la universidad y acceder al curso "ANALISIS Y DISEÑO DE ALGORITMOS - Curso 2007-08" [página web asociada]