Hacer grupos, anillos y campos tienen aplicaciones prácticas en el CS? Si es así, ¿cuáles son?

Question

Esto es UNA cosa acerca de mis estudios de pregrado en ciencias de la computación que no he sido capaz de 'link' en mi vida real (académico y profesional). Casi todo lo que he estudiado, he observado aplicarse (directa o indirectamente) o me ha dado Aha! momentos de la comprensión de los principios detrás de las aplicaciones.

Grupos, Anillos y Campos de tener siempre huían de mí. Siempre pensé que eran útiles (por instinto), pero no pudo ver dónde/cómo. Son sólo conceptos teóricos sin aplicaciones prácticas? Espero que no. Entonces, ¿cuáles son sus aplicaciones, especialmente en el campo de las ciencias de la computación. No importa cómo arcano/remoto de su uso todavía quiero saber.

Answer 1

Si cada segundo o así la memoria de su equipo fueron exterminados completamente limpio, a excepción de los datos de entrada; el reloj; una estática, inmutable programa; y un contador que sólo puede ser 1, 2, 3, 4, o 5, todavía sería posible (dado el tiempo suficiente) para llevar a cabo una arbitrariamente larga de cálculo, como si la memoria no se limpiar cada segundo. Esto es casi seguro que no es cierto si la contador sólo puede ser puesto a 1, 2, 3, o 4. La razón por la 5 es especial aquí es prácticamente la misma razón por la que es especial en el sentido de Galois prueba de el unsolvability de la quintic ecuación.

-Scott Aaronson

Answer 2

Los grupos y los campos, principalmente finito, se utilizan ampliamente en la teoría de la codificación. Muchos de los resultados en la teoría de los números que dan lugar a importantes sistemas de cifrado (por ejemplo, RSA) en realidad puede ser visto resultados en teoría de grupos. Si se incluyen las aplicaciones fuera de informática realmente sería difícil exagerar la importancia de la teoría de grupos. Los grupos están literalmente en todas partes. La teoría del grupo de representaciones por ejemplo, es útil en química (especialmente en la cristalografía).

La razón de la importancia de los grupos es que el modelo de simetría y para los campos, al menos para la teoría de códigos y criptografía, es que codifican muy compleja combinatoria.

Así, en ciencias de la computación, siempre que vea un vídeo en línea, hacer una llamada telefónica, compra algo a través de internet, comprimir un archivo, enviar un correo electrónico, o comunicarse con el Mars Rover de la gran cantidad de grupos y campos se utilizan detrás de las escenas.

Answer 3

Diciendo mi poco y es demasiado largo para caber en un comentario. Me disculpo de antemano acerca de ser un poco hablador. Bueno, este es un soft pregunta, así que la respuesta va a ser suave así.

Varios carteles han puesto de relieve algunas de las aplicaciones tecnológicas de álgebra abstracta. Desde el punto de vista de algebraists estos son excelentes respuestas (sorprendentemente generosamente upvoted en realidad - puede ser el corazón de los profesionales de álgebra abstracta a calentar a estos). Obtendrá respuestas diferentes, si le preguntas a un grupo diferente de personas. Algunos podrían referirse a cómo estructuras algebraicas dar el patio de juegos a los problemas centrales para el estudio de las clases de complejidad de algoritmos. No sé yo?

Me describen dos debates que he tenido que creo que son relevantes para esta pregunta.

Yo una vez charlamos con un profesor en ciencias de la computación. Me sugirió que puede ser que debo complementar nuestra álgebra lineal notas de la conferencia con un capítulo sobre la manera de coordenadas ortogonales transformaciones (rotaciones y tal), se aplican en los gráficos en 3D. Yo había descubierto que los problemas de la tarea en relación con este tema ha motivado a algunos de mis estudiantes. Su respuesta fue que no era clara. La mayoría de los programadores que la universidad produce van a terminar trabajando con los equipos. Su punto era que no es necesario para TODOS los programadores saben acerca de los grupos de rotaciones, porque sólo un pequeño subconjunto del equipo de trabajo en los gráficos en 3D del motor - si es que todos los. En DOS de la época con los canteranos código fue suficiente para que ALGUNOS de los programadores en el equipo para saber que esta adentro hacia afuera. Pero hoy en día una gran cantidad de duro trabajo ha sido "externalizado" a través de un estándar de interfaz para el fabricante de la tarjeta gráfica (así me dijeron). Es cierto que ALGUNOS OTROS, los programadores necesitan saber lo suficiente como para usar la interfaz para un buen efecto.

Estoy pensando que los mismos principios se aplican en otros lugares. No es en absoluto necesario para la mayoría de los programadores para saber sobre campos finitos incluso si están trabajando en un equipo de la creación de aplicaciones en la parte superior de una capa de corrección de errores códigos de y/o módulos criptográficos y protocolos. Sí, estos son fascinantes aplicaciones de álgebra, pero incluso para los chicos una comprensión en profundidad de la álgebra no es una alta prioridad.

