COMBINATORIA

En esta nueva entrada de nuestro blog, queremos exponer un breve repaso de conceptos básicos de combinatoria, que nos ayudarán a entender algunos de los problemas correspondientes al Tema 1 del libro Kurose & Ross.

• PERMUTACIONES DE n ELEMENTOS:

Las permutaciones nos permiten ordenar números, pudiendo responder a preguntas como: ¿Cuántos números de n cifras podemos obtener reordenando la posición de n dígitos distintos?

Como podemos ver en esta imagen, el número de combinaciones posibles viene dado por la operación n factorial, siendo n el número de cifras disponibles:

  

• PERMUTACIONES CON CIFRAS QUE SE PUEDEN REPETIR:

 En este caso queremos contar el número de combinaciones posibles, teniendo en cuentan que tenemos cifras que se pueden repetir (por ejemplo, disponemos de las cifras 1,1,1,1,1,2,2,2). Para ello, debemos contar como uno todas las posibles combinaciones de los números que se repiten:

- Permutaciones de los 1: 5! (ya que tenemos 5 unos posibles).
- Permutaciones de los 2: 3! (ya que tenemos 3 doses posibles).

Con estos datos, el resultado seria: 8!/(5!3!).

Podemos generalizar esta formula como: n!/(k1!k2!....kp!); teniendo en cuenta que ki es el número de veces que tenemos disponibles cada cifra.

• VARIACIONES CON REPETICIÓN: 

En este apartado, resolveremos preguntas del tipo: ¿Cuántos números de n cifras podemos obtener con k dígitos distintos suponiendo que podemos reutilizarlos?

Por ejemplo: si tenemos las cifras 0 ,1 y tenemos n posiciones, el número total de combinaciones será: 2^n.
Si generalizamos esta expresión para k digitos, obtenemos la expresión: k^n.

• VARIACIONES SIN REPETICIÓN DE ELEMENTOS:

En este apartado suponemos, al contrario que en el anterior, que no podemos reutilizar los dígitos disponibles; respondiendo a preguntas del tipo: ¿Cuántos números de n cifras podemos obtener a partir de k (k>=n) cifras sin poder reutilizarlas?

• COMBINACIONES DE k ELEMENTOS SIN REPETICIONES:

En este caso el orden en el que aparece cada cifra no es importante. Un ejemplo muy ilustrativo es el siguiente problema:
De una baraja de 10 cartas se extraen 3, ¿cuántos tríos distintos se pueden extraer?

- Suponemos que m es el número de elementos totales (en el ejemplo serían las 10 cartas) y n, el número de elementos seleccionados (en el ejemplo, los grupos de 3 cartas):

 - Esta fórmula se conoce como el número combinatorio de m sobre n, de manera que su solución daría respuesta a la pregunta del problema.

Pregunta R20

R20.Suponga que el sistema terminal A desea enviar un archivo de gran tamaño al sistema terminal B. Sin entrar en detalles, describa cómo crea el sistema terminal A los paquetes a partir del archivo. Cuando uno de estos paquetes llega a un conmutador de paquetes, ¿qué información del mismo utiliza el conmutador para determinar el enlace por el que debe ser reenviado el paquete? ¿Por qué la conmutación de paquetes en Internet es análoga a viajar de una ciudad a otra preguntando por la dirección a la que nos dirigimos?

RESPUESTA:

1. Cuando el archivo a enviar es muy grande, el sistema terminal fragmentará dicho archivo en unidades más pequeñas denominadas paquetes.
2. Cuando un router de la red recibe un paquete, este examinará la dirección de destino del paquete. A continuación, lo volverá a enviar al router correspondiente.
3. Porque cuando un paquete llega a un router, pregunta cual es la siguiente dirección a la que debe ir, en función de la dirección de destino.

Pregunta R10

R10. Describa las tecnologías de acceso inalámbrico a Internet más populares hoy día.

RESPUESTA:
Las tecnologías más populares de acceso inalámbrico a Internet son:

1. WiFi, para redes de área local.
2. EVDO y HSDPA, para redes móviles. 
3. Próximamente, WiMax. 

Pregunta R16

R16. Considere el envío de un paquete desde un host emisor a un host receptor a través de una ruta fija. Enumere los componentes del retardo terminal a terminal. ¿Cuáles de estos retardos son constantes y cuáles son variables?

RESPUESTA:

Los componentes del retardo terminal a terminal son: retardos de procesamiento, de cola, de transmisión y de propagación, de tal manera que la suma de todos estos retardos da lugar al retardo entre los nodos.

• Constantes: retardo de procesamiento.
• Variables: retardo de transmisión, de propagación y de cola.

Blanca y Andrea