Olimpíada Matemática Argentina

Investigación y docencia

Computación

Primera versión: 26/4/2019, revisado: 30/5/2019

Uno de los objetivos de esta página es difundir el uso de la computadora en la enseñanza de matemáticas.

Hacia 1994 empezamos esta tarea con las computadoras usando el lenguaje Pascal, el software de geometría dinámica Cabri-Géomètre y el sistema Mathematica. Por distintas razones, hemos ido dejando de lado esos lenguajes a favor del lenguaje Python y el software GeoGebra, que son gratis y se pueden usar en computadoras, tabletas y aún teléfonos celulares.

En esta página ponemos comentarios y archivos sobre algoritmos en general, concretados con estas aplicaciones.

Python

Presentamos algunos algoritmos escritos como módulos en el lenguaje Python.

No son de producción “profesional” sino “amateur”: no nos preocupamos por verificar si la entrada es correcta, y muy posiblemente haya errores (“bugs”), que desde ya agracederé que me los comuniquen.

En el mismo sentido, en la mayoría de los casos se trata de algoritmos sencillos antes que eficientes, ya que su propósito es más el de enseñanza y no tanto de resolución de problemas “industriales”.

Esto es especialmente cierto en los algoritmos combinatorios (como los de grafos), y en particular al considerar problemas NP.

Recordar que los módulos de Python 3 están codficados en UTF-8, por lo que pueden no verse bien en un navegador de internet.

Notas sobre la instalación de Python

Ver Python e Idle

Grafos

Módulos para resolver varios problemas sencillos de grafos, algunos con la posibilidad de visualización.

En la mayoría de los casos se trata de grafos simples (sin bucles ni aristas paralelas) y no dirigidos.

En nuestra implementación, los vértices de un grafo con $n$ vértices están numerados de $1$ a $n$, y las aristas son de la forma $[u, v]$ cuando el grafo no es pesado, o de la forma $[u, v, w]$ cuando lo es, donde $u$ y $v$ son vértices y $w$ es el peso (o costo).

Gráficos de grafos: grgrafo

El módulo grgrafo es similar al módulo graficar (descripto más abajo), y como éste se basa en el uso de Tkinter, por lo que funciona en una instalación normal. La mayor diferencia es la posibilidad de mover interactivamente los vértices y las etiquetas de vértices y aristas.

Un ejemplo sencillo de uso puede verse en el módulo grgrsimple.

Ciclos de Euler

El módulo euler define una función para encontrar un ciclo de Euler (si lo hay), y el módulo euler-peli además muestra una “película” de cómo se va construyendo, ejemplificado en el archivo euler-peli.pdf.

Caminos y ciclos de Hamilton

En el módulo hamilton se definen funciones para encontrar caminos o ciclos de Hamilton (si los hubiera), la función hamilton es para grafos sin pesos y la función hamiltonc para el caso pesado.

El módulo hamilton-dibu muestra un gráfico del camino o ciclo obtenido, y el módulo hamiltonc-dibu hace lo mismo cuando las aristas tienen costos. Los gráficos resultantes pueden verse en hamilton-dibu.pdf y hamiltonc-dibu.pdf, respectivamente.

El archivo hamilton-dode.pdf encuentra un ciclo de Hamilton en el dodecaedro (el grafo original del juego de Hamilton), que necesita un tratamiento especial para dibujar los puntos. El gráfico en este caso se obtiene con el módulo hamilton-dode.

Recorrido del caballo en un tablero

El módulo caballo sirve para encontrar un ciclo o camino de Hamilton (si lo hay) en un tablero de dimensión $m\times n$, donde las adyacencias están dadas por los movimientos de un caballo. El problema, con numerosas citas, está descripto en el archivo caballo.pdf.

Grafo de Petersen

El módulo petersen muestra una ilustración de este famoso grafo, determinando la existencia de un camino o un ciclo de Hamilton en él.

Este grafo tiene muchas características interesantes por lo que se usa como ejemplo y contra-ejemplo de varias propiedades.

Por ser un grafo pequeño con tantas propiedades curiosas, lo adopté como ícono de esta página.

Recorrido de grafos

El módulo recorrido implementa recorrido a lo ancho (fifo), y tres variantes de recorrido en profundidad (lifo), una de ellas usando recursión.

Las funciones lifo, fifo y lifovar pueden visualizarse mediante “películas” usando los módulos lifo-peli, fifo-peli y lifovar-peli.

En esos módulos pueden cambiarse los grafos a usar, y se muestran algunas posibilidades en los archivos lifo-circ.pdf, lifo-arbol.pdf, fifo-circ.pdf, fifo-arbol.pdf, lifovar-circ.pdf y lifovar-arbol.pdf.

Árbol generador mínimo

Reproducimos los algoritmos tradicionales de Prim y Kruskal en los módulos prim y kruskal.

Como en otros casos, estos algoritmos se pueden visualizar mediante los módulos prim-peli y kruskal-peli.

