gabbometal

CAPÍTULO III. ÁRBOLES BINARIOS En la vida cotidiana, muchas vedes sin saberlo, trabajamos en ocasiones con los árboles. Por ejemplo: árboles genealógicos, organigramas, directorios en los discos de un computador, etc. Cada uno de estos conceptos representa un árbol. ORGANIGRAMA DE UNA EMPRESA ORGANIZACIOND E UN DIRECTORIO EN UN COMPUTADOR 3.1.DEFINICIONES En el área de la computación también se conoce una materia que trata de los árboles. Este tema es muy extenso y para su estudio vamos a dividirlo en varios capítulos. En este capitulo nos vamos a circunscribir solamente en el estudio de los árboles binarios. Este tipo de árbol se caracteriza porque tiene un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha. La rama izquierda y la derecha, también son dos árboles binarios. El vértice principal se denomina raíz y cada una de las ramas se denomina árbol izquierdo y árbol derecho. Por ejemplo: La raíz de este árbol es A y el árbol izquierdo esta conformado por otro árbol. Que a su vez tiene como raíz B. el árbol derecho esta conformado también por otro árbol. DEFINICIONES NODO Un árbol binario es un conjunto de elementos cada uno de los cuales se denomina nodo. Un árbol binario puede tener cero nodos y en este se dice que esta vació. Puede tener un solo nodo, y en este caso existe solamente la raíz del árbol o puede tener un número finito de nodos. Cada nodo que esta ramificado por la izquierda o por la derecha o puede no tener ninguna ramificación. La anatomía de un nodo en un árbol binario es la siguiente: Información del nodo Apuntador al árbol de la derecha Apuntador al árbol de la izquierda Raíz en un árbol binario se pueden distinguir la raíz principal y las raíces de los demás subárboles. Por ejemplo: La raíz principal es el nodo cuya información es A. podemos distinguir también el árbol. Cuya raíz es el nodo con información D. Este nodo es la raíz del árbol de la derecha. El Árbol de la izquierda Tiene como raíz el nodo cuya información es B y tiene solamente una ramificación. PADRE Un padre es un nodo que puede o no tener ramificaciones. Por ejemplo: Caso 1 caso 2 caso3 En los tres casos el nodo A es un padre. En el caso 1 es un padre que no tiene hijos. En el caso 2, el nodo A es el padre del nodo B. en el caso 3 el nodo A es padre de los nodos By C peo no es padre del nodo D. HIJO Nos referimos al ejemplo anterior. En el caso 1 el nodo A no tiene hijos. En el caso 2, B es un hijo del nodo A y en el caso 3, D es hijo de B y el padre de B es el nodo A HERMANO Nos referimos al caso 3 del ejemplo anterior. Los hermanos son los hijos de un mismo padre. Los nodos B y C son hermanos. El nodo D no tiene hermanos HOJA Una hoja es un nodo que no tiene ramificaciones. Por ejemplo El nodo C es una hoja mientras que el nodo B no se puede considerar como hoja porque tiene una ramificación por la derecha. El nodo D también es una hoja NODO NO TERMINAL Un nodo no Terminal es aquel que posee por lo menos una ramificación. En el ejemplo anterior, el nodo A o el B son nodos no terminales, mientras el nodo D o el nodo C son nodos terminales. CAMINO Un árbol siempre se examina hacia abajo. Por ejemplo: Al nodo C podemos llegar desde el nodo B. Nunca se puede examinar el nodo B a partir del nodo C. Los apuntadores derecho o izquierdo de cualquier nodo apuntan al árbol derecho o izquierdo que siguen a ese nodo. Nunca apuntan a los nodos precedentes. Un camino es el conjunto de nodos que tenemos que visitar con el propósito de llegar a un nodo específico. Por ejemplo para llegar al nodo F es necesario recorrer el camino A D F Del mismo nodo, para llegar al nodo G debemos recorrer el camino A D E G Obsérvese que los caminos se configuran siempre hacia abajo. Nunca se puede hablar de un camino para llegar al nodo C así: G E D A B C Este camino se puede configurar. LONGITUD Longitud es el número de nodos que se deben recorrer para pasar de un nodo a otro. Por ejemplo: La longitud entre A y E es 3. La longitud entre G y G es 0. La longitud entre A y B es 1 Obsérvese que no podemos calcular la longitud entre B y G ya que el camino B A G no existe. DESCENDIENTE El nodo C es descendiente del nodo A si a partir de A podemos llegar a C a través de un camino. Por ejemplo: El nodo C es descendiente de A ya que a C podemos llagar por el camino A B C Siempre que exista un camino para llegar de un nodo V a un nodo X, el nodo X es un descendiente de V. pAra el ejemplo anterior, el nodo E es descendiente de D pero el nodo no es descendiente de B ANCESTRO El nodo A es un ancestro del nodo C si existe un camino entre A y C. basándonos en el ejemplo anterior. A es un ancestro de C ya que existe un camino entre los nodos. No se puede hablar de que D sea ancestro de ya que el camino D A B no existe NIVEL Cada nodo tiene un nivel dentro de un árbol binario. Por definición el nodo raíz tiene un nivel y de los demás nodos tienen el nivel de su padre más 1. Por esto los nodos que son hijos del nodo raíz tienen un nivel 1. Veamos este ejemplo NIVEL 0 NIVEL 1 NIVEL 2 NIVEL 3 Los nodos A, M y S tienen un nivel 0 en tanto que los nodos G y V tienen un nivel 3. Obsérvese que le nivel del nodo G es la longitud del camino desde la raíz hasta el nodo. GRADO DE UN NODO El grado de un nodo es el número de hijos. Por ejemplo el grado del nodo A es 2, el grado del nodo T es 1. El grado de un nodo Terminal siempre es 0.en los árboles binarios, el grado de un nodo fluctúa entre 0 y 2. Existen otros tipos de árboles, (árbol n_ario), en los cuales esta restricción no existe. Estos arboles serán estudiados en el segundo tomo de este libro ALTURA La altura de un árbol binario es el nivel de la hoja o de las hojas que están más distantes de la raíz. Basándonos en el ejemplo anterior, la altura del árbol cuya raíz es A, corresponde a la longitud del camino para llegar a la hoja más distante de la raíz. En este caso será 3. La altura cuya raíz es M, corresponde al nivel de la hoja P. ARBOL BINARIO COMPLETO Un árbol binario completo es aquel en el que todo nodo no Terminal tiene sus dos hijos. El siguiente es un árbol binario de nivel 3: NIVEL 0 NIVEL 1 NIVEL 2 NIVEL 3 Obsérvese que todos los nodos no terminales tienen sus dos hijos. El máximo número de nodos que puede tener un árbol de nivel n es: 20 + 21 + 22 + 23….+ 2n Si n es 3 entonces 20 + 21 + 22 + 23 =15 Este árbol es un árbol binario completo de nivel 3 y este es el máximo número de nodos que puede tener un árbol de nivel 3. ARBOL BINARIO IGUAL Dos árboles son iguales si los dos son vacíos. Existe otro caso ene. Cual dos árboles son iguales: Estos árboles son iguales porque sus raíces son iguales y también lo son su respectivo árbol izquierdo y derecho. Para que un árbol sea igual a otro, es necesario que el contenido de cada uno de sus respectivos nodos sea el mismo y que legan las mismas relaciones de parentesco. Por ejemplo los siguientes árboles Son diferentes porque el contenido de sus respectivos nodos es diferente. Obsérvese que sus nodos tienen las mismas relaciones de parentesco. ARBOL BINARIO SEMEJANTE Dos árboles son semejantes si tienen el mismo número de nodos y los valores de los nodos del primer árbol son los mismos que los valores de los nodos del segundo, sin importar la relación de parentesco entre ellos. Por ejemplo: Estos árboles son semejantes. Contienen los mismos valores en cada uno de sus nodos. ARBOL BINARIO ISOMORFO Dos árboles binarios son isomorfos si tienen la misma estructura aunque el contenido de cada uno e sus nodos sea diferente. Por ejemplo los siguientes árboles son isomorfos. PESO El peso de un árbol en un nodo dado es el número de nodos en el árbol sin contarse el mismo. Por ejemplo: El peso del árbol cuya raíz es A corresponde al número de nodos de ese árbol: los nodos Q,C y R tienen un peso de 2 FORMAS DE RECORRER UN ARBOL BINARIO Universalmente existen 3 formas de recorrer un árbol binario:  Preorden  Inorden  Posorden Si logramos construir un árbol como este: Podemos extraer sus datos de 3 maneras. Veamos cada una. Recorrer un árbol en preorden consiste en:  Examinar el ato del nodo raíz  Recorrer el árbol izquierdo en preorden  Recorrer el árbol derecho en preorden Si deseamos recorrer todo el árbol, evidentemente debemos comenzar por el nodo raíz. Este método exige examinar primero el nodo raíz debemos entender como examinar un nodo, el hecho de efectuar sobre su información cualquier acción: por ejemplo escribirla, efectuar alguna operación matemática sobre ella o con ella, modificarla. También en la gran mayoría de los textos de estructuras de información, se utiliza el termino visitar un nodo. Entre la palabra examinar y la palabra visitar existe una diferencia. Examinar un nodo es revisar su contenido y eventualmente modificarlo en tanto que visitar un nodo es utilizar la dirección de ese nodo con el propósito de seguir explorando el árbol hacia abajo. Si deseamos recorrer un árbol en preorden, con el propósito de escribir su contenido, debemos examinar el contenido de cada uno se sus nodos, mientras si deseamos contar sus nodos, es necesario visitar cada nodo. Supongamos que deseamos escribir un árbol en preorden. Para hacerlo, se debe examinar el nodo raíz y luego recorrer el árbol de la izquierda en preorden. ARBOL A LA IZQUIERDA DE A Recorrer este árbol en preorden es examinar su nodo raíz y recorrer de nuevo el árbol de la izquierda preorden. ARBOL A LA IZQUIERDA DE B Recorrer este árbol en preorden es examinar su nodo raíz. Como ya no existen nodos por la izquierda, debemos empezar a recorrer el árbol D por la derecha. Como ya no existen nodos por la derecha, debemos recorrer el árbol. Por la derecha. El árbol de la derecha lo debemos recorrer también en preorden. ARBOL A LA DERECHA DE B Recorrer este árbol en preorden, es examinar su nodo raíz y recorrer el árbol por la izquierda en preorden y luego recorrerlo por la derecha. Como no existen árboles ni por la izquierda ni por la derecha, debemos recorrer el árbol. En preorden. El orden en el cual debemos examinar estos nodos es: primero el nodo C, luego F y luego G. por lo tanto al imprimir el árbol anterior en preorden, los resultados deben ser: A B D E C F G Antes de seguir adelante, el lector debe certificar que el árbol: Al imprimirlo recorriéndolo en Preorden debe generar los siguientes resultados: 10 5 3 1 4 7 9 15 14 17 16 20 Ahora veamos la segunda forma de recorrer un árbol binario. Recorrer un árbol en inorden, consiste en: Recorrer el árbol izquierdo en inorden Examinar la raíz Recorrer el árbol derecho en inorden. Por ejemplo: Si queremos imprimir este árbol en inorden, debemos primero recorrer el árbol izquierdo en inorden: Al tratar de recorrer este árbol en inorden y no existe árbol por su izquierda debemos examinar el nodo y luego recorrer el árbol de su derecha. Al no existir árbol por su derecha, entonces el árbol a la izquierda del nodo A ha sido totalmente recorrido. Siguiendo con las normas establecidas inicialmente, debemos examinar el nodo A y luego recorrer el árbol a la derecha del nodo A ARBOL DERECHO DE A Para recorrer este árbol en inorden primero debemos recorrer el árbol izquierdo. Al no existir árbol izquierdo, se debe examinar este nodo y luego recorrer el árbol derecho. Al no existir árbol derecho, el árbol ya ha sido recorrido en su totalidad. Por lo tanto los datos impresos serán: B A C Observemos este otro ejemplo Debemos recorrer en inorden el árbol a la izquierda de la raíz: Al recorrer este árbol en inorden ya sabemos, de acuerdo a la explicación del ejemplo anterior, que los resultados son: 3 5 7 Al terminar de recorrer el árbol a la izquierda de la raíz, debemos examinar la raíz y luego recorrer en inorden el árbol a la derecha de la raíz Sabemos que al recorrer este árbol en inorden, los resultados son: 11 12 15 Con lo cual al examinar todo el árbol en inorden, los datos impresos serán: 3 5 7 10 11 12 15 Se invita al lector a certificar que al recorrer el siguiente árbol binario en inorden los resultados son: H D I B E A J F C K G L Veamos el árbol Por ultimo estudiemos la tercera forma de recorrer un árbol binario. Examinar un árbol binario en posorden consiste en:  Recorrer el árbol izquierdo posorden  Recorrer el árbol derecho en posorden  Examinar la raíz. Veamos un ejemplo: Al recorrer el árbol izquierdo en posorden, el único dato impreso será B. después de haber recorrido todo el árbol de la izquierda en posorden, se debe recorrer todo el árbol de la derecha en posorden. Al recorrer el árbol de la derecha en posorden, el único dato impreso será C. una vez recorridos los árboles izquierdo y derecho, debemos examinar la raíz. Según esto los datos impresos serán. B C A Ejercicios 1. Elaborar un programa que cree en la memoria del computador el siguiente árbol binario: 2. Dado el siguiente árbol binario: Certificar que al recorrer el árbol, los siguientes resultados son correctos: Preorden ABCDFGEIJ Inorden BAFDGCIEJ Posorden BFGDIJECA 3. Suponga que en memorial del computador existe el siguiente árbol: Escriba un conjunto de instrucciones que cree un nodo X a la derecha de B y un nodo Y a la derecha de E. 4. dado el siguiente árbol: raíz Cuales serian los datos impresos si se recorre en: Preorden Inorden Posorden MANTENIMIENTO DE UN CONJUNTO DE NUMEROS CLASIFICADOS ASCENDENTEMENTE, UTILIZANDO UN ARBOL BINARIO ORDENADO. Utilizando un árbol binario, es posible mantener un conjunto de números clasificados ascendentemente sin necesidad de rutinas de ordenamiento. Se plantea el problema de leer un conjunto de enteros y listarlos clasificados ascendentemente. Los números repetidos deben ser rechazados. Por ejemplo si la entrada es: 87 25 23 25 48 8 92 El programa debe generar los siguientes resultados: 8 23 25 48 87 92 Este problema se puede resolver fácilmente utilizando un árbol binario ordenado. Solamente es necesario ir leyendo cifra por cifra e ir adicionándola en el árbol así: si es menor al contenido del nodo analizado la instemos por la izquierda de ese nodo y se es mayor por la derecha. Veamos: al leer el número 87, creamos con este dato el nodo raíz. Luego al leer el 25, como 25 es menor que 87, creamos un nuevo nodo a la izquierda de 87. Visualmente el árbol creado hasta el momento sería: Luego al leer el número 23, como este dato es menor a 87, nos debemos desplazar hacia abajo por la izquierda. Al llegar al 25, debemos crear un nuevo nodo a la izquierda por el hecho de que 23 es menor que 25, así: Al leer el siguiente dato este debe ser rechazado porque ya existe en el árbol. Al leer el 48, debemos desplazarnos por la izquierda y al compararlo con 25, se debe crear un nuevo nodo a la derecha del 25, así: Siguiendo este mismo procedimiento, enumero 8 debe insertarse a la izquierda del 23 así Por ultimo al leer el numero 92 este debe insertarse a la derecha del 87. Los datos en el. Árbol quedan, finalmente, distribuidos así: Si imprimimos el contenido del árbol, recorriéndolo en inorden. Tendremos la lista pedida: 8 23 25 48 87 92 IMPRESIÓN DE UN ARBOL EN INORDEN Observemos el siguiente árbol: Raíz Al escribir este árbol en inorden los resultados serán: 3 5 6 7 8 10 15 20 Observando el proceso, lo primero que se escribe siempre es el contenido del nodo de la extrema izquierda del árbol. Luego debemos escribir el contenido del nodo padre para luego escribir en inorden el árbol de la derecha. IMPRESIÓN DE UN ARBOL EN PREORDEN USANDO UNA PILA Deseamos escribir un árbol en preorden. Veamos esta estructura: R A G B I E H D F J La función que vamos a elaborar debe escribir: 100 50 30 10 40 60 65 150 120 160 180 Esta nueva función se diferencia de a función inorden ( ), en que en aquella primero se recorría el árbol izquierdo y luego si se escribía el contenido del padre de ese árbol. En esta nueva rutina primero se debe escribir el contenido del padre del árbol y luego se recorrer en preorden la rama izquierda. El siguiente paso consiste en retirar de la pila la dirección C y determinar si existe un árbol por la derecha del nodo indicado por C. siguiendo el comportamiento de la pila, podemos por esto, deducir que esta función es muy parecida a la función inorden ( ). La diferencia radica en que antes de analizar el árbol izquierdo, la información del nodo ya ha sido escrita. Veamos el comportamiento del proceso: Contenido la pila numero escrito 100 50 30 10 - - 40 - 60 65 - - 150 120 - 180 - IMPRESIÓN DE UN ARBOL EN POSORDEN USANSO UNA PILA La impresión de un árbol en posorden, es un poco más compleja y requiere de modificaciones en el manejo de la pila Veamos este árbol: La impresión en posorden es: 3 7 5 20 40 30 10 Antes de imprimir el nodo, debemos recorrer el árbol izquierdo y luego el derecho. Es claro que primero debemos llegar hasta la hoja de la extrema izquierda del árbol, guardando los apuntes en una pila para luego poder recuperar las direcciones de todos los ancestros de esa hoja. Se llegamos a la hoja: Antes de escribir el contenido del nodo debemos certificar que ya han sido recorridos en posorden los árboles izquierdo y derecho. IMPRESIÓN DE UN ARBOL POR NIVELES USANDO UNA COLA Imprimir un árbol por niveles, es imprimir primero su raíz, luego los contenidos de los nodos del nivel 1, luego los contenidos de los nodos del nivel 2, y así sucesivamente hasta imprimir el contenido de los nodos del ultimo nivel. Por ejemplo: Al imprimir este árbol por niveles, los resultados serán: 20 10 30 5 15 25 40 7 50 Aprovechando una estructura FIFO, podemos efectuar esta impresión sin ningún problema. Al comenzar almacenamos en una cola la dirección del nodo raíz: Ahora mientras la cola no este vacía, retiramos el primer elemento de la cola y escribimos el contenido de la dirección del elemento retirado e insertamos en la cola las direcciones izquierda y derecha almacenadas en el contenido de la dirección retirada de la cola Siguiendo este mismo procedimiento, tendríamos los siguientes estados de la cola: 10 30 5 15 25 40 7 50 Revisando el proceso anterior, observamos dos cosas: la primera es que cuando un apuntador es NULL, a la cola no se adiciona ningún elemento y la segunda es que este proceso repetitivo se debe efectuar mientras la cola no esté vacía. RECONSTRUCCION DE UNA RBOL BINARIO Se plantea el problema de reconstruir un árbol binario dados sus recorridos en preorden y en inorden. Por ejemplo, si un árbol genera lo siguiente: al recorrerse en preorden: G E A I B M C L D F K J H Y genera lo siguiente al recorrerse en inorden: I A B E G L D C F M K H J Se requiere de un programa que a partir de estos datos, genere un árbol binario al cual correspondan las dos impresiones. Vamos a considerar que a la función que elabora este trabajo entran dos arreglos. El método es muy sencillo y consiste en utilizar una estructura LIFO como la herramienta fundamental. Lo más sencillo del proceso es determinar la raíz del árbol. Para el caso que nos ocupa la raíz será: Vamos a utilizar los apuntadores p y q como auxiliares de trabajo. Pre G E A I B M C L D F K J H In I A B E G L D C F M K H J Si se recorre este árbol en Preorden, el primer nodo que visita es G y al recorrerlo en inorden el nodo del extremo izquierdo es I. en este lugar podemos afirmar que los nodos EAIB, forman el sub.-árbol izquierdo de G y los nodos MCLDFKJH el sub.-árbol derecho q Raíz p El problema esta dividido en dos. Ya sabemos que la raíz es G y también sabemos los componentes de la izquierda y de la derecha. Ahora podemos guardar en una pila los componentes del árbol derecho y seguir trabajando sobre el árbol izquierdo. Es decir tratar de organizar el árbol izquierdo. La pila quedara así: Vamos a considerar la G del recuadro como un apuntador que esta en la pila que nos indica la dirección del nodo padre de este sub.-árbol derecho. Ahora debemos seguir trabajando con el sub.-árbol izquierdo. EAIB IABE De la misma forma, el nodo raíz de este nuevo árbol es E. este nodo debe conectarse al nodo G así Q El apuntador que siempre debe estar dirigido al nodo al cual se conectara el nuevo nodo posteriormente. Siempre el nuevo nodo será indicado por el apuntador p. con lo anterior el árbol estará organizado así: Obsérvese con cuidado porque el nodo E no tiene sub-árbol derecho. Siguiendo el mismo orden, debemos crear un nodo A, el cual conectara por la izquierda con E y este nodo si tendrá sub- árbol por la derecha, así: Como siempre que aparezca un sub-árbol derecho debemos actualizar la pila , su nueva información será: Siguiendo por la izquierda, ahora podemos conectar el nodo I, quedando el árbol así: En este lugar debemos efectuar un retiro de la pila y conectar el nuevo nodo por la dercha del nodo indicado por el apuntador que estaba almacenando en el primer elemento de la pila. Con esto, el arbol queda así: Y la pila contendrá solamente un elemento. Como ya se distribuyo la información el árbol izquierdo, debemos retirar de la pila el elemento y conectar por la derecha un nuevo nodo M, quedando el árbol así: La nueva información de la pila será. Y continuamos trabajando con el árbol izquierdo. Siguiendo hacia la solución, debemos crear un nodo C y guardar en la pila el sub-árbol derecho que se conectara al nodo C posteriormente. La pila hasta el momento tendrá estos datos: Acercándonos un poco mas hacia la solución, el árbol se puede ver así: Y la pila almacenara la siguiente información: Obsérvese que siempre que se identifique un sub-árbol derecho, la pila debe ser actualizada. Como ya se acabo la información a distribuir por la izquierda, debemos efectuar un retiro de la pila, con el propósito de seguir el proceso. Efectuando este retiro y sabiendo el nodo al cual debemos conectar el nuevo nodo por la derecha, podemos hacer adecuadamente la inserción del nuevo nodo. El primer elemento de la pila es: Esto quiere decir que el nodo D se debe conectar a la derecha del nodo L, así: De la misma manera, el nodo F debe conectarse a la derecha del nodo C. Después de conectar el nodo F, debemos retirar de la pila el último elemento y comenzar a distribuir por la izquierda la nueva informaron. Veamos el arbol hasta este momento: Y la pila contendrá la siguiente información Ahora al haber distribuido la rama izquierda (no existe rama izquierda e K ), podemos retirar de la pila su único elemento y crear un nodo J e insertar en la pila su rama derecha, ( no existe rama derecha), así: Al observar el proceso, vemos que la pila queda vacía y falta adicionar al árbol el nodo H. con esto podemos afirmar que el proceso se debe efectuar mientras la pila no este vacía o exista información para distribuir por la rama izquierda. Por lo tanto el árbol final será: Existe un buen número de formas para construir una función que efectué el proceso anterior. A continuación presentamos una de estas versiones codificada en lenguaje C. NOTACIONES INFIJO, POSFIJO Y PREFIJO Cuando se nos pregunta, por ejemplo, cuanto es el resultado de 5 multiplicado por 8 más 3, la respuesta automática que se da es 43. No se da el caso de que la respuesta dad sea 55. Ahora si pregunta es: cual es la respuesta de 3 mas 5 multiplicado por 8, también volveremos a dar la misma respuesta: 43. No se nos ocurre sumas 3 y 5 luego multiplicar la respuesta por 8 para que nos de 64. Se nos pregunta cual es la respuesta de 5 por 2 mas 8 por 3, la respuesta dada es 34. Nos hemos acostumbrado a través del tiempo a que el operador * tiene mas prioridad que el operador + y así lo trabaja cerebro. La notación con la cual trabajamos los humanos este tipo de expresiones se denomina infijo, donde la presencia de los operadores es: * / - + = Los humanos trabajamos con notación infijo. De la misma manera los computadores están diseñados para que reconozcan la misma prioridad que reconocemos los humanos. La instrucción: Resol = 5 * 2 + 8 * 3; Deja almacenada, por ello, la cifra 34, ya que la asociación automática es: (result: (5 * 2)+(8 * 3)); Si deseamos que un computador, o un ser humano, calcule: Resul= 5 * 2 + 8 * 3; Pero sumando 2 y 8 primero, debemos diseñar la instrucción así: Result= 5 * (2 + 8) * 3: Se utilizan los paréntesis para modificar la prioridad de los operadores. Un programador al indicarle esta instrucción a un computador: Resul= 5 * 2 + 8 * 3; Espera la respuesta 34 pero no le interesa como lo hizo la maquina. Internamente, esta operación la ejecuta utilizando una pila. La operación la ejecuta reconociendo objeto a objeto. Vamos a ilustrar la transformación que debe hacer la maquina con el propósito de efectuar la operación anterior. De lo único que esta enterada tanto la maquina como el programador, es que el operador * tiene mas prioridad que el operador +. La transformación que se realiza es convertir la expresión de notación infijo a notación posfijo lo cual se estudiará en el siguiente numeral. A continuación estudiaremos que es la notación posfijo. La notación posfijo, es otra manera de escribir una expresión aritmética. La notación posfijo, se caracteriza por la ausencia de paréntesis. Esta notación, aunque nunca utiliza paréntesis, es presentada sin ningún tipo de ambigüedad. Veamos su naturaleza. Si tenemos una expresión en notación infijo. Por ejemplo: a +b Para escribir esa misma expresión en posfijo. Se debe ejecutar los siguientes pasos: 1. agrupar utilizando paréntesis, de acuerdo a la prioridad de los operadores, así: (a+b) 2. escribir en posfijo la expresión, así: ab+ Obsérvese que en la notación posfijo, el operador se escribe después de los operadores . Veamos otro ejemplo: a + b * c Agrupando tenemos: a + ( b * c ) Convirtiendo a posfijo la expresión entre paréntesis resulta: a + ( b c * ) Ahora tratando la expresión entre paréntesis como un operador tenemos a ( b c * )+ y destruyendo los paréntesis, nos queda la expresión escrita en posfijo: a b c * + Veamos este ejemplo; ( x * y ) + ( v * w ) Primero debemos convertir las expresiones encerradas entre paréntesis a notación posfijo, así: ( x y * ) + ( v w * ) Y luego toda la expresión a notación posfijo, así x y * v w * + Veamos estos ejemplos: 1. (a+b)*( c+d) ( a b + ) * ( c d + ) a b + c d + * 2. a+b-c ( a b + ) - c a b + c - 3. (a+b)*(c-d)*e*f ((( a b + ) * ( c d - )) * e ) * f (( a b + c d - * ) * e ) * f ( a b + c d - * e * ) * f a b + c d - * e * f * 4. (a+b)*(c/(d-e)+f)-g ( a b + ) * ( c / ( d e - ) + f ) - g ( a b + ) * ( ( cd e - / )+ f ) – g ( a b + ) * ( c d e - / f + ) - g a b + c d e - / f * g – 5. vamos a suponer que la operación exponenciación esta definida y la representamos así: además, tiene la mayor prioridad de todos los operadores. Veamos estos ejemplos, usando este nuevo operador: (a b c) (a b) c ab c 6. a b * c – d + e / f/ (g+h) ((a b) * c – d ) + ( e / f ) / ( g+ h ) (ab c * d - ) + ( ef / gh + / ) ab c * d – ef / gh + / + 7. a + ((( b – c ) * ( d – e ) + f ) / g ) (h – j ) a + ((( bc - de - * f + ) / g ) (hj - ) a + (( bc – de - * f + a / hj- ) abc – de - * f + g / hj- + Existe otro tipo de notación para escribir las expresiones aritméticas. Esta nueva notación recibe el nombre de prefijo y recaracteriza porque los operadores se escriben primero que los operadores. Por ejemplo la expresión: a+b Escrita en notación prefijo, sería: -ab En general todas las reglas para convertir infijo a posfijo, se aplican para efectuar las conversiones infijo a prefijo, tendiendo en cuenta que los operadores se escriben antes que los operadores. Veamos estos ejemplos: 1. a+b+c (a-b)+ (+ab)+c ++abc 2. a+b-c (a-b)-c (+ab)-c -+abc 3. (a+b)*(c-d) (+ab)*(-cd) *+ab-cd 4. a+b/c-d a+(b/c)-d (a+(/bc))-d (+a/bc)-d - + a / bcd 5. a b*c-d+e/f/(g+h) (((a b) * c ) – d ) + ( e/f ) / (g+h) ( - * abcd) + ( / ef ) / ( + gh) - * abcd + (//ef + gh) + - * abad //ef+gh Podemos también plantear algunos ejemplos para convertir de posfijo a prefijo o infijo. Veamos primero algunos ejemplos para convertir de posfijo a infijo: 1. ab+ El operador se debe aplicar a los últimos dos operandos, quedando así: a+b 2. ab+c- El análisis se comienza por la izquierda de la expresión. Se debe recorrer la expresión hasta que encontremos un operador, así: ab+c- Una vez hayamos encontrado el primer operador, debemos aplicar ese operador a los dos últimos operandos que lo precedan, así (a+b)c- Y luego debemos seguir analizando la expresión hasta encontrar el próximo operador: (a+b)c- Una vez hayamos encontrando el próximo operador debemos aplicar ese operador a los últimos dos operandos. Obsérvese que la expresión encerrada entre paréntesis, se debe trabajar como un solo operando. (a+b)-c 3. ab+cd-* Siguiendo el proceso anterior, tenemos: (a+b)cd-* (a+b)(c-d) (a+b)*(c-d) 4. ab+cd-*e*f* (a+b)cd - * e * f * (a+b)(c-d)e * f * ((a+b)*(c-d)*e) f * ((a+b)*(c-d)*e) * f (a+b)*(c-d) * e * f 5. ab c (a b)c (a b)c a b c 6. ab c*d-ef / gh+/+ (a b*c)d-ef / gh + / + (a b*c-d)ef / gh + / + (a b* c-d)(e/f) gh + / + (a b*c-d)(e/f)(g+h) / + (a b*c-d)((e/f)/(g+h)) + (a b*c-d)+(e/f)/(g+h) A b*c-d+e / f / (g+h) De la misma manera, podemos pasar de la notación prefijo a la notación infijo; veamos un ejemplo +ab En este caso debemos analizar la expresión de derecha a izquierda hasta que encontremos el primer operador. Una vez lo hayamos encontramos, aplicamos este operador a los dos operandos que le siguen, así: a+b Veamos algunos ejemplos: 1. -+abc -(a+b)c (a+b)-c a+b-c 2. *+ab - cd * + ab(c-d) * (a+b) (c-d) (a+b) * (c-d) 3. -*+abc - de -fg -*+abc – de (f-g) -*+abc (d-e) (f-g) -*(a+b)c(d-e)(f-g -((a+b)*c)(d-e)(f-g) (((a+b)*c)-(d-e))(f-g) ((a+b)*c-(d-e)) (f-g) EJERCICIOS 1. cada una de las siguientes expresiones escritas en fijo convertirlas a posfijo a) (x+y)*(z (s+t)+u)-v b) a+((x+y)*(w+v)) (i+j) 2. Convertir las expresiones del ejercicio anterior a prefijo 3. Convertir las siguientes expresiones de prefijo a infijo: a) + - xyz*i**klm b) ++1-* mno/+pq*rst 4. Convertir las siguientes expresiones en posfijo a infijo a) pqrst-+ *uv*- b) lm-n+opq-+ REPRESENTACION DE EXPRESIONES ARITMETICAS EN ÁRBOLES BINARIOS Una expresión aritmética puede expresarse utilizando un árbol binario. Por ejemplo la expresión: a+b Expresada en un árbol binario es: El operador +aplica a los operandos de la rama izquierda y la rama derecha. La expresión: a+b*c Quedara expresada así: El árbol queda organizado así ya que la expresión implícitamente esta asociada así: a+(b*c) Porque por definición el operador * es de mayor jerarquía que el operador + Vamos a construir un árbol par ala expresión: a / b * c + d e * f para defecto esta expresión escrita en infijo, asocia sus operandos así: (( a / b ) * c ) + (( d e ) * f ) Esto indica que la raíz del árbol contiene el operador+. La rama izquierda contiene la expresión (a / b ) * c y la rama derecha la expresión (d e )*f. siguiendo este orden de ideas el árbol queda construido así: Existe un método sencillo para construir una árbol que representa un a expresión. El primer paso consiste en transformar la expresión de infijo a prefijo y partiendo de la expresión escrita en prefijo construir el árbol. Veamos algunos ejemplos: Infijo a+b Prefijo +ab Al tener la expresión en prefijo, fácilmente se puede construir el árbol siguiendo este método: Se insertan nuevos nodos por la izquierda del árbol que hayamos insertado un operando +a Luego volvemos hacia atrás en el árbol e insertamos el siguiente elemento a su derecha. +ab Si el nodo insertado fue un operador, insertamos el siguiendo a su izquierda. Si el nodo insertado fue un operando, volvemos hacia atrás e insertamos el siguiente nodo a la derecha. Este proceso se continúa hasta que se agote la expresión escrita en prefijo. Veamos otro ejemplo: Infijo a+(a*c d) Primero debemos convertir la expresión a prefijo: +a*b cd Luego debemos insertar nuevos nodos hasta encontrar un operando: +a Luego volvemos hacia atrás e insertamos el siguiente elemento a la derecha: +a* Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda: +a*b Como el nodo mas reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha. +a*b Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda: + a * b c Como el nodo más reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha: +a*b cd Siguiendo este método, y antes de seguir adelante, se recomienda al lector revisar los árboles para las siguientes expresiones en prefijo: CONVERSION DE UNA EXPRESION EN UN ARBOL BINARIO A SU REPRESENTACION INFIJO En este numeral se desarrollara una función que a partir de un árbol binario, genere un arreglo que almacene la expresión en infijo. Antes de entrar propiamente en el desarrollo del problema, estudiaremos algunas propiedades de estos árboles. Supongamos que tenemos en la memoria del computador un árbol así: Este árbol representa la siguiente expresión a+b*c La expresión anterior escrita en prefijo será: + a * bc Si recorremos el árbol en preorden los datos generados serán: +a*bc Lo anterior nos permite plantear la primera propiedad: Si se recorre un árbol en preorden, los datos generados representan la expresión escrita en prefijo. Si el árbol anterior recorremos en posorden, los datos generados serán: a b c * + Estos datos representan la expresión a + b * c Escrita en posfijo, lo cual nos permite plantear la segunda propiedad: Si se recorre un árbol en posorden, los datos generados representan la expresión escrita en posfijo. Es de esperarse que si recorremos el árbol en inorden, la expresión generada estará escrita automáticamente en infijo. Veamos: a+b*c Para el caso que nos ocupa se cumplió la norma. Veamos otro ejemplo: (a+b) c/d+e Esta expresión escrita en prefijo será: + / + a b c d e Y en posfijo será: a b + c d / e + y el árbol generado será: Al recorrerlo en preorden, los datos generados serán: + / + a b c d e Al recorrerlo en posorden, los datos generados serán: a b + c d / e + Las dos propiedades anteriores se cumplen. Se recorremos el árbol en inorden los datos generados serán: a + b c / d + e Pero esta expresión, para su evaluación, se asocia así: a + ( ( b c ) / d ) + e Y es bien diferente da la inicial, la cual era: (a+b) c/d+e Lo cual nos permite plantear la siguiente propiedad: Si se recorre un árbol en inorden, los datos generados no representan la expresión escrita en infijo. Si queremos que de un árbol se genere la correspondiente expresión en infijo no basta con recorrerlo en inorden, además debemos efectuar un proceso que parentice la expresión. Para el ejemplo, el recorrido inorden del árbol es: a+b c/d+e Como el operador tiene más prioridad que los demás, y el operador / tiene más prioridad que el +, al tratar de evaluar la expresión esta se asocia así: a + ( ( b c ) / d ) + e Debemos diseñar un proceso que genere un arreglo infijo con los siguientes datos: Lo cual implica que en la medida en que generamos este arreglo debemos ir incluyendo paréntesis donde sea necesario. Veamos la naturaleza del problema: Como el operador de la raíz aplica a los dos subárboles, gráficamente el árbol anterior lo podemos representar así: 1 2 3 4 Si cada cuadro representa un par de paréntesis, este árbol lo podríamos escribir así: (rama izquierda )+e ((rama izquierda ) / ) d ) + e (((rama izquierda ) c ) / d ) + e ((((rama izquierda) + b) c ) / d ) +e ((( a ) + b) c ) / d + e Ahora retiramos los paréntesis innecesarios, debidos a la jerarquía de los operadores, tendremos la expresión: ((( a +b) c ) / d ) + e No podemos retirar los paréntesis que encierran la expresión (a+b), debido a que se cambia la expresión ya que el operador es de mayor prioridad que el operador +. Los paréntesis ya encierran la expresión (a+b) c si se puede retirar, debido a que el operador es de mayor jerarquía que el operador / ((a+b) c/d)+e Los paréntesis que encierran la expresión (a+b) c / d pueden ser retirados ya que el operador + es el de al mínima jerarquía. Con la cual la expresión debidamente patentizada es: Veamos otro ejemplo: Si recorremos el árbol en inorden, los resultados serán: a + b c Lo cual es diferente a la expresión que esta representada en el árbol. (a+ b ) c Si el árbol es: Al recorrerlo en inorden los resultados son: a b+c y no existe la necesidad de insertar paréntesis en la expresión. La diferencia, en este caso particular, radica en que si el operador padre tiene más jerarquía que el operador hijo, debemos patentizar la rama izquierda o derecha del árbol. Observemos los siguientes árboles: Para el árbol la expresión será: (a+b) c Debe patentizarse. El operador tiene mas jerarquía que el operador + Para el árbol la expresión será: a b+c no se necesitan paréntesis. El operador + tiene menos jerarquía que el operador Para el árbol la expresión será: (a-b)-c Para esta expresión., no son necesarios los paréntesis ya que sin ellos la asociación se haría de la misma manera. Veamos este caso. Para este caso al recorrer el árbol en inorden, se genera la siguiente expresión: c – a – b Se deben insertar paréntesis ya que es muy diferente la expresión que está representada en el árbol: c – (a - b ) Ahora debemos puntualizar en que momento se necesitan insertar paréntesis. La respuesta es muy sencilla. Veamos este ejemplo Al recorrer el árbol en inorden, el resultado será: a+b-c d+e*f Debemos insertar paréntesis a la expresión a+b-c y también a la expresión d+e*f. al final arreglo infijo quedara así: ( a + b – c ) ((d + e ) * f ) Como puede identificarse esta situación. Obsérvese que si existen dos nodos cuya relación es padre-hijo y los dos contienen operadores, debemos abrir un paréntesis si el operador hijo tiene menos prioridad que el operador padre. Este paréntesis que se abre debe existir siempre y cuando el padre tenga más jerarquía que el hijo y asea izquierdo o derecho. Para insertar un paréntesis son necesarias tres condiciones: 1. que el nodo contenga un operador. 2. que su hijo (izquierdo o derecho) contenga también un operador. 3. que el nodo padre sea un operador de mayor jerarquía que el nodo hijo. Si estas tres condiciones se cumplen debemos abrir un paréntesis. Este paréntesis, guardaremos en algún lugar el paréntesis que cierra para que en su momento, se incorpore al arreglo infijo. Para la solución a este problema debe servirnos una pila ya que el proceso se asimila a escribir un árbol en inorden, con la salvedad de que bajo las tres condiciones expuestas anteriormente, debemos insertar un paréntesis a la pila.

CAPÍTULO I. 1. SISTEMAS NUMERICOS. 1.1 OBJETIVO. En este capítulo damos nociones elementales sobre el conocimiento de los números, sistemas numéricos más utilizados, símbolos, reglas, overflow, realización de operaciones aritméticas básicas y conversiones en los diferentes sistemas numéricos previamente estudiados. 1.2 NUMERACIÓN. Sistema. En esta área del conocimiento significa los símbolos o signos utilizados para darles una expresión a los números. NUMEROS ROMANOS. Este sistema (tan bien conocido por nosotros) tuvo el mérito de ser capaz de expresar los números del 1 al 1.000.000 con solo siete símbolos: I para el 1, V para el 5, X para el 10, L para el 50, C para el 100, D para el 500 y M para el 1000. Es importante acotar que una pequeña línea sobre el número multiplica su valor por mil. En la actualidad los números romanos se usan para la historia y con fines decorativos. La numeración romana tiene el inconveniente de no ser práctica para realizar cálculos escritos con rapidez. NUMERACIÓN ARÁBICA. El sistema corriente de notación numérica que es utilizado hoy y en casi todo el mundo es la numeración arábiga. Este sistema fue desarrollado primero por los hindúes y luego por los árabes que introdujeron la innovación de la notación posicional; en la que los números cambian su valor según su posición. La notación posicional solo es posible si existe un número para el cero. El guarismo 0 permite distinguir entre 11, 101 y 1001 sin tener que agregar símbolos adicionales. Además todos los números se pueden expresar con sólo diez guarismos, del 1 al 9 más el 0. La notación posicional ha facilitado muchísimo todos los tipos de cálculos numéricos por escrito. SISTEMAS NUMÉRICOS. En matemáticas, varios sistemas de notación que se han usado o se usan para representar cantidades abstractas denominadas números. Un sistema numérico está definido por la base que utiliza. La base de un sistema numérico es el número de símbolos diferentes o guarismos, necesarios para representar un número cualquiera de los infinitos posibles en el sistema. A lo largo de la historia se han utilizado multitud de sistemas numéricos diferentes. Valores posicionales La posición de una cifra indica el valor de dicha cifra en función de los valores exponenciales de la base. En el sistema decimal, la cantidad representada por uno de los diez dígitos -0, 1, 2, 3, 4, 5, 6, 7, 8 y 9- depende de la posición del número completo. Para convertir un número n dado en base 10 a un número en base b, se divide (en el sistema decimal) n por b, el cociente se divide de nuevo por b, y así sucesivamente hasta obtener un cociente cero. Sistema binario El sistema binario desempeña un importante papel en la tecnología de las computadoras. Los números se pueden representar en el sistema binario como la suma de varias potencias de dos. Ya que sólo se necesitan dos dígitos; el sistema binario se utiliza en las computadoras. Números: Palabra o símbolo utilizado para designar cantidades o entidades, que se comporten como cantidades. Es la expresión de la relación existente entre una cantidad y otra magnitud que sirve de unidad. Se pueden considerar números todos aquellos conceptos matemáticos para los cuales se definen dos operaciones, de adición y multiplicación, cada una de las cuales obedece a las propiedades conmutativa y asociativa. CONJUNTOS NUMERICOS Números Naturales Dicho en términos muy simples, los números naturales son los que sirven para contar. El conjunto de los números naturales tiene las siguientes propiedades: • Al conjunto de los números naturales pertenecen el 0 y el 1. • Si se suma a un natural el número 1 el resultado es otro número natural. • Por lo tanto el conjunto de los naturales es un conjunto infinito. • Las propiedades enunciadas anteriormente constituyen el Axioma de Inducción Completa. Números Enteros El conjunto de números enteros, es también infinito. Son parejas de números naturales (x,y), cuya resta x-y define un número entero. Por ejemplo: la pareja (7,3) define el entero positivo 4 ya que 7 - 3 = 4. La pareja (2,4) define el entero negativo -2 ya que 2 - 4 = -2. Existe un isomorfismo entre parte del conjunto de los números enteros y el de los números naturales; ya que el conjunto de los naturales es el de los enteros positivos. Al conjunto de los enteros también pertenece el 0 que está definido por todas aquellas parejas de naturales iguales (1,1) ; (56,56) ; etc. Números Racionales El conjunto de números racionales está integrado por parejas de números enteros cuyos elementos se dividen entre sí. A este conjunto también pertenece el 0, que está definido por todas aquellas fracciones que tienen al 0 por numerador. Los racionales serán positivos o negativos según sea el signo de cada uno de los integrantes de las parejas que los definen. Así será que parejas de enteros de igual signo definirán un racional positivo; y parejas de enteros de distinto signo definirán un racional negativo. No existen racionales cuyo denominador sea 0. Números Reales El campo de los números reales es más amplio que el de los racionales; ya que incluye números que no están formados por parejas de enteros. Por ejemplo la relación que existe entre una circunferencia y su diámetro no es un racional.(número Se trata de un conjunto también infinito. Siempre entre dos números reales hay otro número real; de ahí que se asocie al conjunto de los números reales con una recta. La recta está formada por infinitos puntos y cada punto representaría un número real. 1.3 PROCESO DE CUENTA. En lugar del sistema numérico decimal, se puede utilizar la numeración binaria, introducida en la ciencia de la matemática por Leibnitz en el siglo XVII, que solo utiliza dos tipos de símbolos, el 0 y el 1. también es practico en computación, donde se utilizan corrientemente números de base 8 y 16 elementos binarios, denominados sistema octal y hexadecimal. Por facilidad al usuario de este material se empezará con la creación de la siguiente tabla, en la cual se inicia con el sistema decimal. DECIMAL BINARIO OCTAL HEXADECIMAL 00 0 0 0 01 1 1 1 02 10 2 2 03 11 3 3 04 100 4 4 05 101 5 5 06 110 6 6 07 111 7 7 08 1000 10 8 09 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F 16 10000 20 10 17 10001 21 11 18 10010 22 12 19 10011 23 13 20 10100 24 14 21 10101 25 15 22 10110 26 16 23 10111 27 17 24 11000 30 18 25 11001 31 19 26 11010 32 1A 27 11011 33 1B 28 11100 34 1C 29 11101 35 1D 30 11110 36 1E 31 11111 37 1F 32 100000 40 20 N… N… N… N… Tabla 1.A: Cuatro sistemas de numeración en computación. 1.3 ANÁLISIS DE UN NÚMERO DECIMAL DIGITO POR DIGITO  Número decimal = 6485.5810  Parte entera = 6485  Parte fraccionaria = .58  Análisis del número decimal: 1. Parte entera 2. Parte fraccionaria 5 X 100 = 5 5 X 10-1 = .5 8 X 101 = + 80 8 X 10-2 = .08 4 X 102 = 400 .58 6 X 103 = 6000 6485 Por lo tanto el número 6485.5810 es igual a 6485.5810 1.4 CONVERSION DEL SISTEMA BINARIO A DECIMAL a) Convertir 101112 a N10 1 X 20 = 1 1 X 21 = 2 1 X 22 = + 4 0 X 23 = 0 1 X 24 = 16 23 Significa que el número 101112 es igual a 2310 en decimal b) Convertir 110101.01102 a N10 1.- Parte entera 2.- Parte fraccionaria 1 X 20 = 1 0 X 2-1 = .0 0 X 21 = 0 1 X 2-2 = + .25 1 X 22 = + 4 1 X 2-3 = .125 0 X 23 = 0 0 X 2-4 = .0 1 X 24 = 16 .375 1 X 25 = 32 53 Por lo tanto el número 110101.01102 es igual a 53.37510 1.5.- CONVERSION DEL SISTEMA DECIMAL AL BINARIO Se lo puede efectuar a través del método de divisiones sucesivas, como se muestra en los ejemplos que adjunto. a) Convertir el número 8710 a N2 87 2 1 43 2 21 2 10 2 5 2 2 2 1 2 Por lo tanto el número 8710, convertido a binario es 10101112. b) Convertir el número decimal 36.4410 a N2 1. Parte entera: 3610 2.- Parte fraccionaria: .4410 36 2 .44 X 2 = 0.88 18 2 .88 X 2 = 1.76 9 2 .76 X 2 = 1.52 4 2 .52 X 2 = 1.04 2 2 1 2 0 Por lo tanto el número 36.4410, convertir a binario es igual a 100100.01112 1.6.- OPERACIONES NUMERICAS BÄSICAS EN EL SISTEMA BINARIO 1.6.1.- Efectuar las siguientes sumas binarias: a.- 1111012 b.- 101112 + + 1110102 101102 11101112 1011012 c.- 1111102 d.- 1011.112 1011012 1111.112 1101112 1111.012 + 1110112 + 1111.102 1111112 1111.112 1011112 1111.012 1001112 1111.112 1011100102 1101001.002 1.6.2 Efectuar las siguientes restas binarias a.- 10002 b.- 10010112 - - 01102 1111012 00102 00011102 c.- 11011.012 - 1010.102 10001.102 1.6.3 MULTIPLICACION BINARIA 1.6.3.1 Multiplicación por sumas sucesivas El método consiste en sumar el multiplicando a si mismo un número de veces igual al multiplicador. Así para 10001 X 11 en binario (o sea, 17 X 3 = 51) Por Ejemplo. a.- 10001 X 11 b.- 11011 X 10 100012 110112 + 100012 + 110112 100012 1101102 1100112 c.- 1101 X 111 11012 11012 11012 + 11012 11012 11012 11012 10110112 1.6.3.2 Multiplicación mediante desplazamiento y suma Consiste en ejecutar la multiplicación binaria de la misma decimal, se pone: a.- 100012 b.- 110112 x 112 x 102 10001 00000 10001 11011 1100112 1101102 c.- 11012 x 1112 11012 1101 1101 10110112 1.6.4 DIVISION BINARIA La división binaria se ejecuta como la división decimal Por Ejemplo: a.- 10010102 / 1012 10010102 1012 - 000 011102 1001 -101 1000 -101 0111 -101 0100 -000 100 Por lo tanto 10010102 dividido para 1012 da 011102 con un resto de 1002 b.- 1001101012/ 1012 1001101012 1012 -101 1111012 1001 -101 1000 -101 0111 -101 0100 -000 1001 -101 100 Por lo tanto 1001101012 dividido para 1012 da 1111012 con una resto de 1002 1.7 SISTEMA OCTAL. 1.7.1 Efectuar las siguientes sumas octales: a.- 4274378 b.- 345.6728 243578 + 67.2578 + 654328 435.1518 5414508 1.7.2 Efectuar las siguientes restas: a.- 467568 b.- 76543221.368 - 247548 - 436651.028 220028 76104350.348 c.- 10101257.4638 - 66567.5428 10012467.7218 1.7.3 Efectuar las siguientes multiplicaciones: a.- 545238 b.- 2710654.218 x 228 x 546.238 131246 1053240463 131246 562153042 14437268 2126501146 1344326104 1635413525 201422304617038 1.7.4 efectuar las siguientes divisiones: a.- 1432568 / 178 1432568 178 -132 64768 112 -74 165 -151 146 -132 14 1.8 SISTEMA HEXADECIMAL 1.8.1.- Efectuar las siguientes sumas en hexadecimal. a.- 4A365B16 b.- A2B9CF16 + 24BFD16 +4B3A9 16 4 C815816 A76D78 16 1.8.2 Efectuar las siguientes restas: a.- A2B9CF16 b.- DAC.6FD916 -4B3A916 6.29EA16 9E062616 DA6.45EF16 1.8.3. Efectuar las siguientes multiplicaciones a.- 2D5F16 b.- 2 2 5 F16 x A5B16 x 9 5 B16 1F315 1 7 A1 5 E2DB AB DB 1C5B6 135 5 7 1D5D6C516 14 1B EC516 1.8.4 Efectuar la siguiente división a.- BA23CF9816 / 2A916 BA23CF9816 2A916 -AA4 45F92916 FE3 -D4D 296C -27E7 185F -17F1 6E9 -552 1978 -17F1 187 1.9. CONVERTIR ENTRE LOS SISTEMAS DECIMAL Y HEXADECIMAL 1.9.1 Convertir de decimal a hexadecimal: a.- 243510 a N16 Por lo tanto 243510 = 98316 2435 16 152 16 9 16 0 b.- 8799.23610 a N16 Parte entera Parte fraccionaria 8799 16 .236 X 16 = 3.776 549 16 .776 X 16 = C.416 34 16 .416 X 16 = 6.656 2 16 .656 X 16 = A.496 0 .496 X 16 = 7.936 Por lo tanto 8799.23610 = 225F.3C6A716 1.9.2 Convertir de hexadecimal a decimal a.- A2B9CF16 a N10 F = 15 X 160 = 15 C = 12 X 161 = 192 9 = 9 X 162 = + 2304 B = 11 X 163 = 45056 2 = 2 X 164 = 131072 A = 10 X 165 = 10485760 10664399 Por lo tanto A2B9CF16 = 1066439910 b.- A2C.F316 a N10 Parte entera Parte fraccionaria C = 12 X 100 = 12 F = 15 X 16-1 = .9375 2 = 2 X 161 = +32 3 = 3 X 16-2 = .011718 A = 10 X 162 = 2560 .949218 2604 Por lo tanto A2C.F316 = 2604.94921810 1.10 CONVERSION RAPIDA ENTRE SISTEMAS BINARIOS, OCTAL Y HEXADECIMAL Para convertir un número del sistema binario al sistema octal, se separa el número en grupos de 3 bits y se pone para cada grupo su equivalencia en octal. Para convertir un número del sistema binario al hexadecimal, se separa el número en grupos de 4 bits, y se pone para cada grupo su equivalencia en hexadecimal. Para pasar de octal hexadecimal al binario, el proceso es el inverso del que quedo descrito anteriormente. 1.10.1 Conversión de octal a binario: a.- 4567268 a N2 4 5 6 7 2 6 110 010 111 110 101 100 Por lo tanto 4567268 = 1001011101110101102 b.- 6743.28 a N2 6 7 4 3 . 2 .010 011 100 111 110 Por lo tanto 6743.28 = 110111100011.0102 1.10.2 Conversión de hexadecimal a binario a.- 67ABC916 a N2 6 7 A B C 9 1001 1100 1011 1010 0111 0110 Por lo tanto 67ABC916 = 0110011110101011110010012 b.- 334BD.A316 a N2 3 3 4 B D . A 2 0011 . 1010 1101 1011 0100 0011 0011 Por lo tanto 334BD.A316 = 00110011010010111101.101000112 1.10.3 Conversión de binario a octal: a.- 11011111102 a N8 0 0 1 1 0 1 1 1 1 1 1 0 1 5 7 6 Por lo tanto 11011111102 = 15768 b.- 1101110.102 a N8 0 0 1 1 0 1 1 1 0 . 1 0 0 1 5 6 4 Por lo tanto 1101110.102 = 156.48 1.10.4 Conversión de binario a hexadecimal a.- 1101111111001102 a N16 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 6 F E 6 Por lo tanto 1101111111001102 = 6FE616 b.- 1010101011.102 a N16 0 0 1 0 1 0 1 0 1 0 1 1 . 1 0 0 0 2 A B 8 Por lo tanto 1010101011.102 = 2AB.816 1.11 CONVERSION ENTRE TODOS LOS SISTEMAS NUMERICOS Para convertir un número de cualquier base a una base que ud. desee llegar, lleve a cabo los siguientes pasos: 1. Número X 2. El número X conviértalo a base 10 3. De base 10, convierta a la base deseada Y Para mayor información fíjese en el grafico Nº 1 y en el ejemplo que se adjunta 5 2 3 7 4 N 16 6 GRAFICO 1. 13 P.E. Convertir el número 43.67 a N3 1.- Parte entera Parte fraccionaria 3 X 70 = 3 6 x 7-1 = .8571426 4 X 71 = 28 31 2.- 43.67 = 31. 857142610 3.- Parte entera Parte fraccionaria 31 3 .8571426 X 3 = 2.5714278 10 3 .5714278 X 3 = 1.7142834 3 3 .7142834 X 3 = 2.1428502 1 3 0 Entonces el número 31.857142610 = 1011.2123 Por lo tanto 43.67 = 31.857142610 = 1011.2123 (NUMERO BUSCADO) 1.12 NUMEROS BINARIOS NEGATIVOS 1.12.1 Codificación en valor absoluto y signo El número binario negativo puede ser codificado de varias formas lo fundamental es prever un bit de signo: generalmente es un 0 para el +, y un 1 para el menos. Así, el número 1310, que se escribe 1101 en binario da + 1310 = 011012 y -1310 = 111012 Existen otros procedimientos de codificación. Para recordarlos es conveniente atenerse a dos definiciones: 1.12.2 El complemento A2 Se obtiene el complemento A2 (0 complemento verdadero) de un número binario añadiendo 1 al complemento restringido, así  El complemento a 2 de 1011 es 0100 + 1 = 0101;  El complemento a 2 de 0100 es 1011 + 1 = 1100. 1.12.3 El complemento A 1 Se forma el complemento a 1 (0 complemento restringido) de un número binario, cambiando todos los ceros por unos, y todos los unos en ceros, Por Ejemplo.:  El complemento A 1 de 1011 es 0100;  El complemento A 1 de 0100 es 1011. 1.12.4 Otras formas de codificación de números negativos Los complementos A1 y A2 proporcionan, pues, otros medios de codificar los números binarios negativos, como se muestran en la tabla 1ª DECIMAL VALOR ABSOLUTO Y SIGNO COMPLEMENTO RESTRINGIDO (A1) COMPLEMENTO VERDADERO (A2) +1 +0 -0 -1 -2 : : -7 -8 -9 0 0001 0 0000 1 0000 1 0001 1 0010 : : 1 0111 1 1000 1 1001 0 0000 1 1111 1 1110 1 1101 : : 1 1000 1 0111 1 0110 0 0000 1 0000 1 1111 1 1110 : : 1 1001 1 1000 1 0111 TABLA 1 A LOS COMPLEMENTOS A1 Y A2 DE LOS NUMEROS NEGATIVOS 1.12.5 Operaciones 1.12.5.1 Codificación en valor absoluto y signo Recuerde que consiste en dedicar el bit más significativo de la izquierda como signo. Si = 1 es negativo Si = 0 es positivo Por Ejemplo. 7 = 0 111 Signo (positivo) -7 = 1 111 Signo (negativo) 5 = 0 101 Signo (positivo) -2 = 1 010 Signo (negativo) 1.12.5.2 Complemento A2 a.- Representar -5 en complemento A2 y con cuatro bits 5 = 0 1 0 1 Complemento = 1 0 1 0 Agregar 1 = + 1 -5 = 1 0 1 1 Por lo tanto el número negativo -510 = 10112 b.- Representar -8 en complemento A2 y con cinco bits 8 = 0 1 0 0 0 Complemento = 1 0 1 1 1 Agregar 1 = + 1 -8 = 1 1 0 0 0 Por lo tanto el número negativo -810 = 110002 c.- Ejecutar en complemento A2 con cuatro bits -7 + 5 -7 = 1 0 0 1 7 = 0 1 1 1 5 = 0 1 0 1 1 0 0 0 1 1 1 0 + 1 -7 = 1 0 0 1 Por lo tanto el resultado de -7 +5 = 1110. Significa que el resultado para la computadora es 1110 Es prudente informar que los números positivos son también los complementos A2 de los números negativos. Por Ejemplo.: El complemento del numero anterior A2. 1 1 1 0 0 0 0 1 + 1 0 0 1 0 = resultado positivo d.- ejecutar 5 -1 a complemento A2 con cuatro bits. 5 = 0101 1 = 0001 +1111 1110 0100 +1 Se ignora -1 = 1111 Por lo tanto el resultado de 5 – 110 = 01002 e.- Ejecutar 4 – (-2) a complemento A2 con 4 bits. 4 = 0 1 0 0 2 = 0 0 1 0 2 = + 0 0 1 0 1 1 0 1 6 = 0 1 1 0 + 1 -2 = 1 1 1 0 0 0 0 1 + 1 - (-2) = 0 0 1 0 Por lo tanto el resultado de 4 – (-2)10 = 0 1 1 0 f.- Ejecutar 7 -3 a complemento A2 con 4 bits. 7 = 0 1 1 1 3 = 0 0 1 1 -3 = 1 1 0 1 1 1 0 0 0 1 0 0 + 1 Se ignora -3 = 1 1 0 1 1.12.5.3 Complemento A1 El complemento A 1 se obtiene complementando cada uno de sus bits. P. E.: Representar -5 con 4 bits 5 = 0 1 0 1 -5 = 1 0 1 0 La suma se realiza igual que en el complemento A2, pero cuando ocurre acarreo se suma uno al resultado final a.- Ejecute -7+5 a complemento A1 con 4 bits -7 = 1 0 0 0 7 = 0 1 1 1 5 = + 0 1 0 1 -7 = 1 0 0 0 1 1 0 1 = (resultado para la computadora) b.- Ejecutar -1+6 a complemento A1 -1 = 1 1 1 0 1 = 0 0 0 1 6 = + 0 1 1 0 -1 = 1 1 1 0 0 1 0 0 Acarreo 0 1 0 0 + 1 0 1 0 1 = 5 (cantidad positiva) c.- Ejecutar 5 – 2 a complemento A 1 con cuatro bits 5 = 0 1 0 1 2 = 0 0 1 0 -2 = + 1 1 0 1 -2 = 1 1 0 1 0 0 1 0 Acarreo 0 0 1 0 + 1 0 0 1 1 = 3 (cantidad positiva) Por lo tanto el resultado de 5 -2 10 = 0 0 1 12 1.12.6 Método para detectar sobre capacidad (overflow) en números complementados A2. 1. Antes de sumar las dos cantidades se repite el bit más significativo (mas a la izquierda). 2. Ejecutar la suma usando N + bits, ignorar el acarreo en el bit N+ 2 3. Examinar los dos últimos bits, el resultado del bit N+1; hay overflow o sobre capacidad si los dos bit más a la izquierda no son idénticos. a.- Ejecutar -7+5 a complemento A2 -7 = 1n+1 1n 0 0 1 7 = 0 1 1 1 5 = 0n+1 0n 1 0 1 1 0 0 0 1 1 1 1 0 +1 = -7 = 1 0 0 1 Son idénticos por lo tanto No hay overflow. b.- Ejecutar 6+4 a complemento A2 6 = 0n+1 0n 1 1 0 -5 = 0n+1 0n 1 0 1 0 1 0 1 0 = No son idénticos por lo tanto Existe overflow. 1.12.7. Overflow en complemento A1 El procedimiento es idéntico al complemento A 2, solo que cuatro aparezca el bit N +1 este se debe adicionar al resultado. P.E.: a.- Ejecutar 5+2 al complemento A1 con cuatro bits. 5 = 0n+1 0n 1 0 1 -5 = 0n+1 0n 0 1 0 0 0 1 1 1 = El resultado es idéntico No hay overflow. b.- Ejecutar -4-4 al complemento A 1 -4 = 1n+1 1n 0 1 1 4 = 0 1 0 0 4 = 1n+1 1n 0 1 1 -4 = 1 0 1 1 1 1 0 1 1 0 + 1 1 0 1 1 1 = El resultado no es idéntico Por lo tanto existe overflow. 1.13 Efectuar los siguientes problemas: a.- Convertir del sistema binario al decimal:  1110101112 a N10  1101001.11012 a N10  10011111.11012 a N10 b.- Convertir del sistema decimal al binario  8610 a N2  69.4610 a N2  99.9610 a N2 c.- Efectuar las siguientes operaciones binarias 11110112 111110.112 + 11111002 001011.012 10110112 + 110111.112 10110112 110111.112 101110.112 011111.102 11010102 101101.1012 -01101112 - 011101.1112 1101111 x 101 11101111 x 11112 1011112/112 111110112/1012 d.- Efectuar las siguientes operaciones octales: 2456328 10647.678 + 5434648 + 01432.568 6532458 12346.778 6674328 3456.7678 - 2432148 - 367.6768 456768 x 2438 4567765438 x 2458 46576628 / 428 e.- Efectuar las siguientes operaciones hexadecimales: 1AB69F16 6FACA916 + 24 678A16 - 467 ABB16 56 78BB16

