Me gustaría dar una charla de matemáticas sobre el sistema de control de revisión git . Ahora es ampliamente utilizado en matemáticas, así como en la industria de la informática. Por ejemplo, la comunidad HoTT (Homotopy Type Theory) lo utiliza, y es el sistema de acceso para la edición colaborativa de archivos de texto, ya sea código fuente o marcado de látex.
Sé que git usa la noción de un gráfico acíclico dirigido, que es un comienzo. Sin embargo, una buena charla matemática menciona pruebas y teoremas.
¿Qué teorema podría probar sobre git que sea realmente relevante para su uso?
co.combinatorics
application-of-theory
ThoralfSkolem
fuente
fuente
Respuestas:
Un repositorio git puede considerarse como un conjunto de revisiones parcialmente ordenadas (donde una revisión es anterior a otra en el orden si es un sucesor directo o indirecto de la anterior). Los pedidos parciales que obtiene de los repositorios de git tienden a tener un ancho bajo (el tamaño del conjunto más grande de revisiones mutuamente independientes) porque el ancho está directamente relacionado con el número de desarrolladores activos y el número de tenedores diferentes que cualquier desarrollador individual podría estar trabajando en.
En base a estos antecedentes, sugeriría el teorema de Dilworth , que establece que el ancho de cualquier orden parcial es igual al número mínimo de cadenas (subconjuntos totalmente ordenados) necesarios para cubrir todas las versiones. Y para que sea un tema para este tablero, también podría mencionar los algoritmos basados en la coincidencia de gráficos para calcular el ancho y encontrar una cobertura por un número mínimo de cadenas en el tiempo polinómico.
Una forma en que esto podría ser relevante para el uso real en Git es en un sistema para visualizar el historial de versiones de un sistema: la mayoría de los sistemas de visualización de Git que he visto dibujan tiempo en el eje vertical y versiones independientes del repositorio horizontalmente, por lo que esto le daría una manera de organizar la visualización en un pequeño número de pistas verticales independientes.
Alternativamente, si desea algo más ambicioso y avanzado, pruebe la estructura de datos del árbol de culpa de Demaine et al. , Que está directamente motivada por la resolución de conflictos en sistemas de control de versiones similares a git.
fuente
Curiosamente, hay una naciente matematización de los sistemas de control de versiones, aunque en este punto solo es parcialmente aplicable a Git. Se llama teoría de parches [1, 2, 3, 4, 5] y surgió en el contexto del sistema de control de versiones DARCS. Se puede ver como una teoría abstracta de ramificación y fusión . Recientemente, la teoría del parche ha recibido tratamientos HoTT [6] y categóricos [7].
La teoría de parches es un trabajo en progreso, y no cubre todos los aspectos del control de versiones, pero contiene muchos teoremas que puedes ver. Es un claro ejemplo de teoría aplicable al "mundo real", no es sorprendente, ya que la teoría de parches es una abstracción / simplificación de algo muy concreto. Al mismo tiempo, se conecta con matemáticas de vanguardia como HoTT.
fuente
Otra alternativa es observar estructuras de datos persistentes (o puramente funcionales). La estructura interna de datos de Git puede verse como un árbol confluentemente persistente :
Esta pregunta también es relevante.
fuente
Sí, puedes definir matemáticamente cómo funciona Git. Podría definir estructuras Git primitivas y operaciones Git en ellas y luego tener teoremas que prueben que el uso de estas operaciones de maneras particulares logra objetivos particulares de nivel superior, o intentar caracterizar o cuantificar situaciones en las que este no es el caso. (Por ejemplo, la dependencia de Git de los hashes deja un pequeño margen de error).
Otra idea es hacer lo mismo para Subversion, luego producir teoremas que comparen los dos. Por ejemplo, a menudo se afirma que Git es mejor para tratar fusiones; puedes tener teoremas que prueben esto, cualitativa o cuantitativamente.
La utilidad dependería críticamente de hacer las abstracciones correctas. Describir matemáticamente el funcionamiento del código fuente de Git con todo detalle no tiene sentido: el código fuente en sí lo hace de manera mucho más efectiva y concisa.
fuente