Después de un curso de iniciación a la programación es conveniente estudiar las estructuras de datos y algoritmos básicos que permiten solucionar, de manera eficiente, problemas computacionales típicos. La mejora en el hardware es muy considerable pero no es suficiente para resolver, por sí sola, los requerimientos de las aplicaciones actuales. Es más, los avances del hardware se muestran más fructíferos cuando se utilizan para procesar algoritmos eficientes y, sin embargo, se muestran casi irrelevantes si los algoritmos utilizados para resolver un problema no son los adecuados.



La investigación en estructuras de datos y algoritmos ha sido constante en el tiempo. Esa investigación ha establecido un cuerpo considerable de conocimiento cuyos fundamentos debe estudiar cualquier persona bien formada en computación. El dominio de este conocimiento permite valorar la adecuación de soluciones algorítmicas existentes y, si es pertinente, el desarrollo de otras soluciones más adecuadas que mejoren el consumo de recursos (especialmente el tiempo de ejecución de los programas).



Esta asignatura es una iniciación al estudio de las estructuras de datos y algoritmos, que abre las puertas a cursos más avanzados, en los grados de Ingeniería Informática y de Inteligencia Artificial, y que pondrá al estudiante en condiciones de progresar posteriormente en el dominio de esta materia.

Resultados del aprendizaje

1. Conocer y aplicar correctamente los conceptos fundamentales de estructuras de datos y algoritmos para la resolución de problemas habituales en informática.

2. Ser capaz diseñar algoritmos de complejidad media y plasmarlos en un programa informático, usando cuando proceda las primitivas del lenguaje adecuadas, incluyendo la orientación a objetos.

3 Saber implementar en un lenguaje de programación los algoritmos y las estructuras de datos más adecuadas para hacer efectiva la solución a los problemas abordados. Saber identificar las fuentes de ineficiencia en un programa.

4. Conocer y utilizar, entre otros, algoritmos de acceso, inserción y ordenación para las estructuras de datos utilizadas. Utilizar adecuadamente el diseño recursivo en la solución de problemas.

5. Saber evaluar el coste en tiempo y memoria de las soluciones propuestas y desarrolladas por el propio alumno/a. Utilizar con destreza alguna de las herramientas y entornos de desarrollo de software.

Tema 1: Análisis de algoritmos.

1.1. Notación asintótica. Función de coste.

1.2. Comparación de las funciones de coste.

Tema 2: Estructuras lineales. Implementaciones y características.

2.1. Listas

2.2. Pilas y Colas

2.3. Iteradores.

2.4. Ordenación y búsqueda.

Tema 3: Diseño recursivo.

3.1. Recursión en el diseño de programas.

3.2. Ordenación y búsqueda mediante recursión.

Tema 4. Árboles.

4.1. Estructuras no lineales.

4.2. Diseño recursivo en árboles.

4.3. Árboles binarios de búsqueda.

4.4. Otros tipos de árboles.

Tema 5: Hashing. Tablas Hash y Maps. Características.

Tema 6: Grafos. Algoritmos de recorridos de grafos.

6.1. Definiciones. Grafos dirigidos y no dirigidos.

6.2. Recorridos de grafos.

La asignatura se imparte mediante actividades presenciales y no presenciales.



Las actividades presenciales tendrán la forma de clases magistrales y de sesiones de elaboración y discusión de soluciones para los ejercicios propuestos. Se basará en la asistencia sistemática a las clases, la resolución de los ejercicios propuestos y la participación tanto en las sesiones magistrales como en las sesiones de discusión.

Algunas sesiones presenciales se dedicarán a la implementación, en el laboratorio, de programas que resuelvan problemas propuestos.



Las actividades no presenciales consistirán en el estudio de los algoritmos y las técnicas presentadas en clase y en la realización de ejercicios prácticos de diseño e implementación de soluciones algorítmicas a los problemas propuestos. Los y las estudiantes deben ser capaces de trabajar de manera autónoma con el material de las clases y con las referencias que se proporcionen.

• Sistema de Evaluación Continua
• Sistema de Evaluación Final
• Herramientas y porcentajes de calificación:
  • Prueba escrita a desarrollar (%): 70
  • Realización de prácticas (ejercicios, casos o problemas) (%): 30

