Información Básica
-
Créditos: 3
-
Horas de trabajo acompañado: 5 / semana (3 horas de clase, 2 de taller)
-
Horas de trabajo independiente: 4 / semana
-
Pre-requisitos: Técnicas y Prácticas de Programación, Estructuras de Datos, Álgebra Lineal
-
Tipo de curso: Núcleo de Formación Fundamental
Descripción del Curso
Este curso se exploran las propiedades de árboles y grafos como: (i) elementos computacionales generales para representar situaciones prácticas y con alto contenido algorítmico, y (ii) de sus posibles realizaciones como estructuras de datos y de su utilización en algoritmos eficientes. Sobre los árboles y grafos se estudian problemas y algoritmos clásicos de búsqueda y optimización. Como estructuras de datos arborescentes y jerárquicas (i.e., no lineales) se estudian, entre otros, montones, árboles binarios de búsqueda, árboles de segmentos. También se estudian conceptos y exploran técnicas para escalar algoritmos sobre árboles y grafos para resolver problemas en redes sociales en las cuales hay grandes cantidades de información.
Objetivos
Al finalizar el curso los participantes podrán:
-
Conocer las representaciones y operaciones principales de los árboles y grafos.
-
Implementar y evaluar algoritmos de búsqueda, rutas maś cortas, cadenas y pattern matching.
-
Implementar, identificando sus ventajas, estructuras de datos arborescentes y jerárquicas como montones, árboles rojo-negro y árboles de segmentos.
-
Modelar problemas reales cona grafos (e.g., redes sociales, optimización industrial).
-
Conocer técnicas de programación paralela para solucionar problemas con estructuras de datos arborescentes y jerárquicas.
Se desarrollan competencias en
-
Modelado de problemas por medio de estructuras de datos.
-
Desarrollo de programas usando el lenguaje de programación.
-
Aplicación de técnicas y herramientas de lenguajes de programación de alto nivel.
-
Implementación de software con buenas prácticas de programación.
Contenido
Capítulo 1: Introducción
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 1-2 | 3 | 2 | Introducción y repaso. Inducción matemática. Diseño algorítmico. Notación asintótica. | Uso | [1 caps 1,2] [2 cap 2][3 cap 0, app 1] |
| 3-4 | 3 | 2 | Dividir, conquistar y combinar. Relación con inducción matemática. | Evaluación | [1 cap 4][2 cap 5][3 cap 1] |
Total de Horas: 10.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 1-4 | 8 | Tareas semanales, resolución de problemas en temas vistos | [1,cap 1,2,4][2 cap 2,5][3 caps 0,1, app 1] |
Total de Horas: 8.
Capítulo 2: Conceptos básicos
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 5-7 | 5 | 2.5 | Grafos. Ejemplos y usos. Tipos de grafos. Nociones básicas. Representación de grafos. Algoritmos de búsqueda y recorrido. | Evaluación | [1 cap 22][2 cap 3][3 cap 8][6 cap 2][9 cap 12] |
| 8-9 | 3 | 2 | Árboles. Ejemplos y usos. Representación de árboles. Búsqueda y recorrido. Inducción sobre árboles. | Evaluación | [6 cap 5][4 cap 5][1 cap 6][8 cap 3] |
Total de Horas: 12.5.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 5-9 | 10 | Tareas semanales, resolución de problemas en temas vistos | [1 cap 6,22][2 cap 3][3 cap 8][4 cap 5][6 caps 2,5][9 cap 12][8 cap 3] |
Total de Horas: 10.
Capítulo 3: Extensiones de búsqueda en grafos
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 10-13 | 6 | 4 | Flood fill. Orden topológico. Puentes y puntos de articulación. Componentes fuertemente conexos. | Evaluación | [1 cap 22][2 cap 3][7 cap 4][4 cap 10] |
Total de Horas: 10.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 10-13 | 8 | Tareas semanales, resolución de problemas en temas vistos | [1 cap 22][2 cap 3][7 cap 4][4 cap 10] |
Total de Horas: 8.
Capítulo 4: Tipos abstractos y estructuras de datos arborescentes y jerárquicas
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 14-15 | 3 | 2 | Montones: montones binarios, montones binomiales, montones de Fibonacci, montones de emparejamiento. Colas de prioridad. | Evaluación | [1 caps 6,19][8 cap 7][9 cap 10] |
| 16 | 1.5 | 1 | Clases de equivalencia: Bosques/conjuntos disyuntos. | Evaluación | [1 cap 21][3 cap 17][7 cap 2] |
| 17-18 | 3 | 2 | Árboles binarios de búsqueda: Árboles rojo-negro. | Uso | [1 caps 12,13][8 cap 10][9 cap 6] |
| 19-20 | 3 | 2 | Rangos: árboles de segmentos, árboles de Fenwick. | Evaluación | [7 cap 2] |
| 21-22 | 3 | 2 | Procesamiento de texto: arreglos de sufijos, autómatas. | Evaluación | [1 cap 32][3 cap 13][10 cap 4][7 cap 6] |
Total de Horas: 22.5.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 14-22 | 18 | Tareas semanales, resolución de problemas en temas vistos | [1 caps 6,12,13,19,21,32][3 caps 13,17][7 caps 2,6][8 caps 7,10][9 caps 6,10][10 cap 4] |
Total de Horas: 18.
Capítulo 5: Algorítmos de optimización
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 23-24 | 3 | 2 | Distancia mínima de un vértice a todos los demás (SSSP): el algoritmo de Dijkstra, el algoritmo de Bellman-Ford-Moore. | Evaluación | [1 cap 24][2 cap 4][3 cap 21] |
| 25-26 | 3 | 2 | Distancia mínima entre cualquier par de vértices (ASSP): el algoritmo de Floyd-Warshall-Rho | Evaluación | [1 cap 25][3 cap 22] |
| 27-28 | 3 | 2 | Árboles mínimos de cubrimiento (MST): el algoritmo de Kruskal, el algoritmo de Prim. | Evaluación | [1 cap 23][3 cap 20] |
Total de Horas: 15.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 23-28 | 12 | Tareas semanales, resolución de problemas en temas vistos | [1 caps 23,24,25][2 cap 4][3 caps 20,21,22] |
Total de Horas: 12.
Capítulo 6: Temas seleccionados
| Sesión | Horas teóricas | Prácticas acompañadas | Temas | Profundidad | Bibliografía |
|---|---|---|---|---|---|
| 29-32 | 6 | 4 | Redes de computador modernas. Redes sociales. Planaridad y colorabilidad. Paralelización de algoritmos de grafos. | Uso | [6 caps 8,9][4 caps 11,12] |
Total de Horas: 15.
| Sesión | Horas de trabajo independiente | Temas | Bibliografía |
|---|---|---|---|
| 29-32 | 8 | Tareas semanales, resolución de problemas en temas vistos | [6 caps 8,9][4 caps 11,12] |
Total de Horas: 8.
Bibliografía
-
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. Third Edition. MIT, July, 2009.
-
J. Kleinberg, É. Tardos. Algorithm Design. Pearson, 2005.
-
J. Erickson. Algorithms. Urbana, USA, 2015. Available online: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/
-
W. Kocay and D. Kreher. Graphs, Algorithms, and Optimization. Chapman and Hall/CRC. 2004.
-
S. Even, G. Even. Graph Algorithms. Second Edition. Cambridge University Press, 2012.
-
M. van Steen. Graph Theory and Complex Networks: An Introduction. 2010. Available online: http://pages.di.unipi.it/ricci/book-watermarked.pdf
-
S. Halim, F. Halim. Competitive Programming 3: The new lower bound of programming contests. Lulu, 2013.
-
D. Mehta, S. Sahni. Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.
-
P. Morin. Open Data Structures: An Introduction”. Available online: http://opendatastructures.org/
-
M. Crochemore, C. Hancart, T. Lecroq. Algorithms on Strings. Cambridge University Press, 2014.
Instalaciones
Salón de clase con computador y proyector. Laboratorio de Ingeniería de Sistemas y Computación.