O exame individual de prácticas (proba obxectiva) terá lugar no mesmo
día fixado para o exame da materia e poderán establecerse distintos
turnos dependendo do número de estudantes matriculados; é necesario
dispor, previamente, do material de todas as prácticas realizadas ao
longo do curso no portátil de cada estudante, ou ben na
súa conta de usuario.

Presentarse ao exame de prácticas ou ao exame de teoría suporá unha
calificación distinta ao "non presentado" na acta correspondente.

Segundo
o previsto na Norma que regula o réxime de dedicación ao estudo dos
estudantes de Grao da UDC, os estudiantes poderán optar na matrícula por
unha dedicación a tempo parcial e dispensa académica de exención de
asistencia. A súa implantación no ámbito desta materia suporá que, de
forma xeral, a calificación que figurará na acta será a mellor entre a
obtida según o criterio especificado nesta sección da guía docente, e a
obtida únicamente coa proba obxectiva ponderando nun 70% o exame de
teoría e nun 30% o exame de prácticas.

Na 2ª oportunidade o estudante poderá presentarse novamente tanto ao
exame de prácticas como ao exame teórico (partes previstas na proba
obxectiva). De non presentarse a algún deles, conservarase nel a calificación obtida na 1ª oportunidade.

Na
oportunidade adiantada de decembro o 100% da avaliación corresponderá a
un exame específico de teoría que incluirá cuestións relacionadas coas
prácticas.

A
realización fraudulenta das probas ou actividades de avaliación, unha
vez comprobada, implicará directamente a cualificación de suspenso na
convocatoria en que se cometa: o/a estudante será cualificado con
“suspenso” (nota numérica 0) na convocatoria correspondente do curso
académico, tanto se a comisión da falta se produce na primeira
oportunidade como na segunda. Para isto, procederase a modificar a súa
cualificación na acta de primeira oportunidade, se fose necesario.

Resultados de aprendizaxe	Competencias do título
Saber solucionar problemas de diversa natureza, comprendendo a complexidade e idoneidade das solucións propostas.	A1 A5	B2 B5 B7 B9	C3
Coñecer as estratexias algorítmicas básicas para o deseño de algoritmos eficientes.	A1 A5	B5 B6 B7 B8 B9	C3
Saber aplicar algoritmos eficientes a problemas clásicos, como os de ordenación e procura.	A1	B2 B5 B7 B9	C3
Saber determinar a complexidade espacial e temporal dos distintos algoritmos.	A1	B2 B4 B6 B9	C6
Entender e dominar as estruturas de datos tipo grafos e aprender a deseñar e aplicar algoritmos sobre elas, para resolver problemas básicos de IA.	A5	B5 B6 B7 B8 B9	C3
Aprender a deseñar e aplicar algoritmos sobre grafos, para resolver problemas básicos de IA.	A1 A5	B2 B5 B7 B9	C2

