Árboles y Grafos

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.

Integración Curricular

Resultados de Programa (ABET)

(A) La habilidad para aplicar conocimientos de matemáticas, ciencias e ingeniería.

(B) La habilidad para analizar un problema e identificar los requerimientos necesarios para su definición y solución.

(C) La habilidad para diseñar, implementar y evaluar procesos y sistemas computacionales.

(D) La habilidad para funcionar en equipos de trabajo.

(E) El entendimiento de la responsabilidad profesional y ética.

(F) La habilidad para comunicarse efectivamente.

(G) La habilidad para analizar los impactos de la computación y la ingeniería en las personas, organizaciones y la sociedad.

(H) El reconocimiento de la necesidad de, y la habilidad para, continuar con el desarrollo profesional.

(I) La habilidad para usar las técnicas, destrezas y herramientas modernas para la práctica de la computación.

(J) La habilidad para aplicar los fundamentos y principios de las matemáticas y de la computación en el modelamiento y diseño de sistemas computacionales de manera que se demuestre comprensión de las ventajas y desventajas en las decisiones de diseño.

(K) La habilidad para aplicar los principios de diseño y desarrollo de software en la construcción de sistemas de diferente complejidad.

Relevancia del curso con los resultados de programa

Resultados de Programa
a b c d e f g h i j k
Relevancia 4 0 5 0 0 4 0 0 4 1 3

(1) baja relevancia - (5) alta relevancia

Integración de objetivos, contenido y metodología del curso

El curso es presencial y con participación y trabajo en clase. Se asigna trabajos, ejercicios y lecturas. Durante la sesión se expondrán los conceptos acompañados de ejemplos, se fomentará la participación de los estudiantes. Se realizan talleres semanal o bisemanales en los cuales se aplican los fundamentos teóricos.

Resultados del Programa Indicadores de Desempeño Objetivos/Contenido del Curso Actividades de aprendizaje Instrumentos de medición
(A) Aplicación de Conocimientos (A1) Identificar los fundamentos científicos y los principios de ingeniería que rigen un proceso o sistema. (Conocimiento) (A2) Resolver problemas relacionados con la disciplina y otras áreas por medio de la utilización de conocimientos, modelos y formalismos de las ciencias de la computación, las matemáticas y la ingeniería. (Aplicación) (A4) Interpretar modelos matemáticos para estimar su precisión y confiabilidad. (Comprensión) Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(C) Diseño (C1) Utilizar estándares de codificación en la implementación de componentes de software. (Aplicación). (C2) Identificar componentes, interacciones, relaciones e interfaces entre componentes. (Análisis). (C3) Diseñar procesos y componentes de software haciendo uso de la notación, técnicas y herramientas adecuadas. (Síntesis). (C4) Evaluar un componente de software de acuerdo a su complejidad temporal y espacial. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(F) Comunicación efectiva (F2) Comunicarse de manera efectiva de acuerdo al público objetivo haciendo uso correcto del lenguaje, estilo, tiempo y expresión corporal. (Aplicación). (F4) Defender ideas con precisión y claridad. (Evaluación). Todos Ejercicios de demostración, presentación oral y escrita de talleres Exámenes y proyecto
(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
(J) Modelamiento y diseño de sistemas computacionales (J1) Reconocer la importancia del modelamiento cuando se resuelve un problema. (Compresión). (J2) Relacionar conceptos y principios teóricos para la resolución efectiva de un problema. (Síntesis). (J4) Evaluar decisiones de diseño basándose en principios matemáticos y de computación. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto
(K) Desarrollo de software (K3) Establecer invariantes y propiedades de componentes de software. (Análisis). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto

Contribución al Desarrollo de Competencias (CNA)

La tabla muestra que aspectos de las competencias de Comunicación Escrita, Lectura Crítica y Razonamiento Cuantitativo son evaluados a través de los factores ABET correspondientes. Por otra parte, la competencias de Inglés se favorece gracias a la metodología del curso y también, gracias al factor ABET correspondientes.

Resultados de Programa
A B C D E F G H I J K
Comunicación escrita E E E E E E
Lectura crítica E E E E
Inglés U U U U U U
Razonamiento cuantitativo E E E E E E

E- Se evalúa. U - Se usa

Contribución a los objetivos educacionales

La Carrera de Ingeniería de Sistemas y Computación plantea los siguientes objetivos educacionales, El estudiante graduado de la carrera será capaz de:

  1. Ejercitar la práctica de la Ingeniería de Sistemas y Computación profesionalmente.
  2. Diseñar y operar sistemas de computación que contribuyen a la solución de problemas relacionados a la disciplina, otra área de la ciencia y la ingeniería u otras disciplinas.
  3. Contribuir al bienestar de las comunidades desde posiciones prominentes en la industria, academia, sector público o como un emprendedor.
  4. Ser distinguido por su bases sólidas en computación, su sentido de ciudadanía responsable, su profesionalismo y liderazgo.
  5. Continuar su desarrollo profesional o involucrarse en estudios de posgrado.
Resultados de Programa
A B C D E F G H I J K
Objetivo 1 X X X X X
Objetivo 2 X X X X X X
Objetivo 3 X
Objetivo 4 X X X X X
Objetivo 5 X X X X X X

Recomendaciones del Director del Programa

Reglas del curso

Calificación y Balance de Evaluación del Curso

Instrumento Porcentaje A B C D E F G H I J K
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 %

Uso de material en exámenes

No está permitido el uso de material en los exámenes, ni el uso de computadores personales ni teléfonos celulares.

Asistencia

Es obligatoria.

Bibliografía

  1. T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. Third Edition. MIT, July, 2009.
  2. J. Kleinberg, É. Tardos. Algorithm Design. Pearson, 2005.
  3. J. Erickson. Algorithms. Urbana, USA, 2015. Available online: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/
  4. W. Kocay and D. Kreher. Graphs, Algorithms, and Optimization. Chapman and Hall/CRC. 2004.
  5. S. Even, G. Even. Graph Algorithms. Second Edition. Cambridge University Press, 2012.
  6. M. van Steen. Graph Theory and Complex Networks: An Introduction. 2010. Available online: http://pages.di.unipi.it/ricci/book-watermarked.pdf
  7. S. Halim, F. Halim. Competitive Programming 3: The new lower bound of programming contests. Lulu, 2013.
  8. D. Mehta, S. Sahni. Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.
  9. P. Morin. Open Data Structures: An Introduction”. Available online: http://opendatastructures.org/
  10. 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.

Material de este semestre

 
materias/arbolesgrafos.txt · Última modificación: 2016/09/02 12:03 por camilo.rocha
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki