10 Problemas algorítmicos Sin embargo, para resolver - dummies

Los algoritmos han existido desde hace siglos, por lo que uno pensaría que los científicos ya habrán descubierto y resuelto cada algoritmo. Desafortunadamente, lo opuesto es verdad. La resolución de un algoritmo en particular a menudo presenta algunas preguntas más que el algoritmo no resuelve y que no parecían aparentes hasta que alguien llegó a la solución.

Los algoritmos son una serie de pasos utilizados para resolver un problema, y ​​no debe confundirlos con otras entidades, como las ecuaciones. Un algoritmo nunca es una solución en busca de un problema. Nadie crearía una serie de pasos para resolver un problema que aún no existe (o puede que nunca exista).

Esta lista trata sobre problemas algorítmicos que servirían para un propósito si alguien encontrara una solución para ellos.

Manejo de búsquedas de texto

Muchas búsquedas de texto implican el uso de expresiones regulares, una especie de taquigrafía que le dice a la computadora qué buscar. La gramática utilizada para la expresión regular depende del idioma o la aplicación, pero encontrará expresiones regulares que se usan en varios lugares, incluidos procesadores de texto, aplicaciones de correo electrónico, diálogos de búsqueda y en todo tipo de lugares donde debe proporcionar una búsqueda precisa. términos para una gama de elementos de texto.

Uno de los problemas actuales con expresiones regulares es que parece que cada entorno de aplicación tiene un conjunto similar de reglas, pero con las suficientes diferencias para dificultar la creación de un término de búsqueda. El problema generalizado de la altura estelar busca descubrir si existe una sintaxis de expresión regular generalizada. Si es así, el algoritmo resultante haría posible que alguien aprendiera solo un método de creación de expresiones regulares para realizar búsquedas.

Diferenciar palabras

Al trabajar con caracteres, una computadora ve números, no letras. Los números son en realidad solo una serie de 0 y 1 en la computadora y en realidad no tienen ningún significado. La combinación de caracteres en cadenas solo hace que la serie de 0 y 1 sea más larga. En consecuencia, comparar dos cadenas, algo que un ser humano puede hacer de un vistazo, puede llevar tiempo dentro de una computadora, y es probable que haya confusión entre conjugados. Por ejemplo, a menos que tenga cuidado al construir el algoritmo, una computadora podría confundir alistar y escuchar. Más importante aún, la computadora requeriría tiempo para discernir la diferencia entre los dos. El problema de separación de palabras busca encontrar el algoritmo más pequeño (y el más rápido posible) (un autómata finito determinista, DFN, en este caso) para realizar la separación de palabras.El objetivo es aceptar una palabra y rechazar otra, dadas dos palabras de una longitud particular.

Determinando si una aplicación finalizará

Uno de los problemas que Alan Turing propuso en 1936 es la cuestión de si un algoritmo, dada la descripción de un programa y una entrada, podría determinar si el programa finalmente se detendría (el problema de detención). Cuando se trabaja con una aplicación simple, es fácil determinar en muchos casos si el programa se detendrá o continuará ejecutándose en un bucle infinito. Sin embargo, a medida que aumenta la complejidad del programa, resulta más difícil determinar el resultado de ejecutar el programa con cualquier entrada dada. Una máquina de Turing no puede hacer esta determinación; el resultado es un código defectuoso con bucles infinitos. Ninguna cantidad de prueba que use la tecnología actual puede resolver este problema.

Un hiperordenador es un modelo informático que va más allá de la máquina de Turing para resolver problemas como el problema de detención. Sin embargo, tales máquinas no son posibles usando la tecnología actual. Si fueran posibles, podría preguntarles todo tipo de imponderables que las computadoras no pueden responder actualmente. Este artículo le brinda una buena idea de lo que sucedería si alguien pudiera resolver este problema.

Creación y uso de funciones unidireccionales

Una función unidireccional es una función que es fácil de usar para obtener una respuesta en una dirección, pero casi imposible de usar con la inversa de esa respuesta. En otras palabras, utiliza una función unidireccional para crear algo así como un hash que aparecería como parte de una solución de criptografía, identificación personal, autenticación u otras necesidades de seguridad de datos.

La existencia de una función unidireccional es menos misterio y más una cuestión de prueba. Muchos sistemas de telecomunicaciones, comercio electrónico y banca electrónica actualmente dependen de funciones que supuestamente son de una sola manera, pero nadie sabe realmente si realmente son de una sola manera. La existencia de una función unidireccional es actualmente una hipótesis, no una teoría. Si alguien fuera capaz de demostrar que existe una función unidireccional, los problemas de seguridad de datos serían más fáciles de resolver desde una perspectiva de programación.

Multiplicar números realmente grandes

Existen números realmente grandes en muchos lugares. Por ejemplo, considere realizar los cálculos que implican distancias a Marte, o tal vez a Plutón. Actualmente existen métodos para realizar multiplicaciones en números realmente grandes, pero tienden a ser lentos porque requieren múltiples operaciones para completarse. El problema ocurre cuando los números son demasiado grandes para caber en los registros del procesador. En ese punto, la multiplicación debe ocurrir en más de un paso, lo que ralentiza considerablemente las cosas. Las soluciones actuales incluyen:

• Algoritmo de multiplicación complejo de Gauss
• Multiplicación de Karatsuba
• Toom-Cook
• Métodos de transformación de Fourier

