Tecnicas de conteo

Vista previa del material en texto

TÉCNICAS DE CONTEO
PRINCIPIOS FUNDAMENTALES DEL CONTEO
En los métodos de conteo hay dos principios fundamentales:
Principio Multiplicativo
Principio Aditivo
Basado en estos principios se puede establecer el número de permutaciones o combinaciones que se pueden obtener entre los elementos de un conjunto de datos
PRINCIPIO MULTIPLICATIVO 
Si se desea realizar una actividad que consta de r pasos, en donde el primer paso de la actividad a realizar  puede ser llevado a cabo de n1 maneras, el segundo paso de n2 maneras y el r-ésimo paso de nr maneras, entonces esta actividad puede ser llevada a efecto de: 
 n1 x n2 x ..........x  nr  maneras 
El principio multiplicativo implica que cada uno de los pasos de la actividad deben ser llevados a efecto, uno tras otro. 
PRINCIPIO ADITIVO  
 Si se desea llevar a efecto una actividad, la cuál tiene formas alternativas para ser realizada, donde la primera de esas alternativas puede ser realizada de m maneras, la segunda alternativa puede realizarse de n maneras y la última de las alternativas puede ser realizada de w maneras, entonces esa actividad puede ser llevada  a cabo de 
 m + n + .........+ w  maneras 
EJEMPLO N.1:
Una persona desea comprar una lavadora de ropa, para lo cuál ha pensado que puede seleccionar de entre las marcas Whirpool, Easy y General Electric, cuando acude a hacer la compra se encuentra que la lavadora de la marca W se presenta en dos tipos de carga ( 8 u 11 kilogramos), en cuatro colores diferentes y puede ser automática o semiautomática, mientras que la lavadora de la marca E, se presenta en tres tipos de carga (8, 11 o 15 kilogramos), en dos colores diferentes y puede ser automática o semiautomática y la lavadora de la marca GE, se presenta en solo un tipo de carga, que es de 11 kilogramos, dos colores diferentes y solo hay semiautomática. ¿Cuántas maneras tiene esta persona de comprar una lavadora?
Solución:
M = Número de maneras de seleccionar una lavadora Whirpool 
N = Número de maneras de seleccionar una lavadora de la marca Easy
W = Número de maneras de seleccionar una lavadora de la marca General Electric
M = 2 x 4 x 2 = 16 maneras
N = 3 x 2 x 2 = 12 maneras
W = 1 x 2 x 1 = 2 maneras
 
M + N + W = 16 + 12 + 2 = 30 maneras de seleccionar una lavadora
EJEMPLO N.2:
Rafael Luna desea ir a las Vegas o a Disneylandia  en las próximas vacaciones de verano, para ir a las Vegas él tiene tres medios de transporte para ir de Chihuahua al Paso Texas y dos medios de transporte para ir del Paso a las Vegas, mientras que para ir del paso a Disneylandia él tiene cuatro diferentes medios de transporte, a) ¿Cuántas maneras diferentes tiene Rafael de ir a las Vegas o a Disneylandia?, b) ¿Cuántas maneras tiene Rafael de ir a las Vegas o a Disneylandia en un viaje redondo, si no se regresa en el mismo medio de transporte en que se fue?.
Solución:
a) V = maneras de ir a las Vegas
    D = maneras de ir a Disneylandia
 V = 3 x 2 = 6 maneras
 D = 3 x 4 = 12 maneras
V + D = 6 + 12 = 18 maneras de ir a las Vegas o a Disneylandia
b) V = maneras de ir y regresar a las Vegas
    D = maneras de ir y regresar a Disneylandia
 V = 3 x 2 x 1 x 2 = 12 maneras
 D = 3 x 4 x 3 x 2 = 72 maneras 