Sin embargo, cuando se crea algo nuevo, es obvio que es bueno tener personas en tu equipo, que tienen una comprensión más profunda de los principios subyacentes. Y "profundo" significa algo distinto de lo que significa para los lectores de esta pregunta. Esta es una pons asinorum a la otra discusión que recuerdo. Durante mi breve estancia en telcomm industria conocí a este chico de Nokia-Siemens Networks, me dijeron que es la parte superior de la patente el inventor del equipo de Siemens lado. Yo también lo reconoció como uno de los chicos que compitieron en la OMI para el Oeste de Alemania, al mismo tiempo, he representado a Finlandia. Una modesta tipo que explica la receta de su éxito como "Oh, la mayoría de mis inventos son triviales aplicaciones de la aritmética modular - programadores e ingenieros no lo entiendo". Voy a testificar que su última frase es verdadera. Ellos aprenden sobre el binario mod, y varias reglas a su alrededor, pero no aprenden los bidireccional de potencia de congruencias y no aprender a pensar en términos de los residuos de los anillos de la clase - todos los restos de las divisiones de números enteros. Así que (por estar en el lugar correcto en el momento adecuado) se puede cenar fuera, simplemente porque usted puede trabajar rápidamente con repiten periódicamente, discretas estructuras y patrones.

De nuevo, algo que no todos los CS majors necesita saber, pero "en la tierra de los ciegos tuerto es el rey". <- Lo siento, yo no lo podía resistir. El resultado aquí es que no sabemos qué tipo de ojos va a ser útil.

Así que la razón para aprender un poco sobre álgebra abstracta no es su utilidad en cualquier conjunto dado de aplicaciones. Supongo que (yo realmente no creo que yo soy el hombre correcto para decir esto) es más una cuestión acerca de tener más herramientas para poner orden en el caos que rodea a la (actualmente desconocida) tareas que se encuentran en su futuro.

Answer 4

Grupo de teoría ha sido utilizada en física teórica por cerca de 80 años.

Answer 5

Cuando una pieza de hardware de la computadora se comunica con otra pieza se envía una secuencia de 1s y 0s de longitud arbitraria, y claro está, existe la posibilidad de un error. Para verificar errores, el hardware hace algunos símbolos de anillo de la teoría. Formalmente, esto se llama Comprobación de Redundancia Cíclica (CRC), y es un fiel generalización de la "dígito de verificación" todos aprendimos en la escuela. Sin embargo, se puede detectar $n$ errores en lugar de sólo uno (o más bien, no-igual-a-cero-mod-($n+1$)-errores en contraposición a un número impar de errores).

Derecho, por lo tanto, el hardware que hace es esto: Hay una cadena fija, digamos $1011$. Cada pieza de hardware conocido a este. A continuación, el equipo quiere que para enviar una cadena, que tiene una longitud arbitraria. Por ejemplo, $11111001$. El hardware, a continuación, en repetidas ocasiones realiza un XOR con esta cadena, que es algo que el hardware puede hacer muy rápido (que es uno de los beneficios de la convención). $$\begin{align*} Y 11111001\\ &1011\\ y-----\\ \rightarrow & 01001001 \end{align*}$$ Ahora tenemos una nueva cadena, $1001001$. Así XOR de nuevo, varias veces hasta que nos vemos obligados a parar. $$\begin{align*} Y 1001001\\ &1011\\ y-----\\ \rightarrow & 0010001\\ y-----\\ &10001\\ &1011\\ y-----\\ \rightarrow &111 \end{align*}$$ y tenemos que dejar como $1011$ es de más de $111$, así que no podemos XOR. Si nos terminó con una cadena de longitud inferior a tres, por ejemplo, $11$, a continuación, guardarlo como $011$. El hardware, a continuación, envía la concatenación de la cadena original con la nueva cadena de longitud tres, $11111001111$. La recepción de la pieza de hardware de los recortes de los últimos tres dígitos para obtener la cadena original y realiza las idéntica operación (recuerde: se sabe que la cadena $1011$). Si termina con $111$ las cosas son hunky-dory. De lo contrario, no es un error, por lo que se le pide para enviar la cadena de nuevo.

Este sistema tiene un número de ventajas. Por ejemplo, XOR se realiza de forma rápida por el hardware y las cadenas pueden ser de longitud ilimitada. Así que, esto es realmente utilizado por el hardware.

A la derecha, ahora para las matemáticas! Lo que está pasando es que estamos viendo en las cadenas de elementos sobre el anillo de $\mathbb{F}_2[x]$, por lo que nuestro ejemplo string $11111001$ es el polinomio $x^7+x^6+x^5+x^4+x^3+1$. El hardware es simplemente encontrar el coset representante de este polinomio en el cociente del anillo de $\mathbb{F}_2[x]/(x^3+x^2+1)$, que aquí es de $x^2+x+1$. Simple!

Para el extra matemáticos giro: Esto funciona mejor si la cadena fija corresponde a un polinomio irreducible, entonces el cociente del anillo es en realidad un campo. De lo contrario, hay cero divisores, y cero-divisores significa que los errores no serán recogidos.