1.4 Algoritmos de Booth para la multiplicación y división en binario

¿Qué es el algoritmo de Booth?

 El algoritmo de Booth es un procedimiento algorítmico para realizar la multiplicación de dos números con signo, expresados en base binaria en notación complemento a dos. El algoritmo fue inventado por Andrew Donald Booth en 1950 mientras que hacía investigación sobre cristalografía en la universidad de Bloomsbury, en Birkbeck, Londres. Booth usaba calculadoras de escritorio que eran más rápidas en el desplazamiento que sumando, y creó el algoritmo para aumentar su velocidad. El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras.

 PROCEDIMIENTO:

Debemos saber que un número binario está formado por bits de ceros y unos, y que se puede traducir a decimal fácilmente de la siguiente forma: Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 de derecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso, lo que muestro a continuación: 0•27+1•26+0•25+1•24+0•23+1•22+1•21+0•20 = 86. También debemos saber que el complemento a uno de un número binario es cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1: 101101) y que el complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo): Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6•2=12: Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6•2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P. Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro: Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo el último bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados: Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha. 

1.5 Aplicación de los sistemas numéricos en la computación.

• Sistema Binario: Se utiliza a nivel de hardware, en ese nivel todo se reduce a pulsos eléctricos en los cuales solo se entiende "encendido" o "apagado" es decir unos y ceros a estos impulsos se les llama bits.
• Sistema Octal: Se usa al momento de "empaquetar" los bits en grupos de 8 mejor conocidos como octetos o bytes y son útiles para saber el ancho de banda de algún bus o periférico, es decir cuanta información puede mandarse a través de tal dispositivo en un solo ciclo de reloj.
• Sistema Hexadecimal: Se utiliza para "indexar" las direcciones de memoria ya que al tener mas dígitos es un sistema de numeración que permite representar números mas grandes con menos información. Sistema Decimal: Se usa al momento de comunicarse con el usuario

2.Conjuntos

En matemáticas, un conjunto es una colección de elementos considerada en sí misma como un objeto. Los elementos de un conjunto pueden ser cualquier cosa: personas, números, colores, letras, figuras, etc. Se dice que un elemento (o miembro) pertenece al conjunto si está definido como incluido de algún modo dentro de él.

Ejemplo: el conjunto de los colores del arcoíris es:

AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}

Un conjunto suele definirse mediante una propiedad que todos sus elementos poseen. Por ejemplo, para losnúmeros naturales, si se considera la propiedad de ser un número primo, el conjunto de los números primos es:

P = {2, 3, 5, 7, 11, 13, ...}

2.1 Características de los conjuntos

La palabra conjunto generalmente la asociamos con la idea de agrupar objetos, por ejemplo un conjunto de discos, de libros, de plantas de cultivo y en otras ocasiones en palabras como hato, rebaño, piara, parcelas, campesinado, familia, etc., es decir la palabra conjunto denota una colección de elementos claramente entre sí, que guardan alguna característica en común. Ya sean números, personas, figuras, ideas y conceptos.
En matemáticas el concepto de conjunto es considerado primitivo y ni se da una definición de este, sino que se trabaja con la notación de colección y agrupamiento de objetos, lo mismo puede decirse que se consideren primitivas las ideas de elemento y pertenencia.
La característica esencial de un conjunto es la de estar bien definido, es decir que dado un objeto particular, determinar si este pertenece o no al conjunto. Por ejemplo si se considera el conjunto de los números dígitos, sabemos que el 3 pertenece al conjunto, pero el 19 no. Por otro lado el conjunto de las bellas obras musicales no es un conjunto bien definido, puesto que diferentes personas puedan incluir distintas obras en el conjunto.
Los objetos que forman un conjunto son llamados miembros o elementos. Por ejemplo el conjunto de las letras de alfabeto; a, b, c,..., x, y, z. que se puede escribir así:

{A, b, c,..., x, y, z}

Como se muestra el conjunto se escribe entre llaves ({}), o separados por comas (,).

El detallar a todos los elementos de un conjunto entre las llaves, se denomina forma tabular, extensión o enumeración de los elementos.


Dos conjuntos son iguales si tienen los mismos elementos, por ejemplo:
El conjunto {a, b, c} también puede escribirse:
{ a, c, b }, { b, a, c }, { b, c, a }, { c, a, b }, { c, b, a }