Aunque muchos de los métodos actualmente disponibles producen resultados aceptables, todos llevan su tiempo, y Cuando tiene que realizar muchos cálculos, el problema del tiempo puede volverse crítico. En consecuencia, la multiplicación de números grandes es uno de esos problemas que requiere una solución mejor que los disponibles en la actualidad.

Dividir un recurso por igual

Puede parecer que dividir los recursos por igual no es difícil, pero los humanos, por ser del tipo envidioso, podrían ver que el recurso está dividido de manera desigual a menos que puedas encontrar una forma de asegurar a todos que la división es justa. Este es el problema de corte de pasteles sin envidia. Por supuesto, cuando cortas un pastel, no importa cuán justamente intentes hacerlo, siempre existe la percepción de que la división es injusta. Crear una división equitativa de recursos es importante en la vida cotidiana para minimizar los conflictos entre las partes interesadas en cualquier organización, haciendo que todos sean más eficientes.

Ya existen dos soluciones para el problema de corte de torta libre de envidia con un número específico de personas, pero no existe una solución general. Cuando hay dos personas involucradas, la primera corta la torta y la segunda elige la primera. De esta forma, ambas partes tienen asegurada una división equitativa. El problema se vuelve más difícil con tres personas, pero puede probar la solución de Selfridge-Conway para el problema. Sin embargo, después de llegar a cuatro personas, no hay solución.

Reducir el tiempo de cálculo de la distancia de edición

La distancia de edición entre dos cadenas es la cantidad de operaciones necesarias para transformar una cadena en la otra. El cálculo de distancia gira en torno a las operaciones de distancia de Levenshtein, que son la eliminación, inserción o sustitución de un personaje en la cuerda. Esta técnica particular ve el uso en interfaces de lenguaje natural, cuantificación de secuencia de ADN y todo tipo de otros lugares donde puede tener dos cadenas similares que requieren algún tipo de comparación o modificación.

Actualmente existen varias soluciones para este problema, todas bastante lentas. De hecho, la mayoría de ellos toma un tiempo exponencial, por lo que el tiempo requerido para realizar una transformación se suma rápidamente al punto donde los humanos pueden ver pausas en el procesamiento de la entrada. La pausa no es tan mala cuando se utiliza un procesador de textos que realiza verificaciones automáticas de palabras y cambia una palabra mal escrita por la correcta. Sin embargo, al usar interfaces de voz, la pausa puede ser bastante notoria y hacer que el operador humano cometa errores.

Solución rápida de problemas

A medida que el aprendizaje automático despega y contamos cada vez más en las computadoras para resolver problemas, la cuestión de qué tan rápido una computadora puede resolver un problema se vuelve crítica. El problema P versus NP simplemente pregunta si una computadora puede resolver un problema rápidamente cuando puede verificar rápidamente la solución del problema. En otras palabras, si la computadora puede determinar razonablemente que una respuesta humana a un problema es correcta en un tiempo polinomial o menor, ¿también puede resolver el problema en sí mismo en tiempo polinomial o menos?

Esta pregunta fue discutida originalmente en la década de 1950 por John Nash en cartas a la Agencia de Seguridad Nacional (NSA) y nuevamente en cartas entre Kurt Gödel y John von Neumann. Además del aprendizaje automático (y AI en general), este problema particular es una preocupación en muchos otros campos, incluyendo las matemáticas, la criptografía, la investigación de algoritmos, la teoría de juegos, el procesamiento multimedia, la filosofía y la economía.

Jugar al juego de paridad

Al principio, resolver un juego puede no parecerle tan útil en la vida real. Sí, los juegos son divertidos e interesantes, pero en realidad no proporcionan un fondo para hacer algo útil; al menos, esa es la teoría general. Sin embargo, la teoría de juegos entra en juego en una gran cantidad de escenarios de la vida real, muchos de los cuales involucran procesos complejos que alguien puede entender más fácilmente como juegos que como procesos reales. En este caso, el juego ayuda a las personas a comprender la verificación automática y la síntesis de controladores, entre otras cosas. Puedes leer más sobre el juego de paridad. De hecho, puedes jugarlo.

Comprensión de problemas espaciales

Para contextualizar este problema en particular, piense en mover cajas en un almacén u otras situaciones en las que necesite considerar el espacio en el que se mueven las cosas. Obviamente, si tiene muchas cajas en un gran almacén y todas requieren una carretilla elevadora para recoger, no desea tratar de averiguar cómo almacenarlas de manera óptima reorganizándolas físicamente. Aquí es donde necesita resolver el problema visualizando una solución.

Sin embargo, la pregunta es si todos los problemas espaciales tienen una solución. En este caso, piense en uno de los rompecabezas de esos niños que lo tiene haciendo una imagen deslizando las pequeñas fichas. Parece que debería existir una solución en todos los casos, pero en algunas situaciones, un mal punto de partida puede dar como resultado una situación que no tiene solución.

Los matemáticos como Sam Loyd a menudo usan acertijos para demostrar problemas matemáticos complejos, algunos de los cuales no tienen solución hoy. Visitar estos sitios es divertido porque no solo obtienes entretenimiento gratis sino también algo para pensar. Los problemas que plantean estos rompecabezas tienen aplicaciones prácticas, pero se presentan de una manera divertida.