Un poco de blues...

Algoritmo de Bellman ford

Para poder tomar el tema de esta clase de algoritmos, es necesario poder prestar atención a lo que se denomina como, TEORIA DE GRAFOS, la misma nos enseñara a manipular el orden de distintos procesos a efectuar.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).


mas info en...http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

Para comenzar debemos tener bien definido que el algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo).

Si entendemos bien dicho concepto, entonces podemos decir que el algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.


Este tipo de algoritmo eran originales de ruteo de la ARPANET. Su modo de funcionamiento es el siguiente:

1. Cada ruteador mantiene una tabla (un vector) que almacena las mejores distancias conocidas a cada destino y las líneas a usar para cada destino. Se actualizan las tablas intercambiando información con los vecinos.
2. La tabla de un ruteador almacena una entrada para cada uno de los ruteadores en la subred (los ruteadores son los índices). Las entradas almacenan la línea preferida de salida y una estimación del tiempo o la distancia al destino. Se pueden usar métricas distintas (saltos, retrasos, etc.).
3. Cada ruteador tiene que medir las distancias a sus vecinos. Por ejemplo, si la métrica es el retraso, el ruteador la puede medir usando paquetes de eco.
4. Cada T msegs los ruteadores intercambian sus tablas con sus vecinos. Un ruteador usa lastablas de sus vecinos y sus mediciones de las distancias a sus vecinos para calcular una nueva tabla.

A modo de finalizar, la siguiente imagen, muestra el analisis grafico de un grafo aplicado en los canales de Venecia

Algoritmo de Cadenas Polacas y Rotación

"CERATI -UNO ENTRE MIL-" algo de buena música como siempre...

El método de cadenas polacas y rotación, tendra por objetivo entregarnos datos de salida con una característica especial, los mismos podran ser reversibles de una manera única, que solo nosotros podremos determinar, esto hará referencia a una llave lógica que nos permitirá darle un uso especifico a este algoritmo, será usado como un método alternativo de encriptación de seguridad para datos.

Como ya definimos anteriormente, un algoritmo se encargara mediante un método especifico transformar una entrada de datos en una salida, en forma iterativa casi en la mayoria de los casos, para ello debemos crear reglas especificas a este algoritmo, en este el algoritmo utilizara un operador y un operante

OPERADOR: será un valor numérico en un medio de recursos concretos (numeros naturales, reales, imaginarios, etc)

OPERADOR: Es una función de transformación en la relacion de operantes que pueden ser clasicos o particulares (estos ultimos tendran las mismas atribuciones de los clasicos pero con simbolos modificados o personalizados para un entendimiento personal) + - / *

Principio 1

Relacion del operador con el operante

Es una operacion secuencial consecutiva de pares, ejemplo:

ℓ = (+, -)

A = (7, 4, 1)

R (ℓ, A) = R (+, -) (7, 4, 1)

R(+, -)(7, 4, 1) = 4

Principio 2

Algoritmo de la cadena polaca

(+, -)(7, 4, 1) donde se repartira los signos de la siguiente forma

7-4+1 = 4

a travez de la rotacion de los signos, obtenemos el resultado, definiendo ademas asi, que una cadena polaca posee una notacion prefija en sus procesos

la aplicación mas directa a este tipo de procesos, podemos mencionarla por ejemplo, en la encriptación de información que podria requerir de un algoritmo de cadena polaca y el uso de llaves logicas tras la construccion de matrices numericas que apliquen esa definicion de cadena polaca


vamos a utilizar a continuación un ejemplo aplicando un sistema de encriptacion o criptosistema

"Un Criptosistema se define como la quíntupla (m,C,K,E,D), donde:

* m representa el conjunto de todos los mensajes sin cifrar (texto plano) que pueden ser enviados.
* C Representa el conjunto de todos los posibles mensajes cifrados, o criptogramas.
* K representa el conjunto de claves que se pueden emplear en el Criptosistema UNA LLAVE LOGICA DE NUESTRA CADENA POLACA POR EJEMPLO.
* E es el conjunto de transformaciones de cifrado o familia de funciones que se aplica a cada elemento de m para obtener un elemento de C. Existe una transformación diferente Ek para cada valor posible de la clave K.
* D es el conjunto de transformaciones de descifrado, análogo a E.

Todo Criptosistema cumple la condición Dk(Ek(m))=m es decir, que si se tiene un mensaje m, se cifra empleando la clave K y luego se descifra empleando la misma clave, se obtiene el mensaje original m." (1)

Existen dos tipos fundamentales de Criptosistemas utilizados para cifrar datos e información digital y ser enviados posteriormente después por medios de transmisión libre.

1. Simétricos o de clave privada: se emplea la misma clave K para cifrar y descifrar, por lo tanto el emisor y el receptor deben poseer la clave. El mayor inconveniente que presentan es que se debe contar con un canal seguro para la transmisión de dicha clave.
2. Asimétricos o de llave pública:se emplea una doble clave conocidas como Kp (clave privada) y KP (clave Pública). Una de ellas es utilizada para la transformación E de cifrado y la otra para el descifrado D. En muchos de los sistemas existentes estas clave son intercambiables, es decir que si empleamos una para cifrar se utiliza la otra para descifrar y viceversa.

Los sistemas asimétricos deben cumplir con la condición que la clave Publica (al ser conocida y sólo utilizada para cifrar) no debe permitir calcular la privada. Como puede observarse este sistema permite intercambiar claves en un canal inseguro de transmisión ya que lo único que se envía es la clave pública.

Los algoritmos asimétricos emplean claves de longitud mayor a los simétricos. Así, por ejemplo, suele considerarse segura una clave de 128 bits para estos últimos pero se recomienda claves de 1024 bits (como mínimo) para los algoritmos asimétricos. Esto permite que los algoritmos simétricos sean considerablemente más rápidos que los asimétricos.

En la práctica actualmente se emplea una combinación de ambos sistemas ya que los asimétricos son computacionalmente más costosos (mayor tiempo de cifrado). Para realizar dicha combinación se cifra el mensaje m con un sistema simétrico y luego se encripta la clave K utilizada en el algoritmo simétrico (generalmente más corta que el mensaje) con un sistema asimétrico.

Después de estos Criptosistemas modernos podemos encontrar otros no menos importantes utilizados desde siempre para cifrar mensajes de menos importancia o domésticos, y que han ido perdiendo su eficacia por ser fácilmente criptoanalizables y por tanto "reventables". Cada uno de los algoritmos clásicos descriptos a continuación utilizan la misma clave K para cifrar y descifrar el mensaje.

Transposición

Son aquellos que alteran el orden de los caracteres dentro del mensaje a cifrar. El algoritmo de transposición más común consiste en colocar el texto en una tabla de n columnas. El texto cifrado serán los caracteres dados por columna (de arriba hacia abajo) con una clave K consistente en el orden en que se leen las columnas.

Ejemplo: Si n = 3 columnas, la llave logica K es (3,1,2) y el mensaje a cifrar "SEGURIDAD INFORMATICA".



El mensaje cifrado será: " GIDNRTASUD FMIERAIOAC "