En teoría de conjuntos se acostumbra no repetir a los elementos por ejemplo:
El conjunto {b, b, b, d, d} simplemente será {b, d}.

http://colposfesz.galeon.com/est501/conjunto/teoconj.htm

2.1 Caracteristicas de los conjuntos

2.1.1 Conjunto universo, vacío

-Conjunto Vacío- Un conjunto que no tiene elementos es llamado conjunto vacío o conjunto nulo lo que denotamos por el símbolo Æ. Por ejemplo:
Sean A= {2, 4, 6} y B= {1, 3, 5, 7} encontrar A Ç B. A Ç B= { } El resultado de A Ç B= { } muestra que no hay elementos entre las llaves, si este es el caso se le llamará conjunto vacío o nulo y se puede representar como: A Ç B=Æ

-Conjunto Universo-

El conjunto que contiene a todos los elementos a los que se hace referencia recibe el nombre de conjunto Universal, este conjunto depende del problema que se estudia, se denota con la letra U y algunas veces con la letra S (espacio muestra). Por ejemplo si solo queremos referirnos a los 5 primeros números naturales el conjunto queda: U= {1, 2, 3, 4, 5} Forma alternativa para indicar conjuntos de gran importancia: • Conjunto de números naturales (enteros mayores que cero) representados por la letra N donde N= {1, 2, 3,....} • Conjunto de números enteros positivos y negativos representados por la letra Z donde Z= {..., -2, -1, 0, 1, 2,...} • Conjunto de números racionales (números que se representan como el cociente de dos números enteros {fracciones}). Estos números se representan por una Q • Conjunto de números irracionales (números que no puedan representarse como el cociente de dos números enteros) representados por la letra I. • Conjunto de los números reales que son los números racionales e irracionales es decir todos, representados por R. Todos estos conjuntos tienen un número infinito de elementos, la forma de simbolizarlos por extensión o por enumeración es de gran utilidad cuando los conjuntos a los que se hace referencia tienen pocos elementos para poder trabajar con ellos se emplean la notación llamada comprensión. Por ejemplo, la denotar el conjunto de los números naturales menores que 60. Aquí U es el conjunto N y se tiene una propiedad que caracteriza a los elementos del conjunto: ser menores que 60. Para indicar esta situación empleamos la simbología del álgebra de conjuntos:
{X/x Î N; x<60} En esta expresión se maneja un conjunto de x que pertenece a los números naturales (N) y además que los valores de x son menores que 60. Ahora si se desea trabajar con conjuntos que manejen intervalos estos pueden ser representados por medio de una expresión algebraica; supongamos que se desea expresar los números enteros (Z) entre -20 y 30 el conjunto quedaría de la manera siguiente: {X/x Î Z; -20 £ x £ 30}
También se puede expresar el valor de un conjunto indicando la pertenencia o no pertenencia a uno diferente, por ejemplo L= {1, 3, 4, 6, 9} P= {x/x Î N; X Ï L} En el conjunto P se indica que los elementos x de un conjunto pertenecen a los números naturales y además x no pertenece al conjunto L.

2.1.2 Números naturales, enteros, racionales, reales e imaginarios

Los números naturales

Los números naturales (o que contamos) son 1, 2, 3, 4, 5, etc. Hay infinitamente muchos números naturales. El conjunto de números naturales es algunas veces escrito como N como abreviatura.

La suma de cualesquiera dos números naturales es también un número natural (por ejemplo, 4 + 2000 = 2004), y el producto de cualesquiera dos números naturales es un número natural (4 × 2000 = 8000). Aunque esto no es verdadero para la resta y la división.

Los enteros

Los enteros son el conjunto de números reales que consiste de los números naturales, sus inversos aditivos y cero. El conjunto de enteros es algunas veces escrito como J o Z como abreviatura. La suma, producto, y diferencia de cualesquiera dos enteros también es un entero

Los números racionales

Los números racionales son aquellos números que pueden ser expresados como una relación entre dos enteros. Por ejemplo, las fracciones 1/3 y –1111/8 ambas son números racionales. Todos los enteros están incluidos en los números racionales, ya que cualquier entero z puede ser escrito como la relación z/1.

