¿Cuándo es útil la informática teórica?

https://stackoverflow.com/questions/235394

04-07-2019
|

Pregunta

En clase, aprendimos sobre el problema de detención, máquinas de Turing, reducciones, etc. Muchos compañeros de clase dicen que todos estos son conceptos abstractos e inútiles, y no tiene sentido conocerlos (es decir, puedes olvidarlos una vez el curso ha terminado y no se pierde nada).

¿Por qué es útil la teoría? ¿Alguna vez lo usó en su codificación diaria?

Solución

Cuando me gradué de la universidad, asumí que estaba a la par con todos los demás: " Tengo una licenciatura en CS, y muchas otras personas, y todos podemos hacer esencialmente las mismas cosas . " Finalmente descubrí que mi suposición era falsa. Me destaqué, y mi experiencia tenía mucho que ver con eso, particularmente mi título.

Sabía que había una & "; leve &"; diferencia, en que tuve un & "; B.S. &"; en CS porque mi universidad fue una de las primeras (supuestamente # 2 en 1987) en la nación en recibir la acreditación para su programa de grado de CS, y me gradué en la segunda clase para obtener esa acreditación. En ese momento, no pensé que importara mucho.

También noté durante la escuela secundaria y en la universidad que me fue particularmente bien en CS, mucho mejor que mis compañeros e incluso mejor que muchos de mis maestros. Me pidieron mucha ayuda, hice algunas tutorías, me pidieron ayuda con un proyecto de investigación y me permitieron hacer estudios independientes cuando nadie más lo hizo. Estaba feliz de poder ayudar, pero no pensé mucho en la diferencia.

Después de la universidad (USAFA), pasé cuatro años en la Fuerza Aérea, dos de los cuales estaban aplicando mi título de CS. Allí noté que muy pocos de mis compañeros de trabajo tenían títulos o incluso capacitación relacionada con las computadoras. La Fuerza Aérea me envió a cinco meses de capacitación en certificación, donde nuevamente encontré una falta de títulos o capacitación. Pero aquí comencé a notar la diferencia: se hizo totalmente obvio que muchas de las personas que conocí REALMENTE no sabían lo que estaban haciendo, y eso incluía a las personas con capacitación o títulos. Permítame ilustrar.

En mi entrenamiento de certificación de la Fuerza Aérea había un total de trece personas (incluido yo). Como oficiales de la Fuerza Aérea o su equivalente, todos teníamos títulos de licenciatura. Estaba en el medio según la edad y el rango (era un O-2 entre seis O-1 y seis O-3 y más). Al final de este entrenamiento, la Fuerza Aérea nos puso a todos como igualmente competentes para adquirir, construir, diseñar, mantener y operar CUALQUIER computadora o sistema de comunicación para CUALQUIER parte del Departamento de Defensa.

Sin embargo, de los trece de nosotros, solo seis tenían alguna forma de licenciatura en informática; los otros siete tenían títulos que iban desde aeronáutica a química / biología a psicología. De los seis de nosotros con títulos de CS, aprendí que dos nunca habían escrito un programa de ningún tipo y nunca habían usado una computadora más que casualmente (escribiendo papeles, jugando juegos, etc.). Aprendí que otros dos de nosotros habíamos escrito exactamente un programa en una sola computadora durante su programa de CS. Solo otra persona y yo habíamos escrito más de un programa o usado más de un tipo de computadora; de hecho, descubrimos que nosotros dos habíamos escrito muchos programas y habíamos usado muchos tipos de computadoras.

Hacia el final de nuestra capacitación de cinco meses, a nuestra clase se le asignó un proyecto de programación y nos dividimos en cuatro grupos para llevarlo a cabo por separado. Nuestros instructores dividieron la clase para difundir & Quot; talento de programación & Quot; de manera justa, y asignaron roles de líder de equipo, líder tecnológico y desarrollador. A cada grupo se le dio una semana para implementar (en Ada) una interfaz de usuario basada en texto a pantalla completa (esto era 1990) para un simulador de vuelo en la parte superior de una biblioteca de mecánica de vuelo proporcionada por el instructor. Fui asignado como líder tecnológico para mi equipo de cuatro.

El líder de mi equipo (que no tenía un título en informática) nos pidió a los otros tres que dividiéramos el proyecto en tareas y luego asignó un tercio de ellos a cada uno de nosotros. Terminé mi tercera de las tareas a mediados de ese primer día, luego pasé el resto del día ayudando a mis otros dos compañeros de equipo, hablando con el líder de mi equipo (BSing; ^) y jugando en mi computadora.

A la mañana siguiente (día dos), mi jefe de equipo me informó en privado que nuestros otros dos compañeros no habían progresado (uno no podía escribir un " si " declaración que compilaría), y me pidió que asumiera su trabajo. Terminé todo el proyecto a media tarde, y mi equipo pasó el resto del día volando en el simulador.

El otro tipo con el grado de CS comparable también fue asignado como líder tecnológico para su equipo, y terminaron al final del día tres. También comenzaron a volar su simulador. Los otros dos equipos no habían terminado, o incluso logrado un progreso significativo, al final de la semana. No se nos permitió ayudar a otros equipos, por lo que se quedó en eso.

Mientras tanto, a la mitad del día tres, me di cuenta de que el simulador de vuelo parecía comportarse & "; mal &"; Como uno de mis compañeros tenía un título en aeronáutica, le pregunté al respecto. ¡Estaba desconcertado, luego confesó que en realidad no sabía qué hacía volar a un avión! Estaba estupefacto! Resulta que su programa de estudios completo se refería a investigaciones de seguridad y accidentes, sin matemáticas ni ciencias reales detrás del vuelo. Por otro lado, quizás tenía una especialización en aeronáutica (¿recuerda USAFA?), Pero habíamos diseñado alas y realizado pruebas reales de túnel de viento. Por lo tanto, pasé el resto de la semana en silencio reescribiendo la biblioteca de mecánica de vuelo proporcionada por el instructor hasta que el simulador voló & Quot; right & Quot ;.

Desde entonces, he pasado casi dos décadas como contratista y ocasionalmente como empleado, siempre haciendo desarrollo de software más actividades relacionadas (DBA, arquitecto, etc.). Continué encontrando más de lo mismo, y finalmente renuncié a mi suposición juvenil.

Entonces, ¿qué he descubierto exactamente? No todos son iguales, y eso está bien: no soy una mejor persona porque puedo programar de manera efectiva, pero soy más útil SI eso es lo que necesitas de mí. Aprendí que mi experiencia realmente importaba: creciendo en una familia de electricistas e ingenieros eléctricos, kits de electrónica de construcción, leyendo LITERALMENTE cada libro de computadora en las bibliotecas escolares / públicas porque no tenía acceso a una computadora real, luego me mudé a una nueva ciudad donde mi escuela secundaria tenía computadoras, entonces obteniendo mi propia computadora como regalo, yendo a escuelas que tenían computadoras de diferentes tamaños y tipos (PC a mainframes), obtener un título acreditado de una muy buena escuela de ingeniería, tener que escribir muchos programas en diferentes idiomas en diferentes tipos de computadoras, tener que escribir programas duros (como mi propia máquina virtual con un lenguaje ensamblador personalizado, o una implementación de compresión Huffman, etc.), tener que solucionar por mí mismo construyendo mis propias computadoras a partir de partes e instalando TODO el software, etc.

Finalmente, aprendí que mis habilidades se basan en saber cómo funcionan las computadoras desde el nivel eléctrico en adelante: componentes electrónicos discretos, circuitos, subsistemas, interfaces, protocolos, bits, bytes, procesadores, dispositivos, controladores, bibliotecas, programas, sistemas, redes, hasta los conglomerados masivos de clase empresarial en los que trabajo habitualmente ahora. Entonces, cuando la maldita cosa se porta mal, sé exactamente CÓMO y POR QUÉ. Y sé lo que no se puede hacer tan bien como lo que se puede hacer. Y sé mucho sobre lo que se ha hecho, lo que se ha intentado y lo que queda relativamente sin explorar.

Lo más importante, después de haber aprendido todo eso, he aprendido que no sé nada. Ante todo lo que hay potencialmente para saber, mi conocimiento es minúsculo.

Y estoy bastante contento con eso. Pero te recomiendo que lo pruebes.

Otros consejos

Historia verdadera:

Cuando obtuve mi primer trabajo de programación en la escuela de posgrado, los muchachos que eran dueños de la compañía para la que trabajaba eran pilotos. Unas semanas después de que me contrataron, uno de ellos me hizo esta pregunta:

Hay 106 aeropuertos en Arkansas. ¿Podría escribir un programa que haría encontrar la ruta más corta necesaria para aterrizar en cada uno de ellos?

Pensé seriamente que me estaba cuestionando sobre mi conocimiento del problema del vendedor ambulante y la integridad de NP. Pero resulta que no lo era. No sabía nada al respecto. Realmente quería un programa que encontrara el camino más corto. Se sorprendió cuando le expliqué que había soluciones factoriales 106 y que encontrar la mejor era un problema informático difícil de resolver.

Entonces ese es un ejemplo.

Claro, es útil.

Imagine un desarrollador trabajando en un motor de plantillas. Sabes el tipo de cosas ...

Blah blah blah ${MyTemplateString} blah blah blah.

Comienza simple, con una pequeña expresión regular descarada para realizar los reemplazos.

Pero gradualmente las plantillas se vuelven un poco más elegantes, y el desarrollador incluye características para plantillas de listas y mapas de cadenas. Para lograr eso, escribe una pequeña gramática simple y genera un analizador.

Al ser muy astuto, el motor de plantillas podría incluir una sintaxis para la lógica condicional, para mostrar diferentes bloques de texto dependiendo de los valores de los argumentos.

Alguien con antecedentes teóricos en CS reconocería que el lenguaje de plantillas se está convirtiendo lentamente en Turing completo, y tal vez el patrón Intérprete sería una buena forma de implementarlo.

Después de haber creado un intérprete para las plantillas, un informático podría notar que la mayoría de las solicitudes de plantillas son duplicados, regenerando los mismos resultados una y otra vez. Por lo tanto, se desarrolla un caché y todas las solicitudes se enrutan a través del caché antes de realizar la costosa transformación.

Además, algunas plantillas son mucho más complejas que otras y tardan mucho más en renderizarse. Quizás alguien tenga la idea de estimar la ejecución de cada plantilla antes de renderizarla.

Pero espera !!! ¡Alguien del equipo señala que, si el lenguaje de plantilla realmente está completo, entonces la tarea de estimar el tiempo de ejecución de cada operación de renderizado es una instancia del Problema de detención! ¡Ay, no hagas eso!

Lo que pasa con la teoría, en la práctica, es que toda práctica se basa en la teoría. Teóricamente.

Las cosas que más uso:

complejidad computacional para escribir algoritmos que se escalan con gracia
comprensión de cómo funcionan la asignación de memoria, la paginación y el almacenamiento en caché de la CPU para poder escribir código eficiente
comprensión de las estructuras de datos
comprensión de subprocesos, bloqueo y problemas asociados

En cuanto a esas cosas en las máquinas de Turing, etc. Creo que es importante porque define las restricciones bajo las cuales todos operamos. Eso es importante de apreciar.

es la diferencia entre aprender álgebra y aprender a usar una calculadora

si conoce álgebra, se da cuenta de que el mismo problema puede manifestarse en diferentes formas, y comprende las reglas para transformar el problema en una forma más concisa

si solo sabe cómo usar una calculadora, puede perder mucho tiempo presionando botones en un problema que (a) ya está resuelto, (b) no se puede resolver o (c) es como otro problema (resuelto o no resuelto) que no reconoce porque está en una forma diferente

finge, por un momento, que la informática es física ... ¿la pregunta parecería tonta?

Un amigo mío está trabajando en un idioma con algunas plantillas. Me pidieron que hiciera una pequeña consulta. Parte de nuestra discusión fue sobre la característica de la plantilla, porque si las plantillas estuvieran completas en Turing, tendrían que considerar realmente las propiedades de VM-ish y cómo / si su compilador lo admitiría.

Mi historia es hasta este punto: la teoría de autómatas todavía se enseña, porque todavía tiene relevancia. El problema de detención aún existe y proporciona un límite a lo que puede hacer.

Ahora, ¿estas cosas tienen relevancia para un jinete de bases de datos que está creando código C #? Probablemente no. Pero cuando comience a pasar a un nivel más avanzado, querrá comprender sus raíces & Amp; fundaciones.

Aunque no los aplico directamente en el trabajo diario, sé que mi educación en informática formal ha afectado mi proceso de pensamiento. Ciertamente evito ciertos errores desde el principio porque tengo las lecciones aprendidas de los enfoques formales inculcados en mí.

Puede parecer inútil mientras lo están aprendiendo; pero apuesto a que su compañero de clase eventualmente se encontrará con un problema en el que usarán lo que se les enseñó, o al menos los patrones de pensamiento detrás de esto ...

Encerado ... Encerado ... Encerado ... Encerado ... ¿Qué tiene que ver eso con Karate, de todos modos?

En un trabajo me asignaron la tarea de mejorar el algoritmo de rastreo de red de nuestro modelo de distribución eléctrica, ya que el que estaban usando era demasiado lento. La red trifásica era esencialmente tres n-árboles (ya que los bucles no están permitidos en las redes eléctricas). Los nodos de la red estaban en la base de datos y algunos del equipo original no podían descubrir cómo construir un modelo en memoria, por lo que el seguimiento se realizó mediante SELECCIONES de profundidad sucesivas en la base de datos, filtrando en cada fase. Por lo tanto, para rastrear un nodo, diez nodos de la subestación requerirían al menos 10 consultas de la base de datos (los miembros del equipo original eran genios de la base de datos, pero carecían de un fondo decente en los algoritmos).

Escribí una solución que transformaba las 3 redes de nodos de n-árboles de la base de datos en una estructura de datos donde cada nodo se almacenaba una vez en una matriz de estructura de nodos y la relación de n-árboles se convertía en tres árboles binarios usando doblemente- punteros vinculados dentro de la matriz para que la red pueda rastrearse fácilmente en cualquier dirección.

Fue al menos dos órdenes de magnitud más rápido, tres en trazas aguas abajo muy largas.

Lo triste fue que tuve que enseñar prácticamente una clase de n-árboles, árboles binarios, punteros y listas doblemente vinculadas a varios de los otros programadores que habían sido entrenados en bases de datos y VB para que pudieran entender los algoritmos.

Es una dicotomía clásica, entre " how " y " what " ;. Tus compañeros de clase están mirando & Quot; cómo & Quot; para programar software, y están muy enfocados en el enfoque cercano; desde esa perspectiva, la perspectiva de la implementación, parece que saber cosas como detener estados y máquinas Turing no son importantes.

" ¿Cómo " Sin embargo, es muy poco del trabajo real que se espera que haga con Computer Science. De hecho, la mayoría de los ingenieros exitosos que conozco probablemente lo ubicarían en menos del 20 por ciento del trabajo real. " ¿Qué " hacer es mucho más importante; y para eso, los fundamentos de la informática son fundamentales. " ¿Qué " lo que quieres hacer se relaciona mucho más con el diseño que con la implementación; y un buen diseño es ... bueno, llamémoslo " no trivial " ;.

" Hay dos formas de construir un diseño de software: una es hacerlo tan simple que obviamente no hay deficiencias, y la otra es hacerlo tan complicado que No hay deficiencias obvias. El primer método es mucho más difícil. & Quot; - C.A.R. Hoare

¡Buena suerte con tus estudios!

Creo que la comprensión de los modelos fundamentales de computación es útil: seguro, en la práctica, nunca necesitará poder traducir una máquina de Turing en una máquina de registro, pero aprender a ver que dos problemas muy diferentes son realmente instancias del mismo concepto es una habilidad crítica.

La mayor parte del conocimiento no es " práctico " ;, sino que lo ayuda a conectar puntos de formas que no puede anticipar, o le brinda un vocabulario más rico para describir ideas más complejas.

Lo que importa no son los problemas específicos que estudias, son los principios que aprendes al estudiarlos. Uso conceptos sobre algoritmos, estructuras de datos, lenguajes de programación y sistemas operativos todos los días en mi trabajo. Si trabaja como programador, tomará decisiones todo el tiempo que afecten el rendimiento del sistema. Debe tener una base sólida en los conceptos abstractos fundamentales para tomar las decisiones correctas.

Si trabaja en una empresa que realiza trabajos innovadores, es importante poder comunicar a los arquitectos y desarrolladores cuáles son los beneficios. Hay mucha publicidad sobre todo tipo de tecnologías y posicionarse puede ser difícil. Cuando enmarca su innovación en términos científicos y teóricos, definitivamente tiene una ventaja y los clientes sienten que usted es el verdadero. Puedo decirle a la gente: hay una nueva forma de lidiar con el estado, la codificación y el no determinismo (es decir, las complejidades) y definitivamente puede ser más productivo de lo que es hoy.

Si tiene una visión a largo plazo en su carrera, aprender sobre teoría le dará profundidad, la profundidad que necesita para crecer. El retorno de la inversión en aprender su quinto o sexto lenguaje de programación será mucho menor que aprender su segundo y tercer lugar. La exposición a la teoría le dará una idea de la ingeniería real, sobre dónde están los grados de libertad y cómo puede hacer las compensaciones correctas.

Los conceptos importantes 1) Estado, 2) Codificación, 3) No determinismo. Si no los conoces, no te ayudarán. Lo que la teoría debería proporcionarle es el panorama general y una idea de cómo encajan los conceptos básicos. Debería ayudarte a perfeccionar tu intuición.

