Definir
el concepto discreto no es sencillo pero podemos apelar a ciertos ejemplos
matemáticos conocidos y contraponerlo al concepto de continuo que es la idea
central del curso de Bases de Matemáticas. Lo discreto es lo finito o lo que,
si no es finito, presenta el aspecto de los números naturales, objetos bien
separados entre sí; lo continuo es lo no finito, lo infinitesimalmente próximo,
como los números reales, y de ahí el concepto de límite y las ideas que de
dicho concepto se derivan.
La
matemática discreta surge como una disciplina que unifica diversas áreas
tradicionales de las Matemáticas (combinatoria, probabilidad, geometría de
polígonos, aritmética, grafos,...), como consecuencia de, entre otras cosas, su
interés en la informática y las telecomunicaciones: la información se manipula
y almacena en los ordenadores en forma discreta (palabras formadas por ceros y
unos), se necesita contar objetos (unidades de memorias, unidades de tiempo),
se precisa estudiar relaciones entre conjuntos finitos (búsquedas en bases de
datos), es necesario analizar procesos que incluyan un número finito de pasos
(algoritmos)...
Para
hacernos una idea algo más clara del contenido veamos algunas preguntas que
podemos plantearnos en informática y que se pueden responder con métodos de
matemática discreta:
¿Hay
alguna conexión entre dos ordenadores de una red?
Dada una tecnología de cableado, ¿cuál es el diseño de red más económico para cierta empresa?
Dada una tecnología de cableado, ¿cuál es el diseño de red más económico para cierta empresa?
¿Cómo
puede ordenarse una lista de números enteros (o de tareas de una cadena) en
forma creciente?
¿Cuántas palabras clave válidas hay para acceder a un sistema?
¿Cómo se puede codificar de forma adecuada y segura un mensaje?
¿Cuántas palabras clave válidas hay para acceder a un sistema?
¿Cómo se puede codificar de forma adecuada y segura un mensaje?
Responderemos
alguna de estas preguntas a lo largo del curso. La matemática discreta
proporciona, por otro lado, algunas bases matemáticas para otros aspectos de la
informática: estructuras de datos, algorítmica, bases de datos, teoría de
autómatas, sistemas operativos, investigación operativa,... así como ayuda al
desarrollo de ciertas capacidades fundamentales para un ingeniero: capacidad de
formalizar, de razonar rigurosamente, de representar adecuadamente algunos
conceptos...
Concepto de sistemas numéricos.
Un sistema de numeración es un conjunto de símbolos y reglas de generación que permiten construir todos los números válidos.Los modernos equipos de cómputo actuales no utilizan el sistema decimal para representar valores numéricos, en su lugar se hace uso del sistema binario, también llamado complemento de dos. Es importante entender cómo representan las computadoras los valores numéricos, en éste capítulo analizaremos varios conceptos importantes incluyendo los sistemas binario y hexadecimal, la organización binaria de datos (bits, nibbles, bytes, palabras y palabras dobles), sistemas numéricos con signo y sin signo, operaciones aritméticas, lógicas, de cambio (shift) y rotación en valores binarios, campos de bits, empaquetado de datos y el juego de caracteres ASCII.
Un sistema de numeración puede representarse como
donde:
- N es el sistema de numeración considerado (p.ej. decimal, binario,
etc.).
- S
- R son las reglas que nos indican qué números son válidos en el sistema, y cuáles no. En un sistema de numeración posicional las reglas son bastante simples, mientras que la numeración romana requiere reglas algo más elaboradas.
Teorema Fundamental de la
numeración
Establece la forma general de construir números en un sistema de
numeración posicional. Primero estableceremos unas definiciones básicas:
La fórmula general para construir un número N, con un número
finito de decimales, en un sistema de numeración posicional de base b es
la siguiente:
El valor total del número será la suma de cada dígito multiplicado por
la potencia de la base correspondiente a la posición que ocupa en el número.
Esta representación posibilita la realización de sencillos algoritmos
para la ejecución de operaciones aritméticas.
Sistema decimal.
En el
sistema decimal los símbolos válidos para construir números son {0,1,...9} (0
hasta 9, ambos incluidos), por tanto la base (el número de símbolos válidos en
el sistema) es diez
En la
figura inferior podemos ver el teorema fundamental de la numeración aplicado al
sistema decimal.
Los
dígitos a la izquierda de la coma fraccionaria representados por dn ... d2 d1 d0
, toman el valor correspondiente a las potencias positivas de la base (10 en el
sistema decimal), en función de la posición que ocupan en el número, y
representan respectivamente al dígito de las n-unidades (10n), centenas
(10²=100), decenas (10¹=10) y unidades (100=1), ya que como se ve en el gráfico
están colocados en las posiciones n..., tercera, segunda y primera a la
izquierda de la coma fraccionaria.
Los
dígitos a la derecha de la coma fraccionaria d-1, d-2, d-3 ... d-n representan
respectivamente al dígito de las décimas (10-1=0,1), centésimas (10-2=0,01),
milésimas (10-3=0,001) y n-ésimas (10-n) .
Por ejemplo, el número 1492,36 en decimal, puede
expresarse como: 1492/36
Otro ejemplo es, que hemos utilizado el sistema decimal (de base 10) por tanto tiempo que prácticamente lo tomamos como algo natural. Cuando vemos un número, por ejemplo el 123, no pensamos en el valor en sí, en lugar de ésto hacemos una representación mental de cuántos elementos representa éste valor. En realidad, el número 123 representa:
1*102 + 2*101 + 3*100
ó lo que es lo mismo:
100 + 20 + 3
Cada dígito a la izquierda del punto decimal representa un valor entre cero y nueve veces una potencia incrementada de diez. Los dígitos a la derecha del punto decimal por su parte representan un valor entre cero y nueve veces una potencia decrementada de diez. Por ejemplo, el número 123.456 representa:
1*102 + 2*101 + 3*100 + 4*10-1 + 5*10-2 + 6*10-3
Sistema binario
Tomemos ahora el sistema binario o de base 2. En este sistema los dígitos válidos son {0,1}, y dos unidades forman una unidad de orden superior.
En la figura inferior podemos ver el teorema fundamental
de la numeración aplicado al sistema binario.
Seguimos con el ejemplo del cuentakilómetros visto
arriba. En este caso las ruedas no tienen 10 símbolos (0 al 9)
como en el caso del sistema decimal. En el sistema binario la base es
2, lo que quiere decir que sólo disponemos de 2 símbolos
{0,1} para construir todos los números binarios.
En el sistema binario, para representar cifras mayores
que 1 se combinan los 2 símbolos {0,1} y agrega una segunda columna
de un orden superior.
Aquí las ruedas del cuentakilómetros dan
una vuelta cada dos unidades. Por tanto, una vez que contamos (sumamos)
dos hemos agotado los símbolos disponibles para esa columna,
y debemos poner a cero la columna y usar otra columna a la izquierda.
Para convertir un número decimal en binario es un poco más difícil. Se
requiere encontrar aquellas potencias de 2 las cuales, sumadas, producen el
resultado decimal, una forma conveniente es trabajar en "reversa" por
ejemplo, para convertir el número 1359 a binario:
- 210=1024, 211=2048. Por tanto la mayor potencia de 2 menor que 1359 es 210. Restamos 1024 a 1359 y empezamos nuestro número binario poniendo un "1" a la izquierda. El resultado decimal es 1359-1024=335. El resultado binario hasta este punto es: 1.
- La siguiente potencia de 2 en orden descendente es 29=512 lo que es mayor que el resultado de la resta del punto anterior, por lo tanto agregamos un 0 a nuestra cadena binaria, ahora es: 10. El resultado decimal es aún 335.
- La siguiente potencia es 28=256 por lo que lo restamos a 335 y agregamos 1 a la cadena binaria: 101. El resultado decimal es: 79.
- 27=128, ésto es mayor que 79. Agregamos un 0 a la cadena binaria: 1010 en tanto que el valor decimal es: 79.
- Restamos 26=64 a 79. La cadena binaria es ahora: 10101. El resultado decimal indica: 15.
- 15 es menor que 25=32, por tanto, Binario=101010, el valor decimal sigue siendo: 15.
- 15 es menor que 24=16, de aquí, Binario=1010100, el valor decimal continúa en: 15.
- 23=8 es menor que 15, así que agregamos un 1 a la cadena binaria: 10101001, en tanto que el nuevo valor decimal es: 7.
- 22 es menor que 7. Binario es ahora: 101010011, el resultado decimal ahora vale: 3.
- 21 es menor que 3. Binario=1010100111, el nuevo valor decimal es: 1.
Ejemplo:
1*27 + 1*26 + 0*25 + 0*24 + 1*23 + 0*22 + 1*21 + 0*20=
128 + 64 + 8 + 2
=
20210
Sistema octal
El sistema de numeración octal es también muy usado en la computación por tener una base que es potencia exacta de 2 o de la numeración binaria. Esta característica hace que la conversión a binario o viceversa sea bastante simple. El sistema octal usa 8 dígitos (0, 1, 2, 3, 4, 5, 6, 7) y tienen el mismo valor que en el sistema de numeración decimal.
El teorema fundamental aplicado al sistema octal sería
el siguiente:
Como el sistema de numeración octal usa la notación
posicional entonces para el número 3452,32 tenemos q: 2*80 +
5*81 + 4*82 + 3*83 + 3*8-1 + 2*8-2 = 2 + 40 + 4*64 + 3*512 + 3*0,125
+ 2*0,015625 = 2 + 40 + 256 + 1536 + 0,375 + 0,03125 = 1834 + 0,40625d
Entonces, 3452,32q = 1834,40625d
El sub índice q indica número octal, se
usa la letra q para evitar confusión entre la letra 'o' y el
número 0. En informática, a veces se utiliza la numeración
octal en vez de la hexadecimal.
Tiene la ventaja de que no requiere
utilizar otros símbolos diferentes de los dígitos. Es
posible que la numeración octal se usara en el pasado en lugar
de la decimal, por ejemplo, para contar los espacios interdigitales
o los dedos distintos de los pulgares.
Es utilizado como una forma abreviada de representar números
binarios que emplean caracteres de seis bits. Cada tres bits (medio
carácter) es convertido en un único dígito octal.
Okta es un término griego que significa 8.
Sistema hexadecimal.
El sistema de numeración hexadecimal, de base 16,
utiliza 16 símbolos. Es común abreviar hexadecimal como
hex aunque hex significa base seis. Dado que el sistema usual de numeración
es de base decimal y, por ello, sólo se dispone de diez dígitos,
se adoptó la convención de usar las seis primeras letras
del alfabeto latino para suplir los dígitos que nos faltan: A
= 10, B = 11, C = 12, D = 13, E = 14 y F = 15. Como en cualquier sistema
de numeración posicional, el valor numérico de cada dígito
es alterado dependiendo de su posición en la cadena de dígitos,
quedando multiplicado por una cierta potencia de la base del sistema,
que en este caso es 16. Por ejemplo: 3E0,A(16) = 3×16^2 + E×16^1
+ 0×16^0 + A×16^-1 = 3×256 + 14×16 + 0×1
+ 10×0,0625 = 992,625. El sistema hexadecimal actual fue introducido
en el ámbito de la computación por primera vez por IBM
en 1963. Una representación anterior, con 0–9 y u–z,
fue usada en 1956 por la computadora Bendix G-15 y algunas computadoras
modernas.
