Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

MATEMATICAS DISCRETAS

TEMARIO

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of MATEMATICAS DISCRETAS

photo credit Nasa / Goddard Space Flight Center / Reto Stöckli
UNIDAD 1:
SISTEMAS NUMÉRICOS

Introducción
conversión entre
sistemas numéricos
Operaciones básicas
algoritmo de booth para
la multiplicación y
divicion de binario
Aplicación de los sistemas numéricos en la computación
INTRODUCCIÓN A LOS SISTEMAS DE NUMERACIÓN.

Con origen árabe, el sistema de numeración decimal se basó en los dedos de las manos y es por esto que estamos acostumbrados a manejar 10 cifras diferentes, cuya representación escrita va del 0 al 9. Sin duda, los árabes no debieron tener en cuenta que algún día se plantearía el problema de automatizar el proceso de contar y hacer operaciones, pero marcaron las reglas de funcionamiento de cualquier sistema de numeración.
Entre los infinitos sistemas de numeración posibles, hoy en día se utilizan solo unos pocos, dependiendo de la aplicación para la que se destine. Es claro que prevalece el decimal en las operaciones corrientes que todos hacemos mentalmente, por el contrario, cuando se trata de aparatos digitales, el único sistema que interesa es el binario. Todos los demás tienen menos importancia pero cumplen funciones como simplificar números binarios muy largos, facilitar la manipulación de valores que no son enteros, etc. El primer valor del siguiente cuadro es un número decimal, el segundo es el número binario equivalente. Si obserba con interés, posiblemente encuentre la regla con la que crecen ambos datos.
1.2 Conversiones entre sistemas numéricos.

Sistema Numérico de Base 10
Los sistemas numéricos están compuestos por símbolos y por las normas utilizadas para interpretar estos símbolos. El sistema numérico que se usa más a menudo es el sistema numérico decimal, o de Base 10. El sistema numérico de Base 10 usa diez símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Estos símbolos se pueden combinar para representar todos los valores numéricos posibles.
El sistema numérico decimal se basa en potencias de 10. Cada posición de columna de un valor, pasando de derecha a izquierda, se multiplica por el número 10, que es el número de base, elevado a una potencia, que es el exponente. La potencia a la que se eleva ese 10 depende de su posición a la izquierda de la coma decimal. Cuando un número decimal se lee de derecha a izquierda, el primer número o el número que se ubica más a la derecha representa 100 (1), mientras que la segunda posición representa 101 (10 x 1= 10) La tercera posición representa 102 (10 x 10 =100). La séptima posición a la izquierda representa 106 (10 x 10 x 10 x 10 x 10 x 10 =1.000.000). Esto siempre funciona, sin importar la cantidad de columnas que tenga el número.
Ejemplo:
2134 = (2x10 potencia 3) + (1x10 potencia 2) + (3x10 potencia 1) + (4x10 potencia 0)
Hay un 4 en la posición correspondiente a las unidades, un 3 en la posición de las decenas,
un 1 en la posición de las centenas y un 2 en la posición de los miles. Este ejemplo parece
obvio cuando se usa el sistema numérico decimal. Es importante saber exactamente cómo
funciona el sistema decimal, ya que este conocimiento permite entender los otros dos sistemas
numéricos, el sistema numérico de Base 2 y el sistema numérico hexadecimal de Base 16.
Estos sistemas usan los mismos métodos que el sistema decimal.
Sistema Numérico de Base 2

Los computadores reconocen y procesan datos utilizando el sistema numérico binario, o de Base 2. El sistema numérico binario usa sólo dos símbolos, 0 y 1, en lugar de los diez símbolos que se utilizan en el sistema numérico decimal. La posición, o el lugar, que ocupa cada dígito de derecha a izquierda en el sistema numérico binario representa 2, el número de base, elevado a una potencia o exponente, comenzando desde 0. Estos valores posicionales son, de derecha a izquierda, 2 potencia 0, 2 potencia 1, 2 potencia 2, 2 potencia 3, 2 potencia 4, 2 potencia 5, 2 potencia 6 y 2 potencia 7, o sea, 1, 2, 4, 8, 16, 32, 64 y 128, respectivamente.
Ejemplo:
101100 = (1 x 2 potencia 5 = 32) + (0 x 2 potencia 4 = 0) + (1 x 2 potencia 3 = 8) + (1 x 2potencia 2= 4)+(0 x 2 potencia 1 = 0) (0 x 2 potencia 0 = 0) = 44 (32 + 0 + 8 + 4 + 0+ 0)
Al leer el número binario (101100) de izquierda a derecha, se nota que hay un 1 en la
posición del 32, un 0 en la posición del 16, un 1 en la posición del 8, un 1 en la posición
del 4 un 0 en la posición del 2, y un 0 en lposiciónon de 1 que sumados dan el número
decimal 44.
Sistema Numérico de Base 8