En esos módulos se pueden cambiar los grafos, y algunos resultados puenden apreciarse en los archivos prim-peli.pdf y kruskal-peli.pdf

Distancias entre vértices

Reproducimos los algoritmos tradicionales de Dijkstra y Floyd-Warshall en los módulos dijkstra y floyd.

El algoritmo de Dijkstra, muy similar al de Prim, se puede visualizar con el módulo dijkstra-peli, como se ilustra en el archivo dijkstra-peli.pdf

El problema chino del cartero

El módulo cartero resuelve el problema buscando un emparejamiento de mínimo costo entre los vértices impares.

Para encontrar un emparejamiento de mínimo costo usamos un módulo de Joris van Rantwijk, reproducido acá en mwmatching (ver http://jorisvr.nl/article/maximum-matching y http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py).

El método del camino crítico (cpm)

Este método tiene como versión sencilla encontrar un orden lineal compatible con un orden parcial dado. Resolvemos este problema basándonos en el algoritmo de “clasificación topológica” según el libro de N. Wirth, Algoritmos y estructuras de datos (Vicens Vives, 1998).

Cuando los puntos en las precedencias se piensan como tareas de un proyecto que requieren distintos tiempos, es de interés encontrar el menor tiempo posible en el que se puede terminar el proyecto, dando lugar al método del camino crítico (cpm), en el que además se encuentran las tareas críticas que no se pueden retrasar.

  • En el apunte ordenlineal.pdf se describen con más detalles estos dos métodos.
  • El método de clasificación topológica está implementado en el módulo toposort, y puede probarse con el módulo toposort-prueba.
  • Análogamente, el método del camino crítico está en el módulo cpm, y puede probarse con el módulo cpm-prueba.
Gráficos de puntos y curvas
El módulo graficar

graficar está basado en tkinter y es de elaboración casera. Por lo tanto es muy elemental, y puede tener errores.

Como el módulo Matlplotlib, descripto más abajo, es complicado si no imposible su uso interactivo. En este sentido, GeoGebra es mucho más amigable.

Ejemplos de uso del módulo graficar:

  • grseno es un gráfico sencillo del seno, mostrando cómo ajustar las escalas de los ejes.
  • grexplog muestra la exponencial y su inversa, el logaritmo, incluyendo la diagonal $y = x$.
  • gr1sobrex es el gráfico de la función discontinua $y = 1/x$, dando una tolerancia para alejarse de $0$.
  • grnumerico es un módulo para ilustrar métodos numéricos para encontrar raíces.

    Cada uno de los métodos se ejemplifica en los siguientes módulos, en los que se pueden cambiar las funciones a analizar:

    • grbiseccion ilustra el método de la bisección para encontrar raíces.
    • grpuntofijo ilustra el método de punto fijo, esto es, iteraciones de la forma $x_{n+1} = f(x_n)$.
    • grnewton ilustra el método de Newton-Raphson para encontrar raíces de funciones suaves (es un método de punto fijo).
  • graleat es una serie de gráficos mostrando cómo graficar puntos y el comportamiento de números aleatorios con distribución uniforme.
  • grmandelbrot es... ¡no me acuerdo!
  • Newton-fractal-1 y Newton-fractal-2 son dos vistas del fractal asociado a la convergencia del método de Newton para $z^3 - 1$, explicado en el apunte de Matemática y programación.
El módulo Matplotlib

El módulo Matlplotlib es mucho más elaborado que el módulo graficar que mencionamos antes, pero necesita una instalación separada, que en algunos sistemas no es fácil.

Presentamos ejemplos sencillos, tratando de ver las posibilidades, imitando alguno de los ejemplos de graficar:

  • pltseno: gráfico del seno.
  • plt1sobrex: gráfico de $y = 1/x$.
  • pltaleat: los puntos aleatorios.
  • pltodo: un gráfico mostrando curvas y puntos en distintos estilos.
Módulos del apunte Matemática y programación
Módulos del apunte Algoritmos de aritmética elemental
  • aritbase.py: Algoritmos elementales para factorización, divisibilidad, el algoritmo de Euclides y extensiones.
  • aritejemplos.py Ejemplos de uso de algunos de los algoritmos en aritbase.py:
Módulos del apunte Hasta el infinito... y más acá
Geogebra

En la página personal de GeoGebra, hay algunas activides de interés:

  • Los métodos bisección, punto fijo y Newton para resolver ecuaciones no lineales, son traducciones de los correspondientes módulos de Python con graficar (dentro de Gráficos de puntos y curvas, a su vez dentro de Python).
  • Simpson es una ilustración del método de Simpson para aproximar el valor de integrales.
  • Fichas armónicas es una ilustración de cómo las sumas parciales de la serie armónica crecen sin cota, ejemplificada haciendo una “pila” de fichas que se extienden todo lo que se quiera más allá de la mesa que las sostiene.

    Es una de las actividades del apunte Hasta el infinito... y más acá.