| Competencias do título |
| Código | Competencias da titulación |
| A12 | Coñecemento e aplicación dos procedementos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e a complexidade dos algoritmos propostos. |
| A13 | Coñecemento, deseño e utilización de forma eficiente dos tipos e estruturas de datos máis adecuados á resolución dun problema. |
| B7 | Asumir como profesional e cidadán a importancia da aprendizaxe ao longo da vida. |
| B11 | Capacidade de análise e síntese |
| C3 | Utilizar as ferramentas básicas das tecnoloxías da información e as comunicacións (TIC) necesarias para o exercicio da súa profesión e para a aprendizaxe ao longo da súa vida. |
| Resultados de aprendizaxe | |||
| Competencias de materia (Resultados de aprendizaxe) | Competencias da titulación | ||
| Reconocer la importancia del estudio de la complejidad de los algoritmos y saber realizar estudios empíricos para determinarla. | A12 A13 |
B7 B11 |
C3 |
| Conocer los conceptos básicos relacionados con las técnicas de análisis de la complejidad de los algoritmos. | A12 |
B11 |
|
| Identi ficar estructuras de datos adaptadas a los algoritmos estudiados para obtener implementaciones más efi cientes y robustas. | A13 |
B11 |
C3 |
| Saber aplicar las técnicas de análisis de la complejidad de los algoritmos. | A12 A13 |
B7 B11 |
|
| Conocer las técnicas más utilizadas en el diseño de los algoritmos. | A12 |
B11 |
|
| Utilizar diferentes modelos de computación y niveles de abstracción necesarios para el diseño de algoritmos. | A12 |
B11 |
|
| Comprender elementos de estudio sobre la complejidad computacional. | A12 A13 |
B11 |
|
| Efectuar estudios empíricos para determinar la complejidad de un algoritmo. | A12 A13 |
B11 |
C3 |
| Mostrar interés sobre el análisis de los algoritmos. | A12 |
B7 B11 |
|
| Contidos |
| Temas | Subtemas |
| Tema 1 Título del tema: Análisis de Algoritmos. Código: T1 Presentación: En este primer tema se plantea el análisis de la complejidad de los algoritmos como uno de los principales objetivos del curso. En síntesis, se trata de añadir a los criterios que ya deben resultar familiares de estructuración y de corrección de los programas el de la efi ciencia de los algoritmos. |
Unidades de contenido: 1. Análisis de la efi ciencia de los algoritmos: Notaciones asintóticas, Modelo de computación, Verifi cación empírica del análisis. 2. Cálculo de los tiempos de ejecución: Análisis de los casos peor y medio, Cálculo de la O, Resolución de recurrencias. |
| Tema 2 Título del tema: Estructuras de datos. Código: T2 Presentación: En este segundo tema se propone una revisión de las estructuras de datos básicas (pilas, listas, colas, árboles, conjuntos y grafos) con el objetivo de estudiar todas las implicaciones que conlleva su uso en cuanto a las complejidades espacial y temporal. Igualmente se profundiza en el estudio de estructuras interesantes desde el punto de vista del tiempo de ejecución: las tablas de dispersión y los montículos, estructura ésta última a la que recurriremos más adelante cuando se trate de implementar mejoras en algoritmos de grafos y algún caso de programación dinámica. La complejidad de la operación de búsqueda puede servir como hilo conductor en buena parte de este tema. Conviene en una introducción de esta parte del curso el insistir en los criterios de estructuración que debemos mantener en el diseño de cualquier aplicación, motivando el uso de tipos de datos abstractos y su consiguiente implementación mediante módulos. El objetivo es dar así las líneas generales de lo que se considera la disciplina de programación que debe exigirse al estudiante para la realización de las prácticas. |
Unidades de contenido: 1. Pilas, colas, listas. 2. Árboles, montículos. 3. Dispersión (hashing). 4. Conjuntos disjuntos. 5. Grafos (representación). |
| Tema 3 Título del tema: Algoritmos sobre secuencias y conjuntos de datos Código: T3 Presentación: El problema de la ordenación de una secuencia de elementos se convierte en esta parte del curso en una excusa ideal tanto para estudiar la complejidad de varios tipos de algoritmos como para presentar diferentes estrategias de diseño de algoritmos que se pueden extrapolar para la resolución de otros problemas. Uno de los algoritmos a los que se le dedicará especial atención es la ordenación rápida, ya que permite introducir la característica fundamental de los algoritmos aleatorios que se pueden comportar de forma distinta cuando se aplican dos veces a una misma entrada. Una consecuencia directa es que el cali ficativo de peor caso o mejor caso para una entrada deja de tener sentido, aspecto que es importante debatir en clase. |
Unidades de contenido: 1. Algoritmos de búsqueda. 2. Algoritmos de ordenación: Inserción, Shell, Montículos (heapsort), Fusión (mergesort), Ordenación Rápida (quicksort). 3. Algoritmos aleatorios. |
| Tema 4 Título del tema: Algoritmos voraces Código: T4 Presentación: En este tema se estudian algoritmos ávidos o voraces. Una vez explicada la técnica a través de sus características generales que presentaremos con la ayuda de algún ejemplo, se estudiarán los algoritmos más representativos de esta categoría: los algoritmos de grafos, una solución al problema de la mochila y algún problema de plani ficación de tareas. |
Unidades de contenido: 1. Problema de la mochila. 2. Algoritmos de grafos: Ordenación Topológica, Árbol de recubrimiento mínimo, Caminos mínimos. 3. Problemas de plani ficación de sistemas informáticos. |
| Tema 5 Título del tema: Diseño de algoritmos por inducción Código: T5 Presentación: En este punto, ya se habrá visto a lo largo del curso varios algoritmos que siguen la estrategia divide y vencerás: ordenación por fusión y ordenación rápida, búsqueda dicotómica, suma de la subsecuencia máxima. . . El trabajo propuesto en la primera unidad de este tema consiste básicamente en generalizar los planteamientos de dicha estrategia identifi cando sus distintas características en cada uno de los algoritmos propuestos. En la segunda unidad del tema se plantea usar una estrategia ascendente mediante la búsqueda de una solución general a partir de las soluciones de subproblemas elementales. Desde el punto de vista de la efi ciencia se cuestionará el uso de técnicas descendentes como divide y vencerás en determinadas situaciones. Mientras que con la opción de la programación dinámica se buscará un compromiso que permita, cuando sea posible, una optimización de la cantidad de memoria requerida por el algoritmo. |
Unidades de contenido: 1. Divide y Vencerás. 2. Programación dinámica: Principio de optimalidad, Problema de la mochila. |
| Tema 6 Título del tema: Exploración de grafos. Código: T6 Presentación: El objetivo de este tema es el de dar una visión más amplia de las aplicaciones de los grafos en el tratamiento de problemas de diversa índole, así como la de no dejar de lado las técnicas algorítmicas ligadas al desarrollo de importantes áreas de la computación como la inteligencia arti cial. Los algoritmos de grafos vistos en el tema de algoritmos voraces (T4) coinciden en realizar un recorrido de todos los nodos del grafo. Se insistirá entonces en cómo mejorar los tiempos de ejecución de los algoritmos que se presenten evitando de alguna manera el análisis exhaustivo de todos los nodos. |
Unidades de contenido: 1. Juegos de estrategia. 2. Recorridos. 3. Algoritmos con retroceso. |
| Tema 7 Título del tema: Complejidad Computacional. Código: T7 Presentación: En este último tema planteamos un razonamiento sobre el conjunto de los algoritmos capaces de resolver cada tipo de problema. Hablaremos de las complejidades de los problemas, de cotas inferiores para la complejidad de los problemas y de NP-compleción, en defi nitiva, de las principales técnicas y conceptos que se utilizan en el estudio de la complejidad computacional. |
Unidades de contenido: 1. NP-Completitud, Problemas NP-completos |
| Planificación | |||
| Metodoloxías / probas | Horas presenciais | Horas non presenciais / traballo autónomo | Horas totais |
| Sesión maxistral | 28.75 | 28.75 | 57.5 |
| Proba de resposta breve | 1.25 | 5.25 | 6.5 |
| Prácticas de laboratorio | 20 | 10 | 30 |
| Traballos tutelados | 4 | 10 | 14 |
| Solución de problemas | 6 | 12 | 18 |
| Proba obxectiva | 4 | 20 | 24 |
| Atención personalizada | 0 | 0 | 0 |
| *Os datos que aparecen na táboa de planificación son de carácter orientativo, considerando a heteroxeneidade do alumnado | |||
| Metodoloxías |
| Metodoloxías | Descrición |
| Sesión maxistral | Clases magistrales en la exposición de los conocimientos teóricos utilizando diferentes recursos: la pizarra, transparencias, proyecciones, demostraciones y la facultad virtual. Puede incluir conferencia invitada. |
| Proba de resposta breve | En general consiste en la realización de trabajos tutelados que son evaluados. |
| Prácticas de laboratorio | Prácticas diseñadas por el profesor basadas en los conocimientos que el estudiante va adquiriendo. Los estudiantes desarrollarán estos trabajos bien individualmente bien en parejas. Se implementarán programas que ilustren los problemas relacionados con el tema. Se pedirá el informe de resultados para su evaluación. Se evaluará de forma continua los informes de la práctica anterior. Se evaluará igualmente mediante una práctica individual final. |
| Traballos tutelados | Trabajos tutelados propuestos por el profesor y desarrollados por los estudiantes o bien en grupo o bien individualmente. |
| Solución de problemas | Se desarrollarán ejemplos sobre los conocimientos teóricos relacionados con el tema, y se resolverán dudas. Incluye evaluación. |
| Proba obxectiva | Se evaluará el dominio de los conocimientos teóricos y operativos de la materia. |
| Atención personalizada |
|
|
| Avaliación | ||
| Metodoloxías | Descrición | Cualificación |
| Proba de resposta breve | 3 pruebas escritas de evaluación continua, en las que se evaluará el dominio de los contenidos de los trabajos académicos a revisar. Se realizarán durante las horas de teoría y se anunciarán con al menos 7 días de antelación. |
15 |
| Prácticas de laboratorio | 4 prácticas realizadas en parejas o de forma individual, en las que se evaluará: estructuración de los programas, calidad de la documentación, claridad, adecuación y explicación de los resultados, responsabilidad en la entrega en tiempo y forma. Tutorías de seguimiento de las prácticas, durante las horas de práctica: 10% Examen individual de prácticas: 20% |
30 |
| Solución de problemas | Se desarrollarán ejemplos sobre los conocimientos teóricos relacionados con el tema, y se resolverán dudas. Incluye evaluación de 3 trabajos. Se realizarán durante las horas de Trabajo en Grupo Reducido (Seminarios). |
15 |
| Proba obxectiva | Se evaluará el dominio de los conocimientos teóricos y operativos de la materia. | 40 |
| Observacións avaliación | ||
|
En la 1ª oportunidad, las prácticas de laboratorio se evaluarán durante las tutorías de seguimiento que se realizarán en el horario de prácticas. Esta evaluación continua supondrá 1/3 parte de la evaluación de las prácticas. El examen de prácticas tendrá lugar tras la finalización de la prueba objetiva, en el mismo día del examen teórico; es muy recomendable disponer, previamente, del material de todas las prácticas en la Presentarse a pruebas que supongan el 20% de la evaluación de la asignatura supondrá una calificación distinta al "no presentado" en el acta correspondiente. |
||
| Fontes de información |
| Bibliografía básica |
M. A. Weiss (1995). Estructuras de Datos y Algoritmos. Addison Wesley
G. Brassard y P. Bratley (1997). Fundamentos de Algoritmia. Prentice Hall
U. Manber (1989). Introduction to Algorithms - A Creative Approach. Addison Wesley |
|
|
|
| Bibliografía complementaria |
R. Sedgewick (1988). Algorithms. Addison Wesley
R. Peña Marí (2005). Diseño de Programas. Formalismo y Abstracción. Tercera edición.. Pearson Prentice Hall
B. W. Kernighan y D. M. Ritchie (1991). El lenguaje de programación C, 2ª edición. Prentice Hall
T. H. Cormen, C. E. Leiserson y R. L. Rivest (1990). Introduction to Algorithms. MIT Press |
|
|
| Recomendacións | ||
| Materias que se recomenda ter cursado previamente | ||
|
| Materias que se recomenda cursar simultaneamente |
| Materias que continúan o temario | ||
|
| Observacións | |