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.
Al finalizar el curso los participantes podrá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.
| 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.
| 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.
| 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.
| 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.
| 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.
(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.
| 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
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 |
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
La Carrera de Ingeniería de Sistemas y Computación plantea los siguientes objetivos educacionales, El estudiante graduado de la carrera será capaz de:
| 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 | |||||
| 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 % |
No está permitido el uso de material en los exámenes, ni el uso de computadores personales ni teléfonos celulares.
Es obligatoria.
Salón de clase con computador y proyector. Laboratorio de Ingeniería de Sistemas y Computación.