Eu gostaria de dar uma palestra em matemática sobre o sistema de controle de revisão do git . Agora é amplamente utilizado em matemática e também na indústria de ciência da computação. Por exemplo, a comunidade HoTT (Homotopy Type Theory) a utiliza e é o sistema para edição colaborativa de arquivos de texto, sejam eles código-fonte ou marcação de látex.
Eu sei que o git usa a noção de um gráfico acíclico direcionado, que é um começo. No entanto, uma boa conversa sobre matemática menciona provas e teoremas.
Que teorema posso provar sobre o git que é realmente relevante para seu uso?
co.combinatorics
application-of-theory
ThoralfSkolem
fonte
fonte
Respostas:
Um repositório git pode ser pensado como um conjunto de revisões parcialmente ordenadas (onde uma revisão é anterior a outra na ordem se for um sucessor direto ou indireto do anterior). As ordens parciais que você recebe dos repositórios git tendem a ter baixa largura (o tamanho do maior conjunto de revisões independentes), porque a largura está diretamente relacionada ao número de desenvolvedores ativos e ao número de forquilhas diferentes que qualquer desenvolvedor individual pode estar trabalhando em.
Com base nesse cenário, sugiro o teorema de Dilworth , que afirma que a largura de qualquer ordem parcial é igual ao número mínimo de cadeias (subconjuntos totalmente ordenados) necessários para cobrir todas as versões. E para torná-lo tópico neste fórum, você também pode mencionar os algoritmos baseados em correspondência de gráficos para calcular a largura e encontrar uma cobertura por um número mínimo de cadeias em tempo polinomial.
Uma maneira que isso pode ser relevante para o uso real no Git é em um sistema para visualizar o histórico de versões de um sistema: a maioria dos sistemas de visualização do Git que eu vi desenham o tempo no eixo vertical e as versões independentes do repositório horizontalmente. daria a você uma maneira de organizar a visualização em um pequeno número de trilhas verticais independentes.
Como alternativa, se você quiser algo mais ambicioso e avançado, tente a estrutura de dados da árvore de culpa de Demaine et al. , Que é diretamente motivada pela resolução de conflitos em sistemas de controle de versão do tipo git.
fonte
Curiosamente, existe uma matematização nascente dos sistemas de controle de versão, embora neste momento seja apenas parcialmente aplicável ao Git. É chamado de teoria dos patches [1, 2, 3, 4, 5] e surgiu no contexto do sistema de controle de versão do DARCS. Pode ser visto como uma teoria abstrata de ramificação e fusão . Recentemente, a teoria dos remendos recebeu tratamentos HoTT [6] e categóricos [7].
A teoria dos patches é um trabalho em andamento e não abrange todos os aspectos do controle de versão, mas contém muitos teoremas que você pode examinar. É um exemplo claro de teoria aplicável ao 'mundo real' - não é de surpreender, pois a teoria de patches é uma abstração / simplificação de algo muito concreto. Ao mesmo tempo, ele se conecta com matemáticas de ponta como o HoTT.
fonte
Outra alternativa é examinar estruturas de dados persistentes (ou puramente funcionais). A estrutura de dados interna do Git pode ser vista como uma árvore persistentemente confluente :
Esta questão também é relevante.
fonte
Sim, você pode definir matematicamente como o Git funciona. Você pode definir estruturas Git primitivas e operações Git sobre elas e, em seguida, ter teoremas que provam que o uso dessas operações de maneiras particulares alcança objetivos específicos de nível superior, ou tenta caracterizar ou quantificar situações nas quais esse não é o caso. (Por exemplo, a dependência de Git em hashes deixa uma pequena margem para erro.)
Outra idéia é fazer a mesma coisa com o Subversion, depois produzir teoremas que comparem os dois. Por exemplo, costuma-se afirmar que o Git é melhor para lidar com fusões; você pode ter teoremas que provam isso, qualitativa ou quantitativamente.
A utilidade dependeria criticamente de fazer as abstrações certas. A descrição matemática do funcionamento do código-fonte Git com todos os detalhes é inútil: o próprio código-fonte faz isso de maneira muito mais eficaz e concisa.
fonte