Solución Algorítmica de Problemas con Julia
Este curso de 20 horas tiene el objetivo de aplicar las funciones principales del lenguaje de programación Julia para implementar seudocódigos de manera correcta para que den la resolución de problemas algorítmicos recursivos e iterativos, así como analizar desde una perspectiva matemática la complejidad algorítmica de manera asintótica.
Está contenido dentro del Programa de Actualización y Superación Docente (PASD) Cursos de Licenciatura 2023, DGAPA, y está planeado como un curso presencial, del 12 de junio de 2023 al 23 de junio de 2023, 09:00 a 11:00h, impartido en el laboratorio de cómputo A-421 donde previamente se tendrá instalado el lenguaje de programación Julia. Si un participante desea llevar su equipo personal, indicaremos cómo instalar el software (ver en las pestañas de abajo).
Criterios de evaluación
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.
Contenido y Bibliografía
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.
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.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.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.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.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:
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.
Sobre Julia y Jupyter Notebook
· 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].
Instalación de Julia
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.