Cada estudiante puede optar por una de las dos modalidades de evaluación de la asignatura:

(1) Evaluación continua.

(2) Evaluación final (o de conjunto).



A continuación se describe cada una de esas dos opciones.



(1) Evaluación continua (sobre 10 puntos).



La calificación de la asignatura se obtendrá sumando las calificaciones obtenidas mediante:

(a) trabajos de programación (3 puntos como máximo), y

(b) exámenes individuales (7 puntos como máximo).



En cada uno de los dos apartados (a) y (b) se deberá obtener, al menos, un 50% del máximo.



De cara a la evaluación, el temario se considera dividido en tres bloques, que serán evaluados mediante tres o dos exámenes individuales con un peso de 25%-25%-20% ó 50%-20%, respectivamente. Las fechas de realización de esos exámenes serán los días asignados a la asignatura en las semanas de horario especial y el día publicado por la Junta de Facultad para la primera convocatoria de evaluación final de la asignatura. La calificación final de los exámenes individuales será la suma de esos exámenes intermedios.



Los trabajos de programación consistirán en ejercicios de implementación individual y/o grupal que se realizarán durante todas las semanas del curso.



Quien opta por la evaluación continua se compromete a asistir sistemáticamente a las clases magistrales y de laboratorio, y a entregar los ejercicios propuestos en el plazo establecido. En caso contrario podrá quedar excluido/a de la evaluación continua. Habrá una preinscripción al principio del curso. Esta decisión pasará a ser definitiva en las fechas que se establezcan (hacia la semana 11), tras la verificación del rendimiento parcial por parte del profesor/a. Si el/la alumno/a desea cambiarse a la modalidad de Evaluación Final deberá renunciar expresamente a la modalidad de Evaluación Continua.



(2) Evaluación Final (o de Conjunto) (sobre 10 puntos).



La evaluación final consistirá en un examen escrito y una práctica de programación.

(a) La práctica de programación supondrá el 30% de la calificación total de la asignatura (3 puntos sobre 10). Para aprobar la asignatura será necesario obtener, como mínimo, la mitad (es decir, 1,5 puntos).

(b) El examen escrito, sobre los contenidos de la asignatura, supondrá el 70% de la calificación total de la asignatura (7 puntos sobre 10). Para aprobar la asignatura será necesario obtener, como mínimo, la mitad (es decir, 3,5 puntos).



Se entenderá que el/la estudiante renuncia a la convocatoria de Evaluación Final (o de Conjunto) si no se presenta a las pruebas de evaluación citadas.



Durante el desarrollo de las pruebas de evaluación quedará prohibida la utilización de libros, notas o apuntes, así como de aparatos o dispositivos telefónicos, electrónicos, informáticos, o de otro tipo, por parte del alumnado, salvo que expresamente se indique lo contrario.

La convocatoria extraordinaria se evaluará de la misma manera que la Evaluación Final (o de Conjunto) explicada en el punto anterior.

- Plataforma eGela.
- Entorno de programación Eclipse.
- Lenguaje de programación Java.

Bibliografía básica

- "Java software structures: designing and using data structures" (Fourth edition). John

Lewis, Joseph Chase. Addison Wesley (2014).

- "Algorithms" (4th edition). Robert Sedgewick and Kevin Wayne. Addison Wesley (2011).

- "Data Structures and Problem Solving Using Java" (Fourth edition) Mark A. Weiss. Pearson (2010).

Bibliografía de profundización

- "Introduction to Algorithms" (3rd edition) Cormen, Leiserson, Rivest & Stein. MIT press (2009).
- "Data Structures and Algorithm Analysis in Java" (Third edition). Mark Allen Weiss. Pearson (2012).

Direcciones web

- Algorithms, 4th edition (R. Sedgewick):
http://algs4.cs.princeton.edu
- Dictionary of Algorithms and Data Structures:
http://xlinux.nist.gov/dads/
- JavaTM Platform, Standard Edition 6, API Specification:
http://download.oracle.com/javase/6/docs/api/overview-summary.html
- Eclipse.org
http://www.eclipse.org/