Nombre de la materia
Análisis y diseño de algoritmos avanzados Disciplina
Tecnologías Computacionales Nivel académico general
Profesional Intermedio - Enfoque Tipo de materia especifica
Curricular (Obligatoria) Tecnica didáctica
No especificado Tipo de periodo
Semestral Tipo horario
Teórico Escuela
Ingeniería y Ciencias Departamento
Computación Intención
Es un curso de nivel intermedio en tecnologías computacionales, con enfoque en estructuras de datos y algoritmos avanzados, tomando en cuenta el análisis de complejidad. Requiere conocimientos previos de estructura de datos y análisis de algoritmos fundamentales.Como resultado del aprendizaje, el alumno propone soluciones eficientes utilizando técnicas de diseño de algoritmos avanzados sobre manejo de cadenas de caracteres, grafos, geometría computacional y búsqueda avanzada. Objetivo general
Al terminar la unidad de formación el alumno:- Implementa algoritmos computacionales que solucionan problemas.- Optimiza algoritmos computacionales que se aplican en el desarrollo de soluciones.- Aplica los principios de sustentabilidad en la solución de problemas computacionales y tecnologías de información que garanticen el bienestar de las generaciones futuras. Temas
1. Técnicas de diseño de algoritmos.1.1 Divide y vencerás.1.2 Programación dinámica.1.3 Algoritmos avaros.1.4 Backtracking.1.5 Ramificación y poda. 2. Manejo de Strings.2.1 KMP.2.2 Z function.2.3 Manacher (palíndromo más largo).2.4 Hash strings.2.5 Suffix Array.2.6 Longest Common Substring. 3. Grafos.3.1 Trie.3.2 Ruta de cobertura mínima en un grafo direccionado acíclico.3.3 Algoritmo de Dijkstra para el camino más corto.3.4 Algoritmo de Floyd para encontrar el camino más corto.3.5 Algoritmo de la mochila.3.6 Algoritmo del viajero.3.7 Algoritmo de Prim para encontrar el árbol de mínima extensión.3.8 Algoritmo de Kruskal para encontrar el árbol de mínima extensión.3.9 Algoritmo de ABB óptimo de Gilbert and Moore.3.10 Algoritmo de coloreo de grafos.3.11 Algoritmo de flujo máximo en un grafo. 4. Geometría computacional.4.1 Proximidad e intersección.4.2 Diagramas de Voronoi y triangulación de Delaunay.4.3 Búsqueda geométrica.4.4 Arreglos de hiperplanos.4.5 Cascos convexos, politopos y computación.4.6 Algoritmos aleatorizados. 5. Técnicas de búsqueda avanzada.5.1 Algoritmos fundamentales.5.2 Backtracking con Bitmask.5.3 Backtracking con poda pesada.5.4 Encontrarse en el medio (meet in the middle).5.5 Búsqueda A* e IDA*.5.6 Algoritmos de mejora iterativa.5.7 Búsqueda de escalada (hill-climbing).5.8 Recocido simulado (simulated annealing). Metodologia de la enseñanza
Actividades de aprendizaje conducidas por un académico (Aprendizaje Supervisado):1. Revisión y análisis conceptual conducido por el docente para abordar los temas relacionados con técnicas de diseño de algoritmos, manejo de strings, grafos, geometría computacional y técnicas de búsqueda avanzada.2. Discusiones y resolución de situaciones relacionadas a través de la aplicación de la técnica didáctica de aprendizaje colaborativo, orientado a abordar los conocimientos sobre técnicas de diseño de algoritmos, manejo de strings, grafos, geometría computacional y técnicas de búsqueda avanzada para aportar al desarrollo de competencias del curso.3. Sesiones de asesoría individuales y grupales orientadas a apoyar el desarrollo de competencias. Actividades de aprendizaje independiente (Aprendizaje Individual):1. Investigación individual y en equipo sobre técnicas de diseño de algoritmos, manejo de strings, grafos, geometría computacional y técnicas de búsqueda avanzada.2. Solución de ejercicios, problemas y casos, tanto de manera individual como colaborativa, para desarrollar la capacidad de implementar algoritmos computacionales que solucionan problemas y optimizar algoritmos computacionales que se aplican en el desarrollo de soluciones.3. Generación de programas, repositorios y análisis e implementaciones de algoritmos como evidencias del desarrollo de las competencias asociadas a la materia. Se recomienda que se implemente al menos un programa de cada uno de los temas del analítico. Tiempo estimado
Tema 1 9 horasTema 2 9 horasTema 3 14 horasTema 4 12 horasTema 5 12 horasEvaluación 4 horas Total 60 horas Politica de evaluacion
Para la evaluación del aprendizaje de los estudiantes se usarán procedimientos y criterios que permiten evaluar los resultados del proceso de aprendizaje en su desempeño. Los procedimientos de evaluación y la ponderación de cada uno de ellos son los siguientes: 20% --- Exámenes parciales teórico acumulativos. Se evalúa la comprensión y aplicación de conceptos relacionados con abstracción de datos, manejo de memoria, recursión.30% --- Exámenes parciales prácticos acumulativos. Se evalúa la comprensión y aplicación de conceptos relacionados con recursión, análisis de complejidad, algoritmos de búsqueda y de ordenamiento estructuras de datos lineales y no lineales.20% --- Actividades de programación (laboratorios).5% --- Actividades escritas.25% --- Examen final. Perfil del profesor
(110701)Maestría en Ciencias Computacionales ; (110102)Maestría en Inteligencia Artificial /Robótica ; (110103)Maestría en Tecnología de la Información/Informática/Sistemas Computacionales ; (110201)Maestría en Programación/Programador Computacional ; (110101)Maestría en Ciencias Computacionales/de Información ; (140901)Maestría en Ingeniería Computacional ; (141301)Maestría en Ciencias de la Ingeniería ; (270301)Maestría en Matemáticas Aplicadas ; (270303)Maestría en Matemáticas Computacionales ; (110701)Doctorado en Ciencias Computacionales ; (110102)Doctorado en Inteligencia Artificial /Robótica ; (110103)Doctorado en Tecnología de la Información/Informática/Sistemas Computacionales ; (110201)Doctorado en Programación/Programador Computacional ; (110101)Doctorado en Ciencias Computacionales/de Información ; (140901)Doctorado en Ingeniería Computacional ; (141301)Doctorado en Ciencias de la Ingeniería ; (270301)Doctorado en Matemáticas Aplicadas ; (270303)Doctorado en Matemáticas Computacionales Requisitos
Haber Cursado TC2037 o Estar Cursando TC2037 Equivalencias
TC2043 Bibliografia
9702601428, Algoritmos computacionales : introducción al análisis y diseño, Baase, S.; & Van Gelder, A., Pearson Educación, 3a, Mexico, 2002| 0262033844, Introduction to algorithms, Cormen, T. H.; Leiserson, Ch. E.; Rivest, R. L., MIT Press, 3rd., Cambridge, Mass., 2009| 9780132316811, Introduction to the design & analysis of algorithms, Levitin, A., Pearson, 3rd., Boston, 2012 Atributos
Materia Modelo Tec21 Competencias
SEG0502B, SICT0101C, SICT0401C, STC0101B, STC0102B Créditos
3.00
