08BZ - ALGORITMOS Y ESTRUCTURAS DE DATOS

Año 2004/2005
Curso Segundo
Ingeniero en Informática
Universidad de Murcia

AVISOS | APUNTES | PRACTICAS | PR. OPTATIVAS | TUTORIAS | EXAMENES | EVALUACION | CONVALIDACIONES | BIBLIOGRAFIA

AVISOS PARA LOS ALUMNOS

- Ya han salido las Notas de examen y las Notas finales de diciembre de 2005. Las revisiones serán el 13 y 14 de diciembre, por la mañana.

- Ha finalizado el Reto del Viajante. Ganador: Francisco Sánchez Molina (con 24597). Segundo: Julio Soler del Pozo (con 25209). Esta práctica permanecerá abierta para las convocatorias de septiembre y diciembre. La fecha tope de entrega será el día anterior al examen.

- Los alumnos que deseen realizar la práctica optativa de especificaciones formales para las convocatorias de septiembre y diciembre deben usar el nuevo enunciado de la práctica (PDF, Word97). Esto no afecta a los alumnos con la práctica aprobada, a los cuales se les guarda la nota.

- Atención, está disponible la asignación de alumnos a profesores de prácticas, para las Prácticas 1, 2 y 3 de la asignatura.

- Si buscas información de la asignatura relativa a las convocatorias del curso 2003/2004 usa esta página.

APUNTES
Las transparencias en formato PPT se pueden visualizar con PowerPoint 97, pero para ver las animaciones hay que usar PowerPoint XP o superior.

Parte I: Estructuras de datos
Descargar todas las transparencias y ejercicios: PDF, Word+PPT

Tema 0. Introducción.
transparencias: PDF, PowerPoint97

Tema 1. Abstracciones y especificaciones.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 2. Conjuntos y diccionarios.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 3. Representación de conjuntos mediante árboles.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 4. Grafos.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Parte II: Algoritmos
Descargar todas las transparencias y ejercicios: PDF, Word+PPT

Tema 0. Algorítmica.

Tema 1. Análisis de algoritmos.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 2. Divide y vencerás.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 3. Algoritmos voraces.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 4. Programación dinámica.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 5. Backtracking.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

Tema 6. Ramificación y poda.
transparencias: PDF, PowerPoint97; ejercicios: PDF, Word97

PRÁCTICAS

• Profesores de Prácticas: Domingo Giménez Cánovas, Alberto Pérez Vela

• Asignación de alumnos a profesores de prácticas. Estos serán los profesores encargados de corregir las prácticas de cada grupo.

• Las prácticas consistirán en el análisis, diseño, implementación y prueba de algunos problemas de algoritmos y de estructuras de datos, usando el lenguaje de programación C++.

• Los 6 créditos de prácticas se reparten en 1,5 créditos en el seminario de introducción a C/C++ (no obligatorio), y 4,5 créditos repartidos en tres prácticas en la modalidad de laboratorio abierto (obligatorias).

• Las prácticas se realizarán en grupos de 2 alumnos.

• Como NO hacer unas prácticas de programación.

• Entrevistas de prácticas: Las entrevistas de prácticas se fijarán tras la entrega de las prácticas.

• Seminario 1: Programación en C
  Sesión 1: PDF, Word97
  Sesión 2: PDF, Word97
  Sesión 3: PDF, Word97, TXT
  Sesión 4: PDF, Word97, TXT

• Seminario 2: Programación en C++
  Sesión 1: PDF, Word97, TXT
  Sesión 2: PDF, Word97, TXT
  Sesión 3: PDF, Word97, TXT

• Práctica 1: Implementación y manejo de estructuras de datos
  Indicaciones importantes
  Enunciado de la práctica: PDF, Word97
  Ficheros de ejemplo: access_log.zip (3,7 Mb)
  Tablas de desarrollo del proyecto (necesarias para la memoria): PDF, Word97
  Fecha de entrega: lunes 28/febrero/2005

• Práctica 2: Eficiencia, evaluación y predicción
  Enunciado de la práctica: PDF, Word97
  Programa generador de ficheros de log: generador.zip
  Programa a comparar en el análisis: Webalizer (mirror)
  Instalación: "gunzip webalizer.gz". Ejecución: "webalizer nombre_fichero_log"
  Tablas de desarrollo del proyecto (necesarias para la memoria): PDF, Word97
  Fecha de entrega: 29/abril/2005