El inconveniente de la codificación binaria es que la representación de algunos números resulta muy larga. Por este motivo se utilizan otros sistemas de numeración que resulten más cómodos de escribir: el sistema octal y el sistema hexadecimal. Afortunadamente, resulta muy fácil convertir un número binario a octal o a hexadecimal.
En el sistema octal, usa ocho dígitos diferentes: 0, 1, 2, 3, 4, 5, 6 y 7.Cada posición de columna de un valor, pasando de derecha a izquierda, se multiplica por el número 8, que es el número de base, elevado a una potencia, que es el exponente. Cada dígito tiene, naturalmente, un valor distinto dependiendo del lugar que ocupen. El valor de cada una de las posiciones viene determinado por las potencias de base 8.
Ejemplo:
El número octal 2738 =
2*8 potencia 2 + 7*8 potencia 1 + 3*8 potencia 0 = 2*64 + 7*8 + 3*1 = 187
Sistema Numérico de Base 16 (Hexadecimal)

El sistema hexadecimal usa dieciséis símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F. Se utilizan los caracteres A, B, C, D, E y F representando las cantidades decima­les 10, 11, 12, 13, 14 y 15 respectivamente, porque no hay dígitos mayores que 9 en el sistema decimal. Cada dígito tiene, naturalmente, un valor distinto dependiendo del lu­gar que ocupen. El valor de cada una de las posiciones viene determinado por las potencias de base 16.
Ejemplo:
El valor del número hexadecimal 1A3F =
1*16 potencia 3 + A*16 potencia 2 + 3*16 potencia 1 + F*16 potencia 0
1*4096 + 10*256 + 3*16 + 15*1 = 6719
1A3F16 = 6719 base 10
Suma de números binarios
La tabla de sumar para números binarios es la siguiente:



Las posibles combinaciones al sumar dos bits son:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

Note que al sumar 1 + 1 es 2 decimal es decir, llevamos 1 a la siguiente posición de la izquierda (acarreo). Esto es equivalente, en el sistema decimal a sumar 9 + 1, que da 10: cero en la posición que estamos sumando y un 1 de acarreo a la siguiente posición.
|
Se puede convertir la operación binaria en una operación decimal, resolver la decimal, y después transformar el resultado en un (número) binario. Operamos como en el sistema decimal: comenzamos a sumar desde la derecha, en nuestro ejemplo, 1 + 1 = 10, entonces escribimos 0 en la fila del resultado y llevamos 1 (este "1" se llama acarreo o arrastre). A continuación se suma el acarreo a la siguiente columna: 1 + 0 + 0 = 1, y seguimos hasta terminar todas la columnas (exactamente como en decimal).
Resta de números binarios

El algoritmo de la resta en sistema binario es el mismo que en el sistema decimal. Pero conviene repasar la operación de restar en decimal para comprender la operación binaria, que es más sencilla. Los términos que intervienen en la resta se llaman minuendo, sustraendo y diferencia.
Las restas básicas 0 - 0, 1 - 0 y 1 - 1 son evidentes:
0 - 0 = 01 - 0 = 1
1 - 1 = 0
0 - 1 = 1 (se transforma en 10 - 1 = 1) (en sistema decimal equivale a 2 - 1 = 1)
La resta 0 - 1 se resuelve, igual que en el sistema decimal, tomando una unidad prestada de la posición siguiente: 0 - 1 = 1 y me llevo 1, lo que equivale a decir en el sistema decimal, 2 - 1 = 1.
En decimal, por ejemplo tienes 100-19, obviamente a 0 no le puedes quitar 9, así que debemos tomar prestado 1 para volverlo un 10 (en decimal la base es 10), y así si 10-9=1.
En binarios pasa lo mismo, no le puedes quitar 1 a 0, debes de tomar 1 prestado al de un lado, pero cuidado aquí viene lo complicado tu numero no se va a volver 10, recuerda que en binario la base es 2 y por lo tanto se volverá 2 en binario, y ahora sí a 2 le quitas 1, 2-1=1, y continuas restando pero recuerda que llevas 1, porque pediste prestado.
Ejemplo para que le entiendas mejor, vamos a restar 201 - 67, ya sabemos que es 134, vamos a hacerlo en binario :

