Curso de Análisis de Algoritmos para no-ingenieros de sistemas (computer science) a nivel de posgrado

Saber programar un computador es hoy en día una necesidad más que puntual de solamente algunas profesiones que tienen que ver con el desarrollo de software a nivel empresarial (Ingeniería de Sistemas, en el caso colombiano o Ciencias de la Computación, en un caso más general). Cada vez más profesionales de distintas áreas del saber cómo las ingenierías, ciencias exactas, salud, sociales, entre otras, requieren adquirir habilidades en el desarrollo de programas eficientes que les permita generar soluciones y analizar grandes volúmenes de información en un lapso de tiempo adecuado.

Pero no basta escribir un programa que resuelva un problema matemático o permita obtener una solución puntual a un problema determinado. Es necesario que el programador tenga conocimientos de cómo sería la mejor forma, la más eficiente, por así decirlo, de resolver no solo ese problema puntual sino una familia de problemas similares que se puedan describir de forma similar empleando los mismos algoritmos.

Es por esto que se presenta este curso a un nivel de posgrado dando especial atención a los aspectos que puedan ser de mayor interés para los profesionales de áreas diferentes a la de las Ciencias de la Computación.

Presentar a los estudiantes de áreas diferentes a las de las Ciencias de la Computación, los fundamentos básicos del Análisis de Algoritmos que les posibilitarán escribir programas eficientes y obtener resultados en tiempos razonables.

Clases magistrales en donde el docente expondrá los diferentes temas, propondrá una serie de ejercicios a ser resueltos en clase y se plantearán desafíos de análisis de los algoritmos vistos y su respectiva codificación en algún lenguaje de programación de libre elección por parte del estudiante (C, C , Fortran, MATLAB, Python, Julia, etc.) que deberán ser entregados en la clase siguiente.

1. Introducción

   1.1 Definición de algoritmos

   1.2 Notación matemática

2. Algoritmia elemental

   2.1 Eficiencia de los algoritmos

   2.2 Análisis de “caso medio” y “caso peor”

   2.3 Operaciones elementales

   2.4 Ejemplos y desafíos

3. Notación asintótica

   3.1 “orden de...”

   3.2 Operaciones sobre notación asintótica

   3.3 Ejemplos y desafíos

4. Análisis de algoritmos

   4.1 Estructuras de control: Secuencias, bucles para, mientras y repetir, recursividad.

   4.2 Análisis de caso medio y amortizado

   4.3 Ejemplos y desafíos

5. Estructuras de datos

   5.1 Arreglos, pilas y colas

   5.2 Listas

   5.3 Grafos

   5.4 Árboles

   5.5 Ejemplos y desafíos

6. Algoritmos de ordenación y búsqueda

   6.1 Caso general

   6.2 Algoritmos de ordenación

   6.3 Algoritmos de búsqueda

   6.4 Ejemplos y desafíos

7. Complejidad computacional

   7.1 Introducción

   7.2 Teoría de la información

   7.3 Argumentos del adversario

   7.4 Reducciones lineales

   7.5 Clases P y NP

   7.6 Ejemplos y desafíos

8. Algoritmos probabilistas

   8.1 Introducción

   8.2 Algoritmos probabilistas numéricos

   8.3 Algoritmos de Monte Carlo

   8.4 Ejemplos y desafíos

9. Algoritmos paralelos

   9.1 Introducción a la computación paralela

   9.2 Evaluación de expresiones en paralelos

   9.3 Ordenación en paralelo

   9.4 Cómputo distribuido

   9.5 Ejemplos y desafíos

• Brassard, G., y Bratley, P. Fundamentos de Algoritmia, Prentice Hall, 1998.

• Cormen, T., Algorithms Unloked, The MIT Press, 2013.

• Cormen, T., Leiserson, Ch., Rivest, R. and Stein C.: Introduction to Algorithms, 3rd. Ed. The MIT Press, 2009.

• Martin, R., Clean Code: A handbook of agile software craftsmanship, Prentice Hall, 2009.

• Skiena, S., The Algorithm Design Manual, 2nd. Ed., Springer, 1997.