Temas	Subtemas
Tema 1 Título do tema: Análise de Algoritmos. Código: T1 Presentación: Neste primeiro tema plantexase a análise da complexidade dos algoritmos como uno dos principais obxectivos do curso. En síntese, tratase de engadir a eficiencia dos algoritmos aos criterios que xa deben resultar familiares, os de estruturación e de correción dos programas.	Unidades de contido: 1. Análise da eficiencia dos algoritmos: Notacións asintóticas, Modelo de computación, Verificación empírica da análise. 2. Cálculo dos tempos de execución: Análise dos casos peor e medio, Cálculo da O, Resolución de recurrencias.
Tema 2 Título do tema: Estruturas de datos. Código: T2 Presentación: Neste segundo tema proponse unha revisión das estruturas de datos básicas (pilas, listas, colas, árbores, conxuntos e grafos) co obxectivo de estudar todas as implicacións do seu uso en canto ás complexidades espacial e temporal. Igualmente afondarase no estudo de estruturas interesantes desde o punto de vista do tempo de execución: as taboas de dispersión e os montículos, estrutura ésta última á que recurrirase máis adiante cando se trate de implementar melloras en algoritmos de grafos e nalgún caso de programación dinámica. A complexidade da operación de procura pode servir como fio condutor en boa parte deste tema. Convén nunha introdución desta parte do curso insistir nos criterios de estruturación que debemos manter no deseño de calquer aplicación, motivando o uso de tipos de datos abstractos e a súa implementación modular. O objectivo é dar así as liñas xerais da que se considera a disciplina de programación que debe esixirse ao estudante para a realización das prácticas.	Unidades de contido: 1. Pilas, colas, listas. 2. Árbores, montículos. 3. Dispersión (hashing). 4. Conxuntos disxuntos. 5. Grafos (representación).
Tema 3 Título do tema: Algoritmos sobre secuencias e conxuntos de datos Código: T3 Presentación: O problema da ordenación dunha secuencia de elementos convértese nesta parte do curso nunha escusa ideal tanto para estudar a complexidade de varios tipos de algoritmos como para presentar diferentes estratexias de deseño de algoritmos que se poden extrapolar para a resolución doutros problemas. Un dos algoritmos que merecen especial atención é á ordenación rápida, dado que permite introducir a característica fundamental dos algoritmos aleatorios, que compórtanse de forma distinta na execución dunha mesma entrada. Unha consecuencia directa é que o calificativo de peor caso ou mellor caso para una entrada concreta deixa de ter sentido, aspecto que é importante debatir en clase.	Unidades de contido: 1. Algoritmos de procura. 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 do tema: Algoritmos voraces Código: T4 Presentación: Neste tema estúdanse algoritmos ávidos ou voraces. Unha vez explicada a técnica a través das súas características xerais que presentaremos coa axuda dalgún exemplo, estudaranse os algoritmos máis representativos desta categoría: os algoritmos de grafos, unha solución ao problema da mochila e algún problema de planificación de tarefas.	Unidades de contido: 1. Problema da mochila. 2. Algoritmos de grafos: Ordenación Topolóxica, Árbore de recubrimiento mínimo, Caminos mínimos. 3. Problemas de planificación de sistemas informáticos.
Tema 5 Título do tema: Deseño de algoritmos por indución Código: T5 Presentación: Neste punto, xa se viron ao longo do curso varios algoritmos que seguen a estratexia divide e vencerás: ordenación por fusión e ordenación rápida, procura dicotómica, suma da subsecuencia máxima. . . O traballo proposto na primeira unidade deste tema consiste básicamente en xeneralizar as formulacións da dita estratexia identificando as súas distintas características en cada un dos algoritmos propostos. Na segunda unidad do tema exponse o uso dunha estratexia ascendente mediante a procura dunha solución xeral a partir das solucións de subproblemas elementais. Desde o punto de vista da eficiencia cuestionarase o uso de técnicas descendentes como divide e vencerás en determinadas situacións. Mentres que coa opción da programación dinámica procurarase un compromiso que permita, cando sexa posible, unha optimización da cantidade de memoria requerida polo algoritmo.	Unidades de contido: 1. Divide e Vencerás. 2. Programación dinámica: Principio de optimalidade, Problema da mochila.
Tema 6 Título do tema: Exploración de grafos. Código: T6 Presentación: O objectivo deste tema é o de dar unha visión máis ampla das aplicacións dos grafos no tratamento de problemas de diversa índole, así como a de non deixar de lado as técnicas algorítmicas ligadas ao desenrolo de importantes áreas da computación como a intelixencia artificial. Os algoritmos de grafos vistos no tema de algoritmos voraces (T4) coinciden en realizar un percorrido de todos os nodos do grafo. Insistirase entón en cómo mellorar os tempos de execución dos algoritmos que se presenten evitando una análise exhaustiva de todos os nodos.	Unidades de contido: 1. Xogos de estratexia. 2. Percorridos. 3. Algoritmos con retroceso, ramificación e poda.
Tema 7 Título do tema: Complexidade Computacional. Código: T7 Presentación: Neste último tema plantexamos un razoamento sobre o conxunto dos algoritmos capaces de resolver cada tipo de problema. Falaremos das complexidades dos problemas, de cotas inferiores para a complexidade dos problemas e de NP-compleción, en definitiva, das principais técnicas e conceptos que se utilizan no estudo da complexidade computacional.	Unidades de contido: 1. NP-Completitud, Problemas NP-completos.

Metodoloxías / probas	Competencias	Horas presenciais	Horas non presenciais / traballo autónomo	Horas totais
Sesión maxistral	A1 A5 B2 B5 B6 B7 B8 B9 C3	28.75	28.75	57.5
Proba de resposta breve	A1 A5 B2 B5 B6 B7 B8 B9 C3	1.25	6.25	7.5
Prácticas de laboratorio	A1 A5 B2 B4 B5 B6 B7 B8 B9 C2 C3 C6	19	19	38
Traballos tutelados	A5 B2 B4 B6 B7 C3 C6	4	2	6
Solución de problemas	A1 B2 B5 B6 B7 B8 B9 C3	5	10	15
Proba obxectiva	A1 A5 B2 B4 B6 B7 B8 B9 C3 C6	4	20	24

Atención personalizada		2	0	2

*Os datos que aparecen na táboa de planificación son de carácter orientativo, considerando a heteroxeneidade do alumnado

