• Author / Uploaded
• Vanessa Gomez

Citation preview

Unidad 3 1 //Escenario Escenario25 Lectura Fundamental

Árbolesde Etapas deun decisión plan de comunicación estratégica Contenido 1 2 3 4

Definición Componentes y estructura de los árboles de decisión Ejemplos de problemas resueltos mediante árboles de decisión Ejercicios propuestos

Palabras clave: Árbol, nodo, rama, hoja, anidamiento.

1. Definición Un árbol de decisión es un instrumento que permite resolver problemas a partir de la evaluación de expresiones lógicas. En este tipo de estructuras se evalúa una condición, que puede ser FALSA o VERDADERA, y en función del resultado obtenido se ejecuta una de las posibles opciones (Liang, 2015). Es importante notar que un mismo problema puede ser resuelto por medio del uso de diferentes árboles.

¿Sabía qué...? Existen árboles de decisión determinísticos y probabilísticos, y que la diferencia radica en que los primeros no involucran componentes de probabilidad de eventos, mientras que los segundos sí lo hacen (Castillo, 2008). Es importante saber notar esa diferencia porque si bien en otros módulos futuros se estudiará el árbol de decisión probabilístico, aquí solamente interesa el determinístico. Al buscar en fuentes digitales y escritas la ampliación de este tema, la mayoría de elementos teóricos y ejemplos hallados estará centrada en aquellos basados en probabilidad. Si se estudia ese material en este módulo, el estudiante podría confundirse. Para evitar esos inconvenientes se recomienda acudir a libros de fundamentos de programación de computadores.

2. Componentes y estructura de los árboles de decisión La figura 1 presenta los tres elementos básicos de cualquier árbol de decisión. Un árbol no puede existir si no tiene al menos un nodo, dos ramas y dos hojas; a partir de allí, se puede comenzar a diagramar árboles con distintas cantidades de estos elementos.

POLITÉCNICO GRANCOLOMBIANO

2

Nodo

Condición o expresión lógica Verdadero

Falso Hoja 2

Hoja 1

Ramas Hojas

Figura 1. Estructura elemental de un árbol de decisión y sus componentes Fuente: Elaboración propia

2.1. Nodos Contienen cualquier tipo de expresión lógica, es decir, una expresión que retorne un valor de FALSO o VERDADERO. Pueden representar proposiciones, predicados, datos de tipo lógico y expresiones matemáticas con operadores relacionales y/o lógicos. Se encierran dentro de un ovalo. Un árbol siempre empieza con un único nodo y nunca termina en un nodo.

Cómo mejorar... Repasando la construcción de expresiones matemáticas, especialmente de aquellas que implican un resultado de tipo lógico.

2.2. Ramas Se desprenden de los nodos y siempre lo hacen en pares; en otras palabras, de un nodo nunca se desprenderán menos de dos o más de dos ramas. Una rama estará etiquetada VERDADERO y en su terminación tendrá asociado un nodo o una hoja que sea la consecuencia lógica del resultado VERDADERO de la expresión dada en el nodo de origen; la otra rama estará etiquetada FALSO y en su terminación tendrá asociado un nodo o una hoja que sea la consecuencia lógica del resultado FALSO de la expresión dada en el nodo de origen. Toda rama se conecta a otro nodo o una hoja. A cada nodo y a cada hoja puede llegar únicamente una rama. Un árbol nunca termina en una rama.

POLITÉCNICO GRANCOLOMBIANO

3

2.3. Hojas Son las terminaciones del árbol y cada una contiene uno de los posibles valores que podría tomar la salida del problema. Un árbol siempre termina en hojas.

2.4. Posibles configuraciones de un árbol de decisión A partir de nodos, ramas y hojas se puede construir un número infinito de posibles estructuras. El árbol propuesto para solucionar un problema dependerá del problema mismo y de la lógica que siga cada persona. Como ya se dijo, la estructura básica es aquella que contiene un nodo, dos ramas y dos hojas. La figura 2 contiene cuatro árboles del conjunto infinito de árboles que podrían formarse.