• Práctica 3: Resolución de problemas
  Enunciado de la práctica: ZIP
  Fecha de entrega: lunes 21 de junio de 2005

PRACTICAS OPTATIVAS

El Juego de los Cuadrados
Enunciado y descripción: PDF, DOC
Convalidación de examen: Los alumnos que resuelvan esta práctica, de forma razonablemente adecuada y trabajada, podrán convalidar 1 ejercicio del Segundo Parcial (de 2 puntos sobre 10). Esta práctica optativa puede realizarse en grupos de dos. La fecha de entrega será el viernes 3 de junio de 2005. Esta convalidación no es acumulable con la que se puede obtener con el Reto del Viajante (es decir, como máximo se convalidarán 2 puntos en el examen).

El Reto del VIAJANTE
Enunciado y descripción: retoviajante.html
Mejor solución actual: retoviajante.html#actual
Procedimiento: Enviar por e-mail los ciclos encontrados (según el formato especificado en el enunciado) si son mejores que la mejor solución actual. Sólo se pedirá una explicación del algoritmo y el trabajo realizado al ganador (o ganadores) del reto.
Evaluación: El alumno ganador del reto, tras la correspondiente entrevista, tendrá un 10 en un ejercicio correspondiente del examen (segundo parcial), 1 punto de notas de clase en esa parte y 1 punto de notas adicionales (ver la sección de Evaluación). El reto también puede realizarse por parejas, aunque en este caso las notas de clase y las notas adicionales se repartirán entre ambos alumnos (0,5 puntos en cada una).
Convalidación de examen: Los alumnos que resuelvan el problema, dando un algoritmo razonablemente bueno y trabajado, podrán convalidar 1 ejercicio del Segundo Parcial (de 2 puntos sobre 10). En este caso sí que se deberá documentar el trabajo realizado y se podrá requerir una entrevista con los alumnos. Además, se requiere que la solución use por lo menos dos técnicas de diseño de las vistas en clase. Esta práctica optativa puede realizarse en grupos de dos. La fecha de entrega será el viernes 3 de junio de 2005. Los alumnos con la asignatura "Laboratorio de Programación" (plan antiguo) aprobada, tienen convalidada esta práctica de forma automática.

El Reto de las CIFRAS
Dada una lista de 4, 5, 6, ... ó 10 enteros (entre 1 y 100) encontrar la forma de conseguir otro entre 1 y 2000, utilizando las operaciones de suma, resta, producto y división entera. Cada número de la lista sólo se puede usar una vez.
Versión a retar: cifras.exe (executable Win95)
Reto: Diseñar, implementar y documentar una solución al problema más rápida que el programa "cifras.exe", y que no pierda ninguna solución. El programa debe indicar todos los números alcanzables, entre 1 y 2000, usando los datos de entrada.
Evaluación: Tras la correspondiente entrevista con el profesor, la evaluación si se supera el reto será: un 10 en la tercera práctica de la asignatura, un 10 en un ejercicio correspondiente del examen, más 1 punto de notas de clase en esa parte. Si alguien implementa una solución pero no es más rápida que "cifras.exe", podría valer como uno de los ejercicios de la tercera práctica (también, después de una entrevista). Máximo: 2 personas por grupo.

Olimpiadas Regionales de Programación
Normas: Para realizar esta práctica los alumnos deberán participar en las III Olimpiadas Regionales de Programación, y/o en el Curso de Promoción Educativa de preparación.
Evaluación: La realización de esta práctica no es obligatoria para aprobar la asignatura.
- La nota obtenida se sumará a la Nota Final de la asignatura, siempre que se superen los mínimos en las notas de examen y de prácticas (ver sección Evaluación).
- Para los alumnos que realicen el Curso de Preparación para el Concurso Internacional de la ACM para Estudiantes Universitarios, se sumará 0,5 puntos.
- Para los alumnos que participen en las III Olimpiadas Regionales de Programación, se sumarán 0,5 puntos por cada problema resuelto, que se dividirán por el número de alumnos del grupo.
- Como máximo, la nota adicional no superará nunca 1 punto.

Seminario de Especificaciones Algebraicas

Enunciado para Septiembre y Diciembre de 2005: PDF, Word97

Notas de la Práctica

