Guía DocenteCurso
Facultade de Informática
  Inicio | galego | castellano | english | A A A |  
Grao en Enxeñaría Informática
 Asignaturas
  Algoritmos
   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
Universidade da Coruña - Rúa Maestranza 9, 15001 A Coruña - Tel. +34 981 16 70 00  Soporte Guías Docentes