1 1 0 0 1 0 0 1.......................201
- 0 1 0 0 0 0 1 1.......................67

Tomamos los dos últimos números, 1-1 es igual a 0, y no llevamos nada (no pedimos prestado)

1 1 0 0 1 0 0 1
- 0 1 0 0 0 0 1 1
------------------------
0
Ahora la siguiente columna 0-1, ya dijimos que no se puede, así que va a tomar 1 prestado al de la columna del lado izquierdo, se que vas a decir "es un cero, no nos puede prestar 1", lo que pasa es que ese cero le pide a su vez al de lado, y así hasta que encuentres un 1, pero no te fijes en eso, vamos a seguir restando y no nos vamos a preocupar por eso ahora, entonces ahora nos prestaron 1 (no importa quién) y tenemos un 1 0 (este numero es 2 en binario no 10 en decimal, no te vayas a confundir), entonces en binario tienes 10-1, que en decimal es 2-1=1, y llevamos 1 (porque pedimos 1 prestado)

1 1 0 0 1 0 0 1 arriba
- 0 1 0 0 0 0 1 1 abajo
------------------------
1 0
Para la siguiente columna tenemos 0 - 0, pero recuerda que tomamos 1 prestado así que en realidad tenemos 0 - 1 (le sumamos el 1 al de abajo),
de nuevo tenemos que pedir prestado y entonces tenemos en binaria 1 0 -1 que en decimal es 2-1=1, y de nuevo llevamos 1
1 1 0 0 1 0 0 1
- 0 1 0 0 0 0 1 1
------------------------
1 1 0
Continuamos con 1 - 0 , pero como llevamos 1 tenemos ahora 1 - 1, esto si lo podemos resolver 1 - 1 = 1 (en binario y decimal).
1 1 0 0 1 0 0 1
- 0 1 0 0 0 0 1 1
------------------------
0 1 1 0
Lo demás es muy fácil:
0 - 0=0
0 - 0=0
1 - 1=0
1 - 0=1
1 1 0 0 1 0 0 1
- 0 1 0 0 0 0 1 1
------------------------
1 0 0 0 0 1 1 0 que en decimal es 134.
Es lo mismo que la resta en decimal, pides prestado y llevas, nada más debes de ser cuidadoso y recordar que tu base es 2.
"En este mundo solo existen 10 tipos de personas, las que saben binario y las que no" =)
PRODUCTO DE NÚMEROS BINARIOS
La tabla de multiplicar para números binarios es la siguiente:


El algoritmo del producto en binario es igual que en números decimales; aunque se lleva a cabo con más sencillez, ya que el 0 multiplicado por cualquier número da 0, y el 1 es el elemento neutro del producto.

Por ejemplo, multipliquemos 10110 por 1001:
División de números binarios
La división en binario es similar al decimal; la única diferencia es que a la hora de hacer las restas, dentro de la división, éstas deben ser realizadas en binario.
Ejemplo
Dividir 100010010 (274) entre 1101 (13):
El algoritmo de multiplicación de Booth es un algoritmo de multiplicación que multiplica dos números binarios con signo en la notación de 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.
El algoritmo de Booth examina pares adyacentes de bits del multiplicador Y de N-bits en la representación de complemento a dos con signo, incluyendo un bit implícito debajo del bit menos significativo, y-1 = 0. Para cada bit yi, para i corriendo desde 0 hasta N-1, los bits yi y yi-1 son considerados. Cuando estos dos bits son iguales, el acumulador del producto P es dejado sin cambios. Cuando yi = 0 y yi-1 = 1, el multiplicando multiplicado por 2i es agregado a P; y cuando yi = 1 y yi-1 = 0, el multiplicando multiplicado por 2i es restado de P. El valor final de P es el producto con signo.
La representación del multiplicando y del producto no son especificadas; típicamente, éstos también están ambos en la representación de complemento a dos, como el multiplicador, pero cualquier sistema de numeración que soporte la adición y la substracción trabajará igual de bien. Según lo indicado aquí, el orden de los pasos no está determinado. Típicamente, procede desde el bit menos significativo (LSB) al bit mas significativo (MSB), comenzando en i = 0; la multiplicación por 2i es entonces típicamente reemplazado por el desplazamiento (shifting) incremental del acumulador P a la derecha entre los pasos; los bits bajos pueden ser desplazados hacia fuera, y las adiciones y substracciones subsecuentes entonces pueden ser hechas justo en los N bits más altos de P.1 Hay muchas variaciones y optimizaciones sobre estos detalles.
El algoritmo es a menudo descrito como convertir secuencias de 1s en el multiplicador con un +1 de orden alto y un -1 de orden inferior en los extremos de la secuencia. Cuando una secuencia corre por el MSB, no hay +1 de orden alto, y el efecto neto es la interpretación como un negativo de valor apropiado.

