Descripción del Curso

Justificación

Aunque la capacidad de procesamiento y almacenamiento de los computadores sigue aumentando, también es cierto que los volúmenes de datos y la complejidad de las tareas asignadas a estos es cada vez mayor. Adicionalmente, desde mucho antes de la aparición del computador se han estudiado cientos de problemas de gran aplicación práctica, para los cuales no se conocen procesos algorítmicos eficientes ni se cree que aparezcan en el futuro.

El ingeniero de sistemas debe estar en capacidad de estimar matemáticamente la complejidad computacional de los problemas a los que se enfrenta en su actividad profesional y además, debe ser capaz de proponer, evaluar y elegir acertadamente soluciones para esos de problemas, siendo consciente de antemano, del desempeño que tendrán una vez estén implantadas.


Objetivo

El objetivo del curso es estudiar los principios fundamentales de la solución de problemas a través de algoritmos computacionales. El curso se divide en dos partes principales: el análisis de algoritmos y el diseño de algoritmos eficientes. En la primera parte se estudian las herramientas matemáticas que permiten caracterizar el desempeño de un algoritmo en términos del uso que hace de los recursos computacionales, principalmente tiempo y memoria. En la segunda parte se estudian diversos tipos de problemas y técnicas para resolverlos de manera eficiente.

Contenido


 Tema          Material y Recursos
1. Introducción
1.1 Nociones básicas (algoritmo, programa, problema, instancia, operación básica)
1.2 Análisis de algoritmos
1.3 Diseño de algoritmos
1.4 Complejidad computacional
[Cormen09] Cap 1, Cap 2
[OCW2005] Lect. 1 (video y notas de clase)
Recursos de Python
[OCW2008] Python cost model
[Harel04] Cap 7 (pdf)
2. Análisis de Algoritmos
2.1 Notación asintótica
2.2 Dividir y conquistar
2.3 Recurrencias
2.4 Sustitución
2.5 Método maestro
[Cormen09] Cap 3, Cap 4
[OCW2005] Lect. 2 (video y notas de clase)
3. Algoritmos de Ordenamiento
3.1 Colas de prioridades
3.2 Heapsort
3.3 Quicksort
3.4 Ordenamiento en tiempo lineal
[Cormen09] Cap 6, Cap 7, Cap 8
[OCW2005] Lect. 4 (video y notas de clase)
[OCW2005] Lect. 5 (video y notas de clase)
4. Estructuras de Datos
4.1 Repaso de estructuras básicas
4.2 Tablas hash
4.3 Binary search trees
4.4 Vectores dinámicos y análisis amortizado
[Cormen09] Cap 10, 11, 12, 13, 17
[OCW2005] Lect. 7 (video y notas de clase)
[OCW2005] Lect. 8 (video y notas de clase)
[OCW2005] Lect. 9 (video y notas de clase)
[OCW2005] Lect. 10 (video y notas de clase)
[OCW2005] Lect. 13 (video y notas de clase)
5. Programación Dinámica
5.1 Funciones con memoria
5.2 Corte de la vara
5.3 Multiplicación de matrices
5.4 Secuencia común más larga
[Cormen09] Cap 15
[OCW2005] Lect. 15 (video y notas de clase)
Ejercicios de repaso de Programación Dinámica
6. Algoritmos en Grafos
6.1 Representación de grafos
6.2 Búsquedas sobre grafos
6.3 Arbol de expansion mínimo
6.4 Camino más corto
[Cormen09] Cap 22, 23, 24 
[OCW2005] Lect. 16 (video y notas de clase)
[OCW2005] Lect. 17 (video y notas de clase)


Programa 


Semana
Tema
Entregas
4 de Febrero
(1.1) Presentación general del curso y de nociones básicas.
(1.2 y 1.3) Diseño y Análisis de Algoritmos.

11 de Febrero
(1.4) Complejidad computacional.
(2.1) Notación Asintótica.

18 de Febrero    
(2.2) Dividir y Conquistar.
(2.3) Recurrencias.

25 de Febrero
(2.4) Método de sustitución.
Introducción a Python (Laboratorio).

4 de Marzo
(2.4) Método basado en un árbol de recursión.
(2.5) Método maestro.

11 de Marzo
(3.1) Colas de prioridades.
(3.2) Algoritmo HeapSort.
Primer Examen Parcial


18 de Marzo
(3.3) Algoritmo QuickSort.
(3.4) Ordenamiento en tiempo lineal.