Indicaciones
Las entrevistas (para aquellos alumnos que se indican en la columna Comentario) se realizarán después de vacaciones, en horas de tutorías, cuando puedan los alumnos, pero siempre antes de los exámenes de febrero. Los alumnos que hayan entregado la práctica y tengan una nota menor que 6, pueden realizar opcionalmente una entrevista/revisión/corrección para mejorar su nota. Recordar que sólo se convalidan las notas mayores o iguales a 5.

Guión: PDF, Word97

Programa usado: Maude

Especificaciones de ejemplo: Natural, Letra, Pila, Ejemplo

Fechas
Realización: jueves 9/12/2004, de 8:30 a 10:30 y de 10:30 a 12:30 (Laboratorio 1/1)
Entrega: 21/12/2004
Convocatorias de septiembre/diciembre: hasta 2 días antes del examen

Normas

• Esta práctica se realizará en grupos de dos. De manera especial, en las convocatorias de septiembre y diciembre se deberá realizar indidualmente.

• Para evaluar la práctica se requiere que los miembros del grupo asistan al seminario correspondiente (jueves 9 de diciembre) realizando por lo menos el primer ejercicio. Se pasará lista al final del seminario.

• Todos los ficheros de la práctica deberán entregarse en papel, antes del 21 de diciembre, y deberán estar accesibles dentro de una de las cuentas de los alumnos del grupo.

• Revisión de la práctica: en horarios normales de tutorías.

Evaluación

• La realización de esta práctica no es obligatoria para aprobar la asignatura.

• Los alumnos con nota mayor o igual a 5 (sobre 10) no deberán realizar en el examen parcial o final los ejercicios correspondientes al tema 1, parte 1. La nota obtenida en esta práctica se guardará como la nota de los ejercicios del examen correspondiente.

• Ver más detalles de la práctica en la guía del seminario.

TUTORIAS

Martes: 17:30-20:30

Miércoles: 17:30-20:30

Lugar: Despacho E-20 (3ª planta, Fac. Informática)

EXAMENES

Primer Parcial
Fecha: viernes 4 de marzo
Hora: 12:00 am
Lugar: Aulario General, aulas 0.03, 0.04, 0.07, 0.10
Duración aprox.: 3 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen
Notas del Examen
Examen y soluciones

Segundo Parcial
Fecha: viernes 10 de junio
Hora: 12:00 am
Lugar: Aulario General, aulas 0.03, 0.04, 0.07, 0.10
Duración aprox.: 3 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen
Notas del Examen
Examen y soluciones

Convocatoria de Junio-05
Fecha: 28 de junio
Lugar: Aulario General
PRIMERA PARTE (1er PARCIAL):
Hora: 9:00 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 11:30 Duración: 2 horas, 15 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. Los alumnos cuya nota final de examen esté aprobada (mayor o igual que 5) no tendrán que hacer este examen. Los alumnos que tengan aprobado algún parcial (nota mayor o igual que 5) sólo deben hacer la parte no aprobada.
Notas del Examen
Notas Finales de la convocatoria
Examen y soluciones

Convocatoria de Septiembre-05
Fecha: Martes 6/septiembre/2005
Lugar: Aulario General, Aulas: 0.07-0.11
PRIMERA PARTE (1er PARCIAL):
Hora: 9:00 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 11:30 Duración: 2 horas, 30 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. Se guardan las notas de exámenes previos a partir de 5. La fecha de entrega de prácticas es el día del examen.
Notas del Examen
Notas Finales de la convocatoria
Examen

Convocatoria de Diciembre-05
Fecha: jueves 1/diciembre/2005
Lugar: Facultad de Informática, Aula: 2/1
PRIMERA PARTE (1er PARCIAL):
Hora: 9:00 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 11:30 Duración: 2 horas, 30 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. La fecha de entrega de la práctica es el día del examen.
Notas del Examen
Notas Finales de la convocatoria

EVALUACION

• La Nota Final será un promedio entre la Nota Total de Prácticas y la Nota Total del Examen. La Nota Total de Prácticas contará un 35% y la de Examen un 65%. Ambas partes deben estar aprobadas por separado.

• La Nota Final podrá incrementarse hasta en 1 punto, con la realización de actividades de carácter optativo (notas adicionales) (ver sección Prácticas Optativas).

• La Nota Total de Prácticas será un promedio de la nota obtenida en cada una de las tres prácticas de la asignatura.

