1.- Se evaluará con 2 exámenes, 2 tareas y un proyecto. El Periodo 1 tiene un valor de 40% y el Periodo 2 tiene un valor de 60% de la calificación.
El Periodo i tiene la evaluación Pi como sigue: La Tarea i da derecho al Examen i. Sean Ti y Ei las calificaciones respectivas. Si Ti es al menos 6, entonces Pi es el techo de Ei, sino, Pi es el piso de Ei, donde i=1,2.
Para la Calificación final CF se obtiene como sigue: Si tanto T1 como T2 son al menos 6, entonces CF es el techo de 0.4P1+0.6P2, sino CF es el piso de 0.4P1+0.6P2.
Fecha del Examen 1: jueves de la semana 9.
Fecha del Examen 2: jueves de la semana 16.
Para poder presentar exámen final (ordinario), es necesario que el alumno haya obtenido 5 en su evaluación, ver artículo 10 liga.
2.- Presentar examen final en 1ra o 2da vuelta, y su calificación se pone en actas.
Aviso: El díamartes 22 no hay clase ya que asistiré al Congreso Nacional de la SMM liga
Bibliografía
Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein C. (2022). **Introduction to algorithms**. MIT Press, 4E.
Comellas, F., Fábrega, J., Sánchez, A. y Serra O. (2002). Matemáticas discretas. Ediciones UPC.
Mesografía
Erickson, J. (2019, acceso: julio 2024). Algorithms. Página web: liga.
No se guarda calificación.
No se aceptan calificaciones de otros cursos.
No se cambian calificaciones (ni 5 por NP, ni NP por 5).
Las actividades no se reciben de forma extemporánea.
Las tareas se entregan el día del examen.
Los examenes se devuelven al profesor.
La clase termina 5 minutos antes de la hora.
No se aceptan alumnos oyentes.
No se permiten acompañantes de clase.
Uso recomendado de cubrebocas.
No ingerir alimentos en clase.
Limitar el uso del celular en clase incluyendo no hablar por teléfono en clase.
Acerca de Zoom (en caso de ser requerido)
La plataforma que usaremos para tomar clase es zoom mediante el registro del campus virtual.
Previo a cada clase se enviará la liga por su correo pcpuma
Usar una foto de perfil donde se vea su rostro de frente
Acceder a la plataforma con su nombre completo, sin video ni audio para no sobrecargar la red
La participación será a través de video y audio
Idealmente el curso contempla 16 semanas de clases, con 2 sesiones a la semana de 2 horas, lo que da un total de 32 sesiones de clase. Se reservan 2 sesiones para aplicación de los exámenes I y II (Sesiones 16 y 32), así como 2 sesiones de dudas sobre las tareas I y II (Sesiones 15 y 31), respectivamente. En las primeras 11 sesiones se aborda algún tema para aprender a manejar el software Julia y los Notebooks. Cabe aclarar, que se invita al estudiante a preguntar sus dudas de la clase y de las tareas a lo largo de cualquier sesión.
En el apartado posterior encontrará las instrucciones para instalar Julia y los Notebooks. Los notebooks de cada clase se pueden clonar del repositorio de GitHub (ver liga) de la siguiente:
liga al repositorio en GitHub.
Semana 1
Sesión 01: En esta sesión se realiza la presentación del profesor y del curso contenido en esta página web (forma de evaluación, temario, bibliografía, reglas generales de la clase, tarea, proyecto, recursos, etc.). Se introduce al lenguaje de programación de Julia para que el alumno instale y pueda acceder a los notebooks.
Sesión 02: En esta sesión se introducen al curso, conceptos básicos como el modelo RAM, algoritmo, tiempo de ejecución, el problema de ordenación, el algoritmo de Insertion Sort y se argumenta por qué es correcto. Se introduce el uso de Julia.
Semana 2
Sesión 03: En esta sesión se introduce la notación asintótica, se implementa y se calcula el tiempo de ejecución de Insertion Sort en notación asintótica, se realiza una experimentación sobre distintas entradas y se puntualizan conceptos sobre tiempo de ejecución, peor caso y algoritmo eficiente. Se aborda el uso de números en Julia.
Sesión 04: En esta sesión se aborda el concepto de recursión iniciando con el problema clásico sobre los números de Fibonacci. Se da un algoritmo recursivo y uno iterativo que resuelve el n-ésimo número de Fibonacci, se verifica que sean correctos los algoritmos y se calculan sus tiempos de ejecución en notación asintótica. Se abordan las operaciones de Julia.
Semana 3
Sesión 05: En esta sesión se abordan distintos algoritmos (factorial, potencia, búsqueda lineal y búsqueda binaria) de forma resursiva y de forma iterativa. Se prueba que son correctos y se calculan tus tiempos de ejecución. Se aborda el uso de funciones de Julia.
Sesión 06: En esta sesión se resuelven diferentes recursiones mediante el método de sustitución y se verifica que sean correctas. Se aborda el uso de arreglos de Julia.
Semana 4
Sesión 07: En esta sesión se resuelven diferentes recursiones mediante el método maestro y el método del árbol. Se aborda el uso de Markdown en Julia.
Sesión 08: En esta sesión se resuelven diferentes tipos de recursiones mediante cambio de variable y análisis asintótico en conjunción con los métodos vistos anteriormente. Se aborda el uso del paquete Plots para graficar en Julia.
Semana 5
Sesión 09: En esta sesión regresamos a ver el problema de ordenación para resolverlo mediante el algoritmo Merge Sort. Se abordará el uso de datos en Julia.
Sesión 10: En esta sesión se introduce una nueva estructura de datos y se de otra solución óptima al problema de ordenación mediante el algoritmo llamado Heapsort. Se aborda el uso de instrucciones en Julia.
Semana 6
Sesión 11: En esta sesión se continúa con el algoritmo Heapsort. Se aborda como guardar una función en Julia.
Sesión 12: En esta sesión se da otra solución al problema de ordenación mediante el algoritmo Quicksort. Se introduce el concepto de tiempo de ejecución esperado.
Semana 7
Sesión 13: En esta sesión se analiza la cota inferior al problema de ordenación y se da otra solución mediante el algoritmo Counting Sort asumiendo información extra.
Sesión 14: En esta sesión se da otra solución al problema de ordenación mediante el algoritmo Radix Sort asumiendo información extra y se introduce el concepto de complejidad computacional (P, NP, NP-Completo, NP-Hard).
Semana 8
Sesión 15: Sesión dedicada a las dudas de los alumnos sobre la Tarea I.
Sesión 16: Aplicación del Examen I.
Semana 9
Sesión 17: En esta sesión se hace un repaso sobre representaciones de una gráfica, pilas, colas, listas ligadas, listas doblemente ligadas, y estructuras de datos para conjuntos disjuntos. Se aborda el uso del paquete DataStructures.jl de Julia.
Sesión 18: En esta sesión se introduce la técnica de backtracking. Se revisa el problema de las n-reinas y el juego de los sobres de azúcar.
Semana 10
Sesión 19: En esta sesión se trabaja el concepto de la heurística Greedy, también conocida como voráz, codiciosa o glotona. Se aborda el "problema de la mochila" así como los códigos de Huffman..
Sesión 20: Sesión sobre algoritmos greedy: El problema de selección de actividades. Notebook 20.
Semana 11
Sesión 21: Sesión sobre algoritmos greedy: Matroides. Notebook 21.
Sesión 22: Sesión sobre programación dinámica: La subsucesión común más larga. Notebook 22.
Semana 12
Sesión 23: Sesión sobre programación dinámica: Multiplicación de matrices. Notebook 23.
Sesión 24: Sesión sobre programación dinámica: El problema de la caña. Notebook 24.
Semana 13
Sesión 25: Sesión sobre BFS y DFS. Notebook 25.
Sesión 26: Repaso de gráficas dirigidas. Sesión sobre orden topológico y componentes fuertemente conexas. Notebook 26.
Semana 14
Sesión 27: Sesión sobre árbol generador de peso mínimo: Kruskal y Prim. Notebook 27.
Sesión 28: Sesión sobre Bellman-Ford, DAG y Dijkstra. Notebook 28.
Semana 15
Sesión 29: Sesión sobre trayectorias más cortas sobre todos los vértices: Floyd-Warshall y Johnson. Notebook 29.
Sesión 30: Repaso sobre el teorema de Menger. Sesión sobre redes de flujos: el método de Ford-Fulkerson y el apareamiento bipartito máximo. Notebook 30.
Semana 16
Sesión 31: Sesión dedicada a las dudas de los alumnos sobre la Tarea II. Generalmente el profesor explica algún problema interesante. Notebook 31.
Sesión 32: Aplicación del Examen II. Notebook 32.
· Sobre Julia: 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].
· Sobre Jupyter Notebook: 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].
· Sobre la instalación: 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 dando clic en el ícono, el cual abrirá una terminal y aparecerá la línea
julia>
Frecuentemente requerimos instalar paquetes, en la terminal indica como ir al modo de instalar paquetes, esto es, tecleamos
julia> ]
y automáticamente aparecerá
(@v1.9) pkg
"v1.9" es la versión instalada de Julia. Allí vamos a escribir
(@v1.9) pkg add IJulia
+ Enter a lo que comenzará la instalación de ese paquete "IJulia" para poder iniciar los Notebooks. Posteriormente escribimos
(@v1.9) pkg add Plots
+ Enter a lo que comenzará la instalación del paquete para graficar "Plots". También instale "Graphs" y "DataStructures". Para saber los paquetes instalados, escribimos
(@v1.9) pkg status
Para salir del modo de instalación de paquetes tecleamos
(@v1.9) pkg ⌫
es decir, la tecla "Del" o "Backspace", a lo obtenemos
julia>
Ahora escribimos
julia> using IJulia
para compilar ese paquete. Posteriormente escribimos
julia> notebook()
Esto nos permitirá el acceso a Julia en el repositorio de Jupyter. La primera vez que se corren estos comandos solicita el permiso de una instalación mínima de Python vía Conda. Lo permitiremos al escribir
julia> y
En el caso de Windows, podría generarse un error de instalación que se puede evitar deshabilitando temporalmente su antivirus. Entonces, en nuestro navegador se despliega una página donde se va a trabajar en los Notebooks.
En esa página se muestra una carpeta que está en su ordenador, como podrá verificar. Para abrir los notebooks previamente descargados (o clonados) nos dirigimos a la carpeta “Downloads” (o “Descargas” según el idioma de su ordenador). Dando clic sobre los archivos .ipynb accedemos a ellos.
Para cerrar correctamente damos clic en "Quit" (parte superior-derecha del navegador) en la primer página desplegada. Ya puede cerrar la página e ir a la terminar de Julia, donde verá nuevamente.
julia>
Para salir correctamente de la terminal escribimos exit() + Enter.
La tarea I está en el Notebook 15.
Tarea extra:
Hallar todos los números narcisistas, ver video.
Imagina que hay n autos circulando a distintas velocidades (constantes) sobre una carretera de 2 carriles (tan larga como sea necesaria). Independientemente del orden en el tiempo t_0, al dejar pasar un tiempo suficiente t_1, los autos quedarán ordenados. a) Calcula el tiempo mínimo t_1 para el cual esto sucede. b) Se puede extrapolar el problema a un algoritmo de ordenación? c) Sería un algoritmo de comparación o qué hipótesis serían necesarias para que sea eficiente?
Tarea 2.
Semana 9. Terminar de leer el siguiente artículo de backtracking link (link2) y resuelva lo siguiente:
9. Usando backtracking, escriba un algoritmo para resolver la estrategia ganadora en el juego de las flechas de nxn. Ver Notebook 18.
10. Implemente el pseudocódigo de las n-reinas y el del problema 9 de las flechas.)
Semana 10. Sección 16.1, 16.2, 16.3, 16.4 y 16.5 (Tarea extra: los problemas de la sección 16).
Semana 11. Secciones 15.1, 15.2, 15.3 y 15.4, y los siguientes problemas: (Tarea extra: Sección 15.5 y los problemas de la sección 15).
10. Sean k y n naturales. El (k,n)-problema de los huevos es el siguiente: Tenemos un edificio con n pisos y una cesta con k huevos. Sabemos que hay un piso f tal que si dejamos caer cualesquiera huevo desde el piso f, o desde un piso más arriba, se estrellará. Y si dejamos caer un huevo desde un piso r<f, entonces no se estrellará. Por ejemplo, si f=1, entonces el huevo se estrellará si lo dejamos caer desde cualquier piso, por el contrario, si f=n+1, el huevo nunca se estrellara. Una vez que un huevo se estrelle, no lo podemos usar nuevamente. Al disponer de exactamente k huevos, ¿cuál es el menor número de experimentos (dejar caer huevos) que se tienen que hacer para determinar f? Sea E(k,n) el mínimo número de experimentos que se tiene que hacer para determinar f. Pruebe que E(k,n) es theta(n^{1/k}). Usando programación dinámica de un algoritmo correcto que resuelva el problema y calcule su tiempo de ejecución.
11. Supongamos que quieres marcar un número con n dígitos {r_1,r_2,...,r_n} en un teléfono normal en el que los números están en un arreglo de 4x3 teclas utilizando sólo dos dedos. Supongamos que al comenzar a marcar, tus dedos están en las teclas "*" y "#". Encuentra un algoritmo que en tiempo lineal minimice la distancia euclidiana que tienen que recorrer sus dedos para marcar el número. Use programación dinámica.
12. Sea T un árbol de n vértices. Cada vértice v tiene asociado un peso w(v). Utilizando programación dinámica encuentre un algoritmo lineal para encontrar un conjunto independiente de T de peso máximo.
Semana 12. Secciones 22.1 y 22.2 (tarea extra: secciones 10.1, 10.2)
Semana 13. Secciones 22.3, 22.4, 22.5, 24.1, 24.2 y 24.3 (tarea extra: secciones 24.4 y 24.5). Realizar evaluación docente: https://encuestas.acatlan.unam.mx/aprendizaje/
Semana 14. Secciones 25.1, 25.2, 25.3, 26.1, 26.2, 26.3.
Semana 15. Secciones 23.1 y 23.2 + los siguientes dos problemas:
13. (El problema del escape) Una malla de nxn es una gráfica compuesta por n filas y n columnas de vértices. Denotamos el vértice de la i-ésima fila y j-ésima columna como (i,j). Todos los vértices de una malla tienen exactamente cuatro vecinos, excepto aquellos en la frontera, que son los vértices (i,j) con i=1, i=n, j=1 o j=n.
Dado m (un número entre 1 y n^2) vértices de arranque (x_1,y_1),(x_2,y_2),...,(x_m,y_m) en la malla, el problema del escape es decidir si existen m trayectorias ajenas por vértices que conecten a cada vértice de arranque con algún vértice de la frontera (distintos).
a) Considere una red de flujos cuyos vértices, así como las aristas, tengan capacidades. Esto es, el flujo positivo que entra a cualquier vértice está sujeto a una restricción de capacidad. Muestra que determinar el flujo máximo con capacidades tanto en los vértices como aristas puede ser reducido a un problema de flujo máximo ordinario en una red de flujo de tamaño similar.
b) Describe un algoritmo eficiente que de solución al problema del escape y analice su tiempo de ejecución.
14. Supongamos que tenemos un flujo óptimo en una red 'N' con 'n' vértices (con capacidades enteras) de un nodo fuente 's' a un nodo pozo 't'. Supongamos que la capacidad de una sólo arista 'e' cambia incrementando en 1. Da un algoritmo que en tiempo O(n+m) actualice el flujo, donde 'm' es el número de aristas de la red 'N'.
Este proyecto tiene por objetivo sustituir su tarea II sólo para aquellos alumnos que hayan tenido 6 o más en su examen 1. Si elige hacer este proyecto, lo tiene que entregar junto con su examen II el último día de clases.
Completar los notebook de las clases, del 19 al 32.
El proyecto es un producto cuya presentación debe de ser de un producto terminado y autocontenido.
Más software de interés
Algunas ligas interesantes
Sobre patrones de potencias de 2 link
Sobre dividir por 0 link
Liga a listado de algoritmos en gráficas (de la prof. Lara) link
Liga a algoritmos para entrevistas técnicas link
¿Qué es Geometría Computacional? link
Acerca de Redes Neuronales
- Video 0 link
- Video 1 link
- Video 2 link
- Video 2.5 link
- Video 3 link
- Video 4 link
Algunos examenes previos