1 de Abril    
(4.1) Estructuras básicas.
8 de Abril
(4.2) Tablas hash.
15 de Abril
(4.3) Árboles de búsqueda binaria.
22 de Abril (4.3) Árboles rojo-negro.
(4.4) Vectores dinámicos y análisis amortizado.
 
29 de Abril
(5.1) Funciones con memoria.
(5.2) Secuencia común más larga.

6 de Mayo
(5.3) Multiplicación de matrices.
Segundo Examen Parcial
 
13 de Mayo
(6.1) Representación de grafos.
(6.2) Búsquedas sobre grafos.

20 de Mayo
(6.3) Árbol de expansión mínimo.
(6.4) Camino más corto (camino simple).

27 de Mayo
(6.4) Camino más corto (todas las parejas).
Tercer Examen Parcial


Metodología

Al final de cada clase, el profesor asigna a los estudiantes lecturas sobre los temas que se verán la siguiente clase. Durante la siguiente clase, el profesor hace quizzes orales o escritos a algunos estudiantes sobre dichas lecturas (ver sección Lecturas Asignadas). En las horas de clase el profesor presenta los temas de curso y los estudiantes desarrollan talleres y resuelven problemas representativos de cada tema. De forma paralela a la discusión de los temas en clase, los estudiantes hacen ejercicios escritos y de programación en los que se aplicarán y criticarán los conceptos y técnicas estudiadas. Periódicamente se efectúan pruebas escritas, con el propósito de tener información gradual y oportuna de los logros y dificultades del grupo en cada unidad del curso.

El texto guía del curso es [Cormen09].

Evaluación


La calificación final se obtiene según la siguiente distribución de porcentajes:

    PARCIALES (72%)

  • Primer parcial: 24% 
  • Segundo parcial: 24%
  • Tercer parcial: 24%

    TALLERES (21%)

  • Primer taller: 7 % 
  • Segundo taller: 7%
  • Tercer taller: 7%
  • Los talleres se entregan en determinada fecha. La siguiente clase, uno o más de los integrantes del grupo puede ser llamado a sustentación de cualquiera de los puntos. Si la sustentación de una persona no es exitosa, se les puede bajar hasta 1.5 de la nota de talleres a todos los integrantes del grupo. Esta penalidad es acumulable.

    PARTICIPACIÓN (7%)

  • En esta nota se dejará la nota más alta entre el promedio de los parciales y las evaluaciones orales que se harán durante el semestre. Dichas evaluaciones pueden ser preguntas realizadas por el profesor o participación voluntaria.
Importante:
  • Cualquier forma de plagio en alguno de los items anteriores, implica la anulación de la nota de dicho item para todas las partes implicadas.
  • Para cualquier falla, quiz, examen o cualquier nota se debe informar al profesor lo más pronto posible por correo o en persona. A más tardar, 5 días hábiles después de la falla.
  • Cualquier reclamo sobre cualquier nota/falla debe hacerse en lo posible en la siguiente clase (o antes). Después de dos clases ya no se tendrán en cuenta los reclamos. Por eso deben estar pendientes de revisar la notas las cuales son actualizadas todas las clases (ver al final de la página).

Lecturas Asignadas


Fecha de Control de Lectura
Lecturas
7 de Febrero
 [Harel04] Cap 7 (pdf): Pags 159-173 (8 primeras páginas)
11 de Febrero[Harel04] Cap 7 (pdf) (12 primeras páginas)
13 de Febrero[Harel04] Cap 7 (pdf) (17 primeras páginas)
19 de Febrero[Cormen09] Chapter 2
21 de Marzo
[Cormen09] Chapter 2
 2 de Abril
[Cormen09] Section 2.3 & Chapter 3




























Talleres

  • Prueba Diagnóstica (Ver al final de la página)


Bibliografía

  • [Cormen09] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. 2009 Introduction to Algorithms. 3rd. McGraw-Hill Higher Education
  • [Skiena03] Skiena, S. S. and Revilla, M. A. 2003. Programming challenges: the programming contest training manual. Springer-Verlag.
  • [Harel04] Harel D, Feldman Y. Algorithmics: The Spirit of Computing (3rd Edition). Addison Wesley; 2004.
  • [Goodrich02] MT Goodrich, R Tamassia. 2002. Algorithm design: foundations, analysis, and Internet examples. Wiley. 
  • [Bentley00] Bentley, J. 2000 Programming Pearls (2nd Ed.). ACM Press/Addison-Wesley Publishing Co.

Otros Recursos

Ċ
Juan Carlos Mendivelso Moreno,
Oct 24, 2013, 3:25 PM
Comments