1. Inicio
  2. Pregunta y respuesta
  3. Problemas de informática que aún son problemáticos

Problemas de informática que aún son problemáticos

2009-07-28 8 views
17

Además de los mencionados en la Wikipedia (Unsolved problems in computer science), ¿qué otros problemas de informática todavía no se han resuelto?Problemas de informática que aún son problemáticos

Pensé en hacer esta pregunta porque otras grandes mentes podrían no ser conscientes de que existen tales problemas.

(establecido en wiki de la comunidad; un problema CS por mensaje, por favor)

Aquellos que se publican en Wikipedia son:

Fuente

2009-07-28 Randell

+0

Tenga en cuenta que las funciones unidireccionales implican P! = NP. –

Respuesta

25

Todavía no he descubierto dónde Cualquier clave es.


Ok, en serio (y con el fin de contribuir en algo que vale la pena) ¿qué tal el problema de aplicar a las tareas de computación en paralelo "en serie"? Se están alcanzando los límites teóricos del cálculo en serie, mientras que la computación paralela no tiene un límite teórico. Sin embargo, es muy difícil aplicar la computación paralela a los problemas seriales. Por ejemplo, un problema en serie puede requerir una serie de cálculos, y los resultados de cada cálculo en la serie dependen del resultado del cálculo anterior. ¿Cómo se realiza esta tarea de forma paralela?

This article ilustra las cosas desde un punto de vista teórico y saca a relucir la noción de la computación especulativa como una posible solución (con un punto limpio sobre el cerebro humano). Esta es un área muy nueva, sin embargo, y las soluciones no son fáciles.

Fuente

2009-07-28 08:11:58 zombat

+5

HAHA, muchas respuestas. Pero me pregunto cómo ustedes se perdieron esto: Un navegador que sigue cada regla CSS presente en el conjunto de reglas css del W3C. Y por qué esta publicación en particular no me permite enviar una respuesta, recibo un error de página no encontrada. – pokrate

+4

+1 para cualquier clave. –

+0

@pokrate: porque no es un problema de CS, y quiere decir "especificación de CSS", y hay más de una especificación de CSS (por lo que su respuesta es ambigua), pero sobre todo es una respuesta pobre porque es concebible una solución. Ni siquiera sabemos si algunos de los problemas de CS se pueden resolver. @zombat: las leyes de Amdahl y Gustafson son apropiadas. – outis

1

Enlace de elementos de IU a una base de datos.

Hay muchos intentos miserables y, aunque odio decirlo, .NET es probablemente el mejor hoy en día. Solo piénselo: después de literalmente 30 años, todavía es un dolor construir un editor simple para una persona con varias direcciones.

Fuente

2009-07-28 08:13:58

+4

Si bien es un problema interesante, en realidad no está relacionado con la informática. Ingeniería de software, tal vez. Pero CS? –

+3

Y, de manera similar, cómo a una base de datos bajo control de fuente. Definitivamente no es un problema de CS, pero definitivamente tampoco está resuelto. – Unsliced

1

Una cosa interesante aquí sería la definición de problema. Un problema es simplemente un margen de mejora bajo los recursos dados (y no se ha comprobado que sea insoluble). entonces, según esta nueva definición, tenemos muchos problemas en todos los campos.

Un problema puede ser mejorar una solución de complejidad factorial a la solución de complejidad exponencial. (Si no se prueba que no sale)

Fuente

2009-07-28 08:20:00

10

Encontrar un acuerdo sobre qué lenguaje de programación se utiliza para resolver qué problemas.

Fuente

2009-07-28 08:28:11

+4

Imposible ... ;-) – peSHIr

+1

La respuesta es "Emacs". ... ¿Qué? – zombat

1

cómo mejorar el NetFlix algorithm al SIGUIENTE 10% :) (¡Felicitaciones a The Ensemble!)

Fuente

2009-07-28 08:31:03 pageman

+1

No cuente su pollo todavía, podrían tener o no la mejor puntuación de la prueba. ;) – KTC

+0