Condición 1 V

Condición 1 V

F

Hoja 1

Hoja 2

F

Hoja 1

Condición 2

(A)

V

Hoja 2

Condición 1 V

Hoja 1

F

Hoja 3

(B)

F

V

Hoja 2

Hoja 3

V

Condición 3 F

V

Condición 4 V

Hoja 2

Condición 3

F

Condición 2

Hoja 1

F

Condición 2 V

Condición 1 V

Condición 5 F

V

Hoja 3 V

Hoja 8

(C)

Condición 6 F V

Hoja 5 Hoja 6

Condición 7

F

Hoja 4

F

F

Hoja 7

F

(D)

Hoja 9

Figura 2. Cuatro estructuras diferentes que podría tomar un árbol de decisión Fuente: Elaboración propia

Nótese que en todos los árboles, exceptuando el diagrama A, hay al menos una condición que se desprende de la rama que viene de una condición alojada en un nivel superior. Eso indica que la condición del nivel inferior depende directamente de la condición alojada en el nivel superior; en otras palabras, quiere decir que una condición está anidada dentro de otra. Por ejemplo:

POLITÉCNICO GRANCOLOMBIANO

4

•

En el diagrama B, la condición 2 se desprende de una de las ramas de la condición 1; por lo tanto, se dice que la condición 2 está anidada dentro de la condición 1.

•

En el diagrama C, la condición 2 y la condición 3 se desprenden de las ramas de la condición 1; por lo tanto, la condición 2 y la condición 3 están anidadas dentro de la condición 1. Sin embargo, son independientes entre sí.

•

En el diagrama D existen hasta tres niveles de anidamiento: la condición 7 está anidada dentro de la condición 5, que a su vez se anida dentro la condición 3, que a su vez se anida dentro de la condición 1. La condición 2 y la condición 4 son independientes de la condición 3, condición 5, condición 6 y condición 7 porque se desprenden de distintas ramas de la condición 1. De la misma forma, la condición 5 y la condición 7 son independientes de la condición 6 porque se desprenden de distintas ramas de la condición 3.

3. Ejemplos de problemas resueltos mediante árboles de decisión Previo a la presentación de algunos ejemplos, es importante aclarar que antes de construir el árbol se debe realizar el proceso de modelado y especificación del problema. Las entradas deberán hacer parte de las expresiones lógicas desarrolladas en los nodos, mientras que los posibles valores de las salidas estarán reflejados en las hojas. Aquí no se muestra ese proceso porque tomaría demasiado espacio y ya se estudió suficientemente en el escenario anterior. Se presentarán los ejemplos sobre el supuesto que el estudiante modelará para entender completamente la solución presentada.

3.1. Problema del número par/impar Enunciado. Diagrame un árbol de decisión que dado un número natural, n, permita determinar si el número es par o impar. Solución.

n MOD 2 = 0 V

F

PAR

IMPAR

Figura 3. Árbol de decisión para resolver el problema del número par/impar Fuente: Elaboración propia

POLITÉCNICO GRANCOLOMBIANO

5

Interpretación. Un número par es aquel que es divisible entre dos. Esa condición puede representarse por medio de una expresión matemática que denote que el residuo entre el número n y dos es cero. En caso de que la expresión tome el valor de VERDADERO, significará que el número es par (la hoja toma ese valor); en caso contrario, significará que el número es impar (la hoja toma ese valor). Caso de uso. Suponga el caso en que n es igual a veintiocho. Como el residuo entre veintiocho y dos es cero, se toma la rama marcada como VERDADERA y se llega a la hoja que indica que el número es par.

n MOD 2 = 0 V

F

PAR

IMPAR

Figura 4. Árbol de decisión para resolver el problema del número par/impar Fuente: Elaboración propia

Otra alternativa. El mismo problema también podría haber sido resuelto como lo muestra la figura 5. Se deja como ejercicio al estudiante la interpretación de este árbol y la diagramación de otros árboles que resuelvan el mismo problema.

