5 votos

Proyecto de investigación combinatoria

Estoy buscando un tema para hacer un pregrado proyecto de investigación en el campo de la combinatoria. Quiero que el proyecto se relacionan con la informática. Como digo quiero el código de un programa y los casos de prueba .... etc. También quiero que el tema sea de interés general y no aburrido para ofrecer una presentación. Yo estaba pensando en hacer el proyecto en $P$ VS $NP$, pero luego me di cuenta de que es muy abstracto y no que agradable para hacer la investigación.

Miré en secreto compartido y matrices ortogonales y me pareció realmente interesante y tengo la intención de trabajar en él.

Yo estaba mirando el elegante árbol de la conjetura, suena muy interesante, y estoy pensando en el momento. También, he tomado dos cursos de Álgebra abstracta, así que también puede hacer un proyecto que se relaciona la teoría de grupo con la combinatoria.

¿Ustedes tienen sugerencias ?

1voto

BruceET Puntos 7117

Esta pregunta ha sido durante alrededor de una semana, sin ningún sugerencias, así que voy a hacer uno que podría ser útil. Por supuesto, usted debe consultar con su asesor antes de tomar una decisión. Yo soy un gran ventilador de pregrado proyectos de investigación, y les deseo éxito--con esta u otra idea.

Una idea sería la de investigar estadísticos pruebas de permutación. Aquí está un ejemplo de una prueba de permutación de el libro de La Estadística Sleuth por Ramsey y Shafer (alrededor de la página 103):

En 1986, el transbordador espacial Challenger explotó después de ser lanzado en la inusualmente baja temperatura de $29^o$F. Una posterior investigación reveló que la explosión fue causada por la fuga de combustible alrededor de los O-rings, que había perdido la flexibilidad debido al frío. A continuación se condes de notable, pero no catastrófica, O-anillo de fallas en cada una de las 24 anteriores lanzamientos, roto por el lanzamiento de temperaturas por debajo de $65^o$F (Frío) y por encima de $65^o$F (Caliente).

  Cold   1, 1, 1, 3
  Warm   0, 0, 0, 0, 0,  0, 0, 0, 0, 0,  
         0, 0, 0, 0, 0,  0, 0, 1, 1, 2

En retrospectiva, estos datos muestran evidencia de que la junta tórica errores están asociados con bajas temperaturas en el lanzamiento?

Este es un difícil conjunto de datos para algunas de las tradicionales pruebas estadísticas. Por ejemplo, los datos pueden ser demasiado lejos de la normal utilizar una de dos muestras el test de la t; además, el gran número de lazos que dificultan el uso de una clasificación basada en el test como el de dos muestras de la prueba de Wilcoxon.

La idea de la prueba de permutación es que si el Frío y Cálido observaciones realmente proceden de la misma población, entonces se debe estar bien, poner todos los 24 de las observaciones dentro de un grupo y, a continuación, dividir al azar en un grupo de cuatro y otro grupo de los veinte. Encontrar el ejemplo de los medios de ambos grupos y restar para encontrar el valor de $D = \bar X_4 - \bar X_{20}.$ 'observado' valor de $D\,$ es de 1,3, como se muestra en la breve bits de R código de abajo.

 cold = c(1, 1, 1, 3)
 warm = c(0, 0, 0, 0, 0,  0, 0, 0, 0, 0,  0, 0, 0, 0, 0,  0, 0, 1, 1, 2)
 d.obs = mean(cold) - mean(warm);  d.obs
 ## 1.3

La pregunta entonces es: donde: $D_{\text{obs}} = 1.3$ cae en la "permutación de distribución' de todas las posibles particiones aleatorias en 4 y 20 de las observaciones. Para nuestros datos sólo hay ocho posibles valores de $D.$ Ramsey y Schafer dar la permutación de distribución de la siguiente manera.

 Difference in means   -0.5  -0.2   0.1   0.4   0.7   1.0   1.3   1.6     
 Ways / C(24,4)        2380  3400  2040  1530   855   316    95    10

Por lo tanto el valor de 1,3 parece extrema. El valor de P (probabilidad de un resultado tan extremo o más extrema) es $(95 + 10)/10626 = 0.00988$ o del 1%.

Si 1.3 se encuentra ahora en una cola de este de distribución, entonces podemos concluir que la anterior Frío lanza tendido para tener más O-ring fracasos que hizo Caliente lanza.

A menudo no es factible el uso de la combinatoria para encontrar la permutación de distribución. Así que uno utiliza un programa de computadora para encontrar $D$ para muchos elegido al azar de permutaciones para obtener una aproximación de la permutación de distribución.

 ## Challenger data
 x1 = Cold = c(1, 1, 1, 3)
 x2 = Warm = c(0, 0, 0, 0, 0,  0, 0, 0, 0, 0,  0, 0, 0, 0, 0,  0, 0, 1, 1, 2)

 x = c(x1, x2);  n1 = length(x1);  n2 = length(x2)                              
 d.obs = mean(x1) - mean(x2)

 # Simulate permutation distribution
 m = 100000             # number of random partitions
 d.prm = numeric(m) 

 for (i in 1:m)  {
 perm = sample(x, n1+n2)   # random permutation of data  
 p1 = perm[1:n1]; p2 = perm[(n1+1):(n1+n2)]  # random partition
 d.prm[i] = mean(p1) - mean(p2)
 }
 d.obs;  mean(d.prm >= d.obs)
 ## 1.3
 ## 0.01037  # P-value of simulated permutation test

 # Graphic display
 cut.pt = seq(-.5, 1.9, by=.3) - .15
 hist(d.prm, breaks=cut.pt, col="wheat", xlab="Diff. in Means",
   main = "Simulated Permutation Dist'n of Challenger Data")
 abline(v=d.obs, lwd=2, col="red", lty="dashed")
 rs = m*round(c(2380, 3400, 2040, 1530, 855, 316, 95, 10)/choose(24,4), 3)  # exact
 points(seq(-.5, 1.6, by=.3), rs, pch=19, col="darkgreen")

El histograma a continuación se muestra un histograma de la simulación de la permutación distribución y puntos muestran los valores exactos de Ramsey y Schafer.

enter image description here

Un artículo en la línea de la Revista de Estadísticas de la Educaciónpor Eudey (2010) ofrece una discusión más general de las pruebas de permutación junto con muchos ejemplos. No hay escasez de interesante conjuntos de datos para explorar o de gráficos interesantes para una presentación.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X