Rama orientada al álgebra de la informática teórica

33

Tengo una base muy fuerte en álgebra, a saber

  • álgebra conmutativa,
  • álgebra homológica,
  • teoría de campo,
  • teoría de la categoría,

y actualmente estoy aprendiendo geometría algebraica.

Soy un experto en matemáticas con una inclinación a cambiar a la informática teórica. Teniendo en cuenta los campos mencionados anteriormente, ¿qué campo sería el campo más apropiado en informática teórica al cual cambiar? Es decir, ¿en qué campo se puede utilizar la ventaja teórica y matemática obtenida al seguir los campos anteriores?

spaceman_spiff
fuente
1
¿El estudio de los campos se considera parte del álgebra? Hay algunos en math.se que piensan que no.
alancalvitti
1
Se ofrece en muchos institutos aquí como segundo curso de nivel de álgebra y muchos libros famosos sobre el álgebra como Dummit y el álgebra abstracta de Foote contiene material significativo en la teoría Archivado ...
spaceman_spiff

Respuestas:

24

La geometría algebraica se usa mucho en la teoría de la complejidad algebraica y, en particular, en la teoría de la complejidad geométrica. La teoría de la representación también es crucial para este último, pero es aún más útil cuando se combina con geometría algebraica y álgebra homológica.

Joshua Grochow
fuente
15

Su conocimiento de la teoría de campo sería útil en criptografía, mientras que la teoría de categorías se usa mucho en la investigación sobre lenguajes de programación y sistemas de mecanografía, los cuales están estrechamente relacionados con los fundamentos de las matemáticas.

Martin Berger
fuente
11

La teoría de campo y la geometría algrebraica serían útiles en temas relacionados con los códigos de corrección de errores, tanto en el entorno clásico como en el estudio de códigos decodificables localmente y decodificación de listas. Creo que esto vuelve a funcionar en los códigos Reed-Solomon y Reed-Muller, que luego se generalizó a los códigos geométricos algebraicos. Vea, por ejemplo, este capítulo del libro sobre la visión de la teoría de codificación clásica de los códigos geométricos algebraicos, esta breve encuesta sobre códigos decodificables localmente y este famoso artículo sobre la decodificación de listas de Reed-Solomon y, más en general, los códigos de geometría algebraica.

Sasho Nikolov
fuente
7

Hay algunos problemas en la teoría del aprendizaje computacional, el aprendizaje automático y la visión por computadora que se pueden resolver utilizando álgebra conmutativa y geometría algebraica. Por ejemplo, la convergencia del algoritmo de Propagación de creencias, un algoritmo de paso de mensajes para la inferencia bayesiana, se puede formular en términos de caracterizar la variedad afín del sistema de ecuaciones polinomiales .

Carlos Eduardo Cancino Chacón
fuente
6

¿Has pensado en mirar álgebra computacional? Axiom es un sistema de álgebra computacional en el que el sistema de tipos se basa en la teoría de categorías (o álgebra universal, según su punto de vista). Hay otros dos derivados de Axiom FriCAS y OpenAxiom .

Si está interesado en la teoría de categorías, entonces el sistema de tipos puede ser una cosa a tener en cuenta.

