|
|
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
AVISOS PARA LOS ALUMNOS
- 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
PRÁCTICAS
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.
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: PDF, Word97
Generador de blogs: generador.zip
Práctica
2: Eficiencia, evaluación y predicción
Enunciado: PDF, Word97
Práctica
3: Resolución de problemas
Enunciado: PDF, Word97
Problemas: ZIP
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á 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.
TUTORIAS
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)
EXAMENES
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
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.
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.
BIBLIOGRAFIA
Texto
Guía
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
Ginés García
Mateos: Exámenes de convocatorias
anteriores (con soluciones, a partir de 2001). Septiembre/2005, Junio/2005, Marzo/2005, Diciembre/2004, Septiembre/2004, Junio/2004, Febrero/2004, Diciembre/2003, Septiembre/2003, Marzo/2003, Diciembre/2002, Septiembre/2002, Marzo/2002, Marzo- Septiembre-
Diciembre/2001. Marzo- Septiembre-
Diciembre/2000. Marzo- Septiembre-
Diciembre/1999.
Foro de
discusión en español sobre algorítmica:
http://www.foro.ws/algoritmia/
Dictionary
of Algorithms and Data Structures: http://www.nist.gov/dads/
The Complete
Collection of Algorithm Animations: http://www.cs.hope.edu/~alganim/ccaa/
García de Jalón, J.
et al: Tutorial de C++ de la Escuela Superior de
Ingeniería Industrial de Navarra.
Valladolid Programming
Contest Site: http://acm.uva.es/problemset/
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
|