V + D = 12 + 72 = 84 maneras de ir a las Vegas o a Disneylandia en un viaje redondo
¿Cómo podemos distinguir cuando hacer uso del principio multiplicativo y cuando del aditivo?
Es muy simple, cuando se trata de una sola actividad, la cual requiere para ser llevada a efecto de una serie de pasos, entonces haremos uso del principio multiplicativo y si la actividad a desarrollar o a ser efectuada tiene alternativas para ser llevada a cabo, haremos uso del principio aditivo.
Una persona desea construir su casa, para lo cuál considera que puede construir los cimientos de su casa de cualquiera de dos maneras (concreto o block de cemento), mientras que las paredes las puede hacer de adobe, adobón o ladrillo, el techo puede ser de concreto o lámina galvanizada y por último los acabados los puede realizar de una sola manera ¿cuántas maneras tiene esta persona de construir su casa?
¿Cuántas placas para automóvil pueden ser diseñadas si deben constar de tres letras seguidas de cuatro números, si las letras deben ser tomadas del abecedario y los números de entre los dígitos del 0 al 9?, a. Si es posible repetir letras y números, 
b. No es posible repetir letras y números, c. Cuántas de las placas diseñadas en el inciso b empiezan por la letra D y empiezan por el cero, d. Cuantas de las placas diseñadas en el inciso b empiezan por la letra D seguida de la G.
TÉCNICAS DE CONTEO
Son muy importantes en las matemáticas, en las ciencias de la computación particularmente en el análisis de algoritmos.
Son aquellas que son usadas para enumerar eventos difíciles de cuantificar. 
Las bases para comprender el uso de las técnicas de conteo son el principio multiplicativo y el aditivo.
Existen:
Técnicas de Multiplicación
Técnicas de Permutación
Técnicas de Combinación
TÉCNICA DE LA MULTIPLICACIÓN 
Es aplicada para encontrar el número posible de eventos para dos o más grupos.
Si hay m formas de hacer una cosa y hay n formas de hacer otra cosa, hay m x n formas da hacer ambas cosas. 
En términos de fórmula: 
 Número total de eventos = m x n 
Esto puede ser extendido a más de dos eventos. Para tres eventos, m, n, y o: 
 Número total de eventos = m x n x o 
Ejemplos: 
 Un vendedor de autos quiere presentar a sus clientes todas las diferentes opciones con que cuenta: auto convertible, auto de 2 puertas y auto de 4 puertas, cualquiera de ellos con rines deportivos o estándar. ¿Cuántos diferentes arreglos de autos y rines puede ofrecer el vendedor? 
 
 Número total de arreglos = 3 x 2 
 
 Suponga, sin embargo, que el vendedor tiene para ofrecer ocho modelos de auto y seis tipos de rines. Sería tedioso hacer un dibujo con todas las posibilidades. Aplicando la técnica de la multiplicación fácilmente realizamos el cálculo: 
 
 Número total de arreglos = m x n = 8 x 6 = 48 
TÉCNICA DE LA PERMUTACIÓN 
Es aplicada para encontrar el número posible de arreglos donde hay solo un grupo de objetos e importa el orden a seleccionar. 
 Permutaciones de n objetos distintos tomados de n en n, es:
 nPr = nPn = n!
 Ejemplos:
 1) Se quiere conocer el conjunto de todas las disposiciones posibles de tres personas colocadas en hilera para tomar una fotografía.
 
 3P3 = 3! = 6
 1
 2) Cinco personas desean nombrar un Comité Directivo compuesto de un presidente, un vicepresidente, un secretario, un tesorero y un vocal. ¿Cuántas maneras hay de constituir el comité?
 5P5 = 5! = 120
 3) Hay seis banderas de distintos colores. ¿Cuántas señales diferentes se pueden enviar usando las seis banderas al mismo tiempo?
 6P6 = 6! = 720
