TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE TLÁHUAC
MATEMATICAS DISCRETAS
“Arboles”
ELABORADO POR:
ASESORA:
INGENIERIA EN SISTEMAS COMPUTACIONALES
2018-12-
INDICE
ANÁLISIS DEL PROBLEMA…………………………………………………………… 2
OBJETIVO………………………………………………………………………………... 3
JUSTIFICACION…………………………………………………………………………. 4
MARCO TEORICO………………………………………………………………………. 5
ALGORITMO…………………………………………………………………………….. 8
DIAGRAMA DE FLUJO………………………………………………………………… 9
CODIGO DE BOOTH………………………………………………………………….. 10
ANEXOS………………………………………………………………………………… 12
CONCLUSION………………………………………………………………………….. 13
BIBLIOGRAFIAS………………………………………………………………………. 14
ANÁLISIS DEL PROBLEMA.
pág. 1
Los árboles son estructuras de datos que permiten organizar y mantener
información en un computador, además de ser una estructura de datos
ampliamente usada que limita la forma de un árbol.
Los árboles en un computador además de permitir organizar la información
resultan ser estructuras fáciles para resolver ciertos tipos de problemas.
OBJETIVO
Se realizará un programa que pueda resolver operaciones binarias (algoritmo de
booth) para así poder resolver problemas que estén ligados al sistema de
numeración binaria (lenguaje natal de una computadora), y así dar facilidades al
usuario al momento que se le presenten estos problemas matemáticos.
Al igual que busca agilizar en términos de tiempo para resolver una operación de
este tipo, ya que en algún momento dado puede llegar a ser un poco tardado para
el sujeto que realizara la resolución de estos problemas.
JUSTIFICACIÓN
¿Por qué se hizo este programa?
Para dar solución a la problemática que implica el algoritmo de Booth, este consta
de la multiplicación y la división de números binarios con signo.
¿Que se soluciona con dicho programa?
Da solución principalmente a que barias personas interesadas en el mundo de la
programación no saben cómo convertir números decimales a binarios ni como
multiplicarlos y/o dividirlos, a ese problema se busca darle solución con un
programa que pueda hacer esas operaciones y conversiones.
¿A quién le sirve este programa?
Como ya se mencionó anteriormente, este sirve a los principiantes en
programación (o inclusive a los programadores ya experimentados) o a cualquier
persona que quiera y esté interesado en la multiplicación y división de números
binarios, facilitándoles este programa las operaciones ya mencionadas.
¿Cubre algún hueco del conocimiento?
pág. 2
Da conocimiento de quien fue es su creador en que año lo implemento así mismo
nos dice para que sirve y como se realizan la operación.
Su creador fue Andrew Donald Booth en el año de 1960 con la idea de poder
multiplicar y dividir los números binarios con signo de manera más rápida y
sencilla.
¿Qué es el algoritmo de Booth?
El algoritmo de Booth es un método muy importante ya que nos permite realizar
multiplicaciones y divisiones de números binarios con poca probabilidad de que
estas sean erróneas y más rápidamente, cuanta mucho los bits que vas a utilizar
dependiendo de las cantidades que deseas realizar.
MARCO TEÓRICO.
Árbol
En la informática, un árbol es una estructura de datos ampliamente usada que
imita la forma de un árbol, (un conjunto de nodos conectados). Un árbol se define
como un tipo de grafo que no contiene ciclos, es decir es un grafo también a
cíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en
donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un
grafo también a cíclico, pero a su vez es conexo.
Características y propiedades de los arboles
1. Todo el árbol que no es vacío, tiene un único modo raíz.
2. un nodo x es descendente directo de un nodo y, si el nodo X es apuntado por el
nodo Y. en este caso es como utilizar la expresión X es hijo de Y.
3. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en
este caso es común utilizar la expresión X es padre de Y.
4. Todos los nodos que son descendientes directos (hijos) de un mismo nodo
(Padre), son hermanos.
5. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de
terminal.
6. Todo nodo que no tiene raíz, ni terminal se conoce con el nombre de interior.
7. Altura de árbol es el máximo número de niveles de todos los nodos.
pág. 3
8: Nivel es el número de arcos que deben ser recorridos para llegar a un
determinado nodo. Por definición la raíz tiene nivel 1.
Tipos de arboles
1) Árbol binario
Es una estructura de datos la cual cada nodo siempre tendrá un hijo del lado
izquierdo y un hijo del lado derecho y no pueden tener más de dos hijos.
Si un hijo tiene como referencia a null, o sea que no almacena ningún dato
entonces se denominara como un nodo externo. Siendo el caso contrario el hijo lo
denominamos un nodo externo.
Tipos de árboles binarios
1) árbol binario de búsqueda auto-balanceable
Se trata de un árbol de búsqueda que intenta mantener su altura o el nivel de
nodos que este contiene bajo la raíz.
Esto es importante, ya que en muchas operaciones en un árbol de búsqueda
binaria tardan tiempo en proporcionar a la altura del árbol y los árboles de
búsqueda binarios ordinarios pueden tomar alturas muy grandes en situaciones
normales.
Tiempos para varias operaciones en términos del número de nodos del árbol n:
Operación tiempo en cuota superior asintótica.
Búsqueda O (log n)
Inserción O (log n)8
Iteración en orden O (n)
Estructuras de datos populares que implementan este tipo de árbol:
Árbol AVL
Árbol rojo-negro
Árbol AVL
Es un árbol binario de búsqueda, que cumple con la condición de que la diferencia
entre las alturas de los subárboles de cada uno de sus nodos, como mucho 1.
Se le denomina con ese nombre dado a la escritura de sus creadores (Andelson,
Velskii y Landis).
Para que este árbol se denomine AVL, debe cumplir con la “propiedad de
equilibrio”, esta nos asegura que la profundidad del árbol sea O (log n), por lo que
las operaciones sobre estructuras no deberán recorrer mucho para hallar el
elemento deseado. Como se verá, el tiempo de ejecución, de las operaciones
pág. 4
sobre estos árboles es, a lo sumo O (log(n)) en el peor caso, donde n es la
cantidad de elementos del árbol.
Árbol Rojo-negro
Árbol binario estricto (los nodos nulos se tienen en cuenta en la definición
de las operaciones todo nodo hoja es nulo).
Cada nodo tiene estado rojo o negro.
Nodos hoja (nulos) son negros.
La raíz es negra (esta condición se impone para simplificar algunas
operaciones).
Se cumplen las condiciones:
Un nodo rojo tiene dos hilos negros.
Todo camino de la raíz a cualquier hoja pasa por el mismo número de
nodos negros.
2) Árbol Multicamino
Los arboles multicamino o arboles mutlirrama son estructuras de datos de tipo
árbol usadas en computación.
Es un árbol ordenado cuyos nodos deben tener un número específico de hijos. En
este tipo de árbol conviene definir nodos externos especiales que no tienen hijos, y
normalmente no tiene ni nombre ni información asociada. Los nodos externos
actúan como nodos ficticios para los nodos que tienen el número de hijos
especificados.
pág. 5
Posee un grado a mayor a dos, donde cada nodo de información del árbol tiene un
máximo de g hijos.
Caminos/recorridos de los arboles:
Pre orden: En un recorrido en pre orden, visitamos primero el nodo raíz, luego
recursivamente realizamos un recorrido en pre orden del subárbol izquierdo,
seguido de un recorrido recursivo en pre orden del subárbol derecho.
(Raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre orden,
hay que realizar las siguientes operaciones recursivamente en cada nodo,
comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho
Inorden: En un recorrido en inorden, realizamos recursivamente un recorrido en
inorden en el subárbol izquierdo, visitamos el nodo raíz, y finalmente hacemos un
recorrido recursivo en inorden del subárbol derecho.
(Izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden
(simétrico), hay que realizar las siguientes operaciones recursivamente en cada
nodo:
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho
ALGORITMO.
pág. 6
1. Inicio.
2. Definir variables (a, b).
3. Escribir “Algoritmo de booth”
4. Escribir primer número (“a”).
5. Leer “a”.
6. Escribir Segundo número (“b”).
7. Leer “b”.
8. Escribir “el número a en binario es:”
9. Imprimir “a”.
10. Escribir “el numero b en binario es:”
11. Imprimir “b”.
12. Hacer la operación de “a*b”
13. Escribir “la operación de a*b es:”
14. Imprimir resultado y convertirlo a binario.
15. Fin.
DIAGRAMA DE FLUJO.
pág. 7
Inicio
Imprimir b en
binario
Definir variables
A,b
operacion
Leer “Algoritmo de a*b
booth”
Escribir primer Escribir “La operacion de a*b
número es:”
Leer “a”
Imprimir el
resultado de a*b y
convertirlo a binario
Escribir Segundo
número
Fin
Leer “b”
Escribir “El número a en
binario es:”
imprimir a
en binario
Escribir “El número b en
binario es:”
CODIGO DE BOOTH.
pág. 8
1. #include <iostream>
2. #include <string>
3.
4. using namespace std;
5. string convierteBin(int);
6.
7.
8. int main()
9. {
10. int a, b;
11.
12. cout << " ALGORITMO DE BOOTH" <<endl;
13. cout << "Escribe tu primer numero: ";
14. cin >> a;
15. cout << "Escribe otro numero: ";
16. cin >> b;
17.
18.
19. cout << "El numero " << a << " en binario es: " << convierteBin(a) << endl;
20. cout << "El numero " << b << " en binario es: " << convierteBin(b) << endl;
21. cout << "La multiplicacion de " << a << " * " << b << " = " << (a * b) << " en
binario es: " << convierteBin(a * b) << endl;
22.
23. return 0;
24. }
25. string convierteBin(int num) {
26. int digits[30], ultimo = 0, div;
27. string cadena = "";
28. div = num;
29.
30.
31. do {
32. digits[ultimo++] = div % 2;
33. div /= 2;
34. } while (div > 0);
35.
36.
37. if (ultimo > 0) {
38. while (ultimo > 0) {
39. char digit = digits[--ultimo] + '0';
40. cadena.push_back(digit);
41. }
42.
43. return cadena;
44. } else {
pág. 9
45. return "0";
46. }
47. }
ANEXOS
pág. 10
CONCLUSIÓN
pág. 11
Se elaboró este programa con la finalidad de facilitar las asignaciones de trabajo a
los usuarios a los cuales se les presentan este tipo de circunstancias.
El programa fue elaborado en el software de programación C++ y lo que se busca
resolver con este programa es que las personas obtengan una mejor eficiencia al
realizar este tipo de operaciones y de esta manera traten de buscar más
información sobre este tema (algoritmo de Booth), de esta manera los usuarios
salgan de la zona de confort en la que se encuentran y así nutran su conocimiento
matemático con este tipo de operaciones con el sistema de numeración binario.
BIBLIOGRÁFIAS
pág. 12
[Link]
[Link]
[Link]
Algortimo de [Link]
pág. 13