• Para calcular la Nota Total de Prácticas, cada una de las tres partes (por separado) debe estar aprobada. En otro caso las prácticas se consideran no aprobadas.

• La Nota Total de Prácticas se guarda para convocatorias posteriores si es mayor o igual que 5 sobre 10. También se guardan las notas de las partes que estén aprobadas.

• La Nota Total del Examen se obtendrá promediando la Nota del Primer y el Segundo Parcial.

• El Primer Parcial corresponde al bloque de "Estructuras de Datos" y contará un 40%. El Segundo Parcial corresponde al bloque de "Análisis y Diseño de Algoritmos" y contará un 60%.

• La Nota de cada parcial puede incrementarse hasta en 1 punto con la realización de Ejercicios en Clase, siempre que sea mayor o igual que 4 sobre 10.

• Para calcular la Nota Total del Examen se requiere que la nota de cada parte sea como mínimo de 4 sobre 10 (tanto en los Parciales como en el Examen Final). En otro caso el examen se considera no aprobado.

• La Nota Total del Examen se guarda para convocatorias posteriores si es mayor o igual que 5 sobre 10 (tras sumar las Notas de Clase). También se guardan los Parciales que estén aprobados para las convocatorias finales de Junio, Septiembre y Diciembre.

CONVALIDACIONES (alumnos de otras convocatorias)

Información para los alumnos de Plan Antiguo que han realizado el cambio a Plan Nuevo y de convocatorias anteriores de AED:

• Básicamente, la asignatura "Ampliación de Algoritmos y Estructuras de Datos" (plan antiguo) se corresponde con la teoría de "Algoritmos y Estructuras de Datos" (plan nuevo), y la asignatura "Laboratorio de Programación" (plan antiguo) corresponde a las prácticas de "Algoritmos y Estructuras de Datos" (plan nuevo).

• Para los alumnos con la asignatura "Laboratorio de Programación" (plan antiguo) aprobada, la Nota Total de Prácticas durante las tres convocatorias del curso 2004/05 será la nota obtenida en dicha asignatura.

• Para los alumnos con la asignatura "Ampliación de Algoritmos y Estructuras de Datos" (plan antiguo) aprobada, la Nota Total del Examen durante las tres convocatorias del curso 2004/05 será la nota obtenida en dicha asignatura.

• Para los alumnos con teoría o prácticas aprobadas en convocatorias anteriores de AED, se guardan paras las convocatorias del curso 2004/05 las notas de las partes aprobadas, ya sea la nota final de examen, de uno de los parciales o la nota de prácticas.

BIBLIOGRAFIA

Texto Guía

• García Mateos, G., Giménez Cánovas, D., Cervera López, J., Marín Pérez, N.: Algoritmos y Estructuras de Datos. Diego Marín, 2003.

Básica

• Aho, A.V.; Hopcroft, J.E.; Ullman, J.D.: Estructura de datos y algoritmos. Addison- Wesley, 1988.
• Brassard, G.; Bratley, P.: Fundamentos de Algoritmia. Prentice-Hall, 1998.
• Weiss, M.A.: Estructuras de datos y algoritmos. Addison-Wesley, 1995.
• Collado, M; Morales, R.; Moreno, J.J.: Estructuras de datos. Realización en Pascal. Díaz de Santos, 1987.
• Baase, S.; Van Gelder, A.: Computer Algorithms. Introduction to Design and Analysis. Addison-Wesley, 2000.
• Horowitz, E.; Sahni, S.: Fundamentals of Data Structures. Computer Science Press, 1976.

• Wirth, N.: Algoritmos y estructura de datos. Prentice-Hall, 1987.

Complementaria

• Heileman, G.L.: Estructuras de Datos, Algoritmos y Programación orientada a Objetos. McGraw-Hill, 1997.
• Hoorobeek, I.V.: Algebraic Specifications. From Many-Sorted Algebras to a Practical Specification Language. K.U. Leuven, Dept. of Computer Science, 1985.
• Joyanes, L.; Zahonero, I.: Estructura de datos. McGraw-Hill, 1998.
• Mehlhorn, K.: Data Structures and Algorithms. Springer-Verlag, 1984.
• Peña, R.: Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1997.

On-line

Facultad de Informática. Despacho E-20.
Campus de Espinardo. Universidad de Murcia.
30071 Murcia (SPAIN)
Teléfono: +34 968 36 46 08
Fax: +34 968 36 41 51
E-mail: ginesgm@um.es