Source: http://cic.javerianacali.edu.co/wiki/doku.php?id=materias:arbolesgrafos
Timestamp: 2018-12-16 23:08:41+00:00

Document:
DECC Wiki [materias:arbolesgrafos]
Traza: • arbolesgrafos
Pre-requisitos: Técnicas y Prácticas de Programación, Estructuras de Datos, Álgebra Lineal
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.
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.
Desarrollo de programas usando el lenguaje de programación.
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]
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]
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]
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]
Capítulo 3: Extensiones de búsqueda en grafos
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]
10-13 8 Tareas semanales, resolución de problemas en temas vistos [1 cap 22][2 cap 3][7 cap 4][4 cap 10]
Capítulo 4: Tipos abstractos y estructuras de datos arborescentes y jerárquicas
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.
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]
Capítulo 5: Algorítmos de optimización
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]
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]
Capítulo 6: Temas seleccionados
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]
29-32 8 Tareas semanales, resolución de problemas en temas vistos [6 caps 8,9][4 caps 11,12]
Relevancia 4 0 5 0 0 4 0 0 4 1 3
(I) Uso de herramientas y técnicas (I1) Utilizar herramientas de desarrollo de software. (Aplicación). (I2) Utilizar herramientas de diseño, modelamiento y simulación. (Aplicación). (I3) Combinar herramientas de software y hardware para resolver un problema. (Síntesis). (I4) Demostrar flexibilidad para adaptarse a diferentes paradigmas y lenguajes de programación. (Valuación). Todos Ejercicios de demostración, presentación oral y escrita de talleres Exámenes y proyecto
Lectura crítica E E E E
Parcial 1	 20 % 20 % 23 % 20 % 20 % 5 % 12 %
Parcial 2	 20 % 20 % 23 % 20 % 20 % 5 % 12 %
Examen final	 20 % 20 % 23 % 20 % 20 % 5 % 12 %
Proyecto 1 10 % 25 % 23 % 15 % 20 % 5 % 12 %
Proyecto 2 10 % 25 % 23 % 15 % 20 % 5 % 12 %
Talleres y quices 20 % 10 % 23 % 30 % 20 % 5 % 12 %
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. Third Edition. MIT, July, 2009.
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
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.
materias/arbolesgrafos.txt · Última modificación: 2016/09/02 12:03 por camilo.rocha

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución