El concepto más complicado en Informática (CS), diría, es el concepto de relacionar problemas P, NP, NP-completos .
En conclusión, casi todo el CS se basa en 2 cosas fundamentales: Algoritmos y Matemáticas.
Todos sabemos sobre el poder de las matemáticas, así que solo hablamos de algoritmos.
- ¿Puede un estudiante de rama no CSE obtener una pasantía en Amazon, LinkedIn, Microsoft, Google y Facebook?
- ¿Cuál es una buena explicación del 'método potencial' para el análisis amortizado?
- ¿Cómo construiría un universo de realidad virtual de 5 dimensiones?
- ¿Cómo es AIT, Pune para CSE? ¿Cómo es la multitud, la cultura de codificación y las ubicaciones para CSE allí? ¿Cómo son las instalaciones del albergue? Con 20,000 rango aéreo, ¿vale la pena ir?
- Imágenes e íconos digitales: ¿Habrá una alternativa superior a los GIF para animaciones en el futuro cercano?
Ya sea, computación paralela en supercomputadoras, transacciones de bases de datos, programación del sistema operativo, redes neuronales, minería de datos, procesamiento de imágenes digitales, inteligencia artificial, interconexiones en redes gigantes y densas, es decir, Internet, cada dominio de CS se basa directa o indirectamente en ‘ Algoritmos ‘ . Los fundamentos de los algoritmos rodean casi todos los dominios de CS en sí mismos.
Están en todas partes, ¡lo estás usando todos los días!
Ahora, ten un poco de paciencia y sigue leyendo.
Una cosa común en los algoritmos que se ejecutan detrás de la cortina en cada situación de todos los dominios mencionados anteriormente es que todos son algoritmos de tiempo polinomial, es decir , en entradas de tamaño n, su peor tiempo de ejecución es O (n ^ k) para alguna k constante . En palabras más simples, dan resultados en tiempo finito . Los problemas / situaciones resueltos por estos algoritmos se denominan ” problemas P” .
Hay algunos problemas, como el famoso “Problema de detención” de Turing, que no puede ser resuelto por ninguna computadora, sin importar el tiempo que permitamos.
Por ejemplo, ¿cuál de los siguientes programas se detiene?
Programa 1: mientras (verdadero) continúe;
- no se detiene, continúa para siempre en un bucle infinito
Programa 2: imprima “¡Hola, mundo!”
- se detiene e imprime ‘¡Hola, mundo!’
Tarea fácil, ¿eh? Pero los programas complejos resultarán problemáticos.
Hay una clase de problemas que son ‘verificables’ en tiempo polinómico, llamados ” problemas NP “. El término “verificable” aquí significa, para verificar si la solución para el problema dado es correcta o no, en tiempo finito .
Ahora hay P no es igual a NP pregunta! Que pregunta:
“¿Si cada problema cuya solución se puede verificar en tiempo finito (NP), también se puede resolver en tiempo finito (P)?”
Esta pregunta aparentemente simple ha sido uno de los problemas de investigación abierta más profundos y desconcertantes en la informática teórica desde que se propuso por primera vez en 1971.
Luego, hay una clase de problemas, llamados ” problemas NP-completos , cuyo estado es desconocido. Lo que no puede resolverse en tiempo finito ni tampoco puede probarse que requiere tiempo infinito para resolverse.
Comprender los rudimentos de la teoría de la completitud NP es necesario para un buen diseñador de algoritmos. Si puede establecer un problema como NP completo, proporciona buena evidencia de su intratabilidad. Como ingeniero, sería mejor dedicar su tiempo a desarrollar un algoritmo de aproximación o resolver un caso especial manejable, en lugar de buscar un algoritmo rápido que resuelva el problema exactamente. Además, muchos problemas naturales e interesantes que en la superficie no parecen más difíciles que la clasificación, la búsqueda de gráficos o el flujo de la red, de hecho, son NP completos.
Por ejemplo, está tratando de resolver un problema aparentemente simple del mundo real utilizando redes neuronales o IA, que finalmente resultó ser NP-Complete.
Hay más que quiero agregar para responder esta pregunta, pero espero que esté de acuerdo en eso ahora. 🙂
