Álgebra abstrata para cientistas da computação teóricos

19

Eu tenho uma graduação razoável em matemática, mas nunca me senti 100% à vontade com álgebra abstrata (matemática de grupos, anéis, campos etc.). Eu acho que isso foi parcialmente porque eu precisava ver aplicativos e qualquer um que eu pudesse encontrar estava na física, não no CS. Como meu interesse é realmente CS, existem materiais disponíveis agora (rascunhos on-line, notas de aula, vídeos, livros) que cobrem álgebra abstrata do ponto de vista das aplicações em CS e, particularmente, em algoritmos / teoria? Fico feliz que essas aplicações sejam inteiramente teóricas, mas não devem assumir nenhum conhecimento pré-existente de álgebra abstrata.

Tenho certeza de que, se esses recursos existissem, eles seriam apreciados por um grande número de pesquisadores de CS.

Majid
fonte
4
O stackexchange oferece muitas perguntas "relacionadas" às suas na barra lateral direita. Por favor, leia-os primeiro, em particular estruturas algébricas em Ciência da Computação .
precisa
11
@UdayReddy Thanks. Estou lendo esses e alguns dos links têm coisas boas neles. No entanto, idealmente, estou procurando um curso de aula intitulado "Uma introdução à álgebra abstrata para cientistas da computação teórica" ​​(como um exemplo fictício aleatório), em vez de uma lista de resultados de CS em que a álgebra abstrata foi crucial. Meu interesse é realmente por algoritmos / teoria e longe da teoria das categorias, por exemplo.
Majid

Respostas:

17

Você pode tentar as notas do curso de Madhu Sudan: Álgebra e Computação

arnab
fonte
Isso responde muito bem à pergunta. É uma pena que os cursos de "Matemática para Ciência da Computação", como o 6.042 do MIT, não pareçam cobrir nenhuma álgebra abstrata. Pelo menos não os que eu já vi.
Majid
11

Um caminho possível para a álgebra abstrata pode ser examiná-la do ponto de vista da criptografia, que trata de algoritmos em campos finitos. Campos são anéis e campos também são dois grupos acoplados por leis simples. A teoria dos campos usa espaços vetoriais em posição de destaque (teoria de Galois), portanto esse ângulo deve cobrir muita álgebra abstrata. O livro

Introdução Computacional à Teoria dos Números e Álgebra por V. Shoup

poderia, portanto, ser de interesse.

Minha recomendação pessoal seria ignorar aplicativos e estudar um texto básico de matemática para graduação em álgebra abstrata. Não há escassez deles. Apenas confie que todo esse material é útil e que o uso se revelará mais facilmente quando você tiver uma compreensão básica do material.

A álgebra mais básica é construtiva e você pode facilmente implementar conceitos básicos para entender melhor, por exemplo, algoritmos que verificam se uma tabela de multiplicação é um grupo, um solucionador de equações em um grupo, um programa que verifica se duas estruturas algébricas são isomórficas etc. Esses problemas têm soluções de força bruta que são fáceis de implementar, mas lentas. Quanto mais você aprende sobre álgebra, mais atalhos algorítmicos você pode criar, para acelerar seus programas. Por exemplo, os famosos testes de primalidade Miller-Rabin e AKS .

Martin Berger
fonte
1

Confira este livro de Rudolf Lidl e Harald Niederreiter: Introdução aos campos finitos e suas aplicações (2ª edição, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948

Citando a descrição do livro na Amazônia: "A teoria dos campos finitos é um ramo da álgebra moderna que vem à tona nos últimos anos por causa de suas diversas aplicações em áreas como combinatória, teoria de codificação, criptologia e o estudo matemático de circuitos de comutação. . "

Leandro Zatesko
fonte
-1

Além da criptografia, uma aplicação prática muito agradável de álgebra em ciência da computação talvez seja a implementação de frações, em que numerador e denominador são de um tipo integral ou "grande inteiro" e o comprimento da codificação é pequeno, reduzindo frações (ou seja, fatorando o maior divisor de numerador e denominador).

No que diz respeito aos tipos de dados "grande número inteiro", um resultado interessante é o chamado "teorema do restante chinês", que permite a paralelização de operações inteiras quando a representação como fatores primos dos argumentos é conhecida.

Além disso, a maioria das coisas encontradas na álgebra pode ser esteticamente agradável (apenas um ponto de vista pessoal).

user13407
fonte
2
Não vejo como isso resolve a questão?
András Salamon