El álgebra es increíblemente útil en ciencias de la computación. Voy a prefacio mi respuesta con mi opinión: estoy de ver una buena porción de ciencias de la computación como una rama de las matemáticas. Así que mi respuesta va a ser bastante amplio. Tenga en cuenta que mi opinión es que no todo el mundo comparte.
La Combinatoria algebraica y la Teoría de grafos: Recuerdo del Teorema de Cayley del grupo de teoría, que afirma que cada grupo es el subgrupo de algún grupo de Simetría. Es decir, cada grupo es una permutación de grupo. Inmediatamente, esto motiva el estudio de la combinatoria algebraica. Grupo de acciones se utilizan para el estudio de las simetrías, o automorfismos, de los objetos matemáticos. Informalmente, un grupo de acción es un proceso dinámico de un objeto, de que las particiones de sus miembros en conjuntos que llamamos órbitas. El estudio de la estructura y la cantidad de estas órbitas de los rendimientos importante de la combinatoria de los resultados. Usted ha visto probablemente el Diedro grupo, que es el automorphism grupo de el Ciclo de la gráfica. En general, la búsqueda de la plena automorphism grupo de un objeto (como un gráfico) no es un ejercicio trivial.
Hay varias aplicaciones que vienen a la mente. La primera es Polya Enumeración de la Teoría. Dado un objeto matemático (como un gráfico), tenemos el color de los vértices (esta no es necesariamente apropiado para colorear, en el sentido de que dos vértices adyacentes pueden recibir el mismo color). A continuación, dado que algunos de los subgrupos $H$ de automorfismos (tales como las rotaciones de un collar), cuántos colores existen? Es decir, dos colorantes son equivalentes si pertenecen a la misma órbita bajo la acción de $H$. Polya enumeración de estudio de la teoría de estos tipos de problemas. Si su combinatoria es débil (e incluso si no lo es), Loehr del Bijective la Combinatoria de texto es un recurso excelente.
En algebraicas teoría de grafos, es común para examinar el Grafo de Cayley de un grupo. Dado un grupo de $G$ y un conjunto $S$, el Grafo de Cayley $X(G, S)$ tiene el vértice set $G$, y dos elementos de $g, h$ están conectados por una arista si $hg^{-1} \in S$. Intuitivamente, el Grafo de Cayley nos dice que si un elemento en $S$ puede ser utilizado para llevarnos de $g$$h$. Podemos examinar una relacionada con el gráfico de transposiciones de $\text{Sym}(n)$, y el apalancamiento de los algoritmos de la teoría de grafos para determinar si las transposiciones generar $\text{Sym}(n)$. Me tapa algo de esto en mis notas de la conferencia para la Teoría de la Computación (http://people.math.sc.edu/mlevet/Lecture_Notes.pdf). Godsil y Royle el texto sobre Algebraicas Teoría de grafos es una visión más integral del recurso.
Un tercer pensamiento que viene a la mente es el estudio de la gráfica de homomorphisms. En particular, una adecuada coloración de un grafo es un grafo homomorphism. Si el gráfico de $X$ ha cromática número $c$, entonces existe un gráfico homomorphism $\phi : X \to K_{c}$. Así que hay una conexión directa a la teoría de la complejidad aquí, como la gráfica de colorear es NP-Duro. Satisfacción de restricciones problemas son generalizaciones de este, donde estudiamos homomorphisms de estructuras relacionales de rango finito. Satisfacción de restricciones problemas surgen con frecuencia en la inteligencia artificial. Técnicas algebraicas (concedido, no de alto nivel de álgebra técnicas) surgen en el estudio de los Csp. La Dicotomía Conjetura afirma que todos los CSP es en $P$ o NP-Completo. Dimitry Zhuk recientemente presentó sus resultados en una conferencia de dos semanas en la Vanderbilt en septiembre, resolver la conjetura en la afirmativa. Mientras que él no ha presentado una ponencia, la gente de allí eran relativamente convencido de sus resultados (incluyendo la lgica en mi colegio, que era un Tarski estudiante).
La Teoría de autómatas: El conjunto de regular idiomas formas un Kleene semi-anillo sobre las operaciones de unión de conjuntos (suma) y la concatenación (multiplicación). La noción de la derivada. Ver el dawes de aspect security Derivados. Podemos aprovechar este hecho para el diseño de un lineales algebraicas algoritmo (véase el dawes de aspect security Método Algebraico) para convertir una FSM para una expresión regular. (Yo también cubrir esta en mis notas.)
La Teoría de la complejidad: Babai del reciente resultado en el Gráfico Isomorfismo problema es (o debería ser) el niño del cartel para el álgebra en CS. Él utiliza una gran cantidad de técnicas tales como el grupo de acciones y la teoría de la representación para el estudio de problemas como el Gráfico de Isomorfismo y Grupo de Isomorfismo. Respecto al Grupo de Isomorfismo problema, es indecidible en el caso general. Para grupos finitos, la mejor bound es algo como $n^{\text{log}(n)}$ (que es fácil de obtener, simplemente mostrando que cada grupo finito tiene un set de generación de energía con en la mayoría de las $\text{log}_{2}(n)$ generadores). Para abelian grupos, el Grupo de Isomorfismo tiene un $O(n)$ tiempo de solución. Para la solución de los grupos, la $n^{\text{log}(n)}$ unido ha sido relativamente intacto. Babai y Qiao presentó un polinomio tiempo isomorfismo de prueba para los grupos con abelian Sylow torres. Al mejor de mi conocimiento (que es limitado), esta es la clase más grande de solucionable grupos hasta la fecha con un polinomio de tiempo isomorfismo de prueba.
Muchas de las técnicas de Babai usos son muy fuertes manos. Si estos tipos de problemas de captar su interés, me podría pasar algún tiempo en la teoría de la representación. Creo que un asa sólida en la teoría de grupos (comodidad con los Teoremas de Sylow) y el resumen de álgebra lineal, junto con la motivación, es suficiente para recoger un libro en el área. Hay varios libros sobre Teoría de la Representación a partir de una combinatoria perspectiva. Sagan del texto en el Grupo Simétrico es un texto que viene a la mente. Babai también imparte clases de Algoritmos en Grupos Finitos, que se puede encontrar en su página de inicio. Computacional Teoría de Grupo es la clave de la frase, si usted decide mirar en esta área de más.
La criptología, la Teoría de la Codificación, Computacional y Teoría de números: Estos son los más obvios, y se han cubierto bastante bien.