@KTC realmente? ¿extendieron la fecha límite? http://www.netflixprize.com/closed – pageman

+0

@pageman, "El RMSE para el primer subconjunto de" prueba "se informará públicamente en el Sitio; el RMSE para el segundo subconjunto de" prueba "no se informará públicamente, pero será empleado para calificar una presentación como se describe a continuación ". La clasificación de marcador público basada en el primer conjunto puede corresponder o no al ranking final basado en el segundo conjunto privado. – KTC

3

Gráfico isomorfismo.

Básicamente, la mayoría de los problemas que ocurren naturalmente son fáciles (P) o probablemente duros (NP). Hubo, si la memoria sirve, 2 o 3 problemas que cayeron "en el medio". La primalidad era uno, pero recientemente se demostró que estaba en P. El isomorfismo gráfico es el otro.

El isomorfismo de gráfico es esta pregunta: dado G1 y G2, ¿es G2 simplemente G1, pero "reetiquetado"? Equivalentemente, ¿podemos volver a etiquetar G2 para que sea exactamente igual que G1?

Artículos de Wiki! Un general overview, y el artículo sobre la cuestión de su clase de complejidad here.

Editar: Tengo que recordar escribir TODAS las palabras.

Fuente

2009-07-28 16:38:39 agorenst

2

Ganar con éxito contra humanos en el juego de Go. Wiki Article about computers and go.

Fuente

2009-07-28 16:42:02 Smandoli

+0

.... aunque quizás esto sea demasiado general. Depende del significado de "problema", supongo. Si la prueba de Turing es relevante, creo que esto también es cierto. – Smandoli

+0

Al leer el artículo de la wiki, me aseguro de que sea más en la categoría de Grand Challenge. Curiosamente, no se encuentra en http://en.wikipedia.org/wiki/Grand_Challenge_problem. Ahora, ¿cómo puede ser eso? – Smandoli

+0

en 2016, esto se ha logrado. (: – mauris

1

Tenga en cuenta que la tesis de Church-Turing no es, en realidad, una afirmación sobre las matemáticas. Es una declaración sobre el mundo físico.

Lo más cercano que se puede llegar a prueba es algo así como "es cierto en el modelo estándar".

Esto no quiere decir que no se pueda formalizar en mayor medida, pero lo mejor que puede esperar es aclarar suposiciones específicas sobre el mundo físico.

Fuente

2009-07-28 23:59:31

+0

) Es una afirmación sobre la capacidad de cálculo de ciertas funciones. De acuerdo, la tesis se establece en términos de que puede ser solucionada por una Máquina de Turing, pero eso no es lo mismo que una computadora física. Por ejemplo, una MT puede tiene memoria infinita. Puede tener solo un conjunto finito de estados, pero el número de estados no está estrictamente limitado, por lo que puede tener "tantos como quiera". – Clayton

+0

En la teoría de la computación, sin embargo, hay varios constructos para permitir diferentes mundos de computación. El ejemplo más simple es uno en el que las Máquinas Turing tienen acceso a un llamado "Oracle", que como su nombre lo indica simplemente da una respuesta a un cierto problema. Si una TM tiene un oráculo para el Problema de Detención, usted Estamos en un mundo de cómputo completamente diferente, y aún son posibles los problemas más locos (y siempre hay más que no son consistentes). Aquí hay un wiki miserablemente técnico le: http://en.wikipedia.org/wiki/Arithmetical_hierarchy – agorenst

+0

@Clayton Lo que dice, informalmente, es que cualquier computadora física que pueda hacer puede ser simulada por una máquina de turing. Desde una perspectiva puramente matemática, es fácil encontrar contraejemplos para la tesis, como un ejemplo simple, una TM con un oráculo de alto. Lo único que invalida tales contraejemplos es el mundo físico. –

3

Optimización dinámica para splay trees.

