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

33

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?

spaceman_spiff
fonte
1
O estudo de campos é considerado parte da álgebra? Há alguns em math.se que pensam que não.
alancalvitti
1
É oferecido em muitos institutos aqui como curso de segundo nível álgebra e muitos livros famosos sobre álgebra como dummit e álgebra abstrata do foote contém material significativo na teoria Arquivado ...
spaceman_spiff

Respostas:

24

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.

Joshua Grochow
fonte
15

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.

Martin Berger
fonte
11

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.

Sasho Nikolov
fonte
7

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 .

Carlos Eduardo Cancino Chacón
fonte
6

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.

Nic Doye
fonte
5

LX

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.

StefanH
fonte
Também poderia ser interessante dar uma olhada nos idiomas das árvores, em vez dos idiomas das palavras. O problema aberto de longa data é caracterizar o poder expressivo da lógica de primeira ordem nas árvores em termos de algum objeto algébrico associado a ela (mencionado em "Alguns problemas abertos em autômatos e lógicos" no ACM SIGLOG News). Para uma leitura mais aprofundada, vou recomendar trabalhos de Mikołaj Bojańczyk e Howard Straubing.
Bartosz Bednarczyk
4

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.

Chad Brewbaker
fonte
12
Não sei quais são os costumes aqui, mas no Stack Overflow, essa resposta provavelmente será excluída como resposta apenas por link muito em breve. Você pode fornecer um resumo de como o link responde à pergunta, e não apenas o que faz? Os links tendem a quebrar com o tempo e, sem o link, sua resposta seria quase inútil.
Palec 23/09/19
1
Não se preocupe. Escrevi um lembrete para atualizá-lo com seu rascunho final.
Chad Brewbaker
4
@ChadBrewbaker Mas, ainda assim, sua resposta é essencialmente apenas dois links. Mesmo se você prometer manter esses links atualizados (que é um objetivo nobre e muito apreciado, mas certamente fadado ao fracasso), é uma resposta ruim.
David Richerby
3

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á).

mathDR
fonte
2

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).
jkff
fonte
1

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.

Manolito Pérez
fonte
0

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.

Martin Peters
fonte