Ejemplo: algunas de las respuestas anteriores mencionan el problema de detención y las máquinas de Turing. Cuando me encontré con el trabajo de Turing en la universidad, no me sentí iluminado en absoluto. Un día me encontré con el teorema de incompletitud de Goedel y la numeración de Goedel en particular. Las cosas comenzaron a tener mucho sentido. Años después leí sobre Georg Cantor en una librería. Ahora realmente comencé a entender las máquinas de Turing y el problema de la detención. Pruébelo usted mismo y busque & Quot; Argumento diagonal de Cantor & Quot; en Wikipedia Es una de las cosas más increíbles intelectualmente que jamás encontrarás.

Alimento para el pensamiento: una máquina Turing típica no es la única forma de diseñar una máquina de transición de estado. Una máquina Turing con dos cintas en lugar de una sola le daría mucha más velocidad para varios algoritmos. http://www.math.ucla.edu/~ynm/papers/ eng.ps

Puedes exponerte a estas ideas de manera más eficiente de lo que lo hice leyendo este libro. Enlace al final de esta publicación. (Como mínimo, consulte la tabla de contenido en Amazon para conocer de qué se trata todo esto):

El libro de Rosenberg me pareció sensacional. http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/ dp / 0387096388 Si solo tiene un libro sobre teoría en mi humilde opinión, este debería ser el indicado.

Después de graduarme de CS pensé de manera similar: todas las teorías que estudiamos son completamente inútiles en la práctica. Esto demostró ser correcto por un corto período de tiempo, sin embargo, en el momento en que se ocupan de tareas complejas, la teoría es definitivamente MÁS VALIOSA que la práctica. cada uno después de unos años de codificación puede escribir algunos programas que " funcionan " pero no todos pueden entender cómo. no importa lo que la mayoría de nosotros lidiemos en cierto punto con problemas de rendimiento, retrasos en la red, precisión, escalabilidad, etc. En esta etapa, la teoría es crítica. Para diseñar una buena solución cuando se trata de sistemas complejos es muy importante saber cómo funciona la gestión de la memoria, los conceptos de proceso y subprocesos, cómo se les asigna memoria o estructuras de datos eficientes para el rendimiento, etc.

Una vez, por ejemplo, estaba trabajando en un proyecto que incluía muchos cálculos matemáticos y en cierto punto nuestro software falló. durante la depuración descubrí que después de una operación matemática recibí un número como DOBLE de un valor 1.000000000002 pero desde la perspectiva matemática no podía ser > 1 que en alguna etapa posterior del programa estaba dando la legendaria NaN excepción. Pasé algún tiempo para resolver esto, pero si hubiera prestado más atención a la " aproximación de Double and Float " lección no habría perdido ese tiempo.

No lo uso a diario. Pero me dio mucha comprensión que me ayuda cada día.

Descubrí que todo lo que necesito para la felicidad diaria del mundo teórico de CS es la expresión del mantra " Acoplamiento bajo y Cohesión alta " ;. Roger S. Pressman lo hizo académicamente antes de Steve McConnell lo puso de moda.

Sí, generalmente uso diagramas de estado para diseñar la forma y el flujo del programa. Una vez que funciona en teoría, empiezo a codificar y probar, marcando los estados a medida que avanzo.

Creo que también son una herramienta útil para explicar el comportamiento de un proceso a otras personas.

Simple. Por ejemplo: si estoy usando RSACryptoServiceProvider me gustaría saber qué es eso y por qué puedo confiar en él.

Porque las plantillas de C ++ son en realidad algún tipo de cálculo lambda. Ver www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf

Estoy estudiando para mi curso de algoritmos distribuidos ahora. Hay un capítulo sobre tolerancia a fallas y contiene algunas pruebas en el límite superior de cuántos procesos pueden fallar (o comportarse mal) para que el algoritmo distribuido pueda manejarlo correctamente.

Para muchos problemas, el límite para el mal comportamiento de los procesos es de hasta un tercio del número total de procesos. Esto es bastante útil en mi opinión porque sabes que no tiene sentido tratar de desarrollar un mejor algoritmo (bajo supuestos dados).

Incluso si los cursos teóricos no se van a utilizar directamente, podría ayudarte a pensar mejor en algo.

No sabe qué le va a pedir su jefe, puede que tenga que usar algo que pensó que no sería beneficioso, como dijo Jeffrey L Whitledge.

Para ser honesto, estoy en desacuerdo con muchas de las respuestas aquí. Escribí mi primer compilador (por diversión; realmente tengo demasiado café / tiempo libre) sin haber tomado un curso en compiladores; básicamente escaneé el código en busca de otro compilador y seguí el patrón. Podría escribir un analizador en C en la parte superior de mi cabeza, pero no creo poder recordar cómo dibujar un autómata pushdown si mi vida dependiera de ello.

Cuando decidí que quería poner inferencia de tipos en el lenguaje de programación de mi juguete (imperativo), primero revisé probablemente cinco documentos, mirando algo llamado & "; cálculo lambda escrito &"; ¿Qué pasa ... el ... **** ...? Al principio intenté implementar algo con & Quot; variables genéricas & Quot; y " variables no genéricas " y no tenía idea de lo que estaba pasando. Luego lo descarté todo y me senté allí con un cuaderno para descubrir cómo podría implementarlo prácticamente con soporte para todas las cosas que necesitaba (subtipado, funciones de primera clase, tipos parametrizados, etc.) Con un par de días de reflexión. & amp; escribiendo programas de prueba, me quedé sin aliento por más de una semana tratando de descubrir la basura teórica.

Conocer los conceptos básicos de la informática (es decir, cómo funciona la memoria virtual, cómo funcionan los sistemas de archivos, subprocesos / programación, SMP, estructuras de datos) ha resultado MUY útil. La teoría de la complejidad y las cosas Big-O a veces han resultado útiles (especialmente útiles para cosas como el diseño RDBMS). ¿El problema de la detención y la teoría de autómatas / máquinas de Turing? Nunca.

Sé que esto es viejo, pero mi breve respuesta a quienes afirman que la teoría es "inútil" y que pueden ejercer su profesión sin ella es esta:

Sin la teoría subyacente, hay no práctica.

¿Por qué es útil la teoría?

La teoría es la base subyacente sobre la cual se construyen otras cosas. Cuando la teoría se aplica , la práctica es el resultado.

Considere las computadoras hoy. La computadora común de hoy está modelada y construida sobre la Máquina Turing, que, para simplificar, es un modelo abstracto / teórico para la computación. Este modelo teórico se basa en la base de la informática, y todos los dispositivos informáticos que utilizamos hoy en día, desde servidores de alta gama hasta teléfonos de bolsillo, funcionan porque la base subyacente es sólida.

Considere el análisis de algoritmos. En términos simples, el análisis de algoritmos y la teoría de la complejidad del tiempo se han utilizado para clasificar los problemas (por ejemplo, P, NP, EXP, etc.), así como la forma en que se comportan los algoritmos. al intentar resolver diferentes problemas en diferentes clases.

Suponga que uno de sus amigos consigue un trabajo en algún lugar X y, mientras está allí, un gerente hace algunas solicitudes simples, como estos ejemplos:

Ej 1: Tenemos una gran flota de vehículos de reparto que visitan diferentes ciudades en varios estados. Necesitamos usted para implementar un sistema para determinar cuál es la ruta más corta para cada vehículo y elegir la opción óptima entre todas las posibilidades. ¿Puedes hacerlo?

Pensando que la teoría es 'inútil', sus amigos no se dan cuenta de que se les acaba de dar el Problema del vendedor ambulante (TSP) y comienzan a diseñar este sistema sin pensarlo dos veces, solo para descubrir su ingenuo intento de verificarlos. > todas las posibilidades, como se solicitó originalmente, son tan lentas que su sistema no se puede utilizar para ningún propósito práctico.

De hecho, no tienen idea de por qué el sistema funciona con un " aceptable " nivel cuando se verifican 5 ciudades, pero se vuelve muy lento en 10 ciudades, y simplemente se congela al subir a solo 40 ciudades. Razonan que es solo & Quot; 2x y 8x más ciudades que la prueba de 5 ciudades & Quot; y me pregunto por qué el programa no requiere simplemente " 2x y 8x más tiempo " respectivamente ...

Comprender la teoría les habría permitido darse cuenta de lo siguiente, al menos de un vistazo:

Es el TSP
El TSP es NP-duro
El orden de crecimiento de su algoritmo es O(n!)

Los números hablan por sí mismos:

+--------------+-------+-----------------------------------------------------------------+
|  No. Cities  | O(N!) |  Possibilities                                                  |
+--------------+-------+-----------------------------------------------------------------+
|       5      |   5!  | 120                                                             |
|      10      |  10!  | 3,628,800                                                       |
|      40      |  40!  | 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000 |  <-- GG
+--------------+-------+-----------------------------------------------------------------+

Podrían haberse dado cuenta desde el principio de que su sistema no iba a funcionar como imaginaban. El sistema luego se consideró poco práctico y se canceló después de que se haya asignado una cantidad significativa de tiempo, esfuerzo y otros recursos al proyecto, y finalmente se desperdició en el proyecto, y todo porque el pensamiento & "; La teoría es inútil &" ;.

Entonces, después de este fracaso, los gerentes piensan & "Bueno, tal vez ese sistema fue subestimado; después de todo, hay MUCHAS ciudades en nuestro país y nuestras computadoras simplemente no son tan rápidas como las necesitamos para que nuestro sistema recientemente cancelado haya sido un éxito " ;.

