Matemáticas Discretas (Ciencia de Datos)

Evaluación

1.- Se evaluará con 2 exámenes parciales (el 1ro es colegiado), 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 estimada del Examen parcial 1: viernes de la semana 8.

Fecha estimada del Examen parcial 2: viernes 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 (ordinario) en 1ra o 2da vuelta, y su calificación se pone en actas.


Temario, horario y bibliografía


Bibliografía


Para la parte de Gráficas

Chromatic Graph Theory, Chartrand y Zhang, 2009.

The Fascinating World of Graph Theory, Benjamin, Chartrand, Zhang, 2015.

Matemáticas Discretas, Comellas, Fàbrega, Sànchez, Serra, 2002.


Para la parte de Recursión

Concrete Mathematics: A fundation for computer science, Graham, Knuth, Patashnik, Segunda edición 1994.

Cormen, T. Introduction to algorithms. Cambridge, Mass.: MIT Press.


Para la parte de Algoritmos

Cormen, T. Introduction to algorithms. Cambridge, Mass.: MIT Press.

Notas de Jeff Erickson link

Reglas de clase & Zoom


Acerca de Zoom



Actualizado el 5 de noviembre de 2023: Ver su correo pcpuma sobre inicio de clases presenciales.


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.

Curso

Idealmente el curso contempla 16 semanas de clases, con 3 sesiones a la semana de 2 horas, lo que da un total de 48 sesiones de clase. Se reservan 2 sesiones para aplicación de los exámenes I y II (Sesiones 24 y 48), así como 2 sesiones de dudas sobre las tareas I y II (Sesiones 23 y 47), respectivamente. En las primeras 16 sesiones se abordará teoría de gráficas, y en las siguientes 32 sesiones se abordará Análisis de Algoritmos. De la sesión 17 a la sesión 27 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

Tarea

Estaré actualizando la tarea por semana.

TAREA 1.

Semana 1. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios pares del Capítulo 1. 

Semana 2. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios 2,4,6,8,10,12,14,16,18 del Capítulo 2.

Semana 3. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios pares referente a las Secciones 3.1 y 3.3.

Semana 4. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios pares referente a las Secciones 4.1 y 4.3.

Semana 5. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios 1,3,4,5,6,7,8,11,12,13,14,18 del Capítulo 5.

Semana 6. Del libro de Chartrand "Chromatic Graph Theory". Ejercicios pares referente a las Secciones 6.1 y 6.2. Instalar Julia y Jupyter Notebook.

Semana 7. Ejercicios de la pág. 17 del libro "Concrete Mathematics" y secciones 3.1, 4.3 y 4.4 del libro "Introduction to algorithms" (Tarea extra: revisar 3.2) y Sección 4.5 del libro de Cormen. Revisar los ejercicios de recursiones de la siguiente liga link.

Semanas 8. Del libro de Cormen "Introduction to algorithms" 3ra edición. Sección 2.1, 2.2 y 2.3. Implementar los algoritmos del siguiente link en Julia y hacer experimentos para comparar sus tiempos de ejecuciones entre las versiones recursivas e iterativas. Además genere un algoritmo que resuelva el siguiente problema:

0. Dado un natural n, usando sólo comparaciones, halle un algoritmo que en lg(n) encuentre a n. Escriba el pseudocódigo y verifique que sea correcto. Impleméntelo en Julia.

Liga a la tarea del otro curso link.

Semana 09. Del libro de Cormen "Introduction to algorithms" 3ra edición. Secciones 6.1, 6.2, 6.3, 6.4. 7.1, 7.2 y 8.1, 8.2, 8.3.


Tarea 2

Semana 11. Escribir el pseudocódigo e implementar los algoritmos que solucionan los siguientes problemas:

1. Dados dos conjuntos A y B de n números, y un número x, diseñe un algoritmo que en O(nlgn) encuentre, si existe, un elemento a en A y otro b en B tales que a+b=x.

2. Supongamos que tenemos una lista A con n elementos, y que cada elemento en la lista es verde, rojo o azul. Queremos ordenar los elementos en nuestra lista de tal forma que aparezcan los elementos verdes, después los rojos y al final los azules. Las operaciones que tenemos disponibles son a) Color(A,i), la cual nos da el color del elemento del elemento i en la lista A. b) Intercambio(A,i,j) que intercambia el elemento i de A con el elemento j. Encuentre un algoritmo lineal que solucione el problema.

3. Dada una lista de n enteros {x1,x2,..,xn} y un número y, encuentre un algoritmo que en O(nlgn) encuentre la pareja (i,j) tal que xi+xj es a lo sumo y, ademas es máxima. 

4. Queremos ordenar una lista S de n elementos enteros que contiene muchos elementos duplicados. Supongamos que los elementos de S sólo toman O(lgn) valores distintos. Encuentre un algoritmo que tome a lo más O(nlglgn) tiempo para ordenar S.

Semana 12. Escribir el pseudocódigo e implementar los algoritmos que solucionan los siguientes problemas:

5. Supongamos que tenemos dos listas ordenadas S y T, cada una con n elementos. Encuentre un algoritmo que en O(lgn) encuentre el n-ésimo elemento de SUT si estuviera ordenada.

6. El problema del tornillo y las tuercas es el siguiente. Nos dan en una bolsa un conjunto de n tornillos de distintos tamaños y en otra sus n tuercas. Nuestro problema es encontrar para cada tornillo su tuerca. En cada paso usted sólo puede comparar un tornillo y una tuerca y verificar si una tuerca corresponde al tornillo, o si el diámetro del tornillo es mayor o menor al diámetro de la tuerca. La diferencia en tamaños y las tuercas es tan pequeño que no puede compara los tornillos entre ellos y las tuercas entre ellas. Encuentre un algoritmo que resuelva el problema en O(n^2) en el peor de los casos, pero que su tiempo esperado sea O(nlgn).

7. Dados n números naturales entre 1 y n^2, encuentre un algoritmo lineal que los ordene.

Además terminar de leer el siguiente artículo de backtracking link y resuelva lo siguiente:

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

9-10. Implemente el pseudocódigo de las n-reinas y el juego de las flechas.

Semana 13. Sección 16.1, 16.2, 16.3, 16.4 y 16.5  (Tarea extra: los problemas de la sección 16).


Semana 14. Secciones 15.1,15.2, 15.3 y 15.4. Además resuelva los siguientes problemas: (Tarea extra: Sección 15.5 y los problemas de la sección 15). 

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

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

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

Llenar la encuesta de enseñanza-aprendizaje: https://encuestas.acatlan.unam.mx/aprendizaje/

Semana 15. Capítulo 22 (tarea extra: secciones 10.1, 10.2), Capítulo 23, Secciones 24.1, 24.2, 24.3 e implementar el algoritmo de planaridad visto en la semana 5 (sesión 14).


Semana 16. Capítulo 25 y Secciones 26.1, 26.2, 26.3 + 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 examen 2 y tarea 2 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 el último día de clases. Se puede elaborar en grupo.

Objetivo

El objetivo de este proyecto es tener todos ejercicios de la tarea del libro de Cormen, listos para usarse en el lenguaje de Julia a través de Jupyter Notebook.


Contenido

Su proyecto contará con un índice conforme al temario.

Incluir bibliografía y referencias.


Consideraciones

El proyecto es un producto cuya presentación debe de ser de un producto terminado y autocontenido.

Recursos

Software


Sobre Gráficas


Sobre Algoritmos

- Video 0 link

- Video 1 link

- Video 2 link

- Video 2.5 link

- Video 3 link

- Video 4 link


Sobre Geometría Computacional


Exámenes previos


Curso de Leonardo