La Medida de la Información Según Shannon

En la búsqueda binaria los datos están ordenados, digamos de manera ascendente en un arreglo de N enteros con N par, y gracias a este orden en la información es posible realizar una búsqueda en un tiempo relativamente breve. Esta rapidez en la búsqueda tiene un costo, desde luego, ya que antes fue necesario ordenar las entradas, pero este no es el asunto aquí. Supongamos que queremos verificar si el numero x se encuentra o no dentro del arreglo. El algoritmo en seudocódigo sería más o menos el que sigue:

  • Obtén el valor del arreglo en la entrada N/2
  • Si el valor del arreglo en la entrada N/2 es igual a x, entonces:
  1. Detén la búsqueda e informa que x está en el arreglo.
  • De lo contrario:
  1. Si x es mayor que el valor del arreglo en N/2
  • Obtén el valor del arreglo en (N/2)/2
  • Si en valor del arreglo en (N/2)/2 es igual a x, entonces:
  1. Detén la búsqueda e informa que x está en el arreglo.
  • De lo contrario:

Este algoritmo realiza, en el peor de los casos, ldN pasos (donde ldN es el logaritmo en base 2 de N) para encontrar x o informar al usuario que x no está contenido en el arreglo. Este número es el número de bits de información que puede almacenar el arreglo. En términos sencillos un bit es la mínima cantidad de información que se puede tener. Supongamos, por ejemplo, que se lanza una moneda y obtenemos cara, la información de este acontecimiento puede almacenarse en un arreglo de dos entradas en el que previamente se ha establecido que la entrada de la izquierda es cruz y la de la derecha es cara. Entonces, y con esta convención, si hemos de almacenar el resultado basta con dejar en blanco la primera entrada del arrreglo y colocar un punto * en la segunda. Cuando alguien más vea este arreglo, y conozca la convención que hemos hecho, será capaz de decir que ha ocurrido una cara. En este ejemplo podríamos pensar que basta con un arreglo de una sola entrada, en la que ponemos 0 si ocurre cara o 1 si ocurre cruz, con lo cual almacenamos igual cantidad de información en menos espacio. Lo que ocurre es que en este caso es que hemos invertido los papeles y el arreglo de dos entradas son el 0 y el 1 y el punto es el arreglo de una entrada, también podríamos almacenar información acerca de lo que obtuvimos en un lanzamiento de dados, pero esto implica el uso de un sistema numérico de base 6. Necesitamos de una marca y de un sistema con dos posibles estados. Otra forma de ver esto es el caso presentado arriba, de la búsqueda binaria. Cuantas preguntas necesitemos para localizar el punto, x en el ejemplo, es el número de bits que puede almacenar nuestro sistema. ¿Cuánta información obtenemos cuando sabemos el resultado de un volado? 1 bit, ya lo sabemos, pero ¿Cómo está esto relacionado con la probabilidad de obtener una cara? El número de bits puede expresarse asì:

1 = (-1/2)ln(1/2) – (1/2)ln(1/2)

o

1 = Σplnp

Una relación válida también para los casos que en los que la moneda no es legal y las probabilidades no son iguales en los eventos mutuamente excluyentes.