08BZ - ALGORITMOS Y ESTRUCTURAS DE DATOS

Año 2003/2004
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 Finales de la convocatoria de diciembre de 2004 de AED y AAED.

- Se han actualizado los buscadores a analizar en la Práctica 2 para las convocatorias de septiembre y diciembre. Ver el procedimiento para obtenerlo.

- Convocatoria de diciembre de 2004: las Prácticas Obligatorias son las mismas que para junio de 2004. La práctica optativa de Resolución de Juegos (las cuatro en raya) también es la misma. La práctica de Especificaciones Algebraicas (seminario de Maude) ha cambiado y debe hacerse individualmente. Fecha de entrega de las prácticas: el día del examen.

- La Práctica 3 no tendrá entrevista obligatoria.

- ¡¡Retos!! Sigue abierto el reto del juego de las cifras (ver en la sección Prácticas Optativas). El primero que lo supere tendrá la recompensa indicada. El reto del balón de fútbol ha sido resuelto. Ver la solución (por Bruno Recasens).

- Si buscas información de la asignatura relativa a las convocatorias del curso 2002/2003 o relativa a la asignatura AAED de plan antiguo, usa esta página.

APUNTES

Parte I: Estructuras de datos

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

Tema 0. Algorítmica.
transparencias: PDF, PowerPoint97

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

• Convocatoria de septiembre de 2004: las prácticas obligatorias son las mismas que para junio de 2004. Fecha de entrega: 2 de septiembre (el día del examen)

• NOTAS DE PRÁCTICAS (convocatoria de junio de 2004)

• 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).

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

• Entrevistas de prácticas: Las entrevistas de prácticas de las convocatorias de septiembre y diciembre 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
  Sesión 4: PDF, Word97

• 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
  Programa generador de casos de prueba: Generador, Leeme
  Tablas de desarrollo del proyecto (necesarias para la memoria): PDF, Word97
  Fecha de entrega: Jueves 2/Septiembre/2004

• Práctica 2: Eficiencia, evaluación y predicción
  Enunciado de la práctica: PDF, Word97
  Programas a analizar por cada grupo (además del propio): Buscadores
  Fichero de palabras de la RAE: palabras.zip
  Tablas de desarrollo del proyecto (necesarias para la memoria): PDF, Word97
  Fecha de entrega: Jueves 2/Septiembre/2004

• Práctica 3: Resolución de problemas
  Enunciado de la práctica: PDF, Word97
  Problemas: 529, 704, 10032, 10160, 10270, 10422
  Fecha de entrega: Jueves 2/Septiembre/2004

PRACTICAS OPTATIVAS

Resolución de Juegos: las cuatro en raya
Enunciado: PDF, DOC
Notas de la práctica

Evaluación: La realización de esta práctica no es obligatoria para aprobar la asignatura. La superación de la misma se convalidará por un ejercicio de examen del segundo parcial (que contará aproximadamente el 20% del examen), de acuerdo con la nota obtenida en la práctica.

Convalidación: A los alumnos de plan antiguo que tuvieran aprobada la asignatura “Laboratorio de Programación” se les convalida esta práctica con la nota obtenida en la mencionada asignatura. No obstante, si desean realizarla podrá contar como nota adicional (hasta 1 punto a añadir a la Nota Final): ver el segundo punto de la sección Evaluación.

Fecha de entrega: lunes 7 de junio de 2004

El juego de las CIFRAS
Dado un conjunto 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 del conjunto 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.
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.

El juego del BALON DE FUTBOL **RETO RESUELTO**
Descripción del problema
Solución (por Bruno Recasens)
Reto: Diseñar, implementar y documentar un programa que resuelva el problema.
Evaluación: Tras la correspondiente entrevista con el profesor, para el primero (alumno o grupo) que resuelva el problema la evaluación si se supera el reto será: un 10 en uno de los problemas de 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. Máximo: 2 personas por grupo.

Olimpiadas Regionales de Programación

Normas
Para realizar esta práctica los alumnos deberán participar en las II 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 II Olimpiadas Regionales de Programación, resolviendo por lo menos 1 problema, se sumará 0,5 puntos.
  

Seminario de Especificaciones Algebraicas

Notas de la práctica
(alumnos que han entregado ficha)

Guión y enunciado (convocatorias de septiembre y diciembre de 2004): PDF

Guión: PDF, Word97

Programa usado: Maude

Especificaciones de ejemplo: Natural, Letra, Pila, Ejemplo

Fechas
Realización: 9/12/2003 y 10/12/2003, en horas de prácticas (laboratorio 1/1)
Entrega: 19/12/2003

Normas

• Esta práctica se realizará individualmente.

• Para evaluar la práctica se requiere que los miembros del grupo asistan al seminario correspondiente (martes 9 de diciembre y miércoles 10) 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 19 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

Miércoles: 10:30-13:30

Jueves: 10:30-13:30

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

EXAMENES

Primer Parcial Febrero-04
Fecha: sábado 28/Febrero/2004
Hora: 10:00 am
Lugar: Aulario General, Aulas 0.05 y 0.06
Duración aprox.: 3 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen
Notas del Examen
Examen

Convocatoria de Junio-04
(Segundo Parcial y Final)
Fecha: 16/JUNIO/2004
Lugar: Aulario General, Aulas 0.04, 0.05, 0.06
PRIMERA PARTE (1er PARCIAL):
Hora: 15:30 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 18:00 Duración: 2 horas, 15 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. Los alumnos que tengan aprobado el primer parcial (nota mayor o igual que 5) sólo deben hacer la segunda parte.
Notas del Examen
Notas Finales de la convocatoria
Examen y soluciones

Convocatoria de Septiembre-04
Fecha: 2/Septiembre/2004
Lugar: Aulario General, Aulas 0.04, 0.05, 0.06
PRIMERA PARTE (1er PARCIAL):
Hora: 15:30 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 18:00 Duración: 2 horas, 15 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. Ojo, sólo 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 y soluciones

Convocatoria de Diciembre-04
Fecha: Jueves 2/Diciembre/2004
Lugar: Aulario Norte, Aulas D.01, D.02, C.01
PRIMERA PARTE (1er PARCIAL):
Hora: 15:30 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 18:00 Duración: 2 horas, 15 min.
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora y DNI al examen. Ojo, sólo 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

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 (ver sección Prácticas Optativas).

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

  • La Nota Total de Prácticas podrá incrementarse hasta en 1 punto (sobre 10), con la realización de alguna parte opcional.

  • Para calcular la Nota Total de Prácticas, cada una de las dos/tres partes (por separado) debe tener como mínimo un 4 sobre 10. 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.

• 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.

  • Los alumnos que no aprueben el Primer Parcial deberán realizar el Examen Final (con toda la asignatura), y la nota obtenida será la Nota Total del Examen.

  • 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). Si el Primer Parcial está aprobado pero no el Segundo, no se guarda la nota para las convocatorias de Septiembre y Diciembre.

CONVALIDACIONES (con plan antiguo)

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

• 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 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 será la nota obtenida en dicha asignatura.

• Como FAVOR ESPECIAL, los alumnos de plan antiguo adaptados al plan nuevo podrán presentarse al examen de Diciembre de 2003, en la fecha y lugar correspondientes a la asignatura "Ampliación de Algoritmos y Estructuras de Datos" (plan antiguo). La nota obtenida se guardará para la convocatoria de Junio de 2004.

• No habrá convocatoria de Diciembre de 2003 para las prácticas de la asignatura.

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