CAPÍTULO III. ÁRBOLES BINARIOS En la vida cotidiana, muchas vedes sin saberlo, trabajamos en ocasiones con los árboles. Por ejemplo: árboles genealógicos, organigramas, directorios en los discos de un computador, etc. Cada uno de estos conceptos representa un árbol. ORGANIGRAMA DE UNA EMPRESA ORGANIZACIOND E UN DIRECTORIO EN UN COMPUTADOR 3.1.DEFINICIONES En el área de la computación también se conoce una materia que trata de los árboles. Este tema es muy extenso y para su estudio vamos a dividirlo en varios capítulos. En este capitulo nos vamos a circunscribir solamente en el estudio de los árboles binarios. Este tipo de árbol se caracteriza porque tiene un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha. La rama izquierda y la derecha, también son dos árboles binarios. El vértice principal se denomina raíz y cada una de las ramas se denomina árbol izquierdo y árbol derecho. Por ejemplo: La raíz de este árbol es A y el árbol izquierdo esta conformado por otro árbol. Que a su vez tiene como raíz B. el árbol derecho esta conformado también por otro árbol. DEFINICIONES NODO Un árbol binario es un conjunto de elementos cada uno de los cuales se denomina nodo. Un árbol binario puede tener cero nodos y en este se dice que esta vació. Puede tener un solo nodo, y en este caso existe solamente la raíz del árbol o puede tener un número finito de nodos. Cada nodo que esta ramificado por la izquierda o por la derecha o puede no tener ninguna ramificación. La anatomía de un nodo en un árbol binario es la siguiente: Información del nodo Apuntador al árbol de la derecha Apuntador al árbol de la izquierda Raíz en un árbol binario se pueden distinguir la raíz principal y las raíces de los demás subárboles. Por ejemplo: La raíz principal es el nodo cuya información es A. podemos distinguir también el árbol. Cuya raíz es el nodo con información D. Este nodo es la raíz del árbol de la derecha. El Árbol de la izquierda Tiene como raíz el nodo cuya información es B y tiene solamente una ramificación. PADRE Un padre es un nodo que puede o no tener ramificaciones. Por ejemplo: Caso 1 caso 2 caso3 En los tres casos el nodo A es un padre. En el caso 1 es un padre que no tiene hijos. En el caso 2, el nodo A es el padre del nodo B. en el caso 3 el nodo A es padre de los nodos By C peo no es padre del nodo D. HIJO Nos referimos al ejemplo anterior. En el caso 1 el nodo A no tiene hijos. En el caso 2, B es un hijo del nodo A y en el caso 3, D es hijo de B y el padre de B es el nodo A HERMANO Nos referimos al caso 3 del ejemplo anterior. Los hermanos son los hijos de un mismo padre. Los nodos B y C son hermanos. El nodo D no tiene hermanos HOJA Una hoja es un nodo que no tiene ramificaciones. Por ejemplo El nodo C es una hoja mientras que el nodo B no se puede considerar como hoja porque tiene una ramificación por la derecha. El nodo D también es una hoja NODO NO TERMINAL Un nodo no Terminal es aquel que posee por lo menos una ramificación. En el ejemplo anterior, el nodo A o el B son nodos no terminales, mientras el nodo D o el nodo C son nodos terminales. CAMINO Un árbol siempre se examina hacia abajo. Por ejemplo: Al nodo C podemos llegar desde el nodo B. Nunca se puede examinar el nodo B a partir del nodo C. Los apuntadores derecho o izquierdo de cualquier nodo apuntan al árbol derecho o izquierdo que siguen a ese nodo. Nunca apuntan a los nodos precedentes. Un camino es el conjunto de nodos que tenemos que visitar con el propósito de llegar a un nodo específico. Por ejemplo para llegar al nodo F es necesario recorrer el camino A D F Del mismo nodo, para llegar al nodo G debemos recorrer el camino A D E G Obsérvese que los caminos se configuran siempre hacia abajo. Nunca se puede hablar de un camino para llegar al nodo C así: G E D A B C Este camino se puede configurar. LONGITUD Longitud es el número de nodos que se deben recorrer para pasar de un nodo a otro. Por ejemplo: La longitud entre A y E es 3. La longitud entre G y G es 0. La longitud entre A y B es 1 Obsérvese que no podemos calcular la longitud entre B y G ya que el camino B A G no existe. DESCENDIENTE El nodo C es descendiente del nodo A si a partir de A podemos llegar a C a través de un camino. Por ejemplo: El nodo C es descendiente de A ya que a C podemos llagar por el camino A B C Siempre que exista un camino para llegar de un nodo V a un nodo X, el nodo X es un descendiente de V. pAra el ejemplo anterior, el nodo E es descendiente de D pero el nodo no es descendiente de B ANCESTRO El nodo A es un ancestro del nodo C si existe un camino entre A y C. basándonos en el ejemplo anterior. A es un ancestro de C ya que existe un camino entre los nodos. No se puede hablar de que D sea ancestro de ya que el camino D A B no existe NIVEL Cada nodo tiene un nivel dentro de un árbol binario. Por definición el nodo raíz tiene un nivel y de los demás nodos tienen el nivel de su padre más 1. Por esto los nodos que son hijos del nodo raíz tienen un nivel 1. Veamos este ejemplo NIVEL 0 NIVEL 1 NIVEL 2 NIVEL 3 Los nodos A, M y S tienen un nivel 0 en tanto que los nodos G y V tienen un nivel 3. Obsérvese que le nivel del nodo G es la longitud del camino desde la raíz hasta el nodo. GRADO DE UN NODO El grado de un nodo es el número de hijos. Por ejemplo el grado del nodo A es 2, el grado del nodo T es 1. El grado de un nodo Terminal siempre es 0.en los árboles binarios, el grado de un nodo fluctúa entre 0 y 2. Existen otros tipos de árboles, (árbol n_ario), en los cuales esta restricción no existe. Estos arboles serán estudiados en el segundo tomo de este libro ALTURA La altura de un árbol binario es el nivel de la hoja o de las hojas que están más distantes de la raíz. Basándonos en el ejemplo anterior, la altura del árbol cuya raíz es A, corresponde a la longitud del camino para llegar a la hoja más distante de la raíz. En este caso será 3. La altura cuya raíz es M, corresponde al nivel de la hoja P. ARBOL BINARIO COMPLETO Un árbol binario completo es aquel en el que todo nodo no Terminal tiene sus dos hijos. El siguiente es un árbol binario de nivel 3: NIVEL 0 NIVEL 1 NIVEL 2 NIVEL 3 Obsérvese que todos los nodos no terminales tienen sus dos hijos. El máximo número de nodos que puede tener un árbol de nivel n es: 20 + 21 + 22 + 23….+ 2n Si n es 3 entonces 20 + 21 + 22 + 23 =15 Este árbol es un árbol binario completo de nivel 3 y este es el máximo número de nodos que puede tener un árbol de nivel 3. ARBOL BINARIO IGUAL Dos árboles son iguales si los dos son vacíos. Existe otro caso ene. Cual dos árboles son iguales: Estos árboles son iguales porque sus raíces son iguales y también lo son su respectivo árbol izquierdo y derecho. Para que un árbol sea igual a otro, es necesario que el contenido de cada uno de sus respectivos nodos sea el mismo y que legan las mismas relaciones de parentesco. Por ejemplo los siguientes árboles Son diferentes porque el contenido de sus respectivos nodos es diferente. Obsérvese que sus nodos tienen las mismas relaciones de parentesco. ARBOL BINARIO SEMEJANTE Dos árboles son semejantes si tienen el mismo número de nodos y los valores de los nodos del primer árbol son los mismos que los valores de los nodos del segundo, sin importar la relación de parentesco entre ellos. Por ejemplo: Estos árboles son semejantes. Contienen los mismos valores en cada uno de sus nodos. ARBOL BINARIO ISOMORFO Dos árboles binarios son isomorfos si tienen la misma estructura aunque el contenido de cada uno e sus nodos sea diferente. Por ejemplo los siguientes árboles son isomorfos. PESO El peso de un árbol en un nodo dado es el número de nodos en el árbol sin contarse el mismo. Por ejemplo: El peso del árbol cuya raíz es A corresponde al número de nodos de ese árbol: los nodos Q,C y R tienen un peso de 2 FORMAS DE RECORRER UN ARBOL BINARIO Universalmente existen 3 formas de recorrer un árbol binario:  Preorden  Inorden  Posorden Si logramos construir un árbol como este: Podemos extraer sus datos de 3 maneras. Veamos cada una. Recorrer un árbol en preorden consiste en:  Examinar el ato del nodo raíz  Recorrer el árbol izquierdo en preorden  Recorrer el árbol derecho en preorden Si deseamos recorrer todo el árbol, evidentemente debemos comenzar por el nodo raíz. Este método exige examinar primero el nodo raíz debemos entender como examinar un nodo, el hecho de efectuar sobre su información cualquier acción: por ejemplo escribirla, efectuar alguna operación matemática sobre ella o con ella, modificarla. También en la gran mayoría de los textos de estructuras de información, se utiliza el termino visitar un nodo. Entre la palabra examinar y la palabra visitar existe una diferencia. Examinar un nodo es revisar su contenido y eventualmente modificarlo en tanto que visitar un nodo es utilizar la dirección de ese nodo con el propósito de seguir explorando el árbol hacia abajo. Si deseamos recorrer un árbol en preorden, con el propósito de escribir su contenido, debemos examinar el contenido de cada uno se sus nodos, mientras si deseamos contar sus nodos, es necesario visitar cada nodo. Supongamos que deseamos escribir un árbol en preorden. Para hacerlo, se debe examinar el nodo raíz y luego recorrer el árbol de la izquierda en preorden. ARBOL A LA IZQUIERDA DE A Recorrer este árbol en preorden es examinar su nodo raíz y recorrer de nuevo el árbol de la izquierda preorden. ARBOL A LA IZQUIERDA DE B Recorrer este árbol en preorden es examinar su nodo raíz. Como ya no existen nodos por la izquierda, debemos empezar a recorrer el árbol D por la derecha. Como ya no existen nodos por la derecha, debemos recorrer el árbol. Por la derecha. El árbol de la derecha lo debemos recorrer también en preorden. ARBOL A LA DERECHA DE B Recorrer este árbol en preorden, es examinar su nodo raíz y recorrer el árbol por la izquierda en preorden y luego recorrerlo por la derecha. Como no existen árboles ni por la izquierda ni por la derecha, debemos recorrer el árbol. En preorden. El orden en el cual debemos examinar estos nodos es: primero el nodo C, luego F y luego G. por lo tanto al imprimir el árbol anterior en preorden, los resultados deben ser: A B D E C F G Antes de seguir adelante, el lector debe certificar que el árbol: Al imprimirlo recorriéndolo en Preorden debe generar los siguientes resultados: 10 5 3 1 4 7 9 15 14 17 16 20 Ahora veamos la segunda forma de recorrer un árbol binario. Recorrer un árbol en inorden, consiste en: Recorrer el árbol izquierdo en inorden Examinar la raíz Recorrer el árbol derecho en inorden. Por ejemplo: Si queremos imprimir este árbol en inorden, debemos primero recorrer el árbol izquierdo en inorden: Al tratar de recorrer este árbol en inorden y no existe árbol por su izquierda debemos examinar el nodo y luego recorrer el árbol de su derecha. Al no existir árbol por su derecha, entonces el árbol a la izquierda del nodo A ha sido totalmente recorrido. Siguiendo con las normas establecidas inicialmente, debemos examinar el nodo A y luego recorrer el árbol a la derecha del nodo A ARBOL DERECHO DE A Para recorrer este árbol en inorden primero debemos recorrer el árbol izquierdo. Al no existir árbol izquierdo, se debe examinar este nodo y luego recorrer el árbol derecho. Al no existir árbol derecho, el árbol ya ha sido recorrido en su totalidad. Por lo tanto los datos impresos serán: B A C Observemos este otro ejemplo Debemos recorrer en inorden el árbol a la izquierda de la raíz: Al recorrer este árbol en inorden ya sabemos, de acuerdo a la explicación del ejemplo anterior, que los resultados son: 3 5 7 Al terminar de recorrer el árbol a la izquierda de la raíz, debemos examinar la raíz y luego recorrer en inorden el árbol a la derecha de la raíz Sabemos que al recorrer este árbol en inorden, los resultados son: 11 12 15 Con lo cual al examinar todo el árbol en inorden, los datos impresos serán: 3 5 7 10 11 12 15 Se invita al lector a certificar que al recorrer el siguiente árbol binario en inorden los resultados son: H D I B E A J F C K G L Veamos el árbol Por ultimo estudiemos la tercera forma de recorrer un árbol binario. Examinar un árbol binario en posorden consiste en:  Recorrer el árbol izquierdo posorden  Recorrer el árbol derecho en posorden  Examinar la raíz. Veamos un ejemplo: Al recorrer el árbol izquierdo en posorden, el único dato impreso será B. después de haber recorrido todo el árbol de la izquierda en posorden, se debe recorrer todo el árbol de la derecha en posorden. Al recorrer el árbol de la derecha en posorden, el único dato impreso será C. una vez recorridos los árboles izquierdo y derecho, debemos examinar la raíz. Según esto los datos impresos serán. B C A Ejercicios 1. Elaborar un programa que cree en la memoria del computador el siguiente árbol binario: 2. Dado el siguiente árbol binario: Certificar que al recorrer el árbol, los siguientes resultados son correctos: Preorden ABCDFGEIJ Inorden BAFDGCIEJ Posorden BFGDIJECA 3. Suponga que en memorial del computador existe el siguiente árbol: Escriba un conjunto de instrucciones que cree un nodo X a la derecha de B y un nodo Y a la derecha de E. 4. dado el siguiente árbol: raíz Cuales serian los datos impresos si se recorre en: Preorden Inorden Posorden MANTENIMIENTO DE UN CONJUNTO DE NUMEROS CLASIFICADOS ASCENDENTEMENTE, UTILIZANDO UN ARBOL BINARIO ORDENADO. Utilizando un árbol binario, es posible mantener un conjunto de números clasificados ascendentemente sin necesidad de rutinas de ordenamiento. Se plantea el problema de leer un conjunto de enteros y listarlos clasificados ascendentemente. Los números repetidos deben ser rechazados. Por ejemplo si la entrada es: 87 25 23 25 48 8 92 El programa debe generar los siguientes resultados: 8 23 25 48 87 92 Este problema se puede resolver fácilmente utilizando un árbol binario ordenado. Solamente es necesario ir leyendo cifra por cifra e ir adicionándola en el árbol así: si es menor al contenido del nodo analizado la instemos por la izquierda de ese nodo y se es mayor por la derecha. Veamos: al leer el número 87, creamos con este dato el nodo raíz. Luego al leer el 25, como 25 es menor que 87, creamos un nuevo nodo a la izquierda de 87. Visualmente el árbol creado hasta el momento sería: Luego al leer el número 23, como este dato es menor a 87, nos debemos desplazar hacia abajo por la izquierda. Al llegar al 25, debemos crear un nuevo nodo a la izquierda por el hecho de que 23 es menor que 25, así: Al leer el siguiente dato este debe ser rechazado porque ya existe en el árbol. Al leer el 48, debemos desplazarnos por la izquierda y al compararlo con 25, se debe crear un nuevo nodo a la derecha del 25, así: Siguiendo este mismo procedimiento, enumero 8 debe insertarse a la izquierda del 23 así Por ultimo al leer el numero 92 este debe insertarse a la derecha del 87. Los datos en el. Árbol quedan, finalmente, distribuidos así: Si imprimimos el contenido del árbol, recorriéndolo en inorden. Tendremos la lista pedida: 8 23 25 48 87 92 IMPRESIÓN DE UN ARBOL EN INORDEN Observemos el siguiente árbol: Raíz Al escribir este árbol en inorden los resultados serán: 3 5 6 7 8 10 15 20 Observando el proceso, lo primero que se escribe siempre es el contenido del nodo de la extrema izquierda del árbol. Luego debemos escribir el contenido del nodo padre para luego escribir en inorden el árbol de la derecha. IMPRESIÓN DE UN ARBOL EN PREORDEN USANDO UNA PILA Deseamos escribir un árbol en preorden. Veamos esta estructura: R A G B I E H D F J La función que vamos a elaborar debe escribir: 100 50 30 10 40 60 65 150 120 160 180 Esta nueva función se diferencia de a función inorden ( ), en que en aquella primero se recorría el árbol izquierdo y luego si se escribía el contenido del padre de ese árbol. En esta nueva rutina primero se debe escribir el contenido del padre del árbol y luego se recorrer en preorden la rama izquierda. El siguiente paso consiste en retirar de la pila la dirección C y determinar si existe un árbol por la derecha del nodo indicado por C. siguiendo el comportamiento de la pila, podemos por esto, deducir que esta función es muy parecida a la función inorden ( ). La diferencia radica en que antes de analizar el árbol izquierdo, la información del nodo ya ha sido escrita. Veamos el comportamiento del proceso: Contenido la pila numero escrito 100 50 30 10 - - 40 - 60 65 - - 150 120 - 180 - IMPRESIÓN DE UN ARBOL EN POSORDEN USANSO UNA PILA La impresión de un árbol en posorden, es un poco más compleja y requiere de modificaciones en el manejo de la pila Veamos este árbol: La impresión en posorden es: 3 7 5 20 40 30 10 Antes de imprimir el nodo, debemos recorrer el árbol izquierdo y luego el derecho. Es claro que primero debemos llegar hasta la hoja de la extrema izquierda del árbol, guardando los apuntes en una pila para luego poder recuperar las direcciones de todos los ancestros de esa hoja. Se llegamos a la hoja: Antes de escribir el contenido del nodo debemos certificar que ya han sido recorridos en posorden los árboles izquierdo y derecho. IMPRESIÓN DE UN ARBOL POR NIVELES USANDO UNA COLA Imprimir un árbol por niveles, es imprimir primero su raíz, luego los contenidos de los nodos del nivel 1, luego los contenidos de los nodos del nivel 2, y así sucesivamente hasta imprimir el contenido de los nodos del ultimo nivel. Por ejemplo: Al imprimir este árbol por niveles, los resultados serán: 20 10 30 5 15 25 40 7 50 Aprovechando una estructura FIFO, podemos efectuar esta impresión sin ningún problema. Al comenzar almacenamos en una cola la dirección del nodo raíz: Ahora mientras la cola no este vacía, retiramos el primer elemento de la cola y escribimos el contenido de la dirección del elemento retirado e insertamos en la cola las direcciones izquierda y derecha almacenadas en el contenido de la dirección retirada de la cola Siguiendo este mismo procedimiento, tendríamos los siguientes estados de la cola: 10 30 5 15 25 40 7 50 Revisando el proceso anterior, observamos dos cosas: la primera es que cuando un apuntador es NULL, a la cola no se adiciona ningún elemento y la segunda es que este proceso repetitivo se debe efectuar mientras la cola no esté vacía. RECONSTRUCCION DE UNA RBOL BINARIO Se plantea el problema de reconstruir un árbol binario dados sus recorridos en preorden y en inorden. Por ejemplo, si un árbol genera lo siguiente: al recorrerse en preorden: G E A I B M C L D F K J H Y genera lo siguiente al recorrerse en inorden: I A B E G L D C F M K H J Se requiere de un programa que a partir de estos datos, genere un árbol binario al cual correspondan las dos impresiones. Vamos a considerar que a la función que elabora este trabajo entran dos arreglos. El método es muy sencillo y consiste en utilizar una estructura LIFO como la herramienta fundamental. Lo más sencillo del proceso es determinar la raíz del árbol. Para el caso que nos ocupa la raíz será: Vamos a utilizar los apuntadores p y q como auxiliares de trabajo. Pre G E A I B M C L D F K J H In I A B E G L D C F M K H J Si se recorre este árbol en Preorden, el primer nodo que visita es G y al recorrerlo en inorden el nodo del extremo izquierdo es I. en este lugar podemos afirmar que los nodos EAIB, forman el sub.-árbol izquierdo de G y los nodos MCLDFKJH el sub.-árbol derecho q Raíz p El problema esta dividido en dos. Ya sabemos que la raíz es G y también sabemos los componentes de la izquierda y de la derecha. Ahora podemos guardar en una pila los componentes del árbol derecho y seguir trabajando sobre el árbol izquierdo. Es decir tratar de organizar el árbol izquierdo. La pila quedara así: Vamos a considerar la G del recuadro como un apuntador que esta en la pila que nos indica la dirección del nodo padre de este sub.-árbol derecho. Ahora debemos seguir trabajando con el sub.-árbol izquierdo. EAIB IABE De la misma forma, el nodo raíz de este nuevo árbol es E. este nodo debe conectarse al nodo G así Q El apuntador que siempre debe estar dirigido al nodo al cual se conectara el nuevo nodo posteriormente. Siempre el nuevo nodo será indicado por el apuntador p. con lo anterior el árbol estará organizado así: Obsérvese con cuidado porque el nodo E no tiene sub-árbol derecho. Siguiendo el mismo orden, debemos crear un nodo A, el cual conectara por la izquierda con E y este nodo si tendrá sub- árbol por la derecha, así: Como siempre que aparezca un sub-árbol derecho debemos actualizar la pila , su nueva información será: Siguiendo por la izquierda, ahora podemos conectar el nodo I, quedando el árbol así: En este lugar debemos efectuar un retiro de la pila y conectar el nuevo nodo por la dercha del nodo indicado por el apuntador que estaba almacenando en el primer elemento de la pila. Con esto, el arbol queda así: Y la pila contendrá solamente un elemento. Como ya se distribuyo la información el árbol izquierdo, debemos retirar de la pila el elemento y conectar por la derecha un nuevo nodo M, quedando el árbol así: La nueva información de la pila será. Y continuamos trabajando con el árbol izquierdo. Siguiendo hacia la solución, debemos crear un nodo C y guardar en la pila el sub-árbol derecho que se conectara al nodo C posteriormente. La pila hasta el momento tendrá estos datos: Acercándonos un poco mas hacia la solución, el árbol se puede ver así: Y la pila almacenara la siguiente información: Obsérvese que siempre que se identifique un sub-árbol derecho, la pila debe ser actualizada. Como ya se acabo la información a distribuir por la izquierda, debemos efectuar un retiro de la pila, con el propósito de seguir el proceso. Efectuando este retiro y sabiendo el nodo al cual debemos conectar el nuevo nodo por la derecha, podemos hacer adecuadamente la inserción del nuevo nodo. El primer elemento de la pila es: Esto quiere decir que el nodo D se debe conectar a la derecha del nodo L, así: De la misma manera, el nodo F debe conectarse a la derecha del nodo C. Después de conectar el nodo F, debemos retirar de la pila el último elemento y comenzar a distribuir por la izquierda la nueva informaron. Veamos el arbol hasta este momento: Y la pila contendrá la siguiente información Ahora al haber distribuido la rama izquierda (no existe rama izquierda e K ), podemos retirar de la pila su único elemento y crear un nodo J e insertar en la pila su rama derecha, ( no existe rama derecha), así: Al observar el proceso, vemos que la pila queda vacía y falta adicionar al árbol el nodo H. con esto podemos afirmar que el proceso se debe efectuar mientras la pila no este vacía o exista información para distribuir por la rama izquierda. Por lo tanto el árbol final será: Existe un buen número de formas para construir una función que efectué el proceso anterior. A continuación presentamos una de estas versiones codificada en lenguaje C. NOTACIONES INFIJO, POSFIJO Y PREFIJO Cuando se nos pregunta, por ejemplo, cuanto es el resultado de 5 multiplicado por 8 más 3, la respuesta automática que se da es 43. No se da el caso de que la respuesta dad sea 55. Ahora si pregunta es: cual es la respuesta de 3 mas 5 multiplicado por 8, también volveremos a dar la misma respuesta: 43. No se nos ocurre sumas 3 y 5 luego multiplicar la respuesta por 8 para que nos de 64. Se nos pregunta cual es la respuesta de 5 por 2 mas 8 por 3, la respuesta dada es 34. Nos hemos acostumbrado a través del tiempo a que el operador * tiene mas prioridad que el operador + y así lo trabaja cerebro. La notación con la cual trabajamos los humanos este tipo de expresiones se denomina infijo, donde la presencia de los operadores es: * / - + = Los humanos trabajamos con notación infijo. De la misma manera los computadores están diseñados para que reconozcan la misma prioridad que reconocemos los humanos. La instrucción: Resol = 5 * 2 + 8 * 3; Deja almacenada, por ello, la cifra 34, ya que la asociación automática es: (result: (5 * 2)+(8 * 3)); Si deseamos que un computador, o un ser humano, calcule: Resul= 5 * 2 + 8 * 3; Pero sumando 2 y 8 primero, debemos diseñar la instrucción así: Result= 5 * (2 + 8) * 3: Se utilizan los paréntesis para modificar la prioridad de los operadores. Un programador al indicarle esta instrucción a un computador: Resul= 5 * 2 + 8 * 3; Espera la respuesta 34 pero no le interesa como lo hizo la maquina. Internamente, esta operación la ejecuta utilizando una pila. La operación la ejecuta reconociendo objeto a objeto. Vamos a ilustrar la transformación que debe hacer la maquina con el propósito de efectuar la operación anterior. De lo único que esta enterada tanto la maquina como el programador, es que el operador * tiene mas prioridad que el operador +. La transformación que se realiza es convertir la expresión de notación infijo a notación posfijo lo cual se estudiará en el siguiente numeral. A continuación estudiaremos que es la notación posfijo. La notación posfijo, es otra manera de escribir una expresión aritmética. La notación posfijo, se caracteriza por la ausencia de paréntesis. Esta notación, aunque nunca utiliza paréntesis, es presentada sin ningún tipo de ambigüedad. Veamos su naturaleza. Si tenemos una expresión en notación infijo. Por ejemplo: a +b Para escribir esa misma expresión en posfijo. Se debe ejecutar los siguientes pasos: 1. agrupar utilizando paréntesis, de acuerdo a la prioridad de los operadores, así: (a+b) 2. escribir en posfijo la expresión, así: ab+ Obsérvese que en la notación posfijo, el operador se escribe después de los operadores . Veamos otro ejemplo: a + b * c Agrupando tenemos: a + ( b * c ) Convirtiendo a posfijo la expresión entre paréntesis resulta: a + ( b c * ) Ahora tratando la expresión entre paréntesis como un operador tenemos a ( b c * )+ y destruyendo los paréntesis, nos queda la expresión escrita en posfijo: a b c * + Veamos este ejemplo; ( x * y ) + ( v * w ) Primero debemos convertir las expresiones encerradas entre paréntesis a notación posfijo, así: ( x y * ) + ( v w * ) Y luego toda la expresión a notación posfijo, así x y * v w * + Veamos estos ejemplos: 1. (a+b)*( c+d) ( a b + ) * ( c d + ) a b + c d + * 2. a+b-c ( a b + ) - c a b + c - 3. (a+b)*(c-d)*e*f ((( a b + ) * ( c d - )) * e ) * f (( a b + c d - * ) * e ) * f ( a b + c d - * e * ) * f a b + c d - * e * f * 4. (a+b)*(c/(d-e)+f)-g ( a b + ) * ( c / ( d e - ) + f ) - g ( a b + ) * ( ( cd e - / )+ f ) – g ( a b + ) * ( c d e - / f + ) - g a b + c d e - / f * g – 5. vamos a suponer que la operación exponenciación esta definida y la representamos así: además, tiene la mayor prioridad de todos los operadores. Veamos estos ejemplos, usando este nuevo operador: (a b c) (a b) c ab c 6. a b * c – d + e / f/ (g+h) ((a b) * c – d ) + ( e / f ) / ( g+ h ) (ab c * d - ) + ( ef / gh + / ) ab c * d – ef / gh + / + 7. a + ((( b – c ) * ( d – e ) + f ) / g ) (h – j ) a + ((( bc - de - * f + ) / g ) (hj - ) a + (( bc – de - * f + a / hj- ) abc – de - * f + g / hj- + Existe otro tipo de notación para escribir las expresiones aritméticas. Esta nueva notación recibe el nombre de prefijo y recaracteriza porque los operadores se escriben primero que los operadores. Por ejemplo la expresión: a+b Escrita en notación prefijo, sería: -ab En general todas las reglas para convertir infijo a posfijo, se aplican para efectuar las conversiones infijo a prefijo, tendiendo en cuenta que los operadores se escriben antes que los operadores. Veamos estos ejemplos: 1. a+b+c (a-b)+ (+ab)+c ++abc 2. a+b-c (a-b)-c (+ab)-c -+abc 3. (a+b)*(c-d) (+ab)*(-cd) *+ab-cd 4. a+b/c-d a+(b/c)-d (a+(/bc))-d (+a/bc)-d - + a / bcd 5. a b*c-d+e/f/(g+h) (((a b) * c ) – d ) + ( e/f ) / (g+h) ( - * abcd) + ( / ef ) / ( + gh) - * abcd + (//ef + gh) + - * abad //ef+gh Podemos también plantear algunos ejemplos para convertir de posfijo a prefijo o infijo. Veamos primero algunos ejemplos para convertir de posfijo a infijo: 1. ab+ El operador se debe aplicar a los últimos dos operandos, quedando así: a+b 2. ab+c- El análisis se comienza por la izquierda de la expresión. Se debe recorrer la expresión hasta que encontremos un operador, así: ab+c- Una vez hayamos encontrado el primer operador, debemos aplicar ese operador a los dos últimos operandos que lo precedan, así (a+b)c- Y luego debemos seguir analizando la expresión hasta encontrar el próximo operador: (a+b)c- Una vez hayamos encontrando el próximo operador debemos aplicar ese operador a los últimos dos operandos. Obsérvese que la expresión encerrada entre paréntesis, se debe trabajar como un solo operando. (a+b)-c 3. ab+cd-* Siguiendo el proceso anterior, tenemos: (a+b)cd-* (a+b)(c-d) (a+b)*(c-d) 4. ab+cd-*e*f* (a+b)cd - * e * f * (a+b)(c-d)e * f * ((a+b)*(c-d)*e) f * ((a+b)*(c-d)*e) * f (a+b)*(c-d) * e * f 5. ab c (a b)c (a b)c a b c 6. ab c*d-ef / gh+/+ (a b*c)d-ef / gh + / + (a b*c-d)ef / gh + / + (a b* c-d)(e/f) gh + / + (a b*c-d)(e/f)(g+h) / + (a b*c-d)((e/f)/(g+h)) + (a b*c-d)+(e/f)/(g+h) A b*c-d+e / f / (g+h) De la misma manera, podemos pasar de la notación prefijo a la notación infijo; veamos un ejemplo +ab En este caso debemos analizar la expresión de derecha a izquierda hasta que encontremos el primer operador. Una vez lo hayamos encontramos, aplicamos este operador a los dos operandos que le siguen, así: a+b Veamos algunos ejemplos: 1. -+abc -(a+b)c (a+b)-c a+b-c 2. *+ab - cd * + ab(c-d) * (a+b) (c-d) (a+b) * (c-d) 3. -*+abc - de -fg -*+abc – de (f-g) -*+abc (d-e) (f-g) -*(a+b)c(d-e)(f-g -((a+b)*c)(d-e)(f-g) (((a+b)*c)-(d-e))(f-g) ((a+b)*c-(d-e)) (f-g) EJERCICIOS 1. cada una de las siguientes expresiones escritas en fijo convertirlas a posfijo a) (x+y)*(z (s+t)+u)-v b) a+((x+y)*(w+v)) (i+j) 2. Convertir las expresiones del ejercicio anterior a prefijo 3. Convertir las siguientes expresiones de prefijo a infijo: a) + - xyz*i**klm b) ++1-* mno/+pq*rst 4. Convertir las siguientes expresiones en posfijo a infijo a) pqrst-+ *uv*- b) lm-n+opq-+ REPRESENTACION DE EXPRESIONES ARITMETICAS EN ÁRBOLES BINARIOS Una expresión aritmética puede expresarse utilizando un árbol binario. Por ejemplo la expresión: a+b Expresada en un árbol binario es: El operador +aplica a los operandos de la rama izquierda y la rama derecha. La expresión: a+b*c Quedara expresada así: El árbol queda organizado así ya que la expresión implícitamente esta asociada así: a+(b*c) Porque por definición el operador * es de mayor jerarquía que el operador + Vamos a construir un árbol par ala expresión: a / b * c + d e * f para defecto esta expresión escrita en infijo, asocia sus operandos así: (( a / b ) * c ) + (( d e ) * f ) Esto indica que la raíz del árbol contiene el operador+. La rama izquierda contiene la expresión (a / b ) * c y la rama derecha la expresión (d e )*f. siguiendo este orden de ideas el árbol queda construido así: Existe un método sencillo para construir una árbol que representa un a expresión. El primer paso consiste en transformar la expresión de infijo a prefijo y partiendo de la expresión escrita en prefijo construir el árbol. Veamos algunos ejemplos: Infijo a+b Prefijo +ab Al tener la expresión en prefijo, fácilmente se puede construir el árbol siguiendo este método: Se insertan nuevos nodos por la izquierda del árbol que hayamos insertado un operando +a Luego volvemos hacia atrás en el árbol e insertamos el siguiente elemento a su derecha. +ab Si el nodo insertado fue un operador, insertamos el siguiendo a su izquierda. Si el nodo insertado fue un operando, volvemos hacia atrás e insertamos el siguiente nodo a la derecha. Este proceso se continúa hasta que se agote la expresión escrita en prefijo. Veamos otro ejemplo: Infijo a+(a*c d) Primero debemos convertir la expresión a prefijo: +a*b cd Luego debemos insertar nuevos nodos hasta encontrar un operando: +a Luego volvemos hacia atrás e insertamos el siguiente elemento a la derecha: +a* Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda: +a*b Como el nodo mas reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha. +a*b Como el último nodo insertado fue un operador, debemos insertar el siguiente a la izquierda: + a * b c Como el nodo más reciente insertado fue un operando, volvemos hacia atrás e insertamos el siguiente a la derecha: +a*b cd Siguiendo este método, y antes de seguir adelante, se recomienda al lector revisar los árboles para las siguientes expresiones en prefijo: CONVERSION DE UNA EXPRESION EN UN ARBOL BINARIO A SU REPRESENTACION INFIJO En este numeral se desarrollara una función que a partir de un árbol binario, genere un arreglo que almacene la expresión en infijo. Antes de entrar propiamente en el desarrollo del problema, estudiaremos algunas propiedades de estos árboles. Supongamos que tenemos en la memoria del computador un árbol así: Este árbol representa la siguiente expresión a+b*c La expresión anterior escrita en prefijo será: + a * bc Si recorremos el árbol en preorden los datos generados serán: +a*bc Lo anterior nos permite plantear la primera propiedad: Si se recorre un árbol en preorden, los datos generados representan la expresión escrita en prefijo. Si el árbol anterior recorremos en posorden, los datos generados serán: a b c * + Estos datos representan la expresión a + b * c Escrita en posfijo, lo cual nos permite plantear la segunda propiedad: Si se recorre un árbol en posorden, los datos generados representan la expresión escrita en posfijo. Es de esperarse que si recorremos el árbol en inorden, la expresión generada estará escrita automáticamente en infijo. Veamos: a+b*c Para el caso que nos ocupa se cumplió la norma. Veamos otro ejemplo: (a+b) c/d+e Esta expresión escrita en prefijo será: + / + a b c d e Y en posfijo será: a b + c d / e + y el árbol generado será: Al recorrerlo en preorden, los datos generados serán: + / + a b c d e Al recorrerlo en posorden, los datos generados serán: a b + c d / e + Las dos propiedades anteriores se cumplen. Se recorremos el árbol en inorden los datos generados serán: a + b c / d + e Pero esta expresión, para su evaluación, se asocia así: a + ( ( b c ) / d ) + e Y es bien diferente da la inicial, la cual era: (a+b) c/d+e Lo cual nos permite plantear la siguiente propiedad: Si se recorre un árbol en inorden, los datos generados no representan la expresión escrita en infijo. Si queremos que de un árbol se genere la correspondiente expresión en infijo no basta con recorrerlo en inorden, además debemos efectuar un proceso que parentice la expresión. Para el ejemplo, el recorrido inorden del árbol es: a+b c/d+e Como el operador tiene más prioridad que los demás, y el operador / tiene más prioridad que el +, al tratar de evaluar la expresión esta se asocia así: a + ( ( b c ) / d ) + e Debemos diseñar un proceso que genere un arreglo infijo con los siguientes datos: Lo cual implica que en la medida en que generamos este arreglo debemos ir incluyendo paréntesis donde sea necesario. Veamos la naturaleza del problema: Como el operador de la raíz aplica a los dos subárboles, gráficamente el árbol anterior lo podemos representar así: 1 2 3 4 Si cada cuadro representa un par de paréntesis, este árbol lo podríamos escribir así: (rama izquierda )+e ((rama izquierda ) / ) d ) + e (((rama izquierda ) c ) / d ) + e ((((rama izquierda) + b) c ) / d ) +e ((( a ) + b) c ) / d + e Ahora retiramos los paréntesis innecesarios, debidos a la jerarquía de los operadores, tendremos la expresión: ((( a +b) c ) / d ) + e No podemos retirar los paréntesis que encierran la expresión (a+b), debido a que se cambia la expresión ya que el operador es de mayor prioridad que el operador +. Los paréntesis ya encierran la expresión (a+b) c si se puede retirar, debido a que el operador es de mayor jerarquía que el operador / ((a+b) c/d)+e Los paréntesis que encierran la expresión (a+b) c / d pueden ser retirados ya que el operador + es el de al mínima jerarquía. Con la cual la expresión debidamente patentizada es: Veamos otro ejemplo: Si recorremos el árbol en inorden, los resultados serán: a + b c Lo cual es diferente a la expresión que esta representada en el árbol. (a+ b ) c Si el árbol es: Al recorrerlo en inorden los resultados son: a b+c y no existe la necesidad de insertar paréntesis en la expresión. La diferencia, en este caso particular, radica en que si el operador padre tiene más jerarquía que el operador hijo, debemos patentizar la rama izquierda o derecha del árbol. Observemos los siguientes árboles: Para el árbol la expresión será: (a+b) c Debe patentizarse. El operador tiene mas jerarquía que el operador + Para el árbol la expresión será: a b+c no se necesitan paréntesis. El operador + tiene menos jerarquía que el operador Para el árbol la expresión será: (a-b)-c Para esta expresión., no son necesarios los paréntesis ya que sin ellos la asociación se haría de la misma manera. Veamos este caso. Para este caso al recorrer el árbol en inorden, se genera la siguiente expresión: c – a – b Se deben insertar paréntesis ya que es muy diferente la expresión que está representada en el árbol: c – (a - b ) Ahora debemos puntualizar en que momento se necesitan insertar paréntesis. La respuesta es muy sencilla. Veamos este ejemplo Al recorrer el árbol en inorden, el resultado será: a+b-c d+e*f Debemos insertar paréntesis a la expresión a+b-c y también a la expresión d+e*f. al final arreglo infijo quedara así: ( a + b – c ) ((d + e ) * f ) Como puede identificarse esta situación. Obsérvese que si existen dos nodos cuya relación es padre-hijo y los dos contienen operadores, debemos abrir un paréntesis si el operador hijo tiene menos prioridad que el operador padre. Este paréntesis que se abre debe existir siempre y cuando el padre tenga más jerarquía que el hijo y asea izquierdo o derecho. Para insertar un paréntesis son necesarias tres condiciones: 1. que el nodo contenga un operador. 2. que su hijo (izquierdo o derecho) contenga también un operador. 3. que el nodo padre sea un operador de mayor jerarquía que el nodo hijo. Si estas tres condiciones se cumplen debemos abrir un paréntesis. Este paréntesis, guardaremos en algún lugar el paréntesis que cierra para que en su momento, se incorpore al arreglo infijo. Para la solución a este problema debe servirnos una pila ya que el proceso se asimila a escribir un árbol en inorden, con la salvedad de que bajo las tres condiciones expuestas anteriormente, debemos insertar un paréntesis a la pila.

CAPITULO II  ALGEBRA BOLEANA  DEFINICION: Algebra para expresar relaciones lógicas denominadas en honor del científico George Boole (1815-1864).  MECANISMOS DE LA ALGEBRA DE BOOLE Y LA NORMAL CONJUNTOS BOOLE 0 1 1 0 0 U 0 0 U 1 * U + U O  AXIOMAS DEL ALGEBRA DE BOOLE: 1_ (1) (1) = 1 1_ 1+1 = 1 2_ (1) (0) = 0 2_ 0+1 = 1 3_ (0) (0) = 0 3_ 0+0 = 0 4_ 1 = 0 4_ 0 = 1  TEOREMAS DEL ALGEBRA DE BOOLE: 1.- 0. x = 0 0 x = 0 1.- 0 + x = x 0Ux 0 x 2.- 1. x = x u x = x 2.- 1 + x = 1 uUx = x 3.- x. x = x x x = x 3.- x + x = x xUx = x 4.- x. x = x x x = 0 4.- x + x = 1 xUx = u 5.- XY = YX PROP.CONM. 5.- x + y = y+x 6.- xyz = (x)(yz)ó (xy)(z) prop. Aso. 6.- x + y + z = x+(y+z)ó(x+y)+z 4.1. REOMENDACIONES PARA LA COMPROBACION DE TEOREMAS DE BOOLE 1. Se tratara de comprobar aplicando teoremas básicos del (1 al 16) 2. se realizara el miembro más complicado, ejecutando operaciones y se tratara de igualar con el más simple. 3. Después de realizar el miembro mas complicado, se agregan literales en forma de unos o ceros según el caso 4. Se tratara de comprobar con algún teorema no básico pero previamente comprobado. 4.2. FORMA DE AGRAGAR UNOS EN UNA FUNCION BOLEANA Ej. Agregar al teorema xy la variable u en forma de unos (1’s) 1ero xy ( u + u ) = xyu + xyu :. Esto es = xy ( u + u) = xy (1) :. xy 2do xy ( 1+ u ) = xy + xyu :. Esto es = xy ( 1 + u ) = xy (1) :. xy 3er xy ( 1+ u ) = xy + xyu:. Esto es = xy ( 1 + 0 ) = xy (1) :. xy 4.3. PLANTEAMIENTO Y SOLUCION DE TEOREMAS: Ejemplo demostrativo: 1_a) x + y z = x + y z 1_b) x + y z = x + y z x(y+y)+yz = x + y z x(y+1)+yz = x + y z xy+xy+yz = x + y z xy+x+yz = x + y z x(y+y)+yz = x + y z x(1+y)+yz = x + y z x (1) + y z = x + y z x (1) + y z = x + y z x + y z = x + y z x + y z = x + y z 1_c) x + y z = x + y z x(y+1)+yz = x + y z xy+x+yz = x + y z x(1+y)+yz = x + y z x(1) + y z = x + y z x + y z = x + y z 1A x y + x z = x (y+z) 1B_ (x+y) (x+z) = x + y z x ( y z ) = x (y+z) x+xz+xy+yz = x + y z x(1+z+y)+yz = x + y z x(1) + yz = x + y z x + y z = x + y z 2A_ x y + x y = x 2B_ (x+y) (x+y) = x x (y+y) = x x+xy+xy+yy = x x(1) = x x(1+y+y)+0 = x x = x x(1) = x x = x 3A_ x + x y = x 3B_ x (x+y) = x x (1+y) = x x + xy = x x(1) = x x (1+y) = x x = x x (1) = x x = x 4A_ x + x y = x + y 4B_ x (x+y) = x y x(y+1)+xy = x + y x x + x y = x y xy+x+xy = x + y 0 + x y = x y x+y+(x+x) = x + y x y = x y x + y(1) = x + y x + y = x + y 5A_ zx + zxy = zx + zy 5A'_ xy + xz + yz = xy + xz zx(y+1)+zxy = zx + zy xy+xz+yz(x+x) = xy + xz zxy+zx+zxy = zx + zy xy+xz+xyz+xyz = xy + xz zx+zy(x+x) = zx + zy xy(1+z)+xz(1+y) = xy + xz zx + zy(1) = zx + zy xy (1) +xz (1) = xy + xz zx+zy = zx +zy xy + xz = xy + xz 4.5. TEOREMAS DE DEMORGAM El teorema o ley de de morgan se puede explicar de la siguiente forma: 1.- Si cada variable se sustituye por su complemento 2.- Cada suma por multiplicación y c/multiplicación por suma 3.- En último se obtiene la función complemento  FUNCIONES DUALES: Dos funciones serán duales si difieren únicamente por el intercambio simultáneo: (+ sust. Por x ) ( x sust. Por + ) Ej. (x,y,z)= x.y.z + x y z + x y z  FUNCION COMPLEMENTO Esto se obtiene 1ero buscando el dual de la función 2do complementando c/una de las variables. FUNCION: F (x,y,z) = (x+y+z) (x+y+z) (x+y+z) DUAL : F (x,y,z) = x y z + x y z + x y z COMPLEMENTO: F (x, y , z) = x y z + x y z + x y z  Ahora puede aplicar la Ley De Demorgan así:  DEMORGAN F(x, y, z ) = x y z +x y z + x y z  Realizar los siguientes problemas y aplique la ley de demorgan 1_ F= X1 X2 X3 + X1 X2 X3 + X1 X2 X3 DUAL F= (X1 X2 X3) + (X1 X2 X3) +(X1 X2 X3) COMPLEMENTO F= (X1 X2 X3) + (X1 X2 X3) +(X1 X2 X3) DE DEMORGAN F= (X1 X2 X3) + (X1 X2 X3) +(X1 X2 X3) 2_ F= (X1 X2 X3) + (X1 X2 X3) +(X1 X2 X3) DUAL F= X1 X2 X3 + X1 X2 X3 +X1 X2 X3 COMPLEMENTO F= X1 X2 X3 + X1 X2 X3 +X1 X2 X3 DE DEMORGAN F= X1 X2 X3 + X1 X2 X3 +X1 X2 X3 3_ F= c + xy = x (x+y) :. = x (x+y) 4_ F= (A+B) c+D E:.= (AB+C)D+E 5_ F= AB+(CD+AB)E F:.= (A+B) (((C+D)(A+B)+E)+ F 6_ F= (AB+C) D+E:.= (A+B) C+D E  EJERCICIOS PROPUESTOS: FUNCIONES DE BOOLE 1_ BC + AC + AB = AB + AC 2_ (A+C) (A+B+C) = (A+C) (B+C) 3_ X1+X1 X2 = X1+X2 4_ (A+B) (A+C) = A + BC 5_ zx + zxy = zx +y 6_ xy + xz +yz = xy + xz 7_ (x+y) (x+y) = x 8_ zx + zxy = zx + zy 9_ X1 X2 X3 + X1 X2 + X1 X2 X3 + X2 X3: TEOREMAS DE DEMORGAN 10_ (z+x) (x+z+y) (x+z+y) 11_ (ABC) + (AB)+B C 12_ X1 (X2+X3+X4) +X5 X6 13_ P(Q+Y) 14_ (M+B) K+D W 15_ (ABC) (ABC) E 6B_ x+y = xy x+y = xy (x+y) (xy) = 0 x+y + xy = 1 (x+y) (xy) = 0 x+y + xy = 1 (0+y)(x 0) = 0 x(y+y)+y(x+x)+xy = 1 (y) (0) = 0 xy+xy+xy+xy = 1 0 = 0 x(y+y)+x(y+y) = 1 x(1)+x(1) = 1 x+x = 1 EJERCICIOS PROPUESTOS 1_ BC + AC + AB = AB + AC 2_ (A+C) (A+B+C) = (A+C) (B+C) 3_ X1 + X1X2 = X1+X2 4_ (A+B) (A+C) = A + BC 5_ zx + zxy = zx + y 6_ xy + xz + yz = xy +xz 7_ (x+y) (x+y) = x 8_ zx + zxy = zx + zy 9_ X1X2X3 + X1X2 + X1X2X3 + X2X3 (DE DEMORGAN) 10_ (z+x) (x+z+y) (x+z+y) 11_ (ABC)+(AB)+B C 12_ (X1+X2X3X4)+ X5 X6 13_ (X1+X2X3X4) X5+X6 14_ P(Q+Y) 15_ (M+B)K+D W TABLAS DE VERDAD Y MINIMIZACION DE FUNCIONES DE BOOLE CON LA APLICACION DE TEOREMAS 1_ TABLAS DE VERDAD, VERACIDAD O PRUEBA DE INDUCCION PERFECTA. Esta tabla e una forma de comprobación que contiene todas las combinaciones posibles de una función de BOOLE o de un grupo de variables. La forma de cómo se desarrolla una tabla de verdad se describe con el siguiente ejemplo: Ej: desarrolle una tabla de verdad para cuatro variables (A,B,C,D) N variables tiene 2n combinaciones distintas, por lo que para este ejemplo tendremos 24 combinaciones distintas TABLA No 2 2 2 2 A B C D 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 RELACION DE NUMEROS DECIMALES Y SU EQUIVALENCIA A N2 BINARIA 2 2 2 2 2 2 1410 = N2 1 1 1 0 3310 = N2 1 0 0 0 0 1 610 = N2 1 1 0 1010 = N2 1 0 1 0 4310 = N2 1 0 1 0 1 1 4410 = N2 1 0 1 1 0 0 6010 = N2 1 1 1 1 0 0 6310 = N2 1 1 1 1 1 1 ETC N2 6.2. UTILIZACION DE LA TABLA DE VERDAD COMO MEDIO DE VERDAD 6.2.1 COMPROBACION DE TEOREMAS: 1_ XY = X + Y x y x . y F1 x + y F2 0 0 0 . 0 1 1 + 1 1 0 1 0 . 1 1 1 + 0 1 1 0 1 . 0 1 0 + 1 1 1 1 1 . 1 0 0 + 0 0 2_ xy = xy x y x . y F1 x y F2 1 1 1 . 1 0 0 0 0 1 0 1 . 0 1 0 1 0 0 1 0 . 1 1 1 0 0 0 0 0 . 0 1 1 1 1 F1 F2 = :. xy = xy = F1 = F2 3_ xy +xz = (x+z) (x+y) x y z xy + xz F1 (x+z) (x+y) F2 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 F1 F2 = :. xy + xz = (x+z) (x+y) 6.3_ MINIMIZACION DE FUNCIONES DE BOOLE CON APLICAION DE TEOREMAS. 1_ A + B + AB + (A+B) AB A+B + AB + AB + AB (A+AB) + (B+AB) A(1+B) + B(1+A) A(1) + B(1) A+B 2_ x + y xy + (x+y)xy x+y + xy + xxy + xyy x + y+xy x(y+y)+ y(x+x)+xy xy+xy+xy+xy+xy xy+xy+xy+xy+xy x(y+y)+x(y+y) x+x 3_ (A+B+AB) (A+B) (AB) (A+B+AB) (0B+A0) (A+B+AB) (0+0) (A+B + AB) (0) 0 + 0 + 0 0 4_ ABC+ABCD+AC ABC(D+D) +ABCD+AC ABCD+ABCD+ABCD+AC ABCD+ABCD+AC AC(1+BC+BD) AC(1) = AC 7_ MINIMIZACION DE FUNCIONES DE BOOLE ATRAVES DE LOS MAPAS DE KARNAUGH (PARA 2,3 Y VARIABLES) 7._ INTRODUCCION Los mapas de KARNAUGH se utilizan para la minimización de funciones de BOOLE. Estos mapas consisten en representar los valores tomados por una función lógica en una tabla rectangular o cuadrara en la cual cada casilla corresponde a una combinación distinta de las variables, esas casilla están dispuestas de tal manera que las combinaciones asociadas a do casilla difieren únicamente por el valor de una variable; en la practica pueden utilizarse llaves que designan las casillas para las cuales c/variable toma el valor de 1. 0 2 6 4 0 0 0 0 1 0 1 1 0 1 0 0 1 3 7 5 0 0 1 0 1 1 1 1 1 1 0 1 ABC + ABC = AB(C+C) = AB ABC+ABC=BC(A+A=BC) Los mapas de KARNAUGH tienen 2n casillas en donde n es igual al numero de variables. Estos mapas pueden dibujarse de la siguiente manera: mapas 2 variables. A=0 A=1 A B A B B=0 0 0 1 0 A B A B B=1 0 1 1 1 Mapas para 3 variables (8casilla) A=1 0 0 0 0 1 0 1 1 0 1 0 0 0 2 6 4 C=1 0 0 1 0 1 1 1 1 1 1 0 1 0 3 7 5 Mapas para cuatro variables (16 casillas) A=1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 4 12 8 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 5 13 9 D=1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 3 7 15 11 C=1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 2 6 14 10 B=1 Las relaciones de las variables que tiene el mapa KARNAUGH no tienen que ser necesariamente las anteriores estas regiones se pueden determinar en otras posiciones siguiendo las siguientes reglas: a) Cada variable debe ocupar la mitad del total de las casillas del mapa. b) Cada variable debe compartir la mitad de sus casillas con el resto de las variables. C 1 0 1 1 9 8 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 A 1 4 1 5 1 3 1 2 B 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 6 7 5 4 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 2 3 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 D Aun cuando las regiones en los mapas no tienen necesariamente una posición fija; es muy conveniente en la minimización de funciones adaptar una posición determinada con la finalidad de adquirir más rapidez en la solución de problemas. Los mapas descritos al inicio de este objetivo son comúnmente usados y llamados por algunos autores mapas estándar Otra forma comúnmente utilizada para elaborar mapas de KARNAUGH es la siguiente: BA 0 1 A B A B 0 0 0 1 0 A B A B 1 0 1 1 1 CAB 00 01 11 10 A B C A B C A B C A B C 0 0 0 0 0 1 0 1 1 0 1 0 0 A B C A B C A B C A B C 1 0 0 1 0 1 1 1 1 1 1 0 Mapa para dos variables Mapa para tres variables CDAB 0 0 0 1 1 1 1 0 A B C D A B C D A B C D A B C D 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 A B C D A B C D A B C D A B C D 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 A B C D A B C D A B C D A B C D 11 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 A B C D A B C D A B C D A B C D 10 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 Mapa para cuatro variables Puede decirse que los mapas de KARNAUGH son una forma diagramática de la tabla de verdad. Puesto que todas las combinaciones posibles de un grupo de variables se encuentran contenidas en el mapa. Con el objeto de agilizar la minimización de funciones las casillas de los mapas que en este curso se utilizaran como estándar, que darían numeradas de la siguiente forma. 7.1_ REPRESENTACION DE UNA FUNCION DE BOOLE EN UNA MAPA DE KARNAUGH. SUMA DE - Forma canónica F(A,B,C)= ABC+ABC+ABC PRODUCTOS - Forma binaria F(A,B,C)= 001+011+110+100 1's - Forma técnica F(A,B,C) = Em (1,3,4,6) FUNCIONES - Forma no canónica F(ABC)=ABC+AB+ABC+BC DE BOOLE PRODUCTO - Forma canónica F(ABC)=(A+B+C)(A+B+C)(A+B+C)(A+B+C) DE SUMA - Forma binaria F(ABC)=(1+1+1)(1+0+1)(0+1+0)(1+0+1) 0's - Forma técnica F(ABC)= (0,2,3,4,5) - Forma no canónica F(ABC)=(A+B)(A+B+C)(A+C)(A+B+C) Por lo pronto solo se estudiarían las funciones que representan unos (1’s) en los mapas. Como ya se dijo anteriormente una función de BOOLE puede representar 1’s o 0’s en un mapa; y esto puede realizarse de diversas formas, las cuales explicaremos con los siguientes ejemplos: Representar en un mapa la siguiente funcion: F= ABC+ABC+ABC+ABC F=(x,y,z,w)= Em (0,3,5,6,7,11,13,15) ZWXY 00 01 11 10 00 1 01 1 1 11 1 1 1 1 10 1 A 1 1 1 C 1 B 7.2_ ASOCIACION DE 1’s EN LOS MAPAS En un mapa de KARNAUGH se pueden asociar los 1’s que se encuentren en casillas adyacentes o vecinas. La adyacencia o vecindad entre dos casillas puede ser de manera vertical u horizontal, y en términos generales se dice que 2 o mas casillas son adyacentes si solo difieren en l valor de una variable. .- Se pueden asociar 1’s en cantidades que provengan de 2n. .- Un 1 puede formar parte en más de una ocasión. .- Debe asociarse siempre la mayor cantidad permitida de 1’s y no cometer redundancias. Ej:1) F=ABC+ABC+ABC+ABC+ABC A 1 1 1 1 C 1 B FUNCION MINIMIZADA F C + AB 2._ F= ABC+AC+BC+ABC A 1 1 C 1 1 1 B FUNCION MINIMIZADA F=AB+BC+AB A 1 1 C 1 1 1 1 B 3._ F=BC+AB+BC+AC FUNCION MINIMIZADA F=B+C 4._ F(w,x,y,z)= Em(3,4,5,7,11,12,14,15) YZWX 00 01 11 10 00 1 1 01 1 11 1 1 1 1 10 1 FUNCION MINIMIZADA F = yz + wxy + wxz 5._ f(X0,X1,X2,X3) = Em (0,2,10,11,12,14) X2X3X0X1 0 1 11 10 0 1 1 1 11 1 10 1 1 1 FUNCION MINIMIZADA F= X0X1X3 + X0X1X2 + X0X1X2 6._ F=ABCD+ABC+ABCD+ABCD+ABCD+ABCD+ABCD A 1 1 D C 1 1 1 1 1 1 B FUNCION MINIMIZADA F= CD+BD 7.3 ASOCIACION COMUN DE 1’s EN LOS MAPAS DE 3 VARIABLES 1. 1 1 1 2. 1 1 1 3. 1 1 1 1 4. 1 1 5. 1 1 1 1 7.4_ ASOCIACION COMUN DE 1’s EN LOS MAPAS DE 4 VARIABLES 1. 1 1 1 1 1 1 1 1 2. 1 1 1 1 3. 1 1 1 1 1 1 1 1 4. 1 1 1 1 1 1 5. 1 1 1 1 1 1 1 1 7.4_ PROBLEMAS PROPUESTOS a) F(W,X,Y,Z) =Em (3,4,5,7,11,12,14,15) b) F=ABCD+ABC+ABCD+ABCD+ABCD+ABCD c) F= ABCD+ABCD+ABCD+ABC+ABCD+ABCD+ACD+ABCD d) F(K,L,M,N) = Em (0,4,6,10,11,13) e) F=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD f) F(A,B,C,D)= Em (1,5,6,7,11,12,13,15) g) F(X,Y,Z,W)= Em (0,1,2,4,5,8,10) 8._ FUNCION LOGICAS 0 0 VOLTIOS (TEORICO) PRACTICO 0 a 1.2V 1 3.6 VOLTIOS (RIORICO) PRACTICO 3.6 a 9V 8.1._ COMPUERTAS 8.1.1 COMPUERTAS BASICAS NOT (NO) AND (Y) OR (Ó) 8.1.2 COMPUERTAS NO BASICAS NAND MOR OR EXCLUSIVO 8.1.3 OPERACIÓN DE LAS COMPUERTAS BASICAS NOT SIMBOLO OPERACIÓN (INVERTIDO COMPLEMENTAR) TABLA DE VERDAD X F=X 0 1 1 0 AND SIMBOLO OPERACIÓN (MULTIPLICACION) TALA DE VERDAD A B F = A.B 0 0 0 0 1 0 1 0 0 1 1 1 OR SIMBOLO OPERACIÓN (SUMA) TABLA DE VERDAD A B F= A+B 0 0 0 0 1 1 1 0 1 1 1 1 + + 8.1.4 OPERACIONDE LA COMPUERTAS NO BASICAS NAND SIMBOLO OPERACION (MULTIPLICACION Y COMPLEMENTA) COMPLEMENTA EL PRODUCTO TABLA DE VERDAD A B F = A B 0 0 1 0 1 1 1 0 1 1 1 0 NOR SIMBOLO OPERACIÓN: SUMA Y COMPLEMENTA (COMPLEMENTA LA SUMA) TABLA DE VERDAD A B F = A+B 0 0 1 0 1 0 1 0 0 1 1 0 OR EXCLUSIVO (XOR) SIMBOLO OPERACIÓN: SACA UN (1) CUANDO EXCLUSIVAMENTE UNA DE SUS ENTRADAS ES UN (1) A B F = AB+ AB 0 0 0 0 1 1 1 0 1 1 1 0 TABLA DE VERDAD 8.1.3. IMPLEMENTACION DE FUNCIONES DE BOOLE Implementar una función de BOOLE es llenarla a la practica por medio de un circuito que puede ser electrónico hidráulico, neumático o electrónico a base de compuertas lógicas. Ej. Implementar la sig. Función por medio de compuertas lógicas 1._ F= X0 X1 X3 + X0 X1 X3 + X0 X1 X2 2._ IMPLEMENTAR LA SIGUIENTE FUNCION F= YZ + XWZ + XYW 3._ IMPLEMENTAR LA SIGUIENTE FUNCION CON LAS RESTRICCIONES INICIALES 2 SALIDAS. 3_ F= (A+D) (A+B)(B+D)(A+B+C) 4_ IMPLEMENTAR LA SIGUIENTE FUNCION CON COMPUERTAS OR Y NOT F= A B C = A+B+C 5_ IMPLEMENTAR LA SIGUIENTE FUNCION CON COMPUERTAS AND Y NOT F= (X+Y+Z) (X+Y+Z)= XYZ+ XYZ 6_ Se tienen 2 números de 2 bits cada uno: a que estará formado por A1 A0 y B que estará formado por B1 B0 diseñe un circuito que indique con un uno”1” cuando se cumpla cada una de las siguientes condiciones: a) Que A =B b) Que A< B c) Que A> B A B A1 A0 B1 B0 Fa Fb Fc 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 2 0 0 1 0 0 1 0 3 0 0 1 1 0 1 0 4 0 1 0 0 0 0 1 5 0 1 0 1 1 0 0 6 0 1 1 0 0 1 0 7 0 1 1 1 0 1 0 8 1 0 0 0 0 0 1 9 1 0 0 1 0 0 1 10 1 0 1 0 1 0 0 11 1 0 1 1 0 1 0 12 1 1 0 0 0 0 1 13 1 1 0 1 0 0 1 14 1 1 1 0 0 0 1 15 1 1 1 1 1 0 0 B1B0A1A0 00 01 11 10 00 1 01 1 11 1 10 1 A=B F=Em (0,5,10,15) F= A+A0B1B0+A1A0B1B0+A1A0B1B0+A1A0B1B0 B1B0A1A0 00 01 11 10 00 01 1 11 1 1 10 1 1 A<B F= Em (1,2,3,6,7,11) F= A1B1+A0B1B0+A1A0B0 B1B0A1A0 00 01 11 10 00 1 1 1 01 1 1 11 10 1 A>B F= Em (4,8,9,12,13,14) F= A1 B1+ A0 B1 B0 + A1 A0 B0 DISEÑAR UN GENERADOR DE PARIDAD PAR Y OTRP GENERADOR DE PARTIDA IMPAR, PARA 4 BITS tomando en consideración la serie de unos o que integran c/series de bits y haga que el cuanto corra en una sola salida. F(A,B,C,D) = (1,2,4,6,7,8,9,11,12,14) = (1,2,3,4,6,7,8,9,11,12,13,14) A B C D F 0 0 0 0 0 0 1 0 0 0 1 1 2 0 0 1 0 1 3 0 0 1 1 1 4 0 1 0 0 1 5 0 1 0 1 0 6 0 1 1 0 1 7 0 1 1 1 1 8 1 0 0 0 1 9 1 0 0 1 1 10 1 0 1 0 0 11 1 0 1 1 1 12 1 1 0 0 1 13 1 1 0 1 1 14 1 1 1 0 1 15 1 1 1 1 0 CDAB 00 01 11 10 00 1 1 01 1 1 1 11 1 1 10 1 1 1 F= AC+D+ABD+ABC+ACD+BCD CDAB 00 01 11 10 00 1 1 01 1 1 1 11 1 1 1 10 1 1 F= AC+AC+BD+BD F= (A,B,C,D)=(0,3,5,10,15) F(A,B,C,D)=(0,5,10,15) CDAB 00 01 11 10 00 1 01 1 11 1 10 1 CDAB 00 01 11 10 00 1 01 1 11 1 1 10 1 F=ABCD+ABCD+ABC+BCD F=ABCD+ABCD+ABCD+ABCD+ABCD PROBLEMAS PROPUESTOS 1._ Se desea minimizar para luego implementar con compuertas lógicas básicas las siguientes BOOLEANAS: a) ABCD+ ABCD +ABCD + ABCD + ABCD + ABCD+ ABCD b) F(K,L,M,N)=Em (0,4,6,10,11,13) c) F(A,B,C,D)= Em (0,1,3,5,7,9,11,13,15) d) F(X0,X1,X2,X3)=Em(1,4,5,8,9,11,12,14,15) e) F= ABC + ABC + ABC + ABC + ABC + ABC + ABCD 2._ Diseñar un circuito detector de números primos (que reconozca los números primos con un cero) 3._ Diseñe un circuito detector de números pares y nomes (pares con 0’s y nomes con 1’s) 9._ INTERPRETAR DE LOS TEOREMAS DE LOS MINITERMINOS Y MAXTERMINOS A parir de la siguiente tabla de verdad obtenga la siguiente función; una con minitérminos (1’s) y otra con maxtérminos (0’s) X Y Z F MINITERMINOS MAXTERMINOS 0 0 0 0 0 X+Y+Z 1 0 0 1 1 X Y Z 2 0 1 0 0 X+Y+Z 3 0 1 1 0 X+Y+Z 4 1 0 0 1 X Y Z 5 1 0 1 0 X+Y+Z 6 1 1 0 1 X Y Z 7 1 1 1 0 X+Y+Z :. Fmin = XYZ+XYZ+XYZ F(X,Y,Z)=Em (1,4,6) Fmax = (X+Y+Z) (X+Y+Z) (X+Y+Z) (X+Y+Z) (X+Y+Z)= (0,2,3,5,7) NOTAS: 1._ Breve explicación de los minitérminos: Cada ves que la función tome un (1’s) se formara un termino que es el producto de las variables de que consta la función; complementando las variables que en esa connimacion valgan 0’s y dejando tal cual las variables que valgan 1’s 2._ Breve explicación de los maxtérninos: Cada vez que la función tome el valor de 0’s se formara un maxtérmino, el cual será la suma de las variables que consta la función; complementando todas las variable que en esa combinación valgan 1’s. la función maxtérminos se formara del producto de todas las sumas obtenidas. zxy 00 01 11 10 0 1 1 1 1 Fmin = xz + xyz zxy 00 01 11 10 0 0 0 1 0 0 0 Fmax = (x+z) (x+z) (x+y) Maximizar con maxtérminos lo siguiente función F= (A+B+C) (A+B+C+D) (A+B+C+D) (A+B+C+D) (A+B+C+D) (A+B+C) 1 2 3 4 5 6 CDAB0 00 01 11 10 00 0 1 1 0 01 0 1 1 0 11 0 0 0 0 10 1 1 1 1 Fmax M= (C+D)(B+C) Fmin = CD +BC Ej_ Función (A,B,C,D) = (1,3,4,5,6,7,8,9,13,15) CD AB 00 01 11 10 00 0 0 01 0 0 0 0 11 0 0 0 10 0 Función M= (A+D)(B+D)(A+B)(A+B+C) Ej. F(XYZW)= (0,2,8,12,13) X 00 01 11 10 00 0 0 0 01 0 W 11 Z 10 0 Y Fmin M= (X+YW)(Y+Z+W)(X+Y+Z) PROBLEMAS: De las siguientes funciones obtenga los maxitérminos y los minitérminos primero obtenga los maxitérminos y luego los minitérminos: a) F(A,B,C,D)= M(0,2,6,10,14,15,9,1) b) F(X,Y,Z,W)= M(1,4,6,5,2,14,12,10,15) c) F(A,B,C,D)= M(2,6,8,9,10,11,13,14,15) d) F(X,Y,Z,W)= M(3,4,5,9,14,15,11,10,7) 10._IMPLEMENTACION DE FUNCIONES UTILIZANDO SOLO COMPUERTAS NAND O SOLO COMPUERTAS NOR 10.1_ FORMULAS PARA IMPLEMENTAR CON NAND SIMBOLO ALGEBRAICO NAND / a) X= X/1 b) X.Y.Z =(X/Y/Z)/1 c) X+Y+Z=(X/1)(Y/1)(Z/1) Ó (X/Y/Z) d) SUMA DE PRODUCTOS AB+CDE+F= (A/B)/(C/D/E)/F e) PRODUCTO DE SUMAS (A+B)(C+D+E)(F)= (A/B)(C/D/E)/F/1 PROBLEMAS PROPUESTOS: 1._ Implementar con NAND’S F=BD+BC+ABCD=(B/D)/(B/C)/(A/B/C/D) 2._ Implementar con NAND’S la siguiente función F=(X+Z)(X+Y)(Y+W) = (X/Z)/(X/Y)(Y/W) /1 3._ Implementar con NAND’S la siguiente función: F= (A+B+C+D)(B+D)(B+C) = (A/B/C/D)(B/D)(B/C)/1 10.2_ FORMULAS PARA IMPLEMENTAR CON NOR’S SIMBOLO ALGEBRAICO a) A = A 0 ó A A b) MULTIPLICACION ABC = A B C c) SUMA A+B+C= (A+B+C) 0 d) SUMA DE PRODUCTOS AB+CDE+F= (A B)( C D E ) F 0 e) PRODUCTO DE SUMAS (A+B)(C+D+E)(F)(A B)(C D E ) F PROBLEMAS PROPUESTOS: a) Los 2 ejercicios efectuados anteriormente con NAND ahora realícelos con NOR (aplicar las formulas dadas) b) Realizar llos siguientes problemas con compuertas NAN’S y NOR’S b.1_ F= A B C D b.2_ F= A+B+C+D b.3_ F= ABC+ ABC+ BC+ AC b.4_ F=(A+B)(B+C+D)(D+E) b.5_ F=AB+A+D+ABC+E 11._ MINIMIZACION DE FUNCIONESDE 5 VARIABLES CON MAPAS DE KARNAUGH. El mapa de cinco variables que usaremos en este curso estar estructurado de la siguiente forma. A=0 A B 0 4 12 8 1 5 13 9 E D 3 7 15 11 2 6 14 10 C B 16 20 28 24 17 21 29 25 E D 19 23 31 27 18 22 30 26 C DEBC 00 01 11 10 00 00000 00100 01100 01000 01 00001 00101 01101 01001 11 00011 00111 01111 01011 10 00010 00110 01110 01010 DEBC 00 01 11 10 00 10000 10100 11100 11000 01 10001 10101 11101 11001 11 10011 10111 11111 11011 10 10010 10110 11110 11010 A=0 A=1 La adyacencia en este caso puede se da dos formas en cada mapa y entre mapas. En cada mapa seria igual que en mapas de 4 variables; entre mapas la adyacencia puede determinarse de manera rápida y sencilla imaginándonos que uno de los 2 mapas es todo y colocado sobre el otro, y las casillas que queden encima son adyacente o vecinas por ejemplo la casilla 0-16,1-17 ,11-27,8-24, etc todas las reglas aplicadas para los mapas de cuatro variables son validas a las de n variables. Debe notarse que mapa de 5 variables no es mas que una de 4 repetida 2 veces. 1_ Ej minimizar en mapas de KARNAUG la siguiente función: F(x,y,z,w,v)= Em(1,3,4,5,7,8,9,10,12,13,21,24,25,26,28,29) W VYZ 00 01 11 10 00 1 1 1 1 01 1 1 1 1 11 1 1 10 1 wvyz 00 01 11 10 00 1 1 01 1 1 1 11 10 1 F = Em(I,II,II,IV,V) I = Y W II= Y Z V III= Z W V IV=X W V= X Y V 2._ F= ACDE+ABCDE+BCDE+ACD+ABCD+ABCD+ABCDE+ABCDE+ACDC+ABCDE 0 1 11 10 0 1 1 1 1 1 11 1 10 1 1 1 A=0 A=B DEBC 00 01 11 10 00 1 1 1 01 1 11 1 1 1 10 1 1 1 I=BE II=CE III=ABD IV=BCD V=BCDE TRABAJO 1._ F(XYZWV)=Em(0,4,6,8,9,10,13,14,15,17,23,26,29,30) 2._ F(A,B,C,D,E)=Em (1,6,10,14,15,20,23,24,27,30,31) 3._ F=ABCD+ABC+ABCD+BCDE+CDE+ACDE 4._ F=ACD+ABCD+ABCD+ABC+BCDE+ABCDE+CDE 5._ F= ACDE+ABCD+ABCD+ABC+ABCDE+ABCDE+d(ABC+ACD+ABCD+ABCDE+ABCDE FUNCIONES IMCOMPLETAS ESPECIFICADAS: P A Q F 0 0 0 0 0 1 0 0 1 1 2 0 1 0 1 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 X 7 1 1 1 X QPA 00 01 11 10 0 1 1 1 1 1 = F= PQ+PA 00 01 11 10 0 1 X 1 1 1 X EXPRESIONES TECNICA F(P,A,Q)=Em(1,2,3)+d(6,7) Obtener la realización mínima de suma de productos de la F=(A,B,C,D,E)=Emin(1,2,3,4,5,11,18,19,20,21,22,23,31)+d(0,1,2,15,27,30) A=0 A=1 00 01 11 10 00 X 1 X 01 1 1 11 1 X 1 10 1 00 01 11 10 00 1 01 1 11 1 1 1 X 10 1 1 X F= ABC+BDE+BCD+ABD UNIDAD III 3._ CIRCUITOS DE SALIDA MULTIPLES, CONTADORES EMPAQUETADOS Y EXHIBIDORES CON 7 SEGMENTOS (DISPLAY). 3.1._ CIRCUITOS DE SALIDA MULTIPLE: a) CIRCUITO DE SALIDA UNICA b) CIRCUITO DE SALIDA MULTIPLE -SALIDA UNICA -COMBINACIONALES -SALIDA MULTIPLE c) CIRCUITO LOGICOS -SECUENCIALES CIRCUITO DE SALIDA MULTIPLE

