08BZ - ALGORITMOS Y ESTRUCTURAS DE DATOS
Año 2005/2006
Curso Segundo
Ingeniero en Informática
Universidad de
Murcia
AVISOS | APUNTES | PRACTICAS | PR. OPTATIVAS | TUTORIAS | EXAMENES | EVALUACION | CONVALIDACIONES | BIBLIOGRAFIA
- Ya han salido las notas de examen de septiembre de 2006 y las notas finales de la convocatoria, que están también disponibles en los tablones de la Facultad.
- Se ha añadido en la sección de bibliografía on-line un foro de discusión sobre algorítmica de la Universidad de Málaga.
- Ya estoy en el nuevo edificio: despacho 2.34.
- Se abre una nueva práctica optativa, El juego de los cuadrados, convalidable por una pregunta del segundo parcial. Ver el enunciado y guión (PDF, DOC) de esta práctica.
- ¡Ha finalizado el Reto del Viajante! El alumno ganador es Bernardino Romera, con una solución de coste 21486. Se ha enviado un email a los participantes indicándoles la recompensa obtenida.
- Los alumnos que participen en las Olimpiadas Regionales de Programación y en el curso de preparación tendrán hasta 1 punto de notas adicionales. Se ha abierto el plazo de preinscripción para este curso.
- Ver la información relativa a las cuentas de prácticas en los laboratorios, para la realización de las prácticas y los seminarios de este curso.
- 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 2004/2005 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:
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.
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
Profesor de Prácticas: Alberto Pérez Vela
Cuentas de prácticas: este curso las cuentas linux no van a ser por asignatura, sino por alumno. La cuenta de cada alumno empieza por la letra u seguida de su número de DNI. Por ejemplo, para el alumno con DNI 12345678, su login será u12345678. Para conocer la clave, los alumnos deben acceder a la URL: https://correo.dif.um.es/alumnos/olvidoclave.php, donde aportando el DNI, se les envía la clave a su dirección de correo en el dominio @alu.um.es.
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.
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, TXTSeminario 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: PDF, Word97
Generador de blogs: generador.zipPráctica 2: Eficiencia, evaluación y predicción
Enunciado: PDF, Word97Práctica 3: Resolución de problemas
Enunciado: PDF, Word97
Problemas: ZIP
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á hasta una semana antes del segundo parcial.
Ver los detalles de evaluación y convalidación en el
enunciado de la práctica.
Olimpiadas
Regionales de Programación **PRACTICA CERRADA**
Normas:
Para
realizar esta práctica los alumnos deberán participar
en las IV 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 IV 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.
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.
El
Reto del VIAJANTE **RETO CERRADO**
Ganador del reto: Bernardino
Romera Paredes, con un ciclo de coste: 21486
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 2006.
Evaluación: El ganador o ganadores del reto,
tras la correspondiente entrevista, tendrá un 10 en el
ejercicio de grafos del primer parcial.
Seminario
de Especificaciones Algebraicas
**SEMINARIO CONCLUIDO**
Notas
finales
Guión del seminario:
PDF, Word97
Programa
usado: Maude
Especificaciones de ejemplo: Natural, Letra, Pila, Ejemplo
Fechas. Seminario: jueves 3 y martes 8
de noviembre. Entrega: lunes 21 de
noviembre.
Ver descripción, indicaciones y evaluación de esta
práctica en el guión del seminario (PDF, Word97).
El
Reto del Sudoku Samurai **RETO CERRADO**
El reto ha sido superado por 5
retadores
Enunciado:
Escribir un programa para resolver el problema del Sudoku
Samurai en un tiempo razonable. El Sudoku Samurai consta
de 5 Sudokus solapados, tal y como se muestra en esta figura. Cada uno de los Sudokus
individuales debe cumplir las restricciones propias del
problema, a saber, en cada celda de la matriz de 9x9 debe
ir un dígito del 1 al 9, y no se pueden repetir dígitos
en la misma fila, columna o bloque de celdas. Se
garantiza que el problema tiene solución única.
Descripción del formato: El programa
debe leer la entrada de teclado, según el formato
indicado, y debe producir la salida por pantalla según
el mismo formato de salida. No incluir ningún mensaje de
salida adicional. El formato de entrada/salida consta de
21 líneas, cada una con 21 letras separadas por
espacios. Cada letra es un dígito de 1 a 9, o un 0 para
las posiciones vacías en la entrada (no debe aparecer en
la salida), o un punto "." para las posiciones
que caigan fuera del Sudoku Samurai. Todos los ficheros
son en formato de texto ASCII.
Ficheros de entrada/salida: sudokusam.zip. La solución de cada
fichero de entrada inX.txt es el correspondiente
outX.txt. Observar que el ejemplo in3.txt
corresponde a este Sudoku.
Procedimiento: Enviar por e-mail el programa realizado, tras
comprobar la ejecución correcta sobre los ejemplos de prueba. Se hará una entrevista
con el alumno ganador para comprobar la originalidad y
autoría del programa.
Evaluación: El alumno ganador del reto,
tras la correspondiente entrevista, tendrá un 10 en un
ejercicio correspondiente del examen (segundo parcial) y
1 punto de notas de clase en esa parte.
Lunes: 17:45-19:45
Miércoles: 10:45-13:45, y de 17:30-18:30
Lugar: Despacho 2.34 (2ª planta, Fac. Informática nueva)
Convocatoria
de Febrero-2006
Fecha:
martes 7/febrero/2006
Lugar: Aulario Norte Aulas:
B.01, B.02, B.03, B.04, A.01, A.02, A.04
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 Examen
y finales de la convocatoria
Examen y
soluciones
Segundo
Parcial, Junio-2006
Fecha:
jueves 8/junio/2006
Lugar: Aulario Norte Aulas:
A.03, A.04, C.04
Hora: 10:00 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 Examen
Examen
Convocatoria de Junio-2006
Fecha:
lunes 19/junio/2006
Lugar: Aulario Norte Aulas:
A.01 - A.04, B.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 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
respuestas
Convocatoria de Septiembre-2006
Fecha:
martes 5/septiembre/2006
Lugar: Aulario Norte Aulas:
A.01, A.02, A.03, A.04
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
convocatorias previas a partir de 5; también las notas
de practicas convalidables (pero a partir de un 4 en la
parte no convalidada).
Notas del Examen
Notas Finales de la
convocatoria
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 2005/06 las notas de las partes aprobadas, ya sea la nota final de examen, de uno de los parciales o la nota de prácticas.
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.
Facultad de Informática. Despacho 2.34.
Campus de
Espinardo. Universidad de Murcia.
30071 Murcia (SPAIN)
Teléfono: NINGUNO
Fax: +34 968 36 41
51
E-mail: ginesgm@um.es