Ir al contenido

PGD | Ejercicios para la Unidad 1

En todos los casos se muestran las respuestas finales en color.

  1. Calcular el número de bits necesarios para identificar a una persona cualquiera del planeta.
    Estimando la población mundial en alrededor de 7.000.000.000 de personas, este número será nuestra variedad V. Es necesario hallar el menor n tal que 2n ≥ V. Se encuentra que 232 = 4.294.967.296 < V, mientras que 233 = 8.589.934.592 > V. Por lo tanto se necesitan n = 33 bits.
  2. Un matrimonio de granjeros se dedica a la cría de ovejas. El esposo es capaz de reconocer cuatro especies de ovejas, pero es incapaz de reconocer el sexo. La esposa, en cambio, es capaz de reconocer el sexo del animal, pero no la especie.
    1. Indicar el número de bits necesario para especificar una especie reconocida de oveja, y el necesario para especificar uno de los sexos.
      La variedad de especies es Vespecie = 4, por lo tanto nespecie = 2; mientras que la variedad de sexos es Vsexo = 2, luego nsexo = 1.
    2. Determinar cuántas combinaciones (especie y sexo) pueden reconocer los esposos si trabajan juntos, y el número de bits necesario para especificar una de ellas.
      Como cada especie tiene dos sexos, las combinaciones serán Vespecie x Vsexo = 4 x 2 = 8, y como 23 = 8 serán necesarios 3 bits para especificar cualquiera de esas combinaciones.
    3. Indicar por qué este último número es igual a la suma de los encontrados en el punto A.
      La cantidad de bits calculada en B (3 bits) es igual a la suma de las calculadas en A (2 bits y 1 bit) porque las fuentes de información son independientes: saber la especie de oveja no permite adivinar el sexo, y viceversa.
  3. Se diseña un anemómetro que debe proveer una lectura de la dirección del viento, la cual se mide en las direcciones N, S, E, O, en sus intermedias (NE, SE, NO, SO) y en las intermedias entre cada par consecutivo de ellas. Averiguar la cantidad de información en bits generada en cada lectura.
    Entre cada par consecutivo de las ocho direcciones enumeradas (N, NE, E, SE, S, SO, O, NO) hay otras ocho (NNE, ENE, ESE, SSE, SSO, OSO, ONO, NNO) lo que da un total de 16 direcciones; esta es la variedad V de direcciones de cada lectura. Por lo tanto cada una de ellas genera 4 bits (pues 24 = 16).
  4. La pertenencia de una persona a un grupo puede asociarse a un bit de información, ya que la persona puede pertenecer o no a ese grupo. Con esta idea, calcular de cuántas formas un conjunto de 10 personas puede dividirse en dos grupos. (Sugerencia: sólo es necesario definir quiénes pertenecen al primer grupo, ya que el resto pertenecerá automáticamente al segundo)
    Como cada persona, con independencia de la otra, puede pertenecer al grupo o no, cada persona presenta 1 bit de información. Todas las personas juntas generan entonces 1o bits de información para definir el grupo en cuestión. Buscamos la variedad de todos los grupos, por lo tanto será V = 2n = 210 = 1024.
  5. Se tiene una “imagen” formada por mosaicos cuadrados, cada uno de los cuales puede ser blanco, gris claro, gris oscuro o negro, dispuestos formando un cuadrado mayor de 100 x 100 piezas. Por otro lado se tiene un texto compuesto por palabras de 6 caracteres en promedio, cada uno de los cuales está tomado de un alfabeto de 32 caracteres. En estas condiciones, analizar la validez de la frase “una imagen vale más que mil palabras”.
    Por un lado tenemos que la imagen tiene 100 x 100 = 10.000 piezas. Cada pieza tiene uno entre cuatro “colores” distintos y requiere por lo tanto 2 bits para elegirlo. Como tenemos 10.000 piezas, se necesitan 2 x 10.000 = 20.000 bits.
    Por otro lado, elegir un caracter entre 32 requiere 5 bits de información (25 = 32). Una palabra de 6 caracteres necesita entonces 5 x 6 = 30 bits de información, y 1.000 palabras de ese tipo necesitarán 30 x 1.000 = 30.000 bits.
    Comparando ambos resultados, en este caso resulta que las 1000 palabras “valen más” (tienen más información) que una imagen.
  6. Un sistema de código de barras que emplea barras individuales de 4 espesores distintos se aplica a la identificación de productos. Si se necesitan identificar un máximo de 12.000 productos diferentes, ¿cuántas barras deberá tener el código?
    Primero averiguamos cuánta información necesitamos que contenga un código. Con una variedad de 12.000 productos harán falta 14 bits (ya que 213 = 8.192 < 12.000 < 214 = 16.384). Como una barra comunica 2 bits (ya que su variedad, dada por su espesor, es 4), necesitamos un número B de barras tal que 2 x B = 14, es decir B = 7: son necesarias 7 barras.
  7. Un ilusionista realiza una prueba de adivinación, y para ello distribuye convenientemente cartas de póker con las figuras A, 7, 8, 9, 10, J, Q, K, en sus 4 palos (diamante, pique, trébol, corazón) en una mesa, boca arriba, y pide a un sujeto que elija una de ellas, sin mencionar cuál es. Al ilusionista se le permite hacer preguntas al sujeto, siempre que la respuesta sea sí o no. Determinar cuántas preguntas (como mínimo) necesita realizar para dar con la carta elegida.
    La variedad de cartas es 8 figuras x 4 palos = 32; sin importar los detalles del truco, elegir una carta entre 32 requiere 5 bits de información (25 = 32). Como una pregunta cuya respuesta sea sí o no me permite obtener 1 bit de información, son necesarias 5 preguntas.
  8. Se tiene una balanza de platillos, y se desea construir un conjunto de pesas para que sea posible medir cualquier número entero de kilogramos de 1 kg a 15 kg.
    1. ¿Cuál es el mínimo de pesas necesarias?
      Cada operación de pesado en una balanza de platillos equivale a una pregunta del tipo sí-no (¿es el peso incógnita más pesado que la pesa?). Luego, determinar un elemento entre 15 (en realidad 16, ya que podríamos incluir trivialmente un “peso incógnita” de 0 kg) necesita 4 bits de información, es decir, cuatro pesadas; por lo tanto necesitamos 4 pesas.
    2. ¿Qué peso debería tener cada una?
      Los valores de las pesas deben ser 8 kg, 4 kg, 2 kg y 1 kg; referirse a la explicación dada en clase para las razones de elegir estos valores.