96S - AMPLIACIÓN DE ALGORITMOS Y ESTRUCTURA DE DATOS

Año 2000/2001
Curso Segundo
Ingeniero en Informática
Universidad de Murcia


 

AVISOS PARA LOS ALUMNOS

- Ya han salido las notas del examen de la convocatoria de diciembre, las notas finales definitivas y las notas de prácticas de los alumnos no aprobados (que se guardan para la siguiente convocatoria).

- Ya está disponible la convocatoria del examen de diciembre y las soluciones, en la sección de exámenes.

- Ya está disponible el examen de septiembre y la hoja de soluciones.

- A los alumnos que no tengan asignado número de prácticas (o, excepcionalmente, que no lo recuerden) se les asigna a partir de ahora el número 80.

- Criterios para aprobar las prácticas: ver la sección de Prácticas.


APUNTES

Parte I: Estructuras de datos

Tema 1. Abstracciones y especificaciones.
tema1-1.zip (PowerPoint97+Word97), ejerc1-1.zip (Word97)

Tema 2. Conjuntos.
tema2-1.zip (PowerPoint97), ejerc2-1.zip (Word97)

Tema 3. Métodos avanzados de representación de conjuntos.
tema3-1.zip (PowerPoint97), ejerc3-1.zip (Word97)

Tema 4. Grafos.
tema4-1.zip (PowerPoint97), ejerc4-1.zip (Word97)
 

Parte II: Algoritmos

Tema 1. Algorítmica.
tema1-2.zip (PowerPoint97)

Tema 2. Análisis de algoritmos.
tema2-2.zip (PowerPoint97), ejerc2-2.zip (Word97)

Tema 3. Divide y vencerás.
tema3-2.zip (PowerPoint97), ejerc3-2.zip (Word97)

Tema 4. Algoritmos voraces.
tema4-2.zip (PowerPoint97), ejerc4-2.zip (Word97)

Tema 5. Programación dinámica.
tema5-2.zip (PowerPoint97), ejerc5-2.zip (Word97)

Tema 6. Backtracking.
tema6-2.zip (PowerPoint97), ejerc6-2.zip (Word97)

Tema 7. Ramificación y poda.
tema7-2.zip (PowerPoint97), ejerc7-2.zip (Word97)


PRÁCTICAS
Las prácticas pueden estar aprobadas o no aprobadas. Tener aprobadas las prácticas es obligatorio para aprobar la asignatura, aunque no para presentarse al examen.
· La Parte I se aprueba con un máximo de 2 ejercicios mal.
· La Parte II se aprueba con un máximo de 1 ejercicio mal y uno regular, o bien 3 ejercicios regular.

· Los ejercicios del examen que estén aprobados, podrán servir para compensar los ejercicios de prácticas no aprobados correspondientes a ese mismo tema. (La relación contraria no se cumple.) Las notas de prácticas de la Parte II de cada alumno y los ejercicios que debe corregir aparecerán en
esta página.
· Las prácticas para las convocatorias de septiembre y diciembre son las mismas que para la de marzo. Las notas de prácticas se guardan para estas convocatorias. La fecha de entrega (en ambos casos) será la fecha del examen.

Parte I: Estructuras de datos
Última fecha de entrega: Fecha del examen de AAED
Ejercicios a entregar: lista_ejer1.zip (Word97)
Notas definitivas

Parte II: Algoritmos
Última fecha de entrega: Fecha del examen de AAED
Ejercicios a entregar: lista_ejer2.zip (Word97)
Notas definitivas


EXAMENES

Convocatoria de Marzo
Fecha: 9/Marzo/2001
Notas del Examen
Notas finales de la convocatoria de Marzo
Examen y soluciones

Convocatoria de Septiembre
Fecha: Lunes 10/Septiembre/2001
Hora: 9:30 a.m.
Lugar: Edificio D, 2.1 y 2.2
Duración aprox.: 4 horas
Observaciones:
La fecha de entrega de las prácticas es la fecha y hora del examen.
Notas del Examen
Notas finales de la convocatoria de Septiembre
Examen y soluciones

Convocatoria de Diciembre
Fecha: Martes 11/Diciembre/2001
Hora: 9:30 a.m.
Lugar: Aulario General, aula 0.04
Duración aprox.: 4 horas
Observaciones:
La fecha de entrega de las prácticas es la fecha y hora del examen. Ver las notas de prácticas en #pract.
Notas del Examen
Notas finales de la convocatoria de Diciembre
Examen y soluciones


RETOS

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 versión más rápida (o igual) que el programa "cifras.exe".
Retribución: Un 10 en la parte de algorítmica del examen (tras la correspondiente entrevista con el profesor, claro) y no hace falta hacer la Parte II de las prácticas. Si alguien crea una solución pero no es más rápida que "cifras.exe", valdría como Parte II de las prácticas (también, después de una entrevista). Máximo: 2 personas por grupo.

El juego del MASTER-MIND - ** Reto RESUELTO **
Adivinar un número A de 4 cifras (que piensa el usuario), en el menor número de intentos posible. En cada intento el ordenador dice un número B y el usuario responde el número de cifras bien colocadas y el número de cifras mal colocadas (entre A y B).
Reto: Diseñar, implementar y documentar una solución para el problema, relacionándolo con las técnicas vistas en clase. Estudiar el orden de complejidad del algoritmo diseñado.


BIBLIOGRAFIA

Básica

  • Baase, S.; Van Gelder, A.: Computer Algorithms. Introduction to Design and Analysis. Addison-Wesley, 2000.
  • Aho, A.V.; Hopcroft, J.E.; Ullman, J.D.: Estructura de datos y algoritmos. Addison- Wesley, 1988.
  • 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.
  • Horowitz, E.; Sahni, S.: Fundamentals of Data Structures. Computer Science Press, 1976.
  • Wirth, N.: Algoritmos y estructura de datos. Prentice-Hall, 1987.

Complementaria

  • Brassard, G.; Bratley, P.: Fundamentos de Algoritmia. Prentice-Hall, 1998.
  • 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

  • Domingo Giménez Cánovas: Apuntes y problemas de algorítmica (Formato postscript). Universidad de Murcia, 1998.



  •  

    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