Bloque de Colores

Algunos resultados interesantes

Icono de Post March 3 2012 :: Combinatoria, Python, Uncategorized ::

Como conte en este post, para resolver el problema del post anterior, hice una serie de pruebas cuyos resultados se pueden ver acá. Me quedo un cubo triangularmente cortado de resultados de variaciones de los parámetros de la función descripta. Para acelerar un poco los tests, una vez que conseguí una solución (cuya demostración se puede encontrar en una hermosa versión typesetada en LaTeX acá) la programe en python usando técnicas de programacion dinámica. Esta versión se puede encontrar aqui.

Lo interesante fue que me quedaron varias secuencias de números y decidí ir a OEIS para testearlo. Me encontré entonces con una serie de resultados interesantes que decidí publicar acá para revisarlos mas adelante.

Resultados simples

  • Si m=n=k , la función devuelve una permutación. m!
  • si m=n, m<k => f(n, m, k) = k!/(k-m)!

Resultados interesantes

Parece existir algún tipo de patrón, lamentablemente no tengo el tiempo en este momento y sobre todas las cosas el nivel de matemática suficiente como para investigarlo un poco más. Escribo este post más que nada para revisarlo nuevamente después de haber pasado por Concrete Mathematics, que todavía no pude estudiar.

Algún otro resultado

Da la sensación de que jugando con las variables del cubo se encontrarían un montón de resultados interesantes.

Autor: Emiliano Martínez Luque.

Comments Off on Algunos resultados interesantes

Problema de Algoritmia Básico: Simulación del Caso Promedio

Icono de Post February 29 2012 :: Algoritmia, Estadística, Probabilidad, Python ::

Finalmente para analizar el caso promedio, decidí realizar una serie de simulaciones en Python, aproveche de paso, para presentar este programa como trabajo práctico final en la materia “Lenguajes de Scripting” de la facultad. El código del programa de la simulación puede encontrarse aquí, para correrlo compilar algo.c, ejecutar limpiar.sh y luego version-1-0.py. Las muestras se guardan en formato CSV en la carpeta “resultados/muestras” y los reportes en “resultados/reportes”.

Algunas notas sobre la simulación

Me interesaba analizar específicamente el comportamiento de la porción del algoritmo en la que se itera a travéz de la lista pasados que es la porción variable del mismo. Para hacer esto, cree una variable global total y en cada iteración por la lista pasados en la función esta_en_lista() se la incrementa en uno. El programa escribe luego en STDOUT el valor de esta variable al finalizar. Ver algo.c.

En el script de Python se genera una lhttps://github.com/emluque/Post_Stuff/blob/master/Problema_Algoritmia_Basico/Simulacion/version-1-0.pyista randomizada se levanta un proceso al que se le pasa esta lista como argumento y luego se lee el STDOUT del proceso para obtener el costo. Esto se hace en el archivo: muestras.py y la porción de código que hace esto es:


  def generar_lista(self):
    lista = []
    for i in range(self.n):
      lista.append(random.randint(1, self.k))
    return ",".join( [str(x) for x in lista])

  def generar_resultado(self, lista ):
    process = subprocess.Popen(["algoritmo/algo", lista] , shell=False, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    res = ""
    for char in process.stdout.read():
      res += char
    
    process.wait()
    #Esta linea que sigue es medio al dope
    if (process.returncode != None):
      if(process.returncode < 0):
        print("----")
        print(process.returncode)
        print("----")
        raise NameError("Tio, No andubo el proceso.") 
    else:   
      process.kill()

    return int(res)

  def generar_resultados(self):
    for i in range(self.cant):
      strr = self.generar_lista();
      a = self.generar_resultado( strr )
      self.resultados.append(a)

Resultados

Un conjunto de resultados pregenerados (una corrida completa del programa puede tardar varias horas) puede verse aquí.

Reportes de Tipo 1

Lo primero que podemos ver en los reportes de tipo 1 es como a mayor tamaño de muestra, la función va tendiendo a un tipo de gráfica especifica. Que no es exactamente igual para diferentes tamaños de alfabeto y cadena, pero se acerca a un Campana de Gauss aunque un poco deformada en la región derecha y con una media corrida un poco hacia la izquierda del rango de valores posibles.

Por ejemplo, este es el gráfico obtenido para tamaño de cadena 10, tamaño de alfabeto 10 con 100000 muestras:

Y este es para 200,200,100000:

Reportes de Tipo 2

Los reportes de tipo 2, permiten ver el comportamiento de la gráfica manteniendo fijo el tamaño de cadena y de muestra.

Que nos muestra el reporte de tipo 2?

Bueno lo que vemos es que manteniendo el tamaño de cadena fijo, al ir aumentando el tamaño de alfabeto, los valores estadísticos (promedio, mediana, modo) van siendo cada vez mayores, lo mismo sucede con la gráfica. Podemos pensar que la posibilidad de ocurrencia de un elemento mayor a los elementos precedentes aumenta a mayor tamaño de alfabeto, lo cual mueve los valores hacia la derecha. Ver el comportamiento de los valores en el reporte para tamaño de cadena 200.

Por otro lado si el tamaño de alfabeto es significativamente mayor al tamaño de cadena, este comportamiento va disminuyendo. Lo cual indica que luego de un determinado valor en función al tamaño de la cadena, la posibilidad de que ocurra un elemento mayor a los elementos anteriores va estabilizándose. Ver reporte para tamaño de cadena 10.

Reportes de Tipo 3

Los reportes de tipo 3, nos muestran que la gráfica de la función se encuentra corrida hacia la izquierda en relación al rango de valores posibles, y que a mayor valor de n y k más hacia la izquierda se mueve en proporción al rango. Esto parecería coincidir con nuestras intuiciones de los posts anteriores, y parecería confirmarse gráficamente los factores de atenuamiento que habíamos considerado en estey este posts.

Gráfico de la función con alfabeto n=50, k=50 y muestra de tamaño 500:

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Simulación del Caso Promedio