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
Temario link
Horario: martes de 2 a 4pm, jueves de 1 a 3pm y viernes de 4 a 6pm, salón 1523.
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
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
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
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:
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 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 ✔️
Sesión 01 TG: 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. Se revisa el Notebook "Introducción". Se inicia la revisión de conceptos básicos de Teoría de Gráficas: Teorema del saludo de manos.
Sesión 02 TG: Se repasan conceptos de Teoría de Gráficas acerca de distancia en gráficas.
Sesión 03 TG: Se revisa el Notebooks de "Números" de Julia. Se repasan conceptos de Teoría de Gráficas acerca de isomorfismo, así como conceptos básicos como relación de equivalencia y espacio cociente.
Semana 2 ✔️
Sesión 04 TG: Conceptos básicos en gráficas: Gráfica regular, irregular, cúbicas, completas, ciclos, trayectorias, bipartita (y caracterización), bibartita completa, k-partita, k-partita completa, gráfica de Petersen, cuello, H-free como subgráfica/subgráfica inducida y prohibidas.
Sesión 05 TG: Se abordan las operaciones de Julia. (Inscripción de los alumnos-altas/bajas de MAC).
Sesión 06 TG: Conceptos básicos en gráficas: complemento, gráficas autocomplementarias, unión, join, productos de gráficas, grid, k-cubos, gráfica de líneas y gráficas de incidencia en general.
Semana 3 ✔️
Sesión 07 TG: Se aborda el uso de funciones de Julia. Se abordará el significado de los prefijos multi, seudo, simple, di, hiper. Gráficas pesadas y signadas. Conceptos básicos en digráficas: ex e ingrado, conexidad débil y fuerte, gráfica orientada, simétricas y antisimétricas, torneos y su relación con el orden topológico.
Sesión 08 TG: Conceptos básicos en gráficas: vértice de corte, puente, bloque. Árboles.
Sesión 09 TG: Se aborda el uso de arreglos de Julia. Representación de gráficas: matrices de incidencia, adyacencia y listas.
Semana 4 ✔️
Sesión 10 TG: Apareamientos, Condición y teorema de Hall, 1-factor y 1-factorización.
Sesión 11 TG: Se aborda el uso de Markdown en Julia. Factorizaciones.
Sesión 12 TG: Conexidad incluyendo el teorema de Menger. Gráficas Eulerianas y Hamiltonianas.
Semana 5 ✔️
Sesión 13 TG: Se aborda el uso del paquete Plots para graficar en Julia. Se introducen los conceptos de gráficas planas.
Sesión 14 TG: Teorema de Kuratowski y Wagner. Se aborda un algoritmo de planaridad.
Semana 6 ✔️
Sesión 15 TG/01 AA: Se abordará el uso de datos en Julia. Teoría cromática. Notebook 01: Presentación de los notebooks.
Sesión 02 AA: Notebook 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.
Semana 7 ✔️
Sesión 03 AA: Notebook 03: Se aborda el uso de instrucciones en Julia. 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.
Sesión 04 AA: Notebook 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.
Sesión 05 AA: Notebook 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 abordan algunos otros problemas sobre recursión.
Semana 8 ✔️
Sesión 06 AA: Notebook 06&07: En esta sesión se resuelven diferentes recursiones mediante el método de sustitución y se verifica que sean correctas. Se resuelven diferentes recursiones mediante el método maestro y el método del árbol.
Sesión 07 AA: Notebook 08: Se aborda guardar funciones en Julia. 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.
Sesión 08 AA/18 TG: Notebook 09,10,11: En esta sesión regresamos a ver el problema de ordenación para resolverlo mediante el algoritmo Merge Sort. Se introduce una nueva estructura de datos y se de otra solución óptima al problema de ordenación mediante el algoritmo llamado Heapsort.
Semana 9 ✔️
Sesión 09 AA: Notebook 12,13: Se aborda el uso del IDE VSC con Julia. 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, y 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 10 AA: Notebook 15: Sesión dedicada a las dudas de los alumnos sobre la Tarea I.
Semana 10 ✔️
Sesión 11 AA: Notebook 16: Aplicación del Examen I.
Sesión 12 AA: Notebook 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 11 ✔️
Sesión 13 AA: Notebook 17: 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.
Sesión 14 AA: Sesión sobre algoritmos greedy: Códigos de Huffman. Notebook 18.
Sesión 15 AA: Sesión sobre algoritmos greedy: El problema de selección de actividades. Notebook 19.
Semana 12
Sesión 16 AA: Sesión sobre algoritmos greedy: Matroides y el problema de la mochila. Notebook 20.
Sesión 17 AA: Sesión sobre programación dinámica: La subsucesión común más larga. Notebook 21.
Sesión 18 AA: Sesión sobre programación dinámica: Multiplicación de matrices. Notebook 22.
Semana 13
Sesión 19 AA: Sesión sobre programación dinámica: El problema de la caña. Notebook 23.
Sesión 20 AA: Repaso sobre representación de una gráfica, pilas y colas, listas ligadas y doblemente ligadas, y estructuras de datos para conjuntos disjuntos. Notebook 24.
Semana 14
Sesión 21 AA: Sesión sobre BFS y DFS. Notebook 25.
Sesión 22 AA: Repaso de gráficas dirigidas. Sesión sobre orden topológico y componentes fuertemente conexas. Notebook 26.
Sesión 23 AA: Sesión sobre árbol generador de peso mínimo: Kruskal y Prim. Notebook 27.
Semana 15
Sesión 24 AA: Sesión sobre Bellman-Ford, DAG y Dijkstra. Notebook 28.
Sesión 25 AA: Sesión sobre trayectorias más cortas sobre todos los vértices: Floyd-Warshall y Johnson. Notebook 29.
Sesión 26 AA: 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 27 AA: 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 28 AA: Aplicación del Examen II. Notebook 32.
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
Cap 1, Problema 20 link
Cap 3, Problema 10 link
Cap 4, Problema 20 link
Cap 10, Problema 10 link
Juego de isomorfismo de gráficas link
Baby bee link
GraphThing link
Puzzle K_3,3 link
Sobre Algoritmos
Liga a listado de algoritmos en gráficas (de la prof. Lara) link
Liga a algoritmos para entrevistas técnicas link
Acerca de Redes Neuronales
- Video 0 link
- Video 1 link
- Video 2 link
- Video 2.5 link
- Video 3 link
- Video 4 link
Sobre Geometría Computacional
Qué es Geometría Computacional? link
The Computacional Geometry Algorithms Library link
Algunas bases de datos de parámetros y configuraciones link
Curso de Geometría Computacional link
Aplicación del Teorema de Dilworth link
Problema de Geometría Combinatoria link
Sobre familias de cruce link
Sobre Erdős-szekeres link
Sobre Diagramas de Voronoi link
Sobre arreglos de líneas link
Un problema link
Otro problema link
Un software link
Sobre curvas de Jordán link
Carpeta Dropbox link
Exámenes previos
Examen 1 colegiado 2020-I
Examen 1 colegiado 2022-I
Curso de Leonardo