Conceptos básicos sobre información, teoría y algoritmos en informática

Consejería de la Presidencia, Administración Pública e Interior

Instituto Andaluz de Administración Pública

Tema 2. Conceptos básicos sobre información. Teoría de la Información. Codificación y representación de la información. Lógica binaria. Algebra de Boole. Circuitos logicos elementales. Algoritmos.

Este material se formaliza bajo licencia CC BY NC ND (Reconocimiento, No Comercial, Sin Obra Derivada). Esta licencia solo permite que otros puedan descargar las obras y compartirlas con otras personas, siempre que se reconozca su autoría, pero no se pueden cambiar de ninguna manera ni se pueden utilizar comercialmente.

Para más información sobre esta licencia, se puede consultar las siguientes direcciones: https://creativecommons.org/licenses/by-nc-nd/3.0/es/ https://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es

Ayudantes Técnicos - Informática. Tema 02 1/39Consejería de la Presidencia, Administración Pública e Interior Instituto Andaluz de Administración Pública

Sumario

1. - Conceptos básicos sobre información. 3
2. - Conceptos 3
3. - Teoría de la Información 4
4. - Conceptos básicos 4
5. - Codificaciones 5
6. - Compresión 5
7. - Concepto 5
8. - Compresión sin pérdida 6
9. - Compresión con pérdida 6
10. - Entropía. 6
11. - Codificación y representación de la información. 7
12. - Analógico y Digital 7
13. - Codificación y representación de información 8
14. - Representación de números enteros positivos 9
15. - Base 2. 9
16. - BCD 10
17. - Códigos continuos cíclicos 12
18. - Detección de errores 13
19. - Corrección de errores 16 18
20. - Representación de enteros negativos. 19
21. - Representación de números con decimales 20
22. - Representación de caracteres alfanuméricos 22
23. - Little Endian y Big Endian. 26
24. - Lógica binaria y Álgebra de Boole 27
25. - Conceptos 27
26. - Propiedades de los operadores 28
27. - Otras propiedades 28
28. - Mintérminos y maxtérminos 29
29. - Tablas de verdad 29
30. - Diagramas de Karnaugh 30
31. - Otras operaciones 31
32. - Circuitos logicos elementales. 32
33. - NOTA 32
34. - Puertas lógicas 32
35. - Puertas universales 34
36. - Circuitos secuenciales y biestables. 34
37. - Algoritmos 38
38. - Referencias. 39
39. - Autoría 39

Ayudantes Técnicos - Informática. Tema 02 2 / 39 3.3.6 .- Hexadecimal y octal

Conceptos básicos sobre información

Conceptos

Dato: Un valor que corresponde a una apreciación o una medición de un evento, un hecho, una señal o una condición. Por ejemplo, el número 30 es un dato. Los datos no tienen por qué ser numéricos y pueden ser objeto de distintas codificaciones. Otros ejemplos de datos serían "Juan" o "color verde".

Información: Cuando los datos se organizan, combinan, asocian, relacionan o ponen en contexto adquieren un significado y un propósito. Entonces se convierten en información. "Juan tiene 30 años" sería un ejemplo de información. Debe señalarse que esta definición aporta tanto un aspecto estructural, en cuanto a organización e interrelación de datos, como otro funcional, en cuanto a la necesidad de significado y propósito.

Conocimiento: La información puede ser agrupada y analizada en el marco de las experiencias, tanto personales como organizativas. Cuando así se hace y se convierte en algo aplicable, utilizable y útil se convierte en conocimiento. El conocimiento puede encontrarse no sólo en la mente de las personas y en diversas formas de documentación: puede formar parte de los procedimientos, de la forma de organizar y realizar las tareas. "Un incremento de la oferta suele causar una bajada de precios" o "antes de enviar un documento a la calle hay que registrarlo de salida" serían ejemplos de conocimiento. La primera tendría un carácter más proposicional mientras que la segunda sería eminentemente de tipo procedural (know how).

Saber o Sabiduría: Cuando se es consciente del conocimiento se puede ir un paso más allá y someterlo a juicio, buscar formas de aplicarlo de forma óptima para obtener mejores resultados. Entonces se convierte en sabiduría. Es habitual que en la literatura sobre esta materia se mencionen aspectos morales, éticos y eséticos al tratar este concepto.

En la literatura sobre el tema se suele representar la relación entre estos elementos mediante una "pirámide" llamada "pirámide DIKW" (Data - Information - Knowledge - Wisdom, Datos - Información - Conocimiento - Sabiduría).

Señal. Es una variación de una corriente eléctrica, u otra magnitud física, que se utiliza para trasmitir datos.

Ayudantes Técnicos - Informática. Tema 02 3 / 39

Pirámide DIKW

Teoría de la Información

Conceptos básicos de la teoría

Si bien, se habían hecho propuestas de modelos matemáticos para los procesos de información y comunicación, como la de Hartley de 1928, se considera como padres de la Teoría de la Información a Claude E. Shannon y Warren Waver, con sus trabajos realizados en la década de 1940.

Esta teoría es también llamada "Teoría matemática de la información" o "Teoría matemática de la comunicación".

Contexto Mensaje Emisor Receptor Codificación Canal Decodificación

En un proceso de comunicación existe una determinada información, llamada mensaje, que es enviada desde un emisor hacia un receptor. Para que el mensaje llegue a su destino de forma adecuada es necesario tener en cuenta que:

