08BZ - ALGORITMOS Y ESTRUCTURAS DE DATOS

Año 2006/2007
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 septiembre de 2007.

- Ver la solución propuesta por el alumno Germán Ros para el juego de la Plaga (con interface gráfica).

- El Reto del Viajante ha terminado sin que nadie haya sido capaz de superar la mejor solución del año pasado. No obstante, si alguien consigue obtener una buena solución antes de finalizar el curso, se tendrá en cuenta positivamente para el segundo parcial.

- Consultar la fe de erratas del texto guía, para los alumnos que manejen el texto guía de la asignatura.

- Si buscas información de la asignatura relativa a las convocatorias del curso 2005/2006 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.

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

• Seminarios de C/C++: Jesualdo Tomás Fernández Breis

• Profesores de Prácticas: Alberto Pérez Vela y Ginés García Mateos

• 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
  Enunciado
  Generador de casos de prueba

• Práctica 2: Eficiencia, evaluación y predicción
  Enunciado

• Práctica 3: Resolución de problemas
  Enunciado: PDF
  Problemas: ZIP

PRACTICAS OPTATIVAS

El Juego de la Plaga **Plazo finalizado el 1/6/07**
Ver la solución propuesta por el alumno Germán Ros (con interface gráfica)
Notas finales
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á hasta una semana antes del segundo parcial. Ver los detalles de evaluación y convalidación en el enunciado de la práctica.

Seminario de Especificaciones Algebraicas
Notas finales
Guión del seminario: PDF, Word97
Programa usado: Maude
Especificaciones de ejemplo: Natural, Letra, Pila, Ejemplo
Fechas. Seminario: martes 28 y jueves 30 de noviembre. Entrega: lunes 18 de diciembre.
Ver descripción, indicaciones y evaluación de esta práctica en el guión del seminario (PDF, Word97).

El Reto de la COPA **Reto finalizado el 6/10/06**
Ha sido superado por el alumno Antonio García Guirao
Enunciado y descripción: retocopa.html
Procedimiento: Enviar por e-mail el programa que resuelva el problema. La entrada/salida será por teclado/pantalla, ajustándose estrictamente al formato dado en el enunciado. Antes de enviar un programa al profesor, comprobar que se obtiene el resultado correcto, por lo menos para los mismos ejemplos dados en el enunciado. Se pedirá una explicación del algoritmo y el trabajo realizado al ganador del reto. El reto se debe hacer en grupos de 1 alumno. Excepcionalmente se puede hacer en grupos de 2, pero en ese caso cada miembro deberá especificar claramente cuál es su contribución al método desarrollado.
Fecha: El ganador del reto será el primer alumno que consiga resolver el problema correctamente.
Evaluación: El ganador o ganadores del reto, tras la correspondiente entrevista, tendrá 1 punto en los ejercicios de clase de los dos parciales.

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 del reto. El reto se puede hacer en grupos de 2, pero en ese caso cada miembro deberá especificar claramente cuál es su contribución al método desarrollado.
Fecha: El reto estará abierto hasta el 30 de enero del 2007.
Evaluación: El ganador o ganadores del reto, tras la correspondiente entrevista, tendrá un 10 en el ejercicio de grafos del primer parcial.

El Reto de las CIFRAS
Dada una lista de 4, 5, 6, ... ó 10 enteros (entre 1 y 100) encontrar la forma de conseguir otro entero 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. Máximo: 2 personas por grupo.

TUTORIAS

Lunes y jueves de 10:30 a 13:30

Lugar: Despacho 2.34 (2ª planta, Fac. Informática)

EXAMENES

Convocatoria de Febrero-2007
Fecha: martes 6/febrero/2007
Lugar: Aulario Norte Aulas: A.01-A.04, B.01-B.03
PRIMERA PARTE (1er PARCIAL):
Hora: 15:30 Duración: 2 horas 15 minutos
SEGUNDA PARTE (2º PARCIAL):
Hora: 18:00 Duración: 2 horas, 20 minutos
Modalidad: Teórico/Práctico
Observaciones: se aconseja traer calculadora y DNI al examen. La segunda parte es sólo para los alumnos repetidores del curso pasado. Se guardan las notas de convocatorias previas a partir de 5.
Notas del Segundo Parcial y Finales de la convocatoria
Notas del Primer Parcial
Examen y soluciones

Segundo Parcial, Junio-2007
Fecha: viernes 8/junio/2007
Lugar: Aulario Norte Aulas: A.03, A.04 y A.04 bis
Hora: 10:00 am Duración: 3 horas
Modalidad: Teórico/Práctico
Observaciones: se aconseja traer calculadora y DNI al examen. Se pueden presentar todos los alumnos al examen (aunque no tengan aprobado el primer parcial). Para el final, se guardan las notas por parciales.
Notas del Segundo Parcial
Examen y soluciones

Convocatoria de Junio-2007
Fecha: 18/junio/2007
Lugar: Aulario Norte Aulas: A.01-A.04
PRIMERA PARTE (1er PARCIAL):
Hora: 3:30 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 6:00 Duración: 2 horas, 30 min.
Modalidad: Teórico/Práctico
Observaciones: se aconseja traer calculadora y DNI al examen. Los alumnos que hayan aprobado ambos parciales 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

Convocatoria de Septiembre-2007
Fecha: 4/septiembre/2007
Lugar: Aulario Norte Aulas: A.01, A.02, A.03
PRIMERA PARTE (1er PARCIAL):
Hora: 3:30 Duración: 2 horas
SEGUNDA PARTE (2º PARCIAL):
Hora: 6:00 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 convocatorias previas a partir de 5; también las notas de prácticas convalidables (pero a partir de un 4 en la parte no convalidada). La entraga de la práctica es el mismo 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 (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 participación en los 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 previas)

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 2005/06 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 2005/06 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 2006/07 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.
• Martí, M.; Ortega, Y.; Verdejo, A.: Estructuras de datos y métodos algorítmicos: ejercicios resueltos. Prentice Hall, 2004.
• Baase, S.; Van Gelder, A.: Computer algorithms. Introduction to Design and Analysis. Addison-Wesley, 2000.

Complementaria

• Cormen, T.H.; Leierson, C.E.; Rivest, R.L.; Stein, C.: Introduction to algorithms, second edition. The MIT Press, 2001.
• Wirth, N.: Algoritmos y estructura de datos. Prentice-Hall, 1987.
• 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.
• Kernighan, B.W., Ritchie, D.M.: El lenguaje de programación C. Prentice-Hall, 1991.
• Stroustrup, B.: El lenguaje de programación C++. Addison Wesley, 1998.

On-line

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