En Axiom, cada "elemento" (por ejemplo, "1", "5 * x ** 2 + 1") es un elemento de un Dominio. Un "Dominio" es un objeto Axiom declarado miembro de una Categoría particular (por ejemplo, Entero, Polinomial (Entero). Una Categoría Axiom es un objeto Axioma declarado miembro del símbolo distinguido "Categoría" (por ejemplo, Anillo, Polinomio (RVDO)).

Hay una red de herencia para la herencia múltiple entre las Categorías. Por ejemplo, la categoría Monad hereda de SetCategory, Monoid de Monad, Group de Monoid, etc., etc.

También hay un polimorfismo de orden superior, un poco como Generics en Java.

Varias acciones dentro de Axiom se pueden ver como Functores, ¡pero eso sería bastante para entrar aquí!

Si solo desea utilizar Axiom sin preocuparse por la teoría de categorías, como un usuario final típico, entonces un sistema de cálculo simbólico es exactamente el software adecuado para analizar álgebras individuales.

Nic Doye
fuente
5

LX

Las siguientes personas han usado esta visión algebraica en el caso de los idiomas regulares: Samuel Eilenberg sobre Automata Theory, Jean Berstel , Jean-Eric pin , Marcel Schützenberg y Krohn-Rhodes Theory .

También hay álgebra no trivial involucrada en el trabajo en torno a la conjetura de Cerny , la mayor parte es bastante combinatoria. Pero más recientemente, he visto más cosas sobre el álgebra lineal, la teoría de los anillos y la teoría de la representación, espero trabajar con Benjamin Steinberg y Jorge Almeida .

Por cierto, puedes llegar bastante bien en estas áreas con la teoría de Semigrupo, Monoide y Grupo, pero la teoría de Categoría y la Teoría de la Homotopía no se usan tanto en esta área. Pero tal vez sea interesante notar que S. Eilenberg fue uno de los padres fundadores de la teoría de la categoría, a pesar de que esto fue antes de involucrarse en la teoría de los autómatas.

StefanH
fuente
También podría ser interesante echar un vistazo a los lenguajes de árbol, en lugar de los lenguajes de palabras. El problema abierto de larga data es caracterizar el poder expresivo de la lógica de primer orden en los árboles en términos de algún objeto algebraico asociado con él (mencionado en "Algunos problemas abiertos en autómatas y lógica" en ACM SIGLOG News). Para leer más, recomendaré artículos de Mikołaj Bojańczyk y Howard Straubing.
Bartosz Bednarczyk
4

La tesis de Brent Yorgey , aunque todavía es solo un borrador, hace un trabajo increíble al explicar por qué sus intereses son relevantes para TCS.

Aquí está la charla de Joyal en abril pasado sobre material relacionado.

Chad Brewbaker
fuente
12
No estoy seguro de cuáles son las costumbres aquí, pero en Stack Overflow esta respuesta probablemente se eliminará como respuesta de solo enlace muy pronto. ¿Podría proporcionar un resumen de cómo el enlace responde a la pregunta, no solo de que lo hace? Los enlaces tienden a romperse con el tiempo y sin el enlace, su respuesta sería casi inútil.
Palec
1
No te preocupes Me escribí un recordatorio para actualizarlo con su borrador final.
Chad Brewbaker
44
@ChadBrewbaker Pero, aún así, su respuesta es esencialmente solo dos enlaces. Incluso si promete mantener esos enlaces actualizados (lo cual es un objetivo noble y muy apreciado, pero seguramente condenado al fracaso), es una respuesta pobre.
David Richerby
3

No sé si ha considerado la industria, pero la compañía Ayasdi está haciendo un trabajo increíble aplicando mucha homotopía y otros métodos topológicos aplicados dentro de la ciencia de datos. Combinan mucha teoría con aplicaciones. Básicamente, para ver en qué andan, mire el sitio web de Stanford Comptop. (La mayoría de la gente vino de allí).

MathDR
fuente
2

Además de lo que todos los demás dijeron (supongo que la mayor aplicación de estas ramas es en los sistemas de tipos):

  • La teoría del enrejado y las órdenes parciales en general se aplican bastante para el análisis del comportamiento de los sistemas distribuidos y para el análisis del flujo de datos en los compiladores.
  • También vi las conexiones de Galois aplicadas al aprendizaje automático (en particular la clasificación de texto: la conexión de Galois entre subconjuntos de vértices izquierdo y derecho de un gráfico bipartito de documento / palabra permitió acelerar drásticamente un algoritmo).
jkff
fuente
1

Las conexiones entre Álgebra y Ciencias de la Computación Teórica son muy fuertes. Nic Doye ya mencionó Álgebra de computadora, pero no incluyó explícitamente la teoría de los sistemas de reescritura, que es una parte esencial de Álgebra de computadora, con aplicaciones en resolución automática de ecuaciones y razonamiento automático. Los sistemas de reescritura de cadenas son una subárea importante, con aplicaciones en la teoría de grupos computacional. Consulte el libro "Sistemas de reescritura de cuerdas", de Ronald Book y Friedrich Otto, por ejemplo.

También existe la conexión entre la teoría de grafos y el álgebra, que incluye, por ejemplo, la teoría espectral bien desarrollada de gráficos y redes complejas, y también la teoría de simetrías de grafos (grafos de Cayley, grafos transitivos de vértices y otros tipos de grafos simétricos). , que se utilizan mucho como modelos para redes de interconexión en computadoras paralelas). Consulte el libro "Algebraic Graph Theory", de Chris Godsil y Gordon Royle, para obtener una visión general de los diferentes temas.

Manolito Pérez
fuente
0

Echa un vistazo a la situación en visión artificial. Hay muchos temas, en particular, de tipo algorítmico, para los cuales las tres primeras áreas que enumera son muy útiles.

Martin Peters
fuente