Todos los decimales que terminan son números racionales (ya que 8.27 puede ser escrito como 827/100.) Los decimales que tienen un patrón repetitivo después de algún punto también son racionales

Los números reales

Los números reales es el conjunto de números que consiste de todos los números racionales y de todos los números irracionales. Los números reales son “todos los números” en la recta numérica. Hay infinitamente muchos números reales así como hay infinitamente muchos números en cada uno de los otros conjuntos de números. Pero, puede probarse que el infinito de los números reales es un infinito muy grande.

Números Imaginarios o Complejos

Los números complejos son el conjunto {a + bi | a y b son números reales}, donde i es la unidad imaginaria, –1.        
Los números complejos incluyen el conjunto de los números reales. Los números reales, en el sistema complejo, son escritos en la forma a + 0i = a, un número real.     

Este conjunto es algunas veces escrito como C como abreviatura. El conjunto de los números complejos es importante porque para cualquier polinomio p(x) con coeficientes de números reales, todas las soluciones de p(x) = 0 estarán en C.

http://www.estructurayprogramacion.com/materias/matematicas-discretas-i/n%C3%BAmeros-naturales-enteros-racionales-reales-e-imaginarios/

http://hotmath.com/hotmath_help/spanish/topics/number-systems.html

2.1.3 Subconjuntos

Sean los conjuntos A= {0, 1, 2, 3, 5, 8} y B= {1, 2, 5}

En este caso decimos que B está contenido en A, o que B es subconjunto de A. En general

Si A y B son dos conjuntos cualesquiera, decimos que B es un subconjunto de A si todo elemento

De B lo es de A también.

Por lo tanto si B es un subconjunto de A se escribe B  A. Si B no es subconjunto de A se

Indicará con una diagonal  .

Note que  se utiliza solo para elementos de un conjunto y  solo para conjuntos

2.1.4 Conjunto potencia

Dado un conjuntos, se llama conjunto potencia o conjunto de partes de S (se denota por P(S) o 2^s

) Al conjunto de todos los subconjuntos de S. En la teoría de conjuntos basada en los Axiomas

De Zermelo-Fraenkel, la existencia del conjunto potencia se establece por el axioma del conjunto

Potencia.

Por ejemplo, si S= {a, b, c} entonces el conjunto potencia de S es P(S) = {{ }, {a}, {b}, {c}, {a,

B}, {a, c}, {b, c}, {a, b, c}}.

2.2 Operaciones con conjuntos (Unión, Intersección, Complemento, Diferencia y diferencia simétrica)

Unión

La  unión de los conjuntos  A y  B es el conjunto de todos los elementos de  A con todos los  elementos de  B sin repetir ninguno y se denota como  A∪B .

Intersección

La  intersección de los conjuntos  A y  B es el conjunto de los elementos de  A que también  pertenecen a  B y se denota como  A∩ B 

Complemento 

El complemento del conjunto  A con respecto al conjunto universal  U es el conjunto de todos los  elementos de U que no están en  A y se denota como  'A 

Diferencia 

La  diferencia de los conjuntos  A y  B (en ese orden) es el conjunto de los elementos que pertenecen a  A y no pertenecen a  B y se denota como  A− B .

http://www.estructurayprogramacion.com/materias/matematicas-discretas-i/operaciones-con-conjuntos-uni%C3%B3n-intersecci%C3%B3n-complemento-diferencia-y-diferencia-sim%C3%A9trica/

2.3 Propiedades de los conjuntos.

Algunas de estas operaciones poseen propiedades similares a las operaciones con números. Por ejemplo, la unión y la intersección son conmutativas y asociativas. El conjunto vacío es el elemento neutro de la unión, y el elemento absorbente de la intersección y el producto cartesiano. El conjunto universal es el elemento neutro de la intersección y el elemento absorbente de la unión.

Además, las operaciones de unión, intersección, diferencia y complemento son muy similares a las operaciones en un álgebra de Boole, así como a los conectores lógicos de la lógica proposicional. Estas operaciones pueden adjuntarse de acuerdo al margen de igualdad o desigualdad que existe entre los conjuntos

Operaciones Con Conjuntos

               

Unión    




Intersección

Diferencia

Complemento

Diferencia simétrica