1895 - ALGORITMOS Y ESTRUCTURAS DE DATOS I

Grupos 1, 2 y 3

Año 2011/2012
Curso Segundo
Grado en Ingeniería Informática
Universidad de Murcia

AVISOS | APUNTES | PRACTICAS | RETOS | EVALUACION | CONVALIDACIONES | BIBLIOGRAFIA


AVISOS PARA LOS ALUMNOS

- Atención: los avisos de la asignatura se darán a través del Aula Virtual SAKAI. Nos obstante, para la comunicación directa con el profesor usar el email: ginesgm@um.es

- 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 2010/2011, usa esta página. Si es relativa a las convocatorias anteriores, usa esta página.


APUNTES
Las transparencias en formato PPT se pueden visualizar con PowerPoint 2003 o posterior.

Tema 0. Introducción.
 

Tema 1. Abstracciones y especificaciones.
Capítulo 1 y secciones 2.1 y 2.2 del texto guía: PDF
Sección 2.4 del texto guía: PDF
Transparencias: PDF, PowerPoint97
Ejercicios: PDF, Word97 (transparencias de Maude)
Actividad del tema: Ejercicios en Mooshak (Maude 1 para Linux)

Tema 2. Conjuntos y diccionarios.
Sección 3.3 del texto guía: PDF
Transparencias: PDF, PowerPoint97
Ejercicios: PDF, Word97
Actividad del tema: Examen parcial la semana del 21 de noviembre


Tema 3. Representación de conjuntos mediante árboles.
Sección 4.4 del texto guía: PDF
Transparencias: PDF, PowerPoint97
Ejercicios: PDF, Word97
Actividad del tema: 
Examen parcial la semana del 21 de noviembre

Tema 4. Grafos.
Sección 5.6.3 y sección 5.8 del texto guía: PDF
Transparencias: PDF, PowerPoint97
Ejercicios: PDF, Word97
Actividad del tema: Ejercicios en Mooshak



PRÁCTICAS

Profesores de prácticas:

  • Subgrupos 1.1, 1.3, 2.1 y 2.3: Mercedes Balsa Sobejano (mbalsa@um.es)

  • Subgrupo 1.2: Ginés García Mateos (ginesgm@um.es)

  • Subgrupo 2.2: Juan Antonio López Quesada (juanlop@um.es)
  • Subgrupos 3.1, 3.2 y 3.2: Emiliano Salinas Bermúdez (msalinas@um.es)

Indicaciones:

 


RETOS

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 a los alumnos que superen el reto. El reto se debe hacer individualmente.
Fecha: Este reto estará abierto hasta el 10 de enero del 2012.
Evaluación:
Los alumnos que consigan bajar de coste 22000, tendrán un +0,5 en la nota final de la asignatura, tras la entrega de la memoria y la correspondiente entrevista. Además, el alumno ganador (el que consiga el mejor ciclo) tendrá un 10 en la actividad de evaluación continua del tema de grafos.

 

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 como máximo.
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", para tamaños entre 6 y 10, 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 +0.5 en la nota final de la asignatura.



EVALUACIÓN

  • La Nota Final será un promedio entre la Nota Total de Prácticas y la Nota Total de Teoría. La Nota Total de Prácticas contará un 35% y la de Teoría un 65%. Ambas partes deben estar aprobadas por separado.

  • La Nota Final podrá incrementarse con la superación de los retos y actividades de carácter optativo (notas adicionales) (ver sección Retos).

  • La Nota Total de Prácticas corresponde a la práctica que se realizará relacionada con los temas 2 y 3 de la asignatura.

  • En cuanto a la Nota Total de Teoría, los alumnos pueden elegir entre dos alternativas de evaluación de la parte teórica:

  • Evaluación continua: para cada tema se irán proponiendo una serie de actividades (ejercicios, entrega de resúmenes, exámenes parciales, etc.).

    • Los alumnos que superen una actividad, tendrán superado el tema correspondiente.

    • Los alumnos que hayan superado todos los temas, no tendrán que hacer el examen final de la asignatura.

    • Los alumnos que superen sólo algunos temas, tendrán que hacer los temas no superados en el examen final, debiendo aprobar todas las preguntas por separado con un mínimo de un 4 sobre 10. Además, la parte realizada del examen debe tener como mínimo un 5.

    • Para optar a este sistema de evaluación, se requiere una asistencia de al menos el 80% de las clases, y la entrega de todos los resúmenes que se pidan. En otro caso, no se convalidará ningún tema.

  • Evaluación con examen final: se recomienda evitar esta forma de evaluación e intentar seguir el método de evaluación continua.

    • Habrá, al menos, una pregunta por cada tema.

    • Se requerirá que todas las preguntas del examen estén aprobadas por separado con un mínimo de un 4 sobre 10.

    • En este sistema no se requiere la asistencia a clase ni la entrega de resúmenes.

  • La Nota Total de Teoría será la media de las notas de cada uno de los 4 temas de teoría, es decir, todos los temas tienen la misma ponderación.

  • La Nota Total de Teoría se guarda para convocatorias posteriores si es mayor o igual que 5 sobre 10. También se guardan las actividades de evaluación continua que estén aprobadas para las convocatorias de Junio y Septiembre del mismo año, pero no para años posteriores.


CONVALIDACIONES (alumnos de años anteriores)

Información para los alumnos de las antiguas Ingeniería en Informática e Ingenierías Técnicas en Informática:

  • Básicamente, la asignatura "Algoritmos y Estructuras de Datos I" (AED1) del Grado, corresponde al primer parcial de "Algoritmos y Estructuras de Datos" (AED) de las antiguas ingenierías en informática (superior y técnicas).

  • Los alumnos que tuvieran aprobado el primer parcial de teoría de AED, tienen convalidada la teoría de AED1.

  • Los alumnos que tuvieran superado el requisito de evaluación continua (asistencia clases y entrega de resúmenes) no necesitan repetirlo en este curso (si su profesor era distinto de el de este curso, que avisen para que se tenga en cuenta).
  • Los alumnos que tuvieran aprobada la práctica 1 de AED, tienen convalidada la práctica de AED1.
  • No se guardan las actividades de evaluación continua de años anteriores.


BIBLIOGRAFÍA

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.
  • Dictionary of Algorithms and Data Structures: http://www.nist.gov/dads/
  • Algorithm Animations: http://math.ucsd.edu/~fan/math188/bonus/park/top5.html
  • 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 (sólo Firefox): http://uva.onlinejudge.org


  •  

    Facultad de Informática. Despacho 2.34.
    Campus de Espinardo. Universidad de Murcia.
    30100 Murcia (SPAIN)
    Teléfono: +34 868 88 85 30
    Fax: +34 868 88 41 51
    E-mail: ginesgm@um.es