Metodoloxías	Descrición
Sesión maxistral	Clases maxistrais na exposición dos coñecementos teóricos utilizando diferentes recursos: a pizarra, transparencias, proxeccións, demostracións e o Campus Virtual. Pode incluir conferencia invitada.
Proba de resposta breve	En xeral consiste na realización de exercicios sobre a execución de casos sobre os algoritmos estudados ou sobre a súa adaptación a outras situacións. Estas probas son avaliadas.
Prácticas de laboratorio	Prácticas deseñadas polo profesor basadas nos coñecementos que o estudiante vai adquirindo nas clases maxistrais e que polo tanto as complementan. Os estudantes desenvolverán estes traballos en grupos de dúas ou tres persoas ao longo do curso, e individualmente nunha práctica final que se inclúe na proba objectiva. Implementaranse programas que ilustren os problemas relacionados co tema. Esixirase o informe de resultados para a súa avaliación. Ao longo das horas asignadas a cada práctica evaluaranse os informes da práctica anterior.
Traballos tutelados	Traballos tutelados propostos polo profesor e desenvoltos polos estudantes ou ben en grupo ou ben individualmente.
Solución de problemas	Desenvolveranse exemplos sobre os coñecementos teóricos relacionados co tema, e resolveranse dúbidas. Avaliarase individualmente a resolución dalgúns problemas.
Proba obxectiva	Avaliarase o dominio dos coñecementos teóricos e operativos da materia. Avaliarase igualmente a práctica individual final.

Metodoloxías	Competencias	Descrición	Cualificación
Proba de resposta breve	A1 A5 B2 B5 B6 B7 B8 B9 C3	Dúas probas de avaliación continua, nas que se avaliará o dominio dos contidos dos traballos académicos a revisar. Realizaranse durante as horas de teoría que se inclúen na planificación inicial da materia presentada ao inicio do curso.	5
Prácticas de laboratorio	A1 A5 B2 B4 B5 B6 B7 B8 B9 C2 C3 C6	4 prácticas realizadas en grupos de dúas ou tres persoas, nas que se avaliará: estruturación dos programas, calidade da documentación, claridade, adecuación e explicación dos resultados. A entrega en tempo e forma das prácticas é condición necesaria para acceder ao exame individual final de prácticas da 1ª oportunidade. A avaliación realízase mediante titorías de seguimento das prácticas, durante as horas de práctica.	15
Solución de problemas	A1 B2 B5 B6 B7 B8 B9 C3	Avaliación de 2 ou 3 traballos nos que se desenvolverán exemplos sobre os coñecementos teóricos relacionados co tema trala resolución de dúbidas. Realizaranse durante as horas de Traballo en Grupo Reducido (TGR) planificadas ao longo do curso, podendo nalgún caso completarse en horas non presenciais.	10
Proba obxectiva	A1 A5 B2 B4 B6 B7 B8 B9 C3 C6	Avaliarase o dominio dos coñecementos teóricos e operativos da materia. Exame individual de teoría: 50% Exame individual de prácticas: 20% Para ser convocada/o ao exame de prácticas da 1ª oportunidade, é necesaria a entrega en prazo das prácticas de laboratorio.	70

Observacións avaliación
O exame individual de prácticas (proba obxectiva) terá lugar no mesmo día fixado para o exame da materia e poderán establecerse distintos turnos dependendo do número de estudantes matriculados; é necesario dispor, previamente, do material de todas as prácticas realizadas ao longo do curso no portátil de cada estudante, ou ben na súa conta de usuario. Presentarse ao exame de prácticas ou ao exame de teoría suporá unha calificación distinta ao "non presentado" na acta correspondente. Segundo o previsto na Norma que regula o réxime de dedicación ao estudo dos estudantes de Grao da UDC, os estudiantes poderán optar na matrícula por unha dedicación a tempo parcial e dispensa académica de exención de asistencia. A súa implantación no ámbito desta materia suporá que, de forma xeral, a calificación que figurará na acta será a mellor entre a obtida según o criterio especificado nesta sección da guía docente, e a obtida únicamente coa proba obxectiva ponderando nun 70% o exame de teoría e nun 30% o exame de prácticas. Na 2ª oportunidade o estudante poderá presentarse novamente tanto ao exame de prácticas como ao exame teórico (partes previstas na proba obxectiva). De non presentarse a algún deles, conservarase nel a calificación obtida na 1ª oportunidade. Na oportunidade adiantada de decembro o 100% da avaliación corresponderá a un exame específico de teoría que incluirá cuestións relacionadas coas prácticas. A realización fraudulenta das probas ou actividades de avaliación, unha vez comprobada, implicará directamente a cualificación de suspenso na convocatoria en que se cometa: o/a estudante será cualificado con “suspenso” (nota numérica 0) na convocatoria correspondente do curso académico, tanto se a comisión da falta se produce na primeira oportunidade como na segunda. Para isto, procederase a modificar a súa cualificación na acta de primeira oportunidade, se fose necesario.

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. Peña Marí (2005). Diseño de Programas. Formalismo y Abstracción. Tercera edición.. Pearson Prentice Hall T. H. Cormen, C. E. Leiserson y R. L. Rivest (1990). Introduction to Algorithms. MIT Press F. Aguado, F. Gago, M. Ladra, G. Pérez, C. Vidal y A. M. Vieites (2018). Problemas resueltos de Combinatoria. Laboratorio con SageMath. Paraninfo R. Sedgewick (1988). Algorithms. Addison Wesley Goodrich, Michael T. (2013). Data structures and algorithms in Python. John Wiley and Sons