Aplicación de los Sistemas Numéricos en la Computación

Existe una cantidad infinita de sistemas numéricos, sin embargo, para una computadora, únicamente existen 4, que son el Binario (con base 2), el octal (con base 8), el decimal (base 10) y hexadecimal (base 16). Detallaremos el uso decada uno de ellos por la computadora.

Comenzaremos por el Binario, por ser el sistema base de la computación y el único entendido de manera nativa por una computadora, es el sistema en el que está escrita toda instrucción, dato, etc. Está compuesto por dos únicos dígitos que 1 y 0 o como en realidad trabaja la computadora, “apagado” y “encendido” y se es como representa todos los datos con los que trabaja la computadora, desde sumás bajo nivel: el hardware. Estos dígitos son llamados bits.

Para trabajar la computadora agrupa a los bits en grupos de ocho, a los cuales denomina byte y es esta la razón por la que es tan importante el sistema octal, sin embargo una computadora no puede trabajar con el sistema octal como tal, si no que utiliza su conversión en sistema binario, usando tres bits para cada digito octal
El sistema hexadecimal es empleado al indexar la memoria o al representar un byte debido a que al contener más dígitos es posible usar menos números para representar números más grandes, haciendo posible que un byte, conformado por8 bits o términos binarios, se represente con solo dos términos hexadecimales, lo que es un ahorro de información.

Sin embargo, la computadora tampoco reconoce el sistema hexadecimal como tal y, al igual que el sistema octal, lo representa con términos binarios, empleando conjuntos de cuatro bits, para cada término hexadecimal. Sin embargo al presentar información al usuario es más factible presentar A9 que 10101001.Por último el sistema decimal únicamente se utiliza al interactuar con el usuario,debido a que un usuario común no está acostumbrado a tratar con diferentes sistemas numéricos.
Aplicación de los Sistemas Numéricos en la Computación
Existe una cantidad infinita de sistemas numéricos, sin embargo, para una computadora, únicamente existen 4, que son el Binario (con base 2), el octal (con base 8), el decimal (base 10) y hexadecimal (base 16). Detallaremos el uso de cada uno de ellos por la computadora.

Comenzaremos por el Binario, por ser el sistema base de la computación y el único entendido de manera nativa por una computadora, es el sistema en el que está escrita toda instrucción, dato, etc. Está compuesto por dos únicos dígitos que 1 y 0 o como en realidad trabaja la computadora, “apagado” y “encendido” y se es como representa todos los datos con los que trabaja la computadora, desde sumás bajo nivel: el hardware.

Estos dígitos son llamados bits.Para trabajar la computadora agrupa a los bits en grupos de ocho, a los cual es denomina byte y es esta la razón por la que es tan importante el sistema octal, sin embargo una computadora no puede trabajar con el sistema octal como tal, si no que utiliza su conversión en sistema binario, usando tres bits para cada digito octaL.
El sistema hexadecimal es empleado al indexar la memoria o al representar un byte debido a que al contener más dígitos es posible usar menos números para representar números más grandes, haciendo posible que un byte, conformado por8 bits o términos binarios, se represente con solo dos términos hexadecimales, lo que es un ahorro de información.

Sin embargo, la computadora tampoco reconoce el sistema hexadecimal como tal y, al igual que el sistema octal, lo representa con términos binarios, empleando conjuntos de cuatro bits, para cada término hexadecimal. Sin embargo al presentar información al usuario es más factible presentar A9 que 10101001. Por último el sistema decimal únicamente se utiliza al interactuar con el usuario,debido a que un usuario común no está acostumbrado a tratar con diferentessistemas numéricos
AUTORIZO:
M.C.C. CARLOS JULIAN GENIS TRIANA

REALIZO:
NESTOR ISAIAS ESPINOZA JUAREZ

FIN
Full transcript