Download Matemáticas Básicas para Computación

Matemáticas Básicas para
Computación
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Sesión No. 11
Nombre: Árboles
Objetivo:
Al término de la sesión el participante conocerá los tipos de grafos
específicamente los árboles binarios y sus características.
Contextualización
Los árboles son un tipo de grafo que sirve como herramienta útil en todos los
problemas donde la información está jerarquizada y para la toma de decisiones.
Esta estructura es de bastante uso, incluso fuera del campo de la informática;
como ejemplo tenemos los árboles genealógicos, los árboles gramaticales, los
organigramas, entre otros.
En el campo de la informática se aplica la estructura de árboles en una amplia
variedad de problemas, por lo que lo convierte en una herramienta fundamental.
1
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Introducción al Tema
Los árboles conforman las estructuras no lineales y dinámicas de datos más
importantes en la rama de la informática. Se les llama Dinámicas ya que estas
estructuras pueden cambiar en el momento en que se ejecuta el programa. Y
son no lineales debido a que a cada elemento pueden seguirle varios elementos.
Los árboles son una estructura de jerarquización sobre una colección de objetos
o elementos a los cuales conocemos como nodos, uno de estos nodos es
conocido como raíz y de él parte toda la descendencia.
2
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Explicación
Árboles
Los árboles son una de las subclases gráficas que más se utilizan. En la
informática son de mucho uso, en especial para organizar y hacer relación de
datos en una base de datos.
Un árbol es un grafo simple en el cual existe un único camino entre cada par de
vértices.
Componentes
Un árbol está dividido básicamente en tres subconjuntos separados:
Raíz: Nodo en el cual se constituye la única entrada a la jerarquía (no tiene
padre).
Ramas o Arcos: Conexión que existe entre dos nodos del árbol, dicha rama
representa la relación de jerarquía.
Hojas: Es un nodo que carece de hijos.
3
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Clasificación
Características del árbol, en base a su tamaño:
Orden: es el número de hijos que puede tener cada elemento del árbol.
Dependiendo el número de hijos es el número de la orden, ej. 3 hijo = orden tres.
Grado: representa el número de hijos que tiene el elemento con más hijos
dentro del árbol.
Nivel: se define como la distancia de cada elemento del árbol a la raíz, medida
en nodos.
Altura: se define como el nivel del nodo de mayor nivel.
Altura= 3 (el nivel más grande).
Raíz= que no tiene padre (inicial).
Padre = que tiene hijo(s).
Hoja = no tiene hijo(s), tiene padre.
Árbol ordenado: tiene nivel, los
hijos de izquierda a derecha.
n-árbol: cuando cada padre tiene a
lo más n hijos.
Árbol binario: cada padre tiene a lo
más 2 hijos.
Propiedades
Sea G= (V, A) un grafo no dirigido. G se denomina Árbol, si es conexo con n
nodos y n-1 aristas y no contiene ciclos.
•
Existe un único paseo entre dos vértices cualesquiera de un árbol.
•
El número de vértices es mayor en uno al número de aristas de un árbol.
•
Un árbol con dos o más vértices tiene al menos dos hojas.
4
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Conclusión
Al igual que los grafos, los árboles son de mucha utilidad en el ámbito de la
informática, el uso es básicamente el mismo, pero los árboles se usan para
información de jerarquía.
También este método de árbol se usa bastante en computación para los
lenguajes de programación y lógica por su utilidad en los diagramas de flujo.
Me atrevo a decir que esta herramienta es la más usada en las diferentes
ciencias y no sólo las científicas o experimentales.
5
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Para aprender más
•
Matemáticas para computadora. Recorrido de un árbol.
http://brd.unid.edu.mx/recorrido-de-un-arbol/
•
García, K. (2011) Árboles y grafos. Video de youtube.
http://brd.unid.edu.mx/arboles-y-grafos/
•
Sucunuta, M.E. (2012) Árboles. Video de youtube.
http://brd.unid.edu.mx/arboles/
•
Castro, J. (2012) Recorrido de árboles. Video de youtube.
http://brd.unid.edu.mx/recorrido-de-arboles/
6
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Actividad de Aprendizaje
Instrucciones:
Con base en la información revisada anterior, ahora investigarás 3 aplicaciones
reales de los árboles binarios y aplicarás los conceptos relacionados para poder:
1) Definir el problema a través de la contextualización y donde justifiques el
por qué el uso de los árboles binarios es adecuado para este tipo de
problemas.
2) Representarlo como un problema de árboles.
Sube a la plataforma tu trabajo en el lugar indicado.
7
MATEMÁTICAS BÁSICAS PARA COMPUTACIÓN
Bibliografía
•
Gallardo, P. (2004 - 2005). Árboles generales. Obtenido de
Universidad
de
Málaga:
http://www.lcc.uma.es/~pepeg/mates/tema9.pdf
•
Matemáticas para computadora. (2013). Obtenido de Árboles:
http://matematicasparacomputadora.weebly.com/64-arboles.html
•
Universidad de Valladolid. (2003). Árboles. Obtenido de Departamento
de Informática: http://www.infor.uva.es/~cvaca/asigs/transp3.pdf
8