n MOD 2 = 1 V

F

IMPAR

PAR

Figura 5. Otra alternativa para resolver el problema del número par/impar Fuente: Elaboración propia

POLITÉCNICO GRANCOLOMBIANO

6

3.2. Problema del tipo de triángulo Enunciado. Diagrame un árbol de decisión que, dados las longitudes de los lados de un triángulo, a, b, y c, determine qué tipo de triángulo forman: equilátero, isósceles o escaleno. Solución.

a=b

V

F

b=c

a=c V Equilátero

F Isósceles

V

F

Isósceles

a=c V Isóceles

F Escaleno

Figura 6. Árbol de decisión para resolver el problema del tipo de triángulo Fuente: Elaboración propia

Interpretación. Un triángulo equilátero es aquel que tiene todos sus lados de igual longitud; un triángulo isósceles es aquel que tiene solamente dos lados de la misma longitud y un triángulo escaleno es aquel en el que todos los lados tienen longitudes diferentes entre sí. Se comienza por evaluar si los lados a y b son iguales; si el resultado es VERDADERO, no se puede concluir todavía nada y se debe evaluar si el lado a y el lado c son iguales (nótese que esta condición está anidada en la anterior). En caso de que esta última condición sea VERDADERA, se puede concluir que el triángulo es equilátero porque estamos seguros de que todos los lados son iguales; en caso contrario, se concluirá que el triángulo es isósceles porque si bien a y b son iguales, a y c son diferentes. Hasta aquí se ha analizado el lado izquierdo del árbol, es decir, cuando el primer nodo toma el valor de VERDADERO. Volvamos un poco para estudiar el lado derecho del árbol. En caso de que la condición inicial (la que está más arriba) sea FALSA, se puede descartar que el triángulo sea equilátero; pero aún se debe averiguar si es isósceles o escaleno. Por ello, se anida una condición para determinar si los lados b y c son iguales. Si la condición es VERDADERA, puede afirmarse que el triángulo es isósceles porque a

POLITÉCNICO GRANCOLOMBIANO

7

y b no son iguales, pero b y c sí lo son; por otro lado, si la condición es FALSA, no puede formularse una conclusión y debe anidarse una condición que determine si a y c son iguales. Si la condición es VERDADERA, puede afirmarse que el triángulo es isósceles porque, aunque las parejas a-b y b-c sean diferentes, los lados b y c sí son iguales; finalmente, si la condición es FALSA, se concluirá que el triángulo es escaleno porque todos los lados son diferentes entre sí. Caso de uso. Suponga el caso en que los lados del triángulo son: a = 14, b= 16 y c= 14. Primero se evalúa el nodo que interroga acerca de la igualdad entre a y b; en este caso la expresión tomaría el valor de FALSO porque 14 no es igual a 16 y se toma el camino de la derecha. El diagrama A de la figura 7 muestra la situación. La siguiente condición por evaluar será la que compara la igualdad entre b y c. Como 16 y 14 son diferentes, la expresión es FALSA y se toma nuevamente el camino de la derecha. La situación se representa en el diagrama B de la figura 7. Finalmente, se evalúa la condición de igualdad entre a y c. 14 es igual a 14, por lo tanto, la condición es VERDADERA y se llega a la conclusión de que el triángulo conformado por lados de longitudes 14, 16 y 14 es isósceles. Esta última circunstancia está representada por el diagrama C de la figura 7.

a=b

V

F

Equilátero

F Isósceles

F

b=c

a=c

V

F

Isósceles

a=b

V

b=c

a=c V

a=14 b=16 c=14

V

F

Equilátero

a=c V

Isósceles

V

F

Isósceles

a=c

F

Isósceles

V

Escaleno

Isósceles

a=b

V

Equilátero

Escaleno

F

b=c

a=c V

F

F Isósceles

V

F

Isósceles

a=c V Isósceles

F Escaleno

