Álgebra Computacional
Permanent URI for this collection
Browse
Browsing Álgebra Computacional by Sustainable Development Goals (SDG) "09:Indústria, Inovação e Infraestruturas"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
- Bibliotecas de axiomáticas: conceitos e resultados para sistemas algébricosPublication . Ramires, João Jorge da Costa Vieira; Araújo, João; Matos, David Martins deEm 1996, EQP, um programa de computador, resolveu o Problema de Robbins, um problema colocado nos anos 30 e que tinha derrotado alguns dos maiores algebristas do século XX. Em julho de 2022, Enigma, uma ferramenta de inteligência arti cial aplicada à demonstração automática de teoremas produzida por Josef Urban (Czech Technical University) no âmbito de uma bolsas do Conselho Europeu de Investigação (ERC) que lhe foi concedida para o efeito, demonstrou autonomamente 75% dos teoremas na base de dados Mizar, um repositório contendo grande parte dos teoremas mais comuns, nomeadamente os teoremas lecionados numa licenciatura ou mestrado de matemática pura. Os tempos são de grande mudança e a questão natural é esta: como podemos colocar estas ferramentas a ajudar o progresso da matemática? A resposta que existe hoje consiste em fazer uma pergunta ao computador e ter uma resposta (como aconteceu com o EQP e com a Enigma). Mas será possível desenhar um programa para autonomamente descobrir nova matemática? Aqui há um problema. Já hoje temos computadores capazes de descobrir milhões e milhões de novos teoremas (isto é, sentenças válidas numa determinada teoria) de forma autónoma; mas qual o valor dessa matemática e que impacto tem ou poderá ter? Como garantir que esses teoremas gerados não são triviais, desinteressantes ou inúteis? E o que fazer com teoremas que não se compreendem? Que impacto pode ter imenso ruído ou imensos ininteligíveis? Têm sido avançadas diferentes propostas de resolver a questão natural colocada acima. Algumas delas já revelaram falhar. Outras ainda estão a seguir o seu caminho. O objetivo desta tese é dar uma resposta completamente diferente à pergunta e, como prova de conceito, gerar muitos teoremas, novos, inteligíveis e interessantes. De forma simples (a realidade é bastante mais complexa que a descrição que se segue), a resposta que avançamos nesta tese é a seguinte. Vamos construir um plano em que num dos eixos temos teorias e no outro eixo temos teoremas (ie, sentenças válidas sobre determinados objetos em determinada teoria). No início o nosso plano tem apenas alguns pontos (A, B), signi cando que na teoria A o resultado B é verdadeiro. Por exemplo: Teoria de Grupos, É comutativo o grupo em que cada elemento é inverso de si próprio. Agora, o programa, autonomamente veri ca se (X, B) é verdadeiro (onde B é um teorema conhecido xo e X está a percorrer todas as teorias do nosso repositório). Sempre que encontra uma prova para (Q, B), temos um teorema novo, que é totalmente compreensível e familiar, e que (no caso de Q generalizar A) será tão ou mais interessante que o teorema (A, B) original. Por exemplo, ao correr o nosso programa no repositório, imediatamente surge o teorema: Teoria de Semigrupos Inversos, É comutativo o semigrupo inverso em que cada elemento é inverso de si próprio. Acontece que os grupos são uma pequena classe dentro dos semigrupos inversos, uma estrutura que aparece naturalmente na geometria, e o teorema de grupos referido é dado em qualquer curso de teoria de grupos, enquanto o teorema de semigrupos inversos aparentemente nem sequer aparece na literatura. De igual modo, dado o teorema (A, B), podemos procurar teoremas (A, X), em que X está a percorrer teoremas conhecidos do repositório. No caso de se provar (A, P), teremos um teorema famoso P, até então conhecido para a teoria T, e que agora se veri ca ocorrer na teoria A também. Uma vez mais o resultado é familiar, inteligível e novo. Um utilizador que descobre um teorema T numa axiomática A, pode colocar T no nosso sistema que irá procurar pares (X, T), quando X percorre a base de dados de axiomáticas do nosso repositório. Tendo como resposta (A1, T), (A2, T),..., (An, T), o utilizador cará assim a saber que o seu teorema é um fenómeno muito mais geral e portanto pode procurar uma teoria geral Γ que contenha todas as teorias Ai como casos particulares e na qual o seu teorema T ainda seja verdadeiro. Mais interessante ainda, esta busca da teoria Γ pode ser feita autonomamente pelo computador. De forma análoga, um matemático pode ser levado à introdução de uma nova classe A. O nosso sistema vai procurar pares (A, X), onde X são teoremas na base de dados, pelo que poucos minutos depois de ter identi cado a nova classe, o utilizador poderá já ter vários teoremas familiares, possivelmente não triviais e uma base muito mais sólida para prosseguir a sua investigação. Quando antes a introdução de uma nova classe signi cava o início de um longo e penoso caminho a provar novos teoremas, a início elementares, e depois crescentemente complexos, o nosso sistema permite obter um corpo signi cativo de teoremas, podendo alguns ter provas altamente complexas, não obstante soando familiares e compreensíveis. É esta a resposta que esta tese propõe para a pergunta mais natural do momento: como se pode domar, tornar signi cativa e útil, a capacidade ilimitada de gerar novos teoremas dos computadores?
- Finite bases for semigroup varietiesPublication . Pereira, Manuel Jorge Raminhos; Araújo, João; Lee, Edmond W. H.O objetivo deste trabalho é fornecer um atlas das bases de identidades para as variedades geradas por semigrupos e grupos de ordem pequena. Com o propósito de auxiliar os matemáticos que trabalham neste campo a encontrar informações com facilidade, foi implementado um website que executa em segundo plano um conjunto de algoritmos desenvolvidos no âmbito deste trabalho e ainda ferramentas de demonstração automática e construtores de modelos finitos, para que o utilizador tenha um guia automático e inteligente. Por exemplo, o site fornece a primeira lista completa de variedades geradas por semigrupos de ordens iguais ou inferiores a 5, e consegue identificar rapidamente se a variedade gerada por um semigrupo inserido pelo utilizador, mesmo para ordens bastante superiores, coincide com uma das 218 variedades presentes na base de dados (atualmente inclui ainda outras 11 variedades geradas por semigrupos de ordens superiores). O site também fornece bases de identidades para classes arbitrariamente grandes de semigrupos, como bandas, ou a identificação dos semigrupos de ordem 6 conhecidos que geram variedades de base não finita. Além desta base de dados, o site propõe ainda uma lista das variedades geradas pelos semigrupos de ordem 6, num total de 414 conjeturas para novas variedades, entre as 463 identificadas neste trabalho e retirando as 49 variedades já conhecidas. O site disponibiliza ainda a informação para variedades geradas pelos grupos de ordens iguais ou inferiores a 255, obtida em resultado do levantamento e análise da literatura existente sobre as variedades geradas por estes grupos, para um total de 7012 grupos. O tratamento da informação recolhida para variedades geradas por grupos foi efetuado em GAP e através do desenvolvimento de algoritmos específicos para grupos comutativos e grupos metabelianos, nomeadamente para obtenção das identidades especificas de cada grupo, quando possível. O site oferece ainda um conjunto de funções sobre semigrupos, como encontrar o mínimo lexicográfico das cópias isomórficas de um dado semigrupo. Em relação à propriedade de base inerentemente não finita, o site pode decidir se um determinado semigrupo finito possui ou não essa propriedade; calcular a decomposição do semigrupo em semireticulados; ou converter a sintaxe da tabela de multiplicação de um semigrupo para utilização no GAP ou num demonstrador automático de teoremas/construtor de modelos finitos. O site fornece algumas outras funcionalidades, como uma ferramenta que gera a tabela de multiplicação de um semigrupo fornecida por uma apresentação em C, onde C ´e qualquer classe de álgebras definida por um conjunto de fórmulas em predicados de primeira ordem. A operação no sentido inverso também está acessível. O site disponibiliza um conjunto de informações e funcionalidades sobre variedades e as suas bases de identidades, como apresentar todas as inclusões entre as variedades da base de dados (variedades que são sub-variedades de outras variedades, que as contem) em formato gráfico, identificar se a variedade gerada por um semigrupo coincide com uma existente na base de dados, ou identificar a variedade cuja base é equivalente ao conjunto de identidades inseridas pelo utilizador. O site consegue ainda listar todas as variedades da base dados cujas bases de identidades implicam ou são implicadas por um conjunto de identidades definidas pelo utilizador. Neste cálculo o site leva em conta o conhecimento prévio de todas as inclusões entre variedades acima referidas para acelerar o cálculo e minimizar o uso do demonstrador automático de teoremas/construtor de modelos finitos. No desenvolvimento deste site foram utilizados: na implementação de algoritmos no servidor, Python, substituído pela versão compilada Cython em todos os cálculos intensivos; no desenvolvimento da interface cliente, JavaScript, JQuery, Ajax, Flask, HTML5, CSS3, Bootstrap e MathJax; em bases de dados relacionais, MySQL e SQLAlchemy; na preparação da informação presente nas bases de dados: GAP-System e em particular os “packages” smallsemi e smallgroups; na demonstração automática de teoremas e construção de modelos finitos, Prover9 e Mace4; na apresentação de diagramas, Graphviz. Foi desenvolvido um extenso conjunto de algoritmos reutilizáveis, para manipulação de variedades, semigrupos e grupos, organizados em bibliotecas, destacando-se: varlib.pyx – Implementa os algoritmos de cálculo intensivo do site, como o algoritmo que encontra o mínimo lexicográfico das cópias isomorfas de um dado semigrupo, ou o que verifica se um dado semigrupo satisfaz a base de identidades de uma das variedades na base de dados, e não satisfaz as identidades que definem as sub-variedades maximais. Por questões de velocidade, não existe nesta biblioteca recurso a demonstradores automáticos de teoremas ou a construtores de modelos finitos, sendo a sua funcionalidade substituída por algoritmos desenvolvidos otimizados para identidades, correndo nesta biblioteca a uma velocidade tipicamente 1000x superior ao mesmo programa em Python interpretado; p9m4tools.py – Implementa os algoritmos que recorrem ao demonstrador automático de teoremas e construtor de modelos finitos, embora em ´ultimo recurso, por questões de desempenho, através da implementação de diversas técnicas de “cache”. Nesta biblioteca estão por exemplo os algoritmos desenvolvidos para obter um semigrupo e a sua tabela de multiplicação a partir de uma apresentação, e filtrar as variedades cuja bases de identidades implicam, são implicadas por, ou são equivalentes a um conjunto de identidades entradas pelo utilizador; vartools.py – Implementa rotinas de menor exigência computacional, como a interpretação da entrada de dados do utilizador (por exemplo tabelas de multiplicação em diversos formatos à escolha do utilizador) e a formatação dos dados a apresentar, quer em texto que de forma gráfica. Esta biblioteca inclui ainda diversos algoritmos sobre semigrupos, como a decomposição em semireticulados. Este trabalho também contribui para a extensão da base de dados de variedades conhecidas: existem 28634 semigrupos de ordem 6, considerados equivalentes quando isomorfos ou anti-isomorfos. As variedades de 2035 desses semigrupos não coincidem com nenhuma variedade conhecida gerada por semigrupos de ordem até 5. Neste projeto, com base no teorema de Birkhoff e aplicando novos algoritmos de computador e uma ferramenta de demonstração automática de teoremas/construtor de modelo finitos, foi possível dividir esses 2035 semigrupos em 463 conjuntos de semigrupos que satisfazem as mesmas identidades, correspondendo a 414 novas variedades propostas (dado que são já conhecidas 45 variedades de base finita e 4 variedades de base não finita, geradas por semigrupos da ordem 6). Além disso, as identidades candidatas para a bases de identidades para todas estas novas variedades também são propostas e apresentadas nesta tese, acompanhadas por todas as tabelas de Cayley e os IDs no “package” GAPs smallsemi correspondentes, para cada conjunto de semigrupos encontrados que geram a mesma variedade conjeturada. As provas dessas novas variedades representam problemas em aberto e um desafio para todos os matemáticos nesta área. A mesma metodologia pode ser utilizada para encontrar novas variedades candidatas geradas por semigrupos de ordem 7 ou maior (no âmbito deste trabalho foram encontrados 73807 semigrupos não isomorfos de ordem 7 cujas variedades não coincidem com as variedades registadas na base de dados do site). Esta tese começa com um artigo 1 de pesquisa sobre variedades de semigrupos que contém a maior parte do conteúdo matemático desta tese. Este trabalho representa diversas contribuições para o campo do estudo das variedades de semigrupos: pela primeira vez foi reunida a informação dispersa sobre todas as variedades geradas por semigrupos de ordem igual ou inferior a 5, e relativa aos grupos de ordem igual ou inferior a 255, sendo apresentada num site de fácil utilização. O site oferece ainda um conjunto de funcionalidades sobre semigrupos e sobre variedades da base de dados, alicerçadas num conjunto de algoritmos desenvolvidos para maximização da performance e integrando uma interface, transparente para o utilizador, com um demonstrador automático de teorema e um construtor de modelos finitos, funcionando em paralelo para resultados mais rápidos. Adicionalmente, este trabalho contribuiu para o enriquecimento da base de dados de variedades geradas por semigrupos, ao propor conjeturas para todas as variedades não conhecidas geradas por semigrupos de ordem 6 e respetivas bases de identidades. As principais limitações deste trabalho estão relacionadas com o fato de alguns dos algoritmos desenvolvidos exigirem uma utilização intensiva de recursos computacionais (memória e processador). Estes algoritmos, ou não são adequados para colocação no site (como a pesquisa de novas variedades e respetivas bases), ou exigem limitações dos parâmetros de entrada (por exemplo o cálculo do mínimo lexicográfico, a geração de semigrupos a partir de apresentações, e a identificação de variedades, estão limitados a semigrupos de ordem inferior ou igual a, respetivamente, 10, 20 e 100). Noutras situações, embora raras, o site pode atingir o limite de memória permitido a cada utilizador. Este trabalho inspirou um alargado conjunto de ideias para trabalho futuro, e a primeira consiste na criação de um “package” GAP. Além de oferecer tudo o que site oferece e sem as limitações de memória e processador do site, o utilizador pode realizar múltiplas operações de forma automática. Na realidade o grosso do trabalho está pronto, já que este “package” se pode materializar apenas com o desenvolvimento de uma pequena camada de interface de comandos GAP, já que todos os algoritmos do site estão em bibliotecas autónomas e prontos para ser invocados por qualquer programa externo (aliás o acesso pelo GAP a rotinas das bibliotecas do site foi testado com sucesso no âmbito deste trabalho). Outras ideias para trabalho futuro passam por estender a procura de variedades `as variedades geradas por semigrupos de ordem 7; melhorar os algoritmos atuais para propor também as identidades que definem as sub-variedades maximais; automatizar a demonstração das variedades conjeturadas; desenvolver uma interface no site que permita a extensão da base de dados com novas variedades pelos matemáticos; aumentar as funcionalidades sobre variedades de grupos; desenvolver novo algoritmo para acelerar o cálculo do mínimo lexicográfico.
- Francy an interactive discrete mathematics framework for GAPPublication . Martins, Manuel Carlos Machado; Araújo, João; Mitchell, James D.; Pfeiffer, MarkusEm Julho de 2014, uma sessão entitulada A Proposal of scalable web framework for running GAP on the cloud foi apresentada no Workshop International em Algebra Computacional em Lisboa. Até ali, a utilizacão do GAP na Web era uma tarefa difícil, e esta apresentação trouxe algumas ideias novas na tentativa de resolver este problema. Foi então que surgiu um pequeno projeto chamado WebGAP. Em 2015, surge o projeto OpenDreamKit. O projecto OpenDreamKit junta universidades de toda a Europa e visa fortalecer a investigação através da disponibilização de uma plataforma colaborativa virtual. Um dos seus objetivos é enriquecer o ecossistema do Jupyter, fornecendo meios de reprodutibilidade na ciência computacional. Em 2017, a package de software para o GAP Jupyter Kernel é finalmente disponibilizada, tornando possível utilizar o GAP num Web Browser, de forma simples e segura. Foi então identificada a falta de uma package de software para o GAP que permitisse criar interfaces gráficas interactivas, que deu origem a uma package de software para o GAP chamada Francy. Francy é uma package de software para o GAP que permite criar interfaces gráficas interactivas facilitando a representação e exploração de estruturas de dados. Francy é uma package independente de qualquer linguagem de programação ou sistema operativo e permite que virtualmente qualquer outra package de software para o GAP seja transformada numa ferramenta interativa, dando representação gráfica a estruturas matemáticas na forma de grafos ou gráficos topológicos.
- Spherical tilings, GeoGebra contributions to their combinatorial and geometrical classificationPublication . Santos, José Manuel dos Santos dos; Breda, Ana Maria Reis d'Azevedo; Araújo, JoãoO objectivo desta tese é de dar um contributo à classificação de pavimentações da esfera, revelando e caracterizando geométrica e combinatoriamente novas famílias. Para realizar este trabalho, partimos do conhecimento teórico existente neste tema e recorremos ao software GeoGebra, usando as suas funcionalidades de geometria interativa e de cálculo algébrico e simbólico, contruindo novas ferramentas especificamente concebidas para a realização deste estudo. O trabalho de investigação desenvolvido integra cinco artigos, dois publicados (ver Capítulos 3 e 4), dois aceites (ver Capítulos 2 e 6) e um submetido (ver Capítulo 5), sendo o primeiro capítulo reservado à introdução. No segundo capítulo apresentamos as ferramentas criadas no GeoGebra, a aplicação dessas ferramentas para obtenção de pavimentações esféricas conhecidas, apresentando ainda ilustrações de alguns exemplos de novas pavimentações da esfera. No capítulo seguinte, uma nova família de pavimentações da esfera, Bp/q ! , p,q ∈" , é apresentada. Esta família contém pavimentações antiprismáticas, obtidas pela ação global de um subgrupo de isometrias esféricas. No Capítulo 4, estudamos a família monoédrica de pavimentações da esfera, P(C,ρ ) , constituída por quatro pentágonos esféricos congruentes não convexos. Neste caso, a família é obtida por uma ação local de um subgrupo de isometrias esféricas aplicadas a um conjunto de arcos esféricos, C , concorrentes em um ponto. No Capítulo 5, são apresentadas propriedades das duas famílias de pavimentações esféricas, P* (C1,τ * ) e P** (C2 ,τ ** ) , correspondentes a pavimentações diédricas por pentágonos esféricos. As características topológicas e combinatórias de cada elemento dessas famílias são também apresentadas. No capítulo seguinte, exploramos as novas pavimentações monoédricas da esfera, H(C3 ,τ ) , por seis hexágonos não convexos e uma nova família de pavimentações monoédricas por seis pentágonos esféricos, P(SC,θ1,θ2 ) , que surge como um caso degenerado associado à família H(C,0) . Finalmente, são expostas algumas conclusões do trabalho desenvolvido e são apresentadas algumas considerações sobre o uso do GeoGebra para o desenvolvimento da investigação em pavimentações esféricas.