El equipo de administración culpa a las computadoras lentas como la causa del fracaso del proyecto. Después de todo, no son expertos en teoría de CS, no es necesario que lo sean, y aquellos que se supone que son expertos en el tema y podrían haberles informado, no lo hicieron.

Pero tienen otro proyecto en mente. Una más simple en realidad. Vienen la semana después y preguntan lo siguiente:

Ej 2: Tenemos solo unos pocos servidores y tenemos programadores que siguen enviando programas que, por razones desconocidas, terminan en ciclos infinitos y acaparando los servidores. Necesitamos usted para escribir un programa que procesará el código que se envía y detectar si el programa enviado causará un ciclo infinito durante su ejecución o no, y decidir si se debe permitir que el programa enviado se ejecute sobre esta base. ¿Puedes hacerlo?

Tu querido amigo acepta el desafío nuevamente y se pone a trabajar de inmediato. Después de varias semanas de trabajo, no hay resultados, su amigo está estresado y no sabe qué hacer. Otro fracaso más ... tu amigo ahora se siente & "; Tonto &"; por no haber podido resolver este " problema simple " ... después de todo, la solicitud en sí misma lo hizo sonar simple.

Desafortunadamente, tu amigo, mientras insiste en que " la teoría es inútil " no se dio cuenta de que la solicitud, supuestamente simple, era en realidad un problema insoluble sobre la capacidad de decisión (es decir, el problema de detención en sí), y que no había una solución conocida para ello. Era una tarea imposible.

Por lo tanto, incluso comenzar a trabajar para resolver ese problema en particular fue un error evitable y evitable. Si se hubiera implementado el marco teórico para comprender lo que se solicitaba, podrían haber propuesto una solución diferente y alcanzable ... como implementar un proceso de monitoreo que simplemente kill -SIGTERM <id> de cualquier proceso de usuario (según una lista de usuarios) que monopoliza la CPU durante un intervalo arbitrario / razonable bajo ciertos supuestos (por ejemplo, sabemos que cada ejecución del programa debería haber finalizado en 10 minutos, por lo que cualquier instancia en ejecución durante más de 20 minutos debe estar kill ed).

En conclusión, la práctica sin la teoría es como un edificio sin una base . Tarde o temprano, la cantidad correcta de presión desde el ángulo correcto hará que se colapse sobre sí misma . Sin excepciones.

¿Alguna vez lo usó en su codificación diaria?

Sí, pero no directamente . Más bien, confiamos en él indirectamente . La advertencia aquí es que los diferentes conceptos teóricos serán más o menos aplicables dependiendo del dominio del problema en el que estés trabajando.

Seguramente, nosotros:

usar computadoras diariamente, que se basa en modelos computacionales (por ejemplo, máquinas de turing)
escribir código, que se basa en la teoría de computabilidad (por ejemplo, lo que es incluso computable) y el cálculo lambda (por ejemplo, para lenguajes de programación)
confíe en la teoría y los modelos de color (por ejemplo, modelos de color RGB y CMYK) para pantallas de color e impresión, etc.
Teoremas de Euler en gráficos de computadora para que se puedan construir matrices para rotar objetos sobre ejes arbitrarios, y así sucesivamente ...

Es un hecho que alguien que simplemente usa un avión para viajar no necesita comprender la teoría que incluso permitió que los aviones se construyeran y volaran en primer lugar ... pero cuando alguien está se espera que construya dichas máquinas y las haga funcionar ... ¿realmente puede esperar un buen resultado de alguien que no entiende ni siquiera los principios de vuelo?

¿Fue realmente una coincidencia que, durante la mayor parte de la historia, nadie fue capaz de construir una máquina voladora (y algunos incluso murieron probando la suya) hasta que los hermanos Wright entendieron ciertos conceptos teóricos sobre el vuelo y lograron ponerlos en práctica ?

No es casualidad. Hoy tenemos mucha tecnología de trabajo porque las personas que los construyeron entendieron y aplicaron los principios teóricos que les permitieron trabajar en primer lugar.

Supongo que depende del campo en el que entres.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow