Ingeniería en Sistemas de Información

Algoritmos y Complejidad

DATOS GENERALES

Código MCSO134
Pénsum 2020B
Horas semanales 18
Tipo Obligatoria
Asignaturas pre-requisitos Ninguna
Asignaturas co-requisitos Ninguna
Unidad de organización curricular Unidad de Formación Disciplinar Avanzada

RESULTADOS DE APRENDIZAJE

De conocimiento
 Comprender las características de eficiencia y aplicabilidad de diversas estrategias algorítmicas básicas para determinar un abordaje adecuado que permita resolver un problema de manera óptima.
De destrezas Evaluar algoritmos (complejidad computacional, aplicabilidad y otros factores) para implementarlos en un contexto específico.
De valores y actitudes Actuar con ética, objetividad y rigurosidad científica en el diseño y evaluación de algoritmos, valorando la optimización de recursos.

CONTENIDO

Capítulo 1 Algunos problemas representativos
  1. Problema del emparejamiento estable;
  2. Calendarización de intervalos;
  3. Emparejamiento bipartito;
  4. Conjunto independiente, y
  5. Locación competitiva.
Capítulo 2 Fundamentos de análisis de algoritmos
  1. Trazabilidad computacional;
  2. Orden de crecimiento asintótico;
  3. Problema del emparejamiento estable con listas y arreglos;
  4. Evaluación de tiempos de ejecución típicos, y
  5. Colas de prioridades.
Capítulo 3

Grafos
  1. Definiciones y aplicaciones;
  2. Conectividad y búsqueda;
  3. Implementando grafos en colas y pilas;
  4. Conectividad en grafos dirigidos, y
  5. Grafos acíclicos dirigidos y ordenamiento topológico.
Capítulo 4 Algoritmos voraces
  1. Calendarización de intervalos;
  2. Calendarización para minimizar atrasos;
  3. Caché óptimo;
  4. Camino más corto;
  5. Algoritmo de Kruskal;
  6. Clustering, y
  7. Compresión de la información.
Capítulo 5 División y conquista
  1. Algoritmo de ordenamiento por mezcla (merge sort);
  2. Relaciones de recurrencia;
  3. Conteo de inversiones;
  4. Encontrar los puntos más cercanos;
  5. Multiplicación de enteros, y
  6. Convoluciones y la transformada rápida de Fourier.
Capítulo 6 Programación Dinámica
  1. Calendarización ponderada de intervalos;
  2. Principios de programación dinámica;
  3. Mínimos cuadrados segmentados;
  4. Programación dinámica en intervalos;
  5. Alineamiento de secuencias;
  6. Alineamiento de secuencias en espacios lineales usando división y conquista;
  7. Caminos más cortos en un grafo;
  8. Caminos más cortos y protocolos vector-distancia, y
  9. Ciclos negativos en un grafo.

Back to top