Tutorial: Algoritmos de decisión: Principio multiplicativo y aditivo
No me gusta este nuevo tutorial. ¡Llévame de vuelta a la versión antigua de este tutorial
Principio aditivo y multiplicativo
Empecemos con un escenario sencillo:
%%Q Querías ver una película de ciencia ficción o de terror. Entras en el cine y encuentras que hay 3 películas de ciencia ficción y 5 de terror entre las que elegir. ¿Cuántas opciones distintas tienes?%%A Como hay 3 películas de ciencia ficción y 5 de terror, tienes $3 + 5 = 8$ enre las que elegir. Este escenario ilustra el siguiente principio general:
Principio aditivo
Al elegir entre $r$ alternativas cuyos resultados son todos distintos, si:
Al elegir entre $r$ alternativas cuyos resultados son todos distintos, si:
-
Alternativa 1 tiene $n_1$ resultados posibles,
Alternativa 2 tiene $n_2$ resultados posibles,
...
Alternativa $r$ tiene $n_r$ resultados posibles,
%%Example
En el escenario anterior, nuestra decisión sobre qué película ver se basa en las siguientes dos alternativas:
En el escenario anterior, nuestra decisión sobre qué película ver se basa en las siguientes dos alternativas:
-
Alternativa 1 Elige una película de ciencia ficción : 3 resultados,
Alternativa 2 Elige una película de terror : 5 resultados.
%%Q ¿Qué tiene esto que ver con los conjuntos?
%%A ¡Buena pregunta! Cuando hablamos de la cantidad de resultados posibles resultantes de tomar decisiones, en realidad estamos hablando de la cantidad de elementos en el conjunto de los resultados posibles; en otras palabras, la cardinalidad del conjunto de los resultados posibles. %%Q En el %%prevsectut hay muchas reglas para calcular la cardinalidad. ¿Es el principio aditivo algún tipo de regla nueva que deberíamos agregar a la lista?
%%A No. Piensa en el principio de la suma en términos de cardinalidades: si el conjunto de resultados de la primera alternativa es $A$ y el conjunto de resultados de la segunda alternativa es $B$, entonces el conjunto combinado de resultados de ambas alternativas es su unión $A \cup B$. Como insistimos en que no hay dos alternativas que tengan resultados en común, en realidad insistimos en que aquí, $A$ y $B$ son disjuntos y, por lo tanto, según la regla para la cardinalidad de una unión en %%prevsectut,
%%A ¡Buena pregunta! Cuando hablamos de la cantidad de resultados posibles resultantes de tomar decisiones, en realidad estamos hablando de la cantidad de elementos en el conjunto de los resultados posibles; en otras palabras, la cardinalidad del conjunto de los resultados posibles. %%Q En el %%prevsectut hay muchas reglas para calcular la cardinalidad. ¿Es el principio aditivo algún tipo de regla nueva que deberíamos agregar a la lista?
%%A No. Piensa en el principio de la suma en términos de cardinalidades: si el conjunto de resultados de la primera alternativa es $A$ y el conjunto de resultados de la segunda alternativa es $B$, entonces el conjunto combinado de resultados de ambas alternativas es su unión $A \cup B$. Como insistimos en que no hay dos alternativas que tengan resultados en común, en realidad insistimos en que aquí, $A$ y $B$ son disjuntos y, por lo tanto, según la regla para la cardinalidad de una unión en %%prevsectut,
$n(A \cup B) = n(A) + n(B) \qquad$ \t Simplemente suma las cardinalidades si los conjuntos son disjuntos.
%%Q ¿Ahora cuántas elecciones distintas tienes?
%%APara cada una de las 3 películas, hay 2 funciones, lo que da 6 posibilidades, y para cada una de aquellas, tenemos 2 auditorios entre las que elegir, lo que da un total de 12 elecciones. Fíjate que esta vez necesitábamos hacer una secuencia de tres deciciones: Primero decide qué película ver, luego qué hora, y finalmente qué tipo de auditorio. Este escenario ilustra el siguiente principio general.
Principio multiplicativo
Si un proceso requiere varios pasos, tal que:
Si un proceso requiere varios pasos, tal que:
- #[Step 1 has $n_1$ possible outcomes,][Paso 1 tiene $n_1$ resultados posibles,]#
#[Step 2 has $n_2$ possible outcomes,][Paso 2 tiene $n_2$ resultados posibles,]#
...
#[Step $r$ has $n_r$ possible outcomes][Paso $r$ tiene $n_r$ resultados posibles,]#
%%Example
Los juegos de plumas de regalo vienen en tres presentaciones: elegante, semielegante y simple. Cada presentación incluye una pluma estilográfica o un bolígrafo, y viene en cuatro colores. Para decidir sobre un juego de bolígrafos para un conocido, toma una secuencia de tres decisiones:
Los juegos de plumas de regalo vienen en tres presentaciones: elegante, semielegante y simple. Cada presentación incluye una pluma estilográfica o un bolígrafo, y viene en cuatro colores. Para decidir sobre un juego de bolígrafos para un conocido, toma una secuencia de tres decisiones:
-
Paso 1: Elige una presentación: 3 resultados posibles
Paso 2: Elige tipo de pluma: 2 resultados posibles
Paso 3: Elige un color: 4 resultados posibles
%%Q ¿Qué tiene esta regla que ver con los conjuntos?
%%A Como dijimos anteriormente, estamos calculando la cardinalidad del conjunto resultante de resultados. %%Q Para el principio aditivo usamos la regla de la cardinalidad de una unión (disjunta). ¿Qué regla necesitamos aquí y por qué?
%%A Si el conjunto de resultados del primer paso es $A$ y el conjunto de resultados del segundo paso es $B$, entonces el conjunto de resultados de ambos pasos en sucesión es una elección de un elemento $a$ de $A$ seguido por elección de un elemento $b$ de $B$; por lo que realmente estamos eligiendo un par de elementos $(a, b)$ con $a \in A$ y $b \in B;$ en otras palabras, un elemento del producto cartesiano $A \times B$, y así, por la regla de cardinalidad de un producto cartesiano en el %%prevsectut,
%%A Como dijimos anteriormente, estamos calculando la cardinalidad del conjunto resultante de resultados. %%Q Para el principio aditivo usamos la regla de la cardinalidad de una unión (disjunta). ¿Qué regla necesitamos aquí y por qué?
%%A Si el conjunto de resultados del primer paso es $A$ y el conjunto de resultados del segundo paso es $B$, entonces el conjunto de resultados de ambos pasos en sucesión es una elección de un elemento $a$ de $A$ seguido por elección de un elemento $b$ de $B$; por lo que realmente estamos eligiendo un par de elementos $(a, b)$ con $a \in A$ y $b \in B;$ en otras palabras, un elemento del producto cartesiano $A \times B$, y así, por la regla de cardinalidad de un producto cartesiano en el %%prevsectut,
$n(A \times B) = n(A)n(B) \qquad$ \t Multiplica las cardinalidades.
Combinar los rincipios aditivo y multiplicativo
Ahora veamos una situación que requiere combinar ambos principios. Lo siguiente es similar al Ejemplo 1 en Matemáticas finitas:
Podemos pensar en cada uno de los ejemplos que hemos considerado arriba como determinar el número de resultados de alguna actividad, como elegir un juego de plumas, elegir un plato principal, completar una hoja de respuestas de opción múltiple u ordenar refrigerios. En cada caso, necesitábamos tomar una secuencia de decisiones para determinar el resultado, y la secuencia de decisiones que anotamos en cada caso se llama un algoritmo de decisión.
Algoritmos de decisión
Algoritmo de decisión
Un algoritmo de decisión es una lista sistemática de decisiones que debemos tomar para determinar completamente el resultado de alguna actividad. Podemos usar un algoritmo de decisión para determinar el número de resultados posibles aplicando los principios aditivo y multiplicativo al algoritmo de decisión.
En resumen:
%%A Lo que significa que un algoritmo de decisión sea válido es que siempre sale un resultado diferente cuando tomamos decisiones diferentes. Por ejemplo, si observas el algoritmo de decisión que escribimos para decidir sobre un juego de plumas de regalo, tomar decisiones diferentes en cualquiera de los tres pasos daría como resultado un regalo diferente.
Un algoritmo de decisión es una lista sistemática de decisiones que debemos tomar para determinar completamente el resultado de alguna actividad. Podemos usar un algoritmo de decisión para determinar el número de resultados posibles aplicando los principios aditivo y multiplicativo al algoritmo de decisión.
En resumen:
Para contar el número de resultados posibles de alguna actividad, crea un algoritmo de decisión válido* para determinar el resultado por enumerar sistemáticamente las decisiones que se tomarán en cada etapa y luego aplicar los principios aditivo y multiplicativo.
%%Q ¡Espera un minuto! ¿Qué es todo esto sobre un algoritmo de decisión "válido"? %%A Lo que significa que un algoritmo de decisión sea válido es que siempre sale un resultado diferente cuando tomamos decisiones diferentes. Por ejemplo, si observas el algoritmo de decisión que escribimos para decidir sobre un juego de plumas de regalo, tomar decisiones diferentes en cualquiera de los tres pasos daría como resultado un regalo diferente.
%%Examples
1. Eres el entrenador del equipo de explotabol para la Universidad Estatal Enorme. Tu equipo debe tener cuatro jugadores: un delantero, dos blasters zadores y un bloqueador. Tienes cinco posibles jugadores a elegir para formar el equipo. Los siguientes son dos algoritmos de decisión; uno es válido y uno no es válido. En el primer algoritmo, eliges jugadores para las cinco posiciones uno por uno para formar el equipo. En el segundo, en cambio, llenas las tres posiciones una por una:
1. Eres el entrenador del equipo de explotabol para la Universidad Estatal Enorme. Tu equipo debe tener cuatro jugadores: un delantero, dos blasters zadores y un bloqueador. Tienes cinco posibles jugadores a elegir para formar el equipo. Los siguientes son dos algoritmos de decisión; uno es válido y uno no es válido. En el primer algoritmo, eliges jugadores para las cinco posiciones uno por uno para formar el equipo. En el segundo, en cambio, llenas las tres posiciones una por una:
\t
Paso 2: Elige el primero blaster: 4 opciones
Paso 3: Elige el segundo blaster: 3 opciones
Paso 4: Elige el bloqueador 2 opciones
Total: 5×4×3×2 = 120 equipos posibles
\t
Paso 2: Elige el bloqueador 4 opciones
Paso 3: Elige dos de los tres restantes para que sean los blasters: 3 opciones
(Elije cuál de los tres dejar fuera.)
Total: 5×4×3 = 60 equipos posibles
Aunque cada uno de estos algoritmos conduce a un equipo de blastball, el Algoritmo 1 no es válido para contar la cantidad de equipos posibles que puedes formar. ¿Por qué? Supongamos que Joaquim y Matilda son dos jugadores. Entonces, si eliges a Joaquim en el Paso 2 y a Matilda en el Paso 3, terminas con los mismos dos blasters que si eligieras a Matilda en el Paso 2 y a Joaquim en el Paso 3. Por lo tanto, intercambiar tus decisiones en los Pasos 2 y 3 da como resultado el mismo resultado (el mismo equipo), por lo que el Algoritmo 1 no es válido. Por otro lado, si cambias algunas de sus decisiones en el Algoritmo 2, el equipo resultante será diferente (piensa por qué). Por lo tanto, el Algoritmo 2 es válido.
Algoritmo de decisión 1
Paso 1: Elige el delantero: 5 opciones Paso 2: Elige el primero blaster: 4 opciones
Paso 3: Elige el segundo blaster: 3 opciones
Paso 4: Elige el bloqueador 2 opciones
Total: 5×4×3×2 = 120 equipos posibles
Algoritmo de decisión 2
Paso 1: Elige el delantero: 5 opciones Paso 2: Elige el bloqueador 4 opciones
Paso 3: Elige dos de los tres restantes para que sean los blasters: 3 opciones
(Elije cuál de los tres dejar fuera.)
Total: 5×4×3 = 60 equipos posibles
2. Tienes cuatro cartas repartidas frente a ti; cada uno con un solo dígito impreso: dos de ellos tienen un "1", uno tiene un "2" y uno tiene un "3". Quieres saber cuántas secuencias diferentes de 4 dígitos puedes hacer colocando las cartas en diferentes órdenes.Los siguientes son tres algoritmos de decisión; dos son válidos y uno no es válido. En el primer algoritmo, elegimos las cuatro cartas una por una para formar la secuencia. En el segundo y tercero, en cambio, pensamos en colocar las cuatro cartas en cuatro espacios vacíos para obtener la secuencia:
\t
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4-digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 1][Algoritmo de decisión 1]#
#[Step 1: Pick the first card: 4 choices][Paso 1: Escoje la primera carta: 4 opciones]#
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 2][Algoritmo de decisión 2]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para el "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 3][Algoritmo de decisión 3]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para la "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4-digit sequences][secuencias de 4 dígitos]#
#[Although each of these algorithms leads to a 4-digit sequence, Algorithm 1 is not valid for counting the number of possible 4-digit sequences. Why? Because, for instance, we can use Algorithm 1 get the same sequence "3121" by making different decisions as follows:][Aunque cada uno de estos algoritmos conduce a una secuencia de 4 dígitos, el Algoritmo 1 no es válido para contar el número de posibles secuencias de 4 dígitos. ¿Por qué? Porque, por ejemplo, podemos usar el Algoritmo 1 para obtener la misma secuencia "3121" al hacer diferentes decisiones como sigue:]#
\t
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
\t #[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
Ahora prueba algunos de los ejercicios en a Sección 6.3 del libro Matemáticas finitas o la Sección 7.3 en el libro Matemáticas finitas y cálculo aplicado.
Última actualización: julio 2023
Derechos de autor © 2020 Stefan Waner y Steven R. Costenoble
Derechos de autor © 2020 Stefan Waner y Steven R. Costenoble