1- Reconoce situaciones en las que se puede reutilizar el repertorio de estructuras de datos y algoritmos clásicos

2- Aplica con criterio las técnicas básicas de análisis de eficiencia y diseño de algoritmos.

3- Analiza críticamente y con suficiente precisión distintas soluciones algorítmicas, para clasificarlas y optar por la más conveniente.

4- Diseña justificadamente soluciones algorítmicas eficientes de problemas propios de este nivel académico.

1. Análisis de eficiencia de algoritmos

1.1 Conceptos básicos del análisis de algoritmos

1.2 Análisis del coste algorítmico: caso peor, mejor y medio

1.3 Notaciones asintóticas y su uso en las clasificaciones funciones.

1.4 Resolución de recurrencias

1.5 Ejemplos: algoritmos básicos de búsqueda, ordenación y recursión

1.6 Resolución de problemas



2. Estructuras de Datos Avanzadas

2.1 Grafo

2.2 Montículo

2.3 Partición



3. Algoritmos sobre grafos

3.1 Definición de la técnica de diseño de algoritmos

3.2 Presentación de algoritmos clásicos que utilizan la técnica y resolución de otros problemas: Conectividad, Caminos mínimos, etc.



4. Divide y Vencerás

4.1 Definición de la técnica de diseño de algoritmos

4.2 Presentación de algoritmos clásicos que utilizan la técnica y resolución de otros problemas: Ordenación por mezcla, Ordenación rápida, selección del k-ésimo, etc.



5. Programación Dinámica

5.1 Definición de la técnica de diseño de algoritmos

5.2 Presentación de algoritmos clásicos que utilizan la técnica y resolución de otros problemas: devolución de cambio mínimo, mochila 0/1, etc.



6. Backtrack

6.1 Definición de la técnica de diseño de algoritmos

6.2 Presentación de algoritmos clásicos que utilizan la técnica y resolución de otros problemas: Mochila, coloreado de mapas, monedas, etc.





7. Voraz

7.1. Definición de la técnica de diseño de algoritmos

7.2 Presentación de algoritmos clásicos que utilizan la técnica y resolución de otros problemas: selección de acciones, mochila con fracciones de objetos, árboles de recubrimiento mínimo, etc.

En esta asignatura se utilizan diversas metodologías de enseñanza. Se potenciará el trabajo autónomo, mediante el uso de recursos informáticos y bibliográficos que ayuden al alumnado a comprender los distintos aspectos de la materia.



Se impartirán clases de exposición (M) de los contenidos conceptuales de la materia, con participación del alumnado en debates ocasionales sobre los mismos. La resolución de cuestiones y problemas en el aula se realizará de forma participativa. Se proporcionarán problemas y ejercicios que desarrollarán individualmente o en grupo (GL), lo que permitirá profundizar en el conocimiento teórico de la materia y relacionar la asignatura con otras áreas afines.



El alumnado realizará diferentes pruebas que se puntuarán a lo largo del curso, (desarrollo y presentación de ejercicios y resolución de parciales) y algunos alumnos seleccionados podrán realizar implementaciones como complemento opcional.



Para materializar los resultados de aprendizaje el alumnado tendrá que desarrollar, escribir y presentar diferentes ejercicios en seminarios (clases prácticas en aula y laboratorio). El cuarto resultado de aprendizaje se evaluará principalmente a través de las pruebas parciales.



Dada la importancia de documentar adecuadamente la aplicación de las distintas técnicas, se proporcionará un “modelo de documentación” de obligado cumplimiento, accesible en el curso eGela de la asignatura. Para la implementación el alumnado podrá utilizar el lenguaje de programación que el desee (C, Java, Python, ...).



A lo largo del curso se realizarán diferentes pruebas de forma colaborativa y parciales que se deben hacerse de forma individual.

La asignatura tiene dos opciones de evaluación: la evaluación continua y la evaluación final (o de conjunto).



La EVALUACIÓN CONTINUA, a la que el alumnado podrá acogerse voluntariamente, se oferta exclusivamente a los y las estudiantes que puedan realizar el seguimiento continuo de la asignatura en el marco establecido de dedicación y asistencia a las actividades presenciales.



La preinscripción en el modo de evaluación continua será automática, y se producirá como consecuencia de haber realizado alguna actividad evaluada. El alumnado que desee renunciar a la evaluación continua deberá hacerlo explícitamente por escrito antes del segundo parcial.



Las diferentes actividades para la evaluación continua, con sus pesos correspondientes, serán las siguientes:



(1) realización de actividades de forma colaborativa (resolución de problemas en seminarios, generación de preguntas tipo test, implementaciones, etc.): 50%.



(2) exámenes parciales: 50%. Se realizarán dos pruebas individuales para la evaluación de los conocimientos y destrezas del alumnado en las semanas de horario agrupado. Cada una de ellas valdrá un 25% de la nota final de la asignatura. Para poder superar la asignatura será necesario obtener una nota mínima de 2,5 sobre 10 en cada examen parcial. En caso de no alcanzar la nota mínima en alguno de los parciales, habiéndose presentado a ambos parciales, no se sumarán a la nota final el resto de actividades evaluables. En caso de no presentarse a alguno de los dos parciales, o bien no habiendo alcanzado la nota mínima en el primero, implicará abandonar la evaluación continua pasando a evaluación final.



Las rúbricas para el desarrollo de problemas y las técnicas de diseño están disponibles en el curso eGela de la asignatura, así como las fechas de todas las actividades destacables.



La EVALUACIÓN FINAL (o de conjunto) consistirá en una prueba escrita para medir su conocimiento del 100% de los contenidos de la asignatura donde el alumnado deberá mostrar conocimientos y destrezas. Las fechas concretas de las pruebas están disponibles en la eGela asociada la asignatura y en el portal web de la facultad. La no presentación a la prueba escrita de la evaluación final se considerará como renuncia a la evaluación.

El material disponible en la eGela de la asignatura.

Bibliografía básica

- Dasgupta, S., Papadimitriou, C. H., and Vazirani, U. V.: "Algorithms", McGraw-Hill Education, (2006), Isbn: 978-0-07-352340-8



- Arruabarrena, R., and Bermúdez, J.: "66 problemas resueltos de Análisis y Diseño de Algoritmos", (1999), http://hdl.handle.net/10810/42192

Bibliografía de profundización

- Cormen T.H, Leiserson C.E,, Rivest R.L. y Stein C: "Introduction to Algorithms", (4th edition), The MIT Press, (2022), Isbn: 978-0-262-04630-5

- Brassard, G. and Bratley; P.: "Fundamentals of algorithmics". Prentice Hall, (1996), Isbn: 978-0-13-335068-5

- Levitin, A.: "Introduction to The Design and Analysis of Algorithms". 3rd edition. Pearson International Edition, (2012), Isbn: 978-0-13-231681-1

- Kleinberg, J. and Tardos, E.: "Algorithm Design", 1st Edition, Pearson New International Edition, (2013), Isbn: 978-1292023946