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

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

AVISOS PARA LOS ALUMNOS

- Ya han salido las notas del examen y las notas finales de diciembre de 2002 (alumnos que han entregado ficha). Las notas están también disponibles en el tablón de anuncios de la facultad. La revisión del examen será el jueves 19 y el viernes 20.

- Ya está disponible el examen de diciembre de 2002 y las soluciones.

- Las Prácticas para las convocatorias de Septiembre y Diciembre son las mismas que para la convocatoria de Marzo. La fecha de entrega es el día del examen.

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 consistirán en la realización de algunos ejercicios, de los entregados para cada tema. La nota de prácticas cuenta un 20% en la nota final. No es necesario entregar las prácticas para aprobar la asignatura (aunque en tal caso será equivalente a tener un 0 en esa parte).
· Para los alumnos con las prácticas aprobadas en convocatorias anteriores, se calculará la nota en función de los ejercicios que estén bien. El resultado aparecerá en esta página.
· Las notas de prácticas se guardan para las convocatorias de este curso: junio, septiembre y diciembre.

Parte I: Estructuras de datos
Fecha de entrega: 18/1/2002, hasta las 23:59
Ejercicios a entregar: lista_ejer1.zip (Word97)
Notas de la Parte I

Parte II: Algoritmos
Fecha de entrega: 15/3/2002, hasta las 23:59
Ejercicios a entregar: lista_ejer2.zip (Word97)
Notas de la Parte II

PRACTICA OPTATIVA DE ALGORITMOS (ALTERNATIVA A LA PRACTICA-PARTE II)

Se pueden hacer en grupos de hasta 2 alumnos

• Resolver el problema de las letras usando árboles TRIE. Dada una lista de n letras (vocales o consonantes) encontrar la palabra (ó palabras) más larga que se puede conseguir usando esas letras (todas o algunas de ellas). El diccionario de palabras debe representarse mediante un árbol TRIE. Hacer un estudio del tiempo usado para resolver el problema y de la memoria usada en la representación del árbol. Usar la lista de palabras disponible en: aaed/palabras.zip (formato txt, 262 Kbytes).

• Resolver el problema de las 4 en raya. En el juego participan dos jugadores A y B (supondremos que uno es un humano y otro el ordenador), que mueven alternativamente. El tablero es de tamaño nxn. En cada movimiento se indica una columna, entre 1 y n, y la ficha (X ó O para A ó B, respectivamente) se coloca en la fila más baja no ocupada en esa columna. Gana el primer jugador que coloque 4 o más fichas de su tipo en una misma línea (ya sea horizontal, vertical o diagonal).

TUTORIAS

Martes: 10:30-13:30

Miércoles: 17:30-20:30

EXAMENES

Convocatoria de Marzo
Fecha: Viernes 15/Marzo/2002
Hora: 16:30 h.
Lugar: Aulario Norte: A03 - B01
Duración aprox.: 4 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora
Notas del Examen
Notas finales de la Convocatoria de Marzo
Examen y soluciones

Convocatoria de Septiembre
Fecha: 9/Septiembre/2002
Hora: 9:30 a.m.
Lugar: Aulario General: 0.04
Duración aprox.: 4 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora.
La fecha tope de entrega de las prácticas es el día del examen.
Notas del Examen
Notas finales de la Convocatoria de Septiembre
Examen y soluciones

Convocatoria de Diciembre
Fecha: Jueves 12/Diciembre/2002
Hora: 10:30 a.m.
Lugar: Edificio D Aula: 0.2
Duración aprox.: 4 horas
Modalidad: Teórico/Práctico
Observaciones: Se aconseja traer calculadora.
La fecha tope de entrega de las prácticas es el día del examen.
Notas del examen
Notas finales de la Convocatoria de Diciembre
Examen y soluciones

EVALUACION

• Para aprobar la asignatura es necesario tener en la Nota del Examen (0..10) un mínimo de 4,5 puntos. No hay ninguna restricción relativa a la nota de prácticas.

• La nota de prácticas está compuesta por la nota de las dos partes: Nota Práctica I (0..1) + Nota Práctica II (0..1).

• La nota de los Ejercicios de clase puede incrementar la nota final (nunca decrementar) hasta en 1 punto. La nota del test inicial entra dentro de este apartado.

• La nota final de la asignatura será calculada según la fórmula:
  SI Nota Examen (0..10) >= 4,5 ENTONCES
  Nota Final:= (Nota Examen (0..10))*0,8 + Nota Práctica I (0..1) + Nota Práctica II (0..1) + Ejercicios de Clase
  SINO
  Nota Final:= SUSPENSO

• La nota del examen se guarda para las convocatorias del curso 2001/2002, siempre que sea mayor o igual a 5.

• Las notas de prácticas se guardan para próximas convocatorias (independientemente de la nota obtenida) siempre que no cambie sustancialmente el tipo de las prácticas a realizar.

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

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