Datos Identificativos 2020/21
Asignatura (*) Algoritmos Código 614G01011
Titulación
Grao en Enxeñaría Informática
Descriptores Ciclo Período Curso Tipo Créditos
Grao 1º cuadrimestre
 Segundo Obrigatoria 6
Idioma
Castelán
Inglés
Modalidade docente Híbrida
Prerrequisitos
Departamento Ciencias da Computación e Tecnoloxías da Información
Computación
Coordinación
Valderruten Vidal, Alberto
 Correo electrónico
alberto.valderruten@udc.es
Profesorado
Casanova Crespo, Jose Maria
Fontenla Romero, Oscar
Gómez Rodríguez, Carlos
Hernandez Pereira, Elena Maria
Jorge Castro, Jose Santiago
Valderruten Vidal, Alberto
 Correo electrónico
jose.casanova.crespo@udc.es
oscar.fontenla@udc.es
carlos.gomez@udc.es
elena.hernandez@udc.es
santiago.jorge@udc.es
alberto.valderruten@udc.es
Web http://moodle.udc.es/course/view.php?id=55374
Descrición xeral A materia de Algoritmos permite ao estudante de Enxeñería informática profundizar nas técnicas de deseño dos algoritmos tendo en conta factores cualitativos e cuantitativos na avaliación dos mesmos. Dunha parte completa a formación na elaboración de programas eficientes e correctamente estructurados, e doutra parte permite abordar as técnicas de deseño máis utilizadas na resolución dos problemas que pode encontrar o enxeñeiro.
É de destacar que a realización de experimentos de medición de tempos de execución sobre os distintos algoritmos analizados achega un enfoque empírico que adoita ser moi valorado polo estudante, que pode así constatar a interpretación concreta das complexidades atopadas. As dificultades plantexadas por algúns casos estudados permiten unha reflexión complementaria sobre aspectos como a xestión de recursos informáticos, detalles de execución de procesos, arquitecturas e sistemas operativos utilizados, etc.
Tamén é destacable o estudo e análise dun conxunto importante de algoritmos fundamentais, cubrindo un amplo espectro de técnicas algorítmicas e de as súas aplicacións. A posibilidade de usar distintas técnicas na resolución dalgúns problemas leva naturalmente a pensar nas vantaxes e inconvintes das distintas estratexias, e na necesidade de saber elixir a que mellor se adapta a cada situación.
Por último é importante profundizar no rigor necesario para desenvolver non só solucións que se adapten a unhas especificacións dadas, sino ademáis que o fagan de modo eficiente dende o punto de vista dos recursos informáticos necesarios. Resulta fundamental a ilustración mediante varios casos prácticos nos que a existencia de algoritmos eficientes coñecidos leva a desechar os deseños alternativos por moi naturais que podan resultar a primeira vista.
Plan de continxencia 1. Modificacións nos contidos
Sen cambios

2. Metodoloxías
*Metodoloxías docentes que se manteñen
Traballos tutelados

*Metodoloxías docentes que se modifican
Sesión maxistral: Realizarase de forma non presencial, a través de Teams e/ou de vídeos gravados

Proba de resposta breve: Realizarase de forma non presencial, a través de Teams e Moodle.

Prácticas de laboratorio: Realizarase de forma non presencial, usando Teams. Recomendase unha configuración do portatil con linux, gcc e svn.

Solución de problemas: Realizarase de forma non presencial, usando Teams e Moodle

Proba obxectiva: Realizarase de forma non presencial, usando Teams e Moodle, ademáis da configuración recomendada do portatil con linux, gcc e svn para a parte práctica.

3. Mecanismos de atención personalizada ao alumnado
Correo electrónico: diariamente, para facer consultas.
Moodle: diariamente, para acceder aos materiais de clase, consultar o calendario ou facer uso dos foros.
Teams: durante as horas de teoría, TGR ou práctica previstas no horario da asignatura; titorías en grupo sobre a teoría (2h por semana) e sobre as prácticas (2h por semana); no que respecta ás titorías individuais, fora das horas de clase a atención manténse nos horarios de titorías previa solicitude a través do correo electrónico.


4. Modificacións na avaliación
Todas as probas (avaliación continua e proba obxectiva) son en modalidade non presencial.

*Observacións de avaliación:
Mantense as previsións da guía docente.
Ofrecerase unha data alternativa aos estudantes que tiveran problemas loxísticos no momento das probas.

5. Modificacións da bibliografía ou webgrafía
Sen cambios

