Álgebra abstracta y computación paralela

Question

Recientemente he estado aprendiendo un poco acerca de la computación paralela. Dos cosas que he aprendido recientemente acerca de Reducir y Análisis.

Donde Reducir se define como la 2-Tupla de un Conjunto de elementos y una operación binaria que es asociativa.

Scan se define como una 2-Tupla de un conjunto de elementos y una operación binaria que es asociativa y que este par tiene una identidad.

Así que un análisis es esencialmente un Grupo. Ahora yo no he visto mucho más en esto, pero me preguntaba si alguno de ustedes puede saber si esta idea de que la computación paralela de obras en conjuntos de información con el binario (o en realidad cualquier función asociativa) operaciones y aplicar los principios de álgebra abstracta?

Answer 1

Reduce califica como un semigroup, y Scan es un monoid (un monoid es un semi-grupo con una identidad).

Tampoco es un grupo, que es, esencialmente, un monoid en el que el inverso de cada elemento en el "monoid" también está en el "monoid".

Echa un vistazo a los enlaces de las entradas en la Wikipedia para tener una idea de las propiedades compartidas por semigroups, y los compartidos por monoids.

Answer 2

Tal vez no es sorprendente que este tema viene una vez cada tanto, en la Haskell mundo. Yo no soy para mantener el ritmo, pero recientemente me encontré con esta entrada de blog donde una optimización de un algoritmo de aprendizaje de máquina se describe el uso de un monoid, un grupo y un espacio vectorial.

Usted también puede encontrar esta respuesta de stackoverflow interesante.

Estoy de inserción mi cerebro a ver si puedo recordar las palabras clave adecuadas para encontrar un documento presentado a un CS de la conferencia hace un par de años con este tema; es de esperar que voy a editar más tarde.

Answer 3

Creo que puede interesarle observar los enfoques del modelado formal de sistemas concurrentes conocidos como cálculo de procesos o álgebras de procesos . Véase, por ejemplo, "Una breve historia del álgebra de procesos" (JCM Baeten, Theoretical Computer Science, Volumen 335, números 2-3, 23 de mayo de 2005, páginas 131-146).