Solución Algorítmica de Problemas con Julia

• 50% Participación en clase.

• 50% Notebook generado en el curso.

Los notebooks utilizados y resultantes se enviarán al profesor inscrito mediante correo electrónico: christian.rubio@acatlan.unam.mx

El programa PASD solicita al menos el 80% de asistencia, una calificación aprobatoria y posterior al curso realizar el llenado de dos encuestas dentro del la plataforma de inscripción.

Se explicarán (o repasarán) conceptos que se implementarán en los Notebooks de Julia para que los participantes interactúen y ponga en práctica sus aprendizajes. Se planea seguir el siguiente contenido.

1. Introducción
   i) Se introduce el lenguaje de programación Julia y Notebooks.
   ii) Se repasan conceptos básicos de algoritmos: definición, modelo RAM, tiempo de ejecución, ver que un algoritmo es correcto. Se presenta el problema de ordenación.

2. Notación asintótica y recursión
   i) Notación asintótica e INSERTION-SORT.
   ii) Recursión y Fibonacci.
   iii) Funciones, arreglos y Markdown en Julia.

3. Verificar que un algoritmo es correcto / Resolver recursiones
   i) Varios ejemplos de algoritmos iterativos y recursivos.
   ii) Solución de recursiones: sustitución.
   iii) Graficación en Julia.

4. Resolver Recursiones / Algoritmos De Ordenación
   i) Solución de recursiones: método del árbol, método maestro, cambio de variable.
   ii) MERGE-SORT, HEAP-SORT, QUICK-SORT.

5. Complejidad computacional
   i) Espacio de búsqueda.
   ii) Cota inferior e información extra.
   iii) PROBLEMAS P, NP, NP-Completos.

El curso fue una adaptación a la primer parte del curso de Análisis de Algoritmos, que se puede encontrar en la siguiente liga:

Repositorio en GitHub.

Bibliografía consultada

• Comellas F., Fàbrega J., Sánchez, A. & Serra, O. (2001). Matemática discreta. Ed. Alfaomega. 

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Cambridge. (2009). Introduction to Algorithms (3 ed). Massachusetts London, England: The MIT Press.

Bibliografía sugerida

• Comellas F., Fàbrega J., Sánchez, A. & Serra, O. (2001). Matemática discreta. Ed. Alfaomega. (Liga a la edición de la UPC)

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Cambridge. (2009). Introduction to Algorithms (3 ed). Massachusetts London, England: The MIT Press. QA76.6 C657 2009

• Erickson, J. (2019). Algorithms. Independently published. liga

• Kleinberg, J., Tardos, E. (2005). Algorithms Design. U. S. A.: Addison Wesley.

· En este curso se hará uso del lenguaje de programación de Julia ya que es un lenguaje de programación de alto nivel que ofrece una facilidad comparable a Python, pero una potencia y velocidad comparable al lenguaje C. Julia es un lenguaje de programación dinámico creado por el Departamento de Ciencias de la Computación del MIT en el año 2009; desarrollado por Jeff Bezanson, Stefan Karpinski, Viral B. Shah y Alan Edelman, liberado gratuitamente en 2012.

Karpinski, uno se su creadores, comenta que Julia empodera a científicos de datos, físicos, comerciantes de finanzas cuantitativas y diseñadores de robots para resolver problemas sin tener que convertirse en programadores informáticos o contratar programadores informáticos para traducir sus funciones en código informático, ver [D’Cunha, 2017]. Para ver la eficiencia de Julia en un gráfico, ver [JuliaLang.org-Contributors, 2023].

Actualmente Julia está en constante crecimiento. Para dimensionar esto, se tiene como referentes a las grandes compañias como Amazon, Apple, Disney, Facebook, Ford, Google, Blackrock, IBM, Microsoft o NASA, las cuales están contratando significativamente a programadores de Julia, ver [D’Cunha, 2017]. De acuerdo con GitHub, en 2017, Julia esta en el top 10 de lenguajes con mayor desarrollo dentro de su plataforma [Claster, 2017].

· Por otro lado, el proyecto Jupyter es un software de código abierto, gratuito y libre. Uno de sus productos es Jupyter Notebook que es un entorno interactivo basado en la web para crear documentos. Contiene una lista ordenada de celdas de entrada/salida para contener código, texto (incluyendo LaTeX), matemáticas o gráficos. Soporta entornos de ejecución, llamados núcleos, en varios lenguajes, tales como Julia, R o Python. Sus archivos usan la extensión .ipynb.

La interfaz computacional de Jupyter Notebook es similar a la interfaz de notebook de otros programas como Mathematica, Maple o SageMath que se originó con Mathematica en la década de 1980, ver [Somers, 2018].

La guía de instalación la haremos pensando en los usuarios de Windows ya que es el más usado. Julia se puede instalar en las versiones de Windows 7 y posteriores. La instalación de Julia la podemos hacer con los siguientes pasos:

• Descargaremos el archivo de instalación desde la página oficial de Julia. Buscaremos el archivo que se adapte a nuestro equipo puede ser de 32 bits o de 64 bits.

• Una vez descargado, ejecutamos el archivo de instalación y seguimos las indicaciones.

Si todo va bien, ya podremos ejecutar Julia, el cual abrirá una terminal. Para complementar la instalación frecuentemente requerimos instalar paquetes, pero esto lo veremos en clase.