Competencias do título
Código Competencias do título
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.
B3 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
Resultados de aprendizaxe Competencias do título
Saber aplicar as técnicas de análise da complexidade dos algoritmos. A12
A13
 B3
Recoñecer a importancia do estudo da complexidade dos algoritmos e saber realizar estudos empíricos para determinala. A12
A13
 B3
 C3
Coñecer as técnicas máis utilizadas no deseño dos algoritmos. A12
 B3
Comprender elementos de estudo sobre a complexidade computacional. A12
A13
 B3
Utilizar diferentes modelos de computación e niveis de abstracción necesarios para o deseño de algoritmos. A12
 B3
Identificar estruturas de datos adaptadas aos algoritmos estudados para obter implementacións máis eficientes e robustas. A13
 B3
 C3

Contidos
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 aos criterios que xa deben resultar familiares, os de estruturación e de correción dos programas, o da eficiencia dos algoritmos. 		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 profundarase 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 recurriremos 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 nuna 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 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 unidad 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.
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 principales técnicas e conceptos que se utilizan no estudo da complexidade computacional. 		Unidades de contido:
1. NP-Completitud, Problemas NP-completos

Planificación
Metodoloxías / probas Competencias Horas presenciais Horas non presenciais / traballo autónomo Horas totais
Sesión maxistral A13 A12 B3 28.75 28.75 57.5
Proba de resposta breve A12 A13 B3 1.25 6.25 7.5
Prácticas de laboratorio A12 A13 B3 C3 19 19 38
Traballos tutelados A12 A13 B3 C3 4 2 6
Solución de problemas A12 A13 B3 5 10 15
Proba obxectiva A12 A13 B3 C3 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
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 a facultade 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 parellas 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 el 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.

Atención personalizada
Metodoloxías
Traballos tutelados
Prácticas de laboratorio
Solución de problemas
Descrición
Clases de problemas en grupos reducidos: desenvolveranse exemplos sobre os coñecementos teóricos relacionados co tema, e resolveranse dúbidas.
Traballos tutelados ben individuais ben en grupo sobre algún aspecto do tema a estudar. Son controlados por parte do profesor mediante tutorías en grupo e controles de avaliación.
Prácticas de aula de informática: implementaranse programas que ilustren os problemas relacionados co tema. Pedirase o informe de resultados para a súa avaliación.
No que respecta ás titorías individuais, fora das horas de clase a atención manténse nos horarios oficiales de titorías a través dos seguintes canles:
- Correo electrónico, para facer consultas de resposta curta.
- Teams: encontros virtuais preferentemente previa solicitude a través do correo electrónico.



Avaliación
Metodoloxías Competencias Descrición Cualificación
Proba de resposta breve A12 A13 B3 2 probas escritas 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. 		10
Proba obxectiva A12 A13 B3 C3 Avaliarase o dominio dos coñecementos teóricos e operativos da materia.

Exame individual de teoría (2h): 40%
Exame individual de prácticas (2h): 20%

Para ser convocada/o ao exame de prácticas da 1ª oportunidade, é necesaria a entrega en prazo das prácticas de laboratorio. 		60
Prácticas de laboratorio A12 A13 B3 C3 4 prácticas realizadas en parellas, 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 A12 A13 B3 Avaliación de 3 traballos nos que desenvolveranse 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. 		15
 
Observacións avaliación
<p> Na 2ª oportunidade o estudante poderá presentarse novamente tanto ao exame de prácticas como ao exame teórico (partes previstas na proba obxectiva).</p><p>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 na
conta de usuario de cada estudante.</p><p>Presentarse ao exame de prácticas ou ao exame de teoría suporá unha
calificación distinta ao "non presentado" na acta correspondente.</p><p>Según 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 por unha dedicación a tempo parcial. 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.</p><p>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. </p>

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
F. Aguado, F. Gago, M. Ladra, G. Pérez, C. Vidal y A. M. Vieites (2018). Problemas resueltos de Combinatoria. Laboratorio con SageMath. Paraninfo


Recomendacións
Materias que se recomenda ter cursado previamente
Matemática Discreta/614G01004
Programación II/614G01006

Materias que se recomenda cursar simultaneamente
Paradigmas de Programación/614G01014

Materias que continúan o temario
Concorrencia e Paralelismo/614G01018
Sistemas Intelixentes/614G01020

Observacións


(*)A Guía docente é o documento onde se visualiza a proposta académica da UDC. Este documento é público e non se pode modificar, salvo casos excepcionais baixo a revisión do órgano competente dacordo coa normativa vixente que establece o proceso de elaboración de guías