Ayudantes Técnicos - Informática. Tema 02 4/39

• Debe existir una fuente de información (emisor) y un destino de la misma (receptor).
• Es necesario disponer de un canal de comunicaciones que interconecte emisor y receptor. Este canal puede presentar imperfecciones o estar sujeto a condiciones que pueden hacer que el mensaje no llegue a su destino o que llegue alterado. Se habla entonces de ruido.
• Hay que convertir el mensaje en una serie de símbolos (por ejemplo: sonidos, letras, números) que puedan ser enviados a través del canal. Para ello, el emisor codificará el mensaje siguiendo una serie de reglas o codificación. Por su parte, el receptor, tras recibir el mensaje, lo decodificará utilizando el mismo conjunto de reglas.
• El entorno y las circunstancias en que se produce la comunicación conforman el contexto de la misma. Este contexto puede influir en la forma en que el receptor interpreta la información, lo cual debe ser tenido en cuenta por el emisor a la hora de enviar el mensaje.
• Cada canal puede tener una serie de características, como la velocidad de entrega del mensaje o la fiabilidad y plantear exigencias particulares al emisor y/o al receptor.

Codificaciones

La codificación es el proceso mediante el cual se asigna un valor o una serie de valores a un mensaje. El proceso inverso se denomina decodificación. Las reglas que regulan esta transformación se denominan código. En el ámbito de las TIC, con frecuencia se utilizan códigos binarios, basados en bits.

Un código se denomina óptimo si representa los mensajes usando el mínimo número de bits posible.

Compresión

Concepto de compresión

Cuando un mensaje está codificado usando un código que no es óptimo se utiliza más bits de los estrictamente necesarios para representarlo.

Al proceso de codificar un mensaje con un código más eficiente (y con el que, por tanto, serán necesarios menos bits) se le denomina compresión.

Ayudantes Técnicos - Informática. Tema 02 5/39

Compresión sin pérdida

Se habla de compresión sin pérdida cuando el proceso de descomprimir un mensaje produce exactamente el mismo mensaje que fue comprimido inicialmente.

Este tipo de compresiones puede hacerse aprovechando, entre otras cosas, la teoría matemática de probabilidades. Una fuente de información puede producir en un momento dado un mensaje de entre todos los mensajes posibles. Por ejemplo: cuando se tira un dado puede salir cualquiera de los números enteros comprendidos entre el 1 y el 6. En este caso, todos los valores tienen la misma probabilidad de salir.

Sin embargo, lo habitual es que haya unos mensajes que tengan mayor probabilidad de producirse que otros. Siguiendo con el ejemplo anterior, si se tiran dos dados, hay solo una combinación que produce el número 2 (que en ambos dados salga el 1) mientras que hay 5 posibilidades distintas de que salga un 6 (5-1, 4-2, 3-3, 2-4, 1-5).

Esto va a permitir usar codificaciones en los que a los mensajes más probables se les asigne códigos de menor longitud y a los mensos probables se les asigne codificaciones más largas, como las codificaciones de tipo Huffman (ver referencias al final del tema).

Por ejemplo: si en el idioma castellano la letra "e" aparece con mayor probabilidad que la "z", se puede asignar una codificación de pocos bits a la "e" y otra más larga a la "z".

Compresión con pérdida

Hay casos en los que no es necesario que el mensaje obtenido mediante el proceso de descompresión sea exactamente el mismo que el inicial.

Por ejemplo: en el caso de las fotografías, los audios y los videos, nuestra capacidad para percibir los detalles es limitada. Por eso es posible usar métodos de compresión que eliminen detalles que nos son imperceptibles.

A cambio de esta pérdida de detalle se consigue unas tasas de compresión más altas. O sea: se reduce más el tamaño del mensaje comprimido.

Entropía

Una medida de la incertidumbre de una fuente de información es la entropía. Si la fuente puede producir k mensajes, cada uno de los cuales tiene una probabilidad pi, la entropía, representada por la letra H se calcula mediante la fórmula:

H =-_ p;log2(pi) i=1 k

Ayudantes Técnicos - Informática. Tema 02 6/39

Donde log2 es el logaritmo en base 2.

O sea:

1. Para cada mensaje posible: Se toma la probabilidad de que ocurra Se calcula el logaritmo en base dos de dicha probabilidad ◦ · Se multiplica la probabilidad por su logaritmo en base 2
2. Se toman todos los resultados de las multiplicaciones del paso anterior y se suman

Se puede demostrar que la entropía alcanza su valor máximo cuando todos los mensajes tienen la misma probabilidad.

Por otro lado, si solo hay un mensaje posible (un mensaje tiene probabilidad 1 y el resto tiene probabilidad 0), la entropía es nula (vale 0).

La entropía es baja cuando hay uno o unos pocos mensajes con una probabilidad muy alta y el resto tiene probabilidad muy baja.

La entropía nos da una medida de la cantidad de información que nos proporciona la fuente de información. Esta cantidad de información sería el promedio de la información que nos proporciona cada uno de los posibles mensajes

Codificación y representación de la información

Analógico y Digital

Los datos pueden presentar distintas naturalezas o ser interpretados de acuerdo con éstas.

Se define dato analógico como aquel que varía de forma continua. Esto quiere decir que, dados dos valores cualesquiera para el dato, siempre es posible encontrar un valor intermedio. Muchos de los datos que existen en el mundo real son analógicos. Por

Ayudantes Técnicos - Informática. Tema 02 7 / 39