|
|
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
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
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.
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
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/2006, Junio2/2006, Junio/2006, Febrero/2006, 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: +34 968
39 85 30
Fax: +34 968 36 41
51
E-mail: ginesgm@um.es
|