Preguntas y respuestas para científicos informáticos teóricos e investigadores en campos relacionados.
Desde el libro de 1998 de Chris Okasaki "Estructuras de datos puramente funcionales", no he visto aparecer muchas nuevas estructuras de datos puramente funcionales; Puedo nombrar solo algunos: IntMap (también inventado por Okasaki en 1998, pero no presente en ese libro) Árboles de dedos (y su...
Esta pregunta es (inspirada por) / (vergonzosamente robada) una pregunta similar en MathOverflow , pero espero que las respuestas aquí sean bastante diferentes. Todos tenemos trabajos favoritos en nuestras propias áreas teóricas. De vez en cuando, uno encuentra un papel tan sorprendente (por...
Paul Erdos habló sobre el "Libro" donde Dios guarda la prueba más elegante de cada teorema matemático. Esto incluso inspiró un libro (que creo que ahora está en su cuarta edición): Pruebas del libro . Si Dios tuviera un libro similar para algoritmos, ¿qué algoritmo (s) crees que sería un candidato...
Para demostrar la importancia de los algoritmos (por ejemplo, para estudiantes y profesores que no hacen teoría o incluso son de campos completamente diferentes), a veces es útil tener a mano una lista de ejemplos en los que se han implementado algoritmos centrales en empresas comerciales,...
He estado revisando Theory of Computation por diversión y esta pregunta me ha estado molestando por un tiempo (curioso, nunca lo pensé cuando aprendí Automata Theory en mi licenciatura). Entonces, ¿por qué exactamente estudiamos autómatas finitos deterministas y no deterministas (DFA / NFA)? Así...
Norbert Blum publicó recientemente una prueba de 38 páginas de que . ¿Es correcto?PAGS≠ NPAGSP≠NPP \ne NP También sobre el tema: ¿dónde más (en Internet) se está discutiendo su corrección? Nota: el enfoque de este texto de pregunta ha cambiado con el tiempo. Vea los comentarios de las preguntas...
[ Cronología ] Esta pregunta tiene el mismo espíritu de qué documentos deben leer todos y qué videos deben ver todos . Pide libros notables en diferentes áreas de la informática teórica. Los libros pueden estar orientados a las matemáticas, sin embargo, puede ser excelente para un científico de...
Wikipedia solo enumera dos problemas bajo "problemas no resueltos en informática" : P = NP? La existencia de funciones unidireccionales ¿Cuáles son otros problemas importantes que deberían agregarse a esta lista? Reglas: Solo un problema por respuesta Proporcione una breve descripción y los...
Supongamos que Mario camina sobre la superficie de un planeta. Si comienza a caminar desde un lugar conocido, en una dirección fija, por una distancia predeterminada, ¿qué tan rápido podemos determinar dónde se detendrá? Más formalmente, supongamos que se nos da un politopo convexo en 3...
La Universidad de Stanford ahora tiene un canal de Youtube , con acceso gratuito a videos HD de cursos completos sobre todo, desde sistemas dinámicos hasta entrelazamiento cuántico. Más conferencias y talleres están grabando en video sus charlas. ¿Qué videos en línea crees que todos deberían...
La factorización y el isomorfismo gráfico son problemas en NP que no se sabe que están en P ni en NP-Completo. ¿Cuáles son algunos otros problemas naturales (suficientemente diferentes) que comparten esta propiedad? Los ejemplos artificiales que provienen directamente de la prueba del teorema de...
Después de leer la pregunta de Daniel Apon , comencé a pensar que podría ser útil (especialmente para investigadores junior y estudiantes graduados como yo) hacer una pregunta más amplia y más general para que podamos aprender de la experiencia de más investigadores senior. Así que aquí está la...
Se forma una mezcla de dos cadenas intercalando los caracteres en una nueva cadena, manteniendo los caracteres de cada cadena en orden. Por ejemplo, MISSISSIPPIes una combinación de MISIPPy SSISI. Permítanme llamar a un cuadrado de cadena si es una combinación de dos cadenas idénticas. Por ejemplo,...
Ha habido varias preguntas con el mismo esquema que este: ¿Qué documentos deberían leer todos? ¿Qué libros deberían leer todos? ¿Cuáles son los libros recientes de TCS cuyos borradores están disponibles en línea? ¿Qué videos deberían ver todos? Era reacio a publicar otro más, pero las notas de...
La informática teórica ha proporcionado algunos ejemplos del "precio de la abstracción". Los dos más destacados son para la eliminación y clasificación gaussianas. A saber: Se sabe que la eliminación gaussiana es óptima para, por ejemplo, calcular el determinante si restringe las operaciones a...
He estado aprendiendo algunas partes de la teoría de categorías. Ciertamente es una forma diferente de ver las cosas. (Resumen muy aproximado para aquellos que no lo han visto: la teoría de categorías ofrece formas de expresar todo tipo de comportamiento matemático únicamente en términos de...
Después de la publicación Qué libros deberían leer todos , noté que hay libros recientes cuyos borradores están disponibles en línea. Por ejemplo, la entrada de Algoritmos de aproximación de la publicación anterior cita un libro de 2011 (aún por publicar) titulado El diseño de algoritmos de...
En los últimos años se han desarrollado muchos algoritmos de búsqueda de rutas que pueden calcular la mejor ruta en respuesta a los cambios del gráfico mucho más rápido que A *: ¿qué son y en qué se diferencian? ¿Son para diferentes situaciones, o algunas otras obsoletas? Estos son los que he...
Me estoy preparando para una charla dirigida a estudiantes de matemáticas de pregrado y, como parte de ella, estoy considerando discutir el concepto de capacidad de decisión. Quiero dar un ejemplo de un problema que actualmente no sabemos que sea decidible o indecidible. Existen muchos problemas de...
Me gustaría pedir ayuda para compilar una lista de tantas conferencias y talleres relacionados con TCS como sea posible. Mi principal motivación para hacer esto es planificar la posible cobertura del blog de más lugares teóricos: encontrar corresponsales que asistan a estos eventos que estén...