Simulación

La simulación consiste en predecir el futuro estado de un sistema temporal, dado el estado actual y la función de transición, que define como se modifica el estado en cada unidad de tiempo. (Ojo: en la página de la OIE la definición de la simulación es mucho más liberal e incluye otros tipos de problemas.)

Un ejemplo muy sencillo es una cuenta bancaria, donde la unidad de tiempo normalmente es un año, el estado actual es el saldo de la cuenta y la función de transición multiplica el saldo actual por una tasa de interés. Otro ejemplo es la serie Fibonacci, donde el estado actual es dos números seguidos de la serie, y la función de transición asigna al primer número el valor actual del segundo, y al segundo número la suma de los dos números.

Por regla general hay dos maneras de resolver un problema de simulación: por iteración o por análisis.

Solución por iteración

La solución por iteración consiste simplemente en iterar sobre todas las unidades de tiempo y calcular el nuevo estado según la función de transición. Por ejemplo, si el saldo actual de la cuenta es 1000 euros y la tasa de interés es 10%, el saldo después del primer año será 1100 euros, el saldo después del segundo año 1210 euros, etc.

Para la serie Fibonacci, si el estado inicial es (1, 1), los siguientes estados (pares de números de la serie) serán (1, 2), (2, 3), (3, 5), (5, 8), etc. Evidentemente, la solución por iteración tiene complejidad lineal en las unidades de tiempo que hay que recorrer.

Solución por análisis

En algunos casos es posible implementar una solución más eficiente por análisis de la función de transición. Por ejemplo, en el caso de la cuenta bancaria la función de transición multiplica el saldo actual por (1+t), donde t es la tasa de interés. Por lo tanto, si s el el saldo inicial, el saldo después de n años será s*(1+t)n.

Elevar un número a otro se puede hacer en tiempo logarítmico, que es mucho más eficiente que tiempo lineal. Una función recursiva eficiente para elevar un número b (la base) a otro número e (el exponente) es la siguiente:


int exp(int b, int e) {
   if (e == 0) return 1;
   int m = exp(b, e/2);
   if  (e%2 == 0) return m*m;
   else return m*m*b;
}

La idea es escribir be como be = be/2 * be/2 (si e es par) o be = be/2 * be/2 * b (si e es impar). Evidentemente, sólo es necesario calcular be/2 una vez, y multiplicar el resultado por si mismo.

Cada llamada a la función hace exactamente una llamada recursiva, con un valor de e igual al anterior valor dividido entre 2, por lo que el número total de llamadas recursivas será proporcional al logaritmo en base 2 del valor original de e. Otra manera de escribir el código anterior sin recursividad sería:


int exp(int b,int e){
   int res = 1;
   while (e){
      if (e&1) res *= b;
      b *= b;
      e>>=1;
   }
   return res;
}

La misma idea funciona para matrices: si la función de transición consiste en una multiplicación por una matriz, aplicar la función N veces corresponde a elevar esta matriz a N.

Por ejemplo, para la serie de Fibonacci podemos representar la función de transición como la siguiente multiplicación de matriz:

Ejemplo de un grafo

Calcular el n-ésimo número de la serie corresponde a elevar la matriz a n:

Ejemplo de un grafo

Por ejemplo, para calcular el tercer número de la serie se hará

Ejemplo de un grafo

Elevar una matriz M a un exponente e sigue la misma regla, es decir podemos expresar Me como Me = Me/2 * Me/2 (si e es par) o Me = Me/2 * Me/2 * M (si e es impar).

Problemas para resolver esta semana:

Sencillos:

UVa logo 161 - Traffic Lights
UVa logo 362 - 18,000 Seconds Remaining
UVa logo 603 - Parking Lot
UVa logo 637 - Booklet Printing
OIE logo El Juego de la Vida
OIE logo Dados raros
OIE logo Robots

Avanzados:

UVa logo 11254 - Consecutive Integers
UVa logo 12290 - Counting Game
OIE logo Oingo Boingo
OIE logo Torres de Hanoi
OIE logo Transporte espacial