Como investigador de TCS, estoy totalmente en desacuerdo con su afirmación de que todos los “algoritmos realmente importantes y prácticos” se descubrieron en los años 60-90. Debe tener en cuenta que el advenimiento de gran parte de la teoría que utiliza CS se produjo a fines de los años 50 y principios de los 60, por lo que coincide con el inicio de su intervalo (si no cuento el trabajo fundamental de los lógicos). No es de extrañar, la optimización combinatoria alrededor de ese mismo tiempo, que (es mi campo de investigación, así que me disculpo si esto parece sesgado) es muy aplicable para practicar una gran parte del tiempo y aparece por todas partes.
Primero, hay algo con lo que estoy de acuerdo aquí, ” algoritmos prácticos “. Estoy muy seguro de que si le preguntas a la gente en una década cuáles son los “algoritmos prácticos”, estoy seguro de que responderán entre los años 60 y 2000; normalmente hay un lapso de tiempo antes de que la teoría se use y se haga de la manera correcta. Los practicantes (a menos que sean informáticos) no son los que deben saltar a estos grupos para utilizarlos de inmediato y hacerlo correctamente. Además, algunas áreas de investigación no están relacionadas, por lo que a veces con el tiempo se “encuentran” en una idea similar. También vale la pena señalar que en las primeras partes de ese intervalo, era más “obvio” cuando algo tenía un gran impacto, pero el dominio de los problemas es tan grande en estos días en comparación con eso que literalmente podría producirse una gran ondulación en uno área de investigación y ni siquiera se oiría en otra ahora.
No, la investigación actual no se trata solo de “pequeñas mejoras en la Complejidad Big-O”, el simple hecho de que lo haya dicho de esta manera muestra que sabe poco o nada sobre la investigación en Algoritmos. Incluso entonces, no solo quieres obtener un resultado Big-Oh, sino un resultado Big-Theta (que normalmente es lo que los investigadores se esfuerzan). La investigación se basa en los hombros de los anteriores y rara vez es desde cero. Permíteme darte algunos pequeños ejemplos de cosas que las personas en algoritmos pueden intentar mejorar:
- ¿Hay algún sitio web para encontrar la complejidad del tiempo de diferentes algoritmos?
- ¿El uso de una función recursiva en el código aumenta mucho el tiempo de ejecución?
- ¿Cuál es el tiempo de ejecución del método sort () en la biblioteca de Colecciones?
- ¿Cuál es la explicación intuitiva para agregar flujo en bordes inversos en el algoritmo de flujo máximo? ¿Por qué necesitamos eso?
- Preguntado por un no experto en tecnología, ¿qué tan impactante sería si una tecnología pudiera mitigar el ruido impulsivo en tiempo real usando un algoritmo no lineal simple que usa la mediana (en lugar de la media)? Por ejemplo, podría usarse para reemplazar filtros lineales analógicos en teléfonos móviles, esencialmente actuando como un filtro lineal a menos que detecte ruido impulsivo y actúe para condicionarlo.
- ¿Podemos idear algoritmos para nuevas arquitecturas? Estos incluyen cosas como nuevos algoritmos paralelos, algoritmos de ADN, etc.
- ¿Podemos idear mejores algoritmos de aproximación? Es decir, ¿podemos acercar la relación de aproximación al óptimo? ¿Es fundamentalmente imposible hacerlo (si ese es el caso, pruébelo) bajo el supuesto P! = NP. ¿Podemos obtener algoritmos de aproximación más eficientes (esto en sí mismo también es importante, muchos de estos algoritmos dependiendo del dominio pueden tener
- ¿Podemos mejorar la complejidad espacial de un algoritmo? Esto se vuelve increíblemente importante en aplicaciones donde los conjuntos de datos son enormes, como en Bioinformática, donde incluso un algoritmo con tiempo de ejecución cuadrático puede ser costoso en la práctica.
- ¿Existe un algoritmo manejable de parámetros fijos para un problema dado?
Estos son algunos ejemplos entre muchos otros ejemplos. Los practicantes, por definición, están interesados en problemas en el presente o aquellos (irónicamente) que comenzaron 10-20 años antes del presente cuando dicha tecnología es relevante , no en 20-30 años, normalmente en el futuro, donde muchos investigadores de Algoritmos tienden a estar sentados. aunque hay muchos como yo interesados en los grandes problemas modernos. También vale la pena señalar que definitivamente existe una brecha en el conocimiento entre los profesionales y los matemáticos / informáticos que diseñan estos algoritmos. Incluso argumentaría que hay una brecha entre incluso sus científicos informáticos típicos en estos días en comparación con un científico informático teórico que trabaja en Algoritmos, ya que el listón ha estado cayendo en el contexto de un investigador de CS. Si un profesional quiere utilizarlos, necesita aprender más para usarlos (recuerde, los informáticos están haciendo investigación científica la mayor parte del tiempo).