4) Tres componentes electrónicos: un transistor, un capacitor y un diodo, serán ensamblados en una tablilla de una televisión. Los componentes pueden ser ensamblados en cualquier orden. ¿De cuantas diferentes maneras pueden ser ensamblados los tres componentes? 
 
 T D C D T C C D T T C D D C T C T D 
 3P3 = 3! = (3 x 2) = 6 = 6
 Permutación: Todos los arreglos de r objetos seleccionados de n objetos posibles distintos
 La fórmula empleada para contar el número total de diferentes permutaciones es: 
 n P r = n!/(n – r )! 
 Donde nPr es el número de permutaciones posible n es el número total de objetos r es el número de objetos utilizados en un mismo momento.
 
Ejemplos:
 
 Suponga que hay ocho tipos de computadora pero solo tres espaciosdisponibles para exhibirlas en la tienda de computadoras. ¿De cuantas maneras diferentes pueden ser arregladas las 8 máquinas en los tres espacios disponibles? 
 
 n P r = n!/(n – r )! = 8!/(8-3)! = 8!/5! = 336 
 Permutación: Todos los arreglos de r objetos seleccionados de n objetos posibles similares
 n P r = n!/(n1!n2!n3!...nr!) 
 Ejemplo:
 Cuál es el número de formas o maneras de pintar 12 oficinas de tal forma que 3 de ellas son verdes, 2 rosas, 2 amarillos y las restantes blancas.
 
 n P r = n!/(n1!n2!n3!...nr!) 
 = 12! / 3!2!2!5!
 = 166,320
 En el análisis anterior los arreglos no presentan repeticiones, es decir, no hay dos espacios disponibles con el mismo tipo de computadora. Si en los arreglos se permite la repetición, la fórmula de permutaciones es la siguiente: 
 n Pr = nr 
 
 Para ilustrar el punto, queremos saber ¿cuántas series de 2 letras se pueden formar con las letras A, B, C, si se permite la repetición? Las permutaciones son las siguientes: 
 AA, AB, AC, BA, CA, BB, BC, CB, CC 
 Usando la fórmula: 
 n Pr = nr = 3P2 = 32 = 9 
TÉCNICA DE LA COMBINACIÓN 
Combinaciones: es el número de formas de seleccionar r objetos de un grupo de n objetos sin importar el orden.
 n C r = n! / r! (n – r )! 
Por ejemplo, si se quiere formar un equipo de trabajo formado por 2 personas seleccionadas de un grupo de tres (A, B y C). Si en el equipo hay dos funciones diferentes, entonces si importa el orden, los resultados serán permutaciones. Por el contrario si en el equipo no hay funciones definidas, entonces no importa el orden y los resultados serán combinaciones. Los resultados en ambos casos son los siguientes: 
 
 Permutaciones: AB, AC, BA, CA, BC, CB 
 Combinaciones: AB, AC, BC 
 Ejemplo:
 En una compañía se quiere establecer un código de colores para identificar cada una de las 42 partes de un producto. Se quiere marcar con 3 colores de un total de 7 cada una de las partes, de tal suerte que cada una tenga una combinación de 3 colores diferentes. ¿Será adecuado este código de colores para identificar las 42 partes del producto? 
 
 Usando la fórmula de combinaciones: 
 n C r = n! / r! (n – r )! 
 = 7!/ 3! ( 7 – 3 )! 
 = 35 / 3! 4! 
IMPORTANCIA DE LAS TÉCNICAS DE CONTEO EN EL ÁREA DE LA COMPUTACIÓN
En el área de la computación son necesarias para determinar:
El número de ciclos que tiene un programa
El número de comparaciones que realiza un programa para ordenar un conjunto de datos
El número de palabras diferentes que tiene un lenguaje como determinada gramática, el número de intercambios que se llevan a cabo en un programa para resolver un sistema de ecuaciones
CONCLUSIÓN
Las Técnicas de Conteo en computación permiten optimizar los recursos de la computadora y disminuir el tiempo de ejecución de un proceso, lo que produce una mejora en el tiempo de respuesta
Con un buen uso de estas técnicas es posible determinar cual es el programa más eficiente sin necesidad de ejecutarlo