HISTORIA DE LA INFORMATICA  El origen de las máquinas de calcular está dado por el ábaco chino, éste era una tablilla dividida en columnas en la cual la primera, contando desde la derecha, correspondía a las unidades, la siguiente a la de las decenas, y así sucesivamente. A través de sus  Otro de los hechos importantes en la evolución de la informática lo situamos en el siglo XVII, donde el científico francés Blas Pascal inventó una máquina calculadora. Ésta sólo servía para hacer sumas y restas  En base a la calculadora de Pascal, el alemán Leibnitz, en el siglo XVIII, desarrollara una máquina que, además de realizar operaciones de adición y sustracción, podía efectuar operaciones de producto y cociente.  En el siglo XIX se comercializaron las primeras máquinas de calcular. En este siglo el matemático inglés Babbage desarrolló lo que se llamó "Máquina Analítica", la cual podía realizar cualquier operación matemática. Además disponía de una memoria que podía almacenar 1000 números de 50 cifras y hasta podía usar funciones auxiliares, sin embargo seguía teniendo la limitación de ser mecánica.  Recién en el primer tercio del siglo XX, con el desarrollo de la electrónica, se empiezan a solucionar los problemas técnicos que acarreaban estas máquinas, reemplazándose los sistemas de engranaje y varillas por impulsos eléctricos, estableciéndose que cuando hay un paso de corriente eléctrica será representado con un *1* y cuando no haya un paso de corriente eléctrica se representaría con un *0*.  El proyecto entre IBM y Howard Aiken para construir una computadora se inició en 1939. La Mark I se terminó en 1943, presentandose oficialmente en 1944. Con el desarrollo de la segunda guerra mundial se construye el primer ordenador, el cual fue llamado Mark I y su funcionamiento se basaba en interruptores mecánicos. En un principio la MARK I se llamaba ASCC (Calculadora Automática de Secuencias Controladas). Era una máquina automática eléctrica, aunque tenía componentes electromecánicos; podía realizar 5 operaciones aritméticas: suma, resta, multiplicación, división y referencia a resultados anteriores. La Mark I tenía 2.5 metros de alto y 17 metros de largo, pesaba 31500 kg, contenía 800 km de cable aproximadamente y tenía más de 3000000 de conexiones. Se programaba a través de una cinta de papel en la que había perforadas las instrucciones codificadas, la salida podía ser tanto por tarjetas perforadas como en papel ya que a la salida se podía conectar una máquina de escribir eléctrica. La máquina llamaba la atención porque tenía elegantes cubiertas de cristal muy llamativas.  En 1944 se construyó el primer ordenador con fines prácticos que se denominó Eniac.  En 1951 son desarrollados el Univac I y el Univac II (se puede decir que es el punto de partida en el surgimiento de los verdaderos ordenadores, que serán de acceso común a la gente). EVOLUCION Y PRESTACIONES DE LOS COMPUTADORES Generación Fechas aproximadas Tecnología Velocidad típica (operaciones por segundo) 1 1946-1957 Válvulas 40.000 2 1958-1964 Transistores 200.000 3 1965-1971 Pequeña y media integración 1.000.000 4 1972-1977 Gran integración 10.000.000 5 1978 Alta integración 100.000.000 LA PRIMERA GENERACION: LOS TUBOS DE VACIO ENIAC (Electronic Numerical Integrator and Computer) - Diseñado por Joh Mauchly y John Presper Eckert en la Universidad de Pennsylvania. - Primer computador electrónico de uso general del mundo. - El proyecto fue una respuesta a necesidades militares de los Estados Unidos en tiempos de guerra. - Mauchly y Eckert propusieron al ejército construir un computador de uso general usando tubos de vacío, en 1943 se aceptó la propuesta. - Pesaba 30 toneladas, ocupaba 15000 pies cuadrados y contenía más de 18000 tubos de vacío. Cuando funcionaba consumía 140 kilowatios de potencia. Efectuaba 5000 sumas por segundo. - Era decimal y no binaria. - Su memoria consistía en 20 “acumuladores”, cada uno capaz de contener un número decimal de 10 dígitos. Cada dígito estaba representado por un anillo de 10 tubos de vacío. - Un inconveniente era que tenía que ser programado manualmente mediante conmutadores y conectando y desconectando cables. - Fue terminado en 1946. - Fue utilizado por el ejército hasta 1955. La máquina de Von Neumann - Aparece la idea de programa almacenado (El programa se representaba en una forma adecuada para ser guardado en la memoria junto con los datos. Entonces, un computador podría conseguir sus instrucciones leyéndolas de la memoria, y se podría hacer o modificar un programa escribiendo en una zona de memoria). - En 1946, se comenzó en el Instituto para Estudios Avanzados de Princeton el diseño de un nuevo computador de programa almacenado que se llamó IAS. - Una memoria principal que almacena tanto datos como instrucciones. - Una unidad aritmético-lógica (ALU) capaz de hacer operaciones con datos binarios. - Una unidad de control que interpreta las instrucciones en memoria y provoca su ejecución. - Un equipo de entrada/salida dirigido por la unidad de control. Computadores comerciales - Los años 50 contemplaron el nacimiento de la industria de computadores con dos compañías , Sperry e IBM, dominando el mercado. - En 1947 Eckert y Mauchly formaron una corporación para fabricar computadores con fines comerciales. Su primera máquina de éxito fue el UNIVAC I (Universal Automatic Computer), utilizada por la oficina de censos para sus cálculos. - Realizaba operacines algebraicas con matrices, problemas de estadística, reparto de primas para las compañías de seguro de vida y problemas logísticos. - El UNIVAC II, tenía una capacidad de memoria mayor y más aplicaciones que el UNIVAC I, los programas escritos en las viejas máquinas pueden leerse en las nuevas. - IBM, sacó su primer equipo con programas almacenados electrónicamente, el 701, en 1953, fue diseñado para aplicaciones científicas. - En 1955 IBM, presentó los productos 702, que tenían varias características hardware que lo hacían adecuado para aplicaciones de gestión. UNIVAC LA SEGUNDA GENERACIÓN: TRANSISTORES Encapsulado de transistores - Se sustituyo los tubos de vacío por los transistores. - El transistor es más pequeño, más barato, disipa menos calor y puede ser usado de la misma forma que un tubo de vacío en la construcción de computadores. - Mientras que un tubo de vacío requiere cables, placas de metal, una cápsula de cristal y vacío, el transistor es un dispositivo de estado sólido, hechos con silicio. - Fue inventado en 1947 en los laboratorios de Bell. - En esta generación se introdujeron unidades lógicas y aritméticas y unidades de control más complejas, el uso de lenguajes de c programación de alto nivel, y se proporcionó un software del sistema en el computador. - Un computador contenía alrededor de 10000 transistores. - A través de los años 50 y principios de los 60 los equipos electrónicos estaban compuestos por componentes como transistores, resistencias, condensadores, etc., cuando un dispositivos necesitaba un transistor, había que soldar éste, que tenía una forma de un pequeño tubo de metal y contenía una pieza de silicio del tamaño de la cabeza de un alfiler, en una tarjeta de circuitos. Todo el proceso de fabricación desde el transistor hasta el panel de circuitos era caro y engorroso. LA TERCERA GENERACION: LOS CIRCUITOS INTEGRADOS En 1958 se inventó el circuito integrado , que revolucionó la electrónica e inició la era de la Microelectrónica, que significa “ pequeña electrónica”. Desde los comienzos de la electrónica digital y la industria de computadores, ha habido una tendencia persistente y consistente hacia la reducción del tamaño de circuitos electrónicos digitales. Los circuitos integrados utilizaron el hecho de que tales componentes como transistores, resistencias y conductores podían ser fabricados a partir de un semiconductor como el silicio. Se divide en una fina oblea de silicio en una matriz de pequeñas áreas, cada unos pocos milímetros cuadrados, la oblea se divide en chips, cada chip consiste en muchas puertas más una serie de puntos para conexiones de entrada y salida. El chip es encapsulado en una carcasa que lo protege y proporciona patas para conectar dispositivos fuera del chip. Ventajas: - El precio de un chip ha permanecido prácticamente invariable a través de este período de rápido crecimiento en densidad. Esto significa que el costo de la lógica del computador y de la circuitería de la memoria ha caído a una velocidad drástica. - La longitud de las interconexiones eléctricas ha disminuido, incrementándose así la velocidad operativa. - E; computador es ahora más pequeño, lo que lo hace más adecuado para más entornos. - Hay una reducción de las necesidades de potencia y refrigeración. - Las interconexiones de los circuitos integrados son mucho más fiables que las conexiones soldadas. Con más circuitos en cada chip hay menos conexiones entre chip. Primeros computadores son: los IBM Sistema/360 y el DEC PDP-8 ULTIMAS GENERACIONES Con la introducción de la integración a gran escala podía haber más de 1000 componentes en un solo chip, con la integración a muy gran escala 10000 componentes por chip , y los chips actuales pueden contener más de 100000 componentes. Memoria Semiconductora En 1970 Fairchild produjo la primera memoria semiconductora, con relativa capacidad. Este chip del tamaño de un sencillo núcleo de ferrita, podía tener 256 bits de memoria, era no destructiva y mucho más barata, tardaba en 70 milmillonésimas de segundo en leer un bit. A partir de 1970, la memoria semiconductora ha tenido ocho generaciones: qK, 4K, 16K, 64K, 256K, 1M, 4M y ahora 16M< bits en un solo chip. Cada generación ha proporcionado cuatro veces más densidad de almacenamiento que la generación previa junto con un menor costo por bit, y una mayor velocidad de acceso. Microprocesadores Igual que la densidad de elementos en los chips de memoria ha continuado creciendo, también lo ha hecho la densidad de elementos de procesamiento. Conforme el tiempo pasaba, en cada chip había más y más elementos, así que cada vez se necesitaban menos y menos chips para construir un procesador de un computador.