Inicio Discusiones Matemáticas discretas Árboles como estructuras de datos

Discusiones

Temas
Funciones y conceptos del álgebra Cálculo Matemáticas discretas Álgebra de un paso Alternativa justa Árboles como estructuras de datos Auto-similaridad Búsqueda en Internet y operaciones de conjuntos Coeficientes de correlación Conjuntos y elementos Criptografí­a y cifrados De gráficos a máquinas de funciones y viceversa De la Geometría a la Probabilidad De la Geometría a la Probabilidad Deducción de cónicas Diagramas de Venn Diagramas de Venn. Principiante División de enteros El conjunto de Mandelbrot El triángulo de Pascal Enteros Eventos y operaciones de conjuntos Fractales de figuras planas funciones como procesos o reglas: "Las máquinas de funciones" Funciones de dos variables Funciones lineales Funciones múltiples Gráficos imposibles Gráficos imposibles Infinito e iteraciones Introducción a conjuntos y elementos Las funciones como procesos o reglas Las funciones y la prueba de la recta vertical Multiplicación de enteros Prisioneros y fugitivos -Los conjuntos de Julia Probabilidad condicional Probabilidad de eventos simultáneos Probabilidad teórica versus probabilidad experimental probabilidad vs. estadística Probabilidad vs. estadísticas Probabilidad y geometría Probabilidad y Geometría (Elemental) Probabilidad y resultado Probabilidad y Resultado Propiedad distributiva Propiedades de identidad Propiedades de los fractales Propiedades de los fractales Recurrencias Recursión Relojes y aritmética modular Substitución Suma y resta de enteros Tablas y combinatorias Valor posicional ¿Qué son Múltiplos? ¿Qué son residuos? Geometría y medición Modelado Números y operaciones Probabilidad Estadística Trigonometría Otra

Árboles como estructuras de datos

Las preguntas sobre juegos con más de dos dados, conducen a la discusión de los árboles como otro tipo de estructura de datos.

Maestro: Aquí tenemos otro juego  para jugar y estudiar. Los jugadores lanzan 3 dados de cuatro lados. El Jugador 1 gana si la suma de los dados es 3, 4, 5, 6 o 12; el Jugador 2 gana con 7, 8, 9, 10 u 11. ¿Es éste un juego justo?

Estudiante: Ahora se que hay muchas maneras de obtener una misma suma. Antes usamos tablas para contar las posibilidades con dos dados. No podemos usar más la tabla, porque solamente tiene dos…¿cómo se llaman?

Maestro: Dimensiones. Podemos hacer una tabla de tres dimensiones o más, pero será difícil de usar manualmente.  A propósito, los computadores pueden manejar tablas de cientos de dimensiones. ¿Qué otra cosa podemos hacer? Permítanme escribir el primer cuarto de la lista de todas las combinaciones, la parte en que se muestra el resultado del primer dado. 
1. Será una tarea aburridora…

Estudiante: ¿Existe la manera de eliminar todas las repeticiones?  Quiero decir, ¿podemos escribir un “1” bien grande, en vez de dieciséis chiquitos?

Maestro: ¿Por qué no? Si hacemos eso tendremos una estructura llamada un árbol.  ¿Puede adivinar  por qué,  aun antes de hacer la figura? Aquí está la figura que muestra la forma en que se construye esta parte del árbol para nuestro problema.  Habrá otras 3 partes para el resto de los números posibles en el primer dado.  Puede hacerlos usted mismo.

 







Maestro: ¿Puede ver por qué se llama un árbol?

Estudiante: Porque parece un árbol acostado de lado. Podemos agregarle algunas “hojas” y escribir algo en ellas. Yo escribiré la suma de los números de los dados:

Maestro: ¿Puede ver cómo el árbol nos puede ayudar a contar resultados?

Estudiante: Bueno, es útil para contar el número total de resultados.  Hay cuatro “troncos” (para los números posibles en el primer dado), y cada uno tiene cuatro “ramas” (para los números posibles del segundo dado) y cada rama tiene cuatro “ramitas” (para los números posibles en el tercer dado) Un resultado se forma cuando vamos de un tronco a una rama y a una ramita. Hay tantos resultados, como ramitas que existan: 4*4*4=64. ¡Vaya! ¡Parece como un viejo rompecabezas!

Maestro: Ahora miren todas las “hojas” y definan si el juego es justo. ¿Cuál es la probabilidad de ganar de cada jugador?

Estudiante: El Jugador 1 tiene solamente una probabilidad de ganar de 21/64, en tanto que el Jugador 2 tiene una probabilidad de ganar de  43/64. El juego no es justo.

Maestro: ¿Cuántos resultados posibles hay si usted tiene 3 monedas? (2*2*2=8) ¿Si  tiene una moneda y dos dados de seis lados? (2*6*6=72) ¿Si fueran cuatro monedas? (2*2*2*2=16) ¿Cinco dados de seis lados? (6*6*6*6*6) A propósito, si no quiero escribir tantas veces los números,  se puede escribir lo mismo, en forma más corta:

6*6*6*6*6=65

Se lee “seis a la quinta”.  Los amigos de los computadores lo  escriben como 6^5, porque es más rápido de esta forma que cambiar al superíndice.

Estudiante: ¡Yo no quiero tener que dibujar estos árboles tan grandes!

Maestro: El árbol para el problema de las cuatro monedas no debería ser tan complicado. ¿Lo puede dibujar? Observe que cada vez que al árbol se le agregan “ramas”, hay tan solo dos ramas (por las caras y los sellos de la siguiente moneda). Los árboles de este tipo se llaman árboles binarios. Son muy comunes en las ciencias de la computación, y aún en la naturaleza.

Mujer matemática en un árbol binario, fotografía de Dmitri Droujkov.

Maestro: He aquí una adivinanza para usted. Si tenemos un árbol binario completo (no se le ha cortado ninguna rama), que cuenta con 8 ramas pequeñas, ¿cuántos “niveles de dos ramas” tiene? En otras palabras, si estuviéramos jugando con monedas, ¿cuántas monedas necesitaría para producir 8 resultados?

Estudiante: Veamos.  La última bifurcación  ocurre cuando 4 ramas se convierten en 8:

La bifurcación anterior a ésta ocurre cuando 2 ramas se convierten en 4:

y la primera es cuando una sola rama se convierte en 2:

Así que tenemos tres niveles de bifurcación.

Maestro: Cuando usted encuentra el número de bifurcaciones a partir del número de las últimas ramas, a esto se le llama un logaritmo de cómputo y al número de bifurcaciones se le llama  un logaritmo.   Existe un símbolo especial para esto:


Estudiante: En el ejemplo original con 3 dados de cuatro lados, existían 64 “ramas más pequeñas”, pero cada bifurcación se estaba abriendo en cuatro.  Esto significa:

log4 64=3

Maestro: Exactamente,  y 4^3=64.  A propósito, ¿dónde más ha visto árboles como estos?
Estudiante: ¡En los torneos de básquet de la NCAA!

Maestro: Ahora usted puede traducir fácilmente la siguiente pregunta a términos matemáticos: “Si hay 64 equipos en un torneo, ¿cuántas rondas deben jugar para definir un ganador?   

Estudiante 1: ¡La pregunta es mucho más corta en lenguaje matemático!

¿log2 64=?

Estudiante 2: La respuesta es 6.