Análisis de Algoritmos

Evaluación

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 P1+P2, sino CF es el piso de P1+P2.

Fecha del Examen 1: durante la semana 8.

Fecha estimada del Examen 2: durante la semana 16.


2.- Presentar examen final en 1ra o 2da vuelta, y su calificación se pone en actas.

Temario, horario y bibliografía


Bibliografía

Mesografía

Reglas de clase & Zoom


Acerca de Zoom


Curso

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 de la siguiente:

liga al repositorio en GitHub.

Semana 1

Semana 2

Semana 3

Semana 4

Semana 5

Semana 6

Semana 7

Semana 8

Semana 9

Semana 10

Semana 11

Semana 12

Semana 13

Semana 14

Semana 15

Semana 16

Sobre Julia, Jupyter Notebook y su instalación

· 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:

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 para poder iniciar los Notebooks. Posteriormente escribimos

(@v1.9) pkg add Plots 

+ Enter a lo que comenzará la instalación del paquete para graficar. 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> yes

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.

Tarea

La tarea I está en el Notebook 15.

Tarea 2.

Semana 9. Terminar de leer el siguiente artículo de backtracking link y resuelva lo siguiente:

9. Usando backtracking, escriba un algoritmo para resolver la estrategia ganadora en el juego de las flechas de nxn. Ver link.

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).

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'.

Proyecto

Este proyecto tiene por objetivo sustituir su tarea II sólo para aquellos alumnos que hayan tenido 8 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.

Objetivo

Tener todos los algoritmos vistos en clase implementados y listos para usarse en el lenguaje Clojure.


Contenido

Todos los algoritmos listados en el orden vistos en clase.


Consideraciones

El proyecto es un producto cuya presentación debe de ser de un producto terminado y autocontenido. El proyecto es por equipos de 4 alumnos máximo.



Guía Rápida para instalar Clojure en Mac o Linux (en Windows ver liga):

Recursos

Más software de interés


Algunas ligas interesantes

- Video 0 link

- Video 1 link

- Video 2 link

- Video 2.5 link

- Video 3 link

- Video 4 link


Algunos examenes extraordinarios previos