Ramo de álgebra teórica da ciência da computação

Eu tenho uma base muito forte em álgebra, a saber

• álgebra comutativa,
• álgebra homológica,
• teoria de campo,
• teoria da categoria,

e atualmente estou aprendendo geometria algébrica.

Sou formado em matemática, com tendência a mudar para a ciência da computação teórica. Tendo em mente os campos acima mencionados, qual seria o campo mais apropriado em ciência da computação teórica para o qual mudar? Ou seja, em qual campo a teoria e a maturidade matemática obtidas pela busca dos campos acima podem ser usadas em proveito próprio?

Houve desenvolvimentos recentes na teoria de tipos dependentes que relacionam sistemas de tipos a tipos de homotopia .

Agora, este é um campo relativamente pequeno, mas há muito trabalho empolgante sendo realizado no momento e potencialmente muitas frutas pendentes, principalmente na portabilidade de resultados de topologia algébrica e álgebra homológica e formalização da noção de tipos indutivos superiores .

A geometria algébrica é muito usada na teoria da complexidade algébrica e, em particular, na teoria da complexidade geométrica. A teoria da representação também é crucial para o último, mas é ainda mais útil quando combinada com geometria algébrica e álgebra homológica.

Seu conhecimento da teoria de campo seria útil na criptografia, enquanto a teoria da categoria é muito usada na pesquisa de linguagens de programação e sistemas de digitação, os quais estão intimamente relacionados aos fundamentos da matemática.

A teoria de campos e a geometria algrebraica seriam úteis em tópicos relacionados a códigos de correção de erros, tanto no cenário clássico quanto no estudo de códigos decodificáveis ​​localmente e na decodificação de listas. Eu acredito que isso remonta ao trabalho nos códigos de Reed-Solomon e Reed-Muller, que foram generalizados em códigos geométricos algébricos. Veja, por exemplo, este capítulo deste livro sobre a visão da teoria clássica de codificação dos códigos geométricos algébricos, esta breve pesquisa sobre códigos decodificáveis ​​localmente e este famoso artigo sobre códigos de Reed-Solomon e decodificação de lista e, mais geralmente, códigos de geometria algébrica.

Existem alguns problemas na teoria do aprendizado computacional, aprendizado de máquina e visão computacional que podem ser resolvidos usando álgebra comutativa e geometria algébrica. Por exemplo, a convergência do algoritmo de Propagação de Crenças, um algoritmo de transmissão de mensagens para inferência bayesiana, pode ser formulada em termos de caracterizar a variedade afim de sistemas de equações polinomiais .

Você já pensou em olhar para álgebra computacional? Axioma é um sistema de álgebra computacional em que o sistema de tipos é modelado após a Teoria da categoria (ou Álgebra universal, dependendo da sua exibição). Existem mais dois derivados do Axiom FriCAS e do OpenAxiom .

Se você estiver interessado em Teoria das Categorias, o sistema de tipos pode ser uma coisa a se considerar.

No Axiom, todo "item" (por exemplo, "1", "5 * x ** 2 + 1") é um elemento de um Domínio. Um "Domínio" é um objeto Axiom declarado membro de uma Categoria específica (por exemplo, Número Inteiro, Polinômio (Inteiro). Uma Categoria Axiom é um objeto Axiom declarado como membro do símbolo distinto "Categoria" (por exemplo, Anel, Polinômio (R, E, V)).

Há uma estrutura de herança para a herança múltipla entre categorias. por exemplo, a categoria Monad herda de SetCategory, Monoid de Monad, Grupo de Monoid, etc., etc.

Há também um polimorfismo de ordem superior, um pouco como os genéricos em Java.

Várias ações dentro do Axiom podem ser vistas como Functors, mas isso seria bastante para se fazer aqui!

Se você deseja apenas usar o Axiom sem se preocupar com a Teoria das Categorias, como um usuário final típico, um sistema de computação simbólico é exatamente o software certo para analisar álgebras individuais.

$L \subseteq X^{\ast}$

As pessoas a seguir usaram essa visão algébrica no caso de idiomas regulares: Samuel Eilenberg, sobre Teoria dos Autômatos, Jean Berstel , Jean-Eric pin , Marcel Schützenberg e Krohn-Rhodes Theory .

Também há álgebra não trivial envolvida no trabalho em torno da conjectura de Cerny , a maioria é bastante combinatória. Mais recentemente, porém, eu vi mais trabalhos com álgebra linear, teoria dos anéis e teoria das representações, procurando trabalhar com Benjamin Steinberg e Jorge Almeida .

A propósito, você pode se dar muito bem nessas áreas com a teoria Semigrupo, Monóide e Grupo, mas a teoria da categoria e a teoria da homotopia não são muito usadas nessa área. Mas talvez seja interessante notar que S. Eilenberg foi um dos pais fundadores da Teoria das Categorias, apesar disso antes de se envolver na Teoria dos Autômatos.

A tese de Brent Yorgey , embora ainda seja apenas um rascunho, faz um trabalho incrível ao explicar por que seus interesses são relevantes para o TCS.

Aqui está a palestra de Joyal , em abril passado, sobre material relacionado.

Não sei se você considerou a indústria, mas a empresa Ayasdi está fazendo um trabalho incrível aplicando muita homotopia e outros métodos topológicos aplicados na ciência de dados. Eles misturam muita teoria com aplicações. Basicamente, para ver o que eles estão fazendo, consulte o site do Stanford Comptop. (A maioria das pessoas veio de lá).

Além do que todo mundo disse (acho que a maior aplicação desses ramos é de fato nos sistemas de tipos):

• A teoria da rede e as ordens parciais em geral são aplicadas bastante para análise do comportamento de sistemas distribuídos e para análise de fluxo de dados em compiladores.
• Também vi conexões Galois aplicadas ao aprendizado de máquina (em particular a classificação de texto: a conexão Galois entre subconjuntos de vértices esquerdo e direito de um gráfico bipartido de documento / palavra permitiu acelerar drasticamente um algoritmo).

As conexões entre Álgebra e Ciência da Computação Teórica são muito fortes. Nic Doye já mencionou álgebra computacional, mas não incluiu explicitamente a teoria dos sistemas de reescrita, que é uma parte essencial da álgebra computacional, com aplicações em resolução automática de equações e raciocínio automático. Os sistemas de reescrita de cordas são uma subárea importante, com aplicações na teoria de grupos computacionais. Veja o livro "String Rewriting Systems", de Ronald Book e Friedrich Otto, por exemplo.

Há também a conexão entre a teoria dos grafos e a álgebra, que inclui, por exemplo, a bem desenvolvida teoria espectral de grafos e redes complexas, e também a teoria das simetrias de grafos (graxas de Cayley, grafos transitivos por vértices e outros tipos de grafos simétricos). , que são muito usados ​​como modelos para redes de interconexão em computadores paralelos). Confira o livro "Algebraic Graph Theory", de Chris Godsil e Gordon Royle, para uma visão geral dos diferentes tópicos.

Confira a situação na visão computacional. Existem muitos tópicos, em particular, do tipo algorítmico, para os quais as três primeiras áreas listadas são muito úteis.