Soluciona un conjunto de consultas en un árbol de búsqueda binario. ("Buscar nodo 6. Buscar nodo 13. Buscar nodo 42" ...) Los árboles de dispersión son estáticamente óptimo: si crea un árbol de búsqueda binaria fijo y ejecuta las consultas en su contra, se ejecutará no más que un factor constante más rápido que ejecutar las consultas contra un árbol desplegable.

Esto es una comparación de manzanas con naranjas, ya que un árbol desplegable no es un árbol estático. La pregunta abierta es si los árboles de separación son dinámicamente óptimos: ¿está dentro de un factor constante de un árbol que puede modificarse durante las consultas?

Fuente

2009-07-29 00:14:00

+0

+1 - interesante. Nunca había oído hablar de esos antes. – zombat

3

ORM es el Vietnam de Informática -Ted Neward

es decir, que no se resuelve a satisfacción de muchos pueblos.

Fuente

2009-07-29 00:25:49 CoderTao

+1

¿O es un ejercicio costoso y esencialmente sin sentido sin esperanza de éxito? – Clayton

+0

Sí, eso también ... – CoderTao

8

Procesamiento de lenguaje natural que realmente funciona. No puedo creer que esto no haya sido mencionado todavía.

Fuente

2009-07-29 00:33:06 ehsanul

+1

Si puede hacer un algoritmo que pueda comparar cuál de los dos algoritmos NLP "realmente funciona" o simplemente "funciona mejor", ¡eso sería un comienzo! –

1

El problema del vendedor viajero sigue sin resolverse.

Fuente

2009-07-29 00:41:44

+4

Eso no es un problema sin resolver. Se ha demostrado que es NP-completo, pero eso no es lo mismo que sin resolver. Una solución de fuerza bruta es simplemente calcular la longitud de todas las rutas posibles, luego elija la más corta. Eso es computacionalmente caro hasta el punto de ser poco práctico, pero es una solución. – Clayton

+1

Todavía no cumple con ningún estándar formal de eficiencia, pero está en lo cierto, técnicamente está resuelto. –

+0

Está completamente resuelto en el sentido de que se sabe que es NP-completo. –

1

Al volver a analizar las respuestas, creo que encontré que el elemento de combinación de al menos 2 respuestas anteriores es el problema de romper la barrera entre la sintaxis y la semántica. ¿Cuál es el problema en el que está trabajando realmente todo programador e informático? (Últimamente, "semántica" aparece cada vez más como tema de áreas completas de CS).La mayoría de los campos y temas que hemos abierto comienzan con la promesa de romper esta barrera. Hasta ahora, todos ellos, tarde o temprano, se redujeron de "crear inteligencia" a "algoritmos inteligentes".

AI es probablemente el área de investigación donde esto ha sido más prominente, pero al final, muchas otras personas han estado soñando con lo que es básicamente un botón "Haz lo que quiero decir". (Podría encajar en los algoritmos evolutivos, las redes neuronales, y últimamente en la gente web semántica aquí.) El principal obstáculo es que todo lo que hace una computadora es cambiar los bits.

Probablemente estoy diseminando la prejusticia y la tontería aquí, porque para los materialistas esto no es un problema fundamental, porque cambiar los bits es probablemente todo lo que estamos haciendo en el cerebro humano. Simplemente podría ser un problema de complejidad.

Bueno ... No estoy dispuesto a comenzar esa discusión aquí, y además de la sintaxis frente a la semántica es un tema bastante general. Pasar demasiado tiempo en esto definitivamente evita que uno resuelva algunos de los problemas más específicos mencionados en otras respuestas. Abordar estos es mucho más efectivo, pero ayuda tener en cuenta que aquí hay barreras fundamentales que aún no podemos superar.

Fuente

2009-08-05 08:28:23

0

P =? NC sería mi voto. La paralelización automática de muchos núcleos sería posible bajo P = NC, pero se cree que los dos son diferentes y, por lo tanto, hay problemas de P-completo que son difíciles de paralelizar. Comprender qué problemas pertenecen a esta clase es cada vez más importante.

Fuente

2011-09-22 05:58:50 Charles

Cuestiones relacionadas

 Cuestiones relacionadas