Un algoritmo o una expresión algebraica puede representarse visualmente a través de un Grafo de Flujo de Señales (SFG, por sus siglas en inglés). En este capítulo, vamos a:

• Ilustrar cómo se ve un grafo de flujo de señales.
• Definir en detalle un grafo de flujo de señales y sus componentes.
• Construir un grafo de flujo de señales para la serie de Fibonacci.

¿Cómo se ve un grafo de flujo de señales?

Consideremos un algoritmo que toma dos variables, digamos $a$ y $b$, como entradas y produce su suma, denotada por $y$, como salida:

Aquí, $y$ es la variable que representa la suma de $a$ y $b$.

Ejemplo:

La operación $y=a+b$ puede representarse visualmente de la siguiente manera:

o, si la operación no queda clara por el contexto, podemos ilustrarla explícitamente, como en:

Esta representación se llama Grafo de Flujo de Señales (SFG). Un grafo de flujo de señales es una representación visual de un algoritmo que toma varias entradas (aquí, $a$ y $b$) y produce las salidas correspondientes (aquí, $y$). Ahora examinaremos los componentes de un SFG.

Componentes de un SFG

Un grafo de flujo de señales se compone principalmente de nodos y aristas, donde los nodos representan variables y se representan como puntos, y las aristas son segmentos de línea que conectan dos nodos cualesquiera. En el siguiente SFG, hay tres nodos, $a$, $b$ y $y$. También hay dos aristas: una que conecta el nodo $a$ con el nodo $y$, y otra que conecta el nodo $b$ con el nodo $y$.

El nodo $a$ y el nodo $b$ se denominan nodos de entrada, y $y$ se denomina nodo de salida.

Un nodo de entrada solo tiene aristas salientes. Un nodo de salida solo tiene aristas entrantes. Un nodo mixto puede tener tanto aristas entrantes como salientes. En breve veremos ejemplos que incluyen nodos mixtos.

Una arista representa una operación específica. Por ejemplo, en el grafo anterior, si las aristas representan una suma, entonces la variable de salida $y$ está dada por

Si la operación es una comparación, entonces $y$ está dada por

o

dependiendo de la operación de comparación que se utilice.

La flecha en una arista indica su dirección, lo que determina si es una arista entrante o saliente con respecto a un nodo. Si no se especifica ninguna dirección, asumimos una dirección de izquierda a derecha; es decir, la arista sale del nodo de la izquierda y entra al nodo de la derecha.

Un SFG describe cómo interactúan las variables entre sí a través de nodos y aristas.

Un nodo mixto es un nodo que tiene tanto aristas entrantes como salientes, como los nodos $p$ y $q$ en la siguiente ilustración.

Un nodo mixto o un nodo de salida siempre representa el resultado de sus aristas entrantes, dependiendo de las operaciones asociadas a dichas aristas. Consideremos el siguiente SFG:

Aquí, si la operación asociada a las aristas es la suma, entonces

El nodo $p$ es la suma de los valores que llegan de los nodos $a$ y $b$. El nodo $q$ es la suma de los valores que llegan de los nodos $c$ y $d$. Finalmente, el nodo $y$ es la suma de los valores que llegan de los nodos $p$ y $q$.

Aristas Ponderadas

Se le puede asignar un peso a una arista. El peso es un factor que multiplica el valor de un nodo antes de que se aplique la operación asociada a la arista. Veamos el siguiente ejemplo para entender esto.

En el grafo anterior, el peso $3$ multiplica a $a$, y el peso $7$ multiplica a $b$. Se asume que la operación es una suma.

Entonces, la operación de suma produce la salida

Si a una arista no se le asigna ningún peso, entonces se asume que el peso es $1$, lo que significa que el valor del nodo se multiplica por un factor de $1$. Por ejemplo, en el siguiente SFG con la operación definida como suma:

El valor de $y$ está dado por

La resta se puede lograr utilizando pesos negativos en una arista. Por ejemplo, en el siguiente SFG:

El valor de $y$ es

Los grafos de flujo de señales pueden usarse para representar e interpretar una amplia variedad de algoritmos y problemas. Veamos un ejemplo a continuación.

La serie de Fibonacci como un SFG

Consideremos la famosa serie de Fibonacci:

Cada elemento de la serie es la suma de los dos elementos anteriores, siendo el primer y segundo elemento $0$ y $1$ respectivamente.

La secuencia de Fibonacci puede representarse como un SFG en el cual las aristas realizan la operación de suma. Construyamos el SFG de Fibonacci para los elementos hasta el $13$. Sean

Estas dos variables, $a$ y $b$, son los nodos de entrada de nuestro SFG. El siguiente elemento,

puede representarse como:

Para el siguiente elemento,

agregamos dos aristas y un nodo $d$ para obtener:

De manera similar, el nodo $e=c+d=1+2=3$ se representa como:

Continuamos construyendo el SFG hasta llegar al nodo de salida

El SFG anterior puede extenderse aún más para alcanzar cualquier elemento $n^{th}$ de Fibonacci. Por lo tanto, el algoritmo para calcular el elemento $n^{th}$ de Fibonacci también puede representarse como un Grafo de Flujo de Señales, donde tomamos los dos primeros elementos como nodos de entrada y el elemento $n^{th}$ aparece como el nodo de salida. Los demás nodos son mixtos.

Para los lectores que ya estén familiarizados con el SFG de Fibonacci, por simplicidad, el grafo puede representarse sin direcciones, de la siguiente manera:

En general, cuando conocemos el contexto del algoritmo que el SFG está representando, es común ilustrar las aristas sin usar flechas.

En el siguiente capítulo, veremos cómo usar Grafos de Flujo de Señales para escribir un algoritmo que realice la NTT.

Este artículo es parte de una serie sobre la Number Theoretic Transform en nuestro ZK Book