Figura 7. Caso de uso sobre un árbol de decisión para resolver el problema del tipo de triángulo Fuente: Elaboración propia

POLITÉCNICO GRANCOLOMBIANO

8

Otra alternativa. El mismo problema también podría haber sido resuelto como lo muestra la figura 8. Acá, se implementa una novedad: el uso de operadores lógicos. Usar operadores lógicos simplifica la estructura del árbol y puede facilitar la resolución de un problema, pero demanda por parte del estudiante una mayor habilidad para construir expresiones, tema estudiado en el escenario 3. Se deja como ejercicio al estudiante la interpretación de este árbol y la diagramación de otros árboles que resuelvan el mismo problema.

a=b a=c Equilátero

Escaleno

Isósceles

Figura 8. Otra alternativa para resolver el problema del tipo de triángulo Fuente: Elaboración propia

4. Ejercicios propuestos Este tópico, como todos los que se han explorado en el módulo, requiere que el estudiante practique y realice ejercicios para asegurar un completo entendimiento y dominio. Se proponen los siguientes ejercicios para completar el proceso académico del escenario. Para cada uno de los siguientes problemas diagrame un árbol de decisión y pruebe la solución con distintos casos de uso con el fin de asegurar que esta sea correcta. Problema 1. Dados tres números enteros, a, b y c, determinar el valor del mayor de los números. Problema 2. Dadas las longitudes de tres segmentos de recta, a, b y c, determinar si es posible o no formar un triángulo con dichos segmentos de recta. Problema 3. Determinar si un número natural, n, es divisible entre cuatro. Nota: un número es divisible entre cuatro si las dos últimas cifras son ceros o forman un número que sea múltiplo de 4.

POLITÉCNICO GRANCOLOMBIANO

9

Problema 4. El supermercado Doña Mechas sigue la tabla 1 para fijar su política de descuentos. Por ejemplo, si un cliente hace compras por un valor de $450,000, no tiene tarjeta súpercliente y paga en efectivo, el supermercado le hace un descuento de 20 % sobre los $450,000, es decir, pagará finalmente $360,000. Diagrame un árbol de decisión que -sabiendo cuál es el valor de la compra, si el cliente posee tarjeta súpercliente y si cancela en efectivo- permita determinar cuál es el monto que finalmente el cliente pagará. Tabla 1. Descuentos ofrecidos por el supermercado Doña Mechas

Tarjeta súper-cliente Compras mayors o iguales a $300.000 Sin tarjeta

Tarjeta súper-cliente Compras menores a $300.000 Sin tarjeta

Efectivo

25%

Otro medio

17%

Efectivo

20%

Otro medio

15%

Efectivo

12%

Otro medio

3%

Efectivo

7%

Otro medio

0%

Fuente: Elaboración propia

Cómo mejorar... Completando los ejercicios proponiendo múltiples árboles de decisión y probándolos con distintos casos de uso para asegurar que son correctos.

POLITÉCNICO GRANCOLOMBIANO

10

Referencias Castillo, M. (2008). Toma de decisiones en las empresas: entre el arte y la técnica. Bogotá: Uniandes. Liang, D. (2015). Introduction to Java programming. New Jersey: Pearson.

POLITÉCNICO GRANCOLOMBIANO

11

POLITÉCNICO GRANCOLOMBIANO

12

INFORMACIÓN TÉCNICA

Módulo: Pensamiento Algorítmico Unidad 3: Árboles, Diagramas y Diseño De Algoritmos Escenario 5: Árboles de decisión Autor: Javier Fernando Niño Velásquez Asesor Pedagógico: Jeiner Leandro Velandia Diseñador Gráfico: Felipe Puentes Asistente: Leidy Alejandra Morales Eslava Este material pertenece al Politécnico Grancolombiano. Por ende, es de uso exclusivo de las Instituciones adscritas a la Red Ilumno. Prohibida su reproducción total o parcial.

POLITÉCNICO POLITÉCNICO GRANCOLOMBIANO GRANCOLOMBIANO

13