Quando è utile l'informatica teorica?

https://stackoverflow.com/questions/235394

04-07-2019
|

Domanda

In classe, abbiamo appreso del problema dell'arresto, delle macchine di Turing, delle riduzioni, ecc. Molti compagni di classe stanno dicendo che questi sono tutti concetti astratti e inutili, e non ha senso conoscerli (cioè, puoi dimenticarli una volta il corso è finito e non perdere nulla).

Perché la teoria è utile? Lo usi mai nella tua codifica quotidiana?

Soluzione

Quando mi sono laureato, ho pensato di essere alla pari con tutti gli altri: " Ho un BS in CS e quindi molte altre persone, e tutti possiamo essenzialmente fare le stesse cose . " Alla fine ho scoperto che la mia ipotesi era falsa. Mi sono distinto e il mio background ha avuto molto a che fare con questo, in particolare la mia laurea.

Sapevo che c'era un " leggero " differenza, in quanto avevo un " B.S. " in CS perché il mio college è stato uno dei primi (presumibilmente n. 2 nel 1987) nella nazione a ricevere l'accreditamento per il suo programma di laurea in CS, e mi sono laureato in seconda classe per ottenere quel riconoscimento. All'epoca non pensavo che importasse molto.

Avevo notato anche al liceo e al college che ho fatto particolarmente bene al CS - molto meglio dei miei coetanei e persino meglio di molti dei miei insegnanti. Mi è stato chiesto molto aiuto, ho fatto un po 'di tutoraggio, mi è stato chiesto di aiutare con un progetto di ricerca e mi è stato permesso di fare uno studio indipendente quando nessun altro lo era. Sono stato felice di poterti aiutare, ma non ho pensato molto alla differenza.

Dopo il college (USAFA), ho trascorso quattro anni nell'Aeronautica militare, due dei quali stavano applicando la mia laurea in CS. Lì ho notato che pochissimi dei miei colleghi avevano una laurea o addirittura una formazione relativa ai computer. L'Air Force mi ha inviato a cinque mesi di addestramento per la certificazione, dove ho nuovamente riscontrato una mancanza di titoli o addestramento. Ma qui ho iniziato a notare la differenza: è diventato del tutto evidente che molte delle persone che ho incontrato non sapevano VERAMENTE cosa stavano facendo, e questo includeva le persone con formazione o titoli. Consentitemi di illustrare.

Nella mia formazione per la certificazione dell'aeronautica c'erano un totale di tredici persone (incluso me). Come ufficiali dell'aeronautica o l'equivalente, avevamo tutti i gradi BS. Ero nel mezzo in base all'età e al grado (ero un O-2 tra sei O-1 e sei O-3 e superiori). Alla fine di questo addestramento, l'Aeronautica ci ha timbrato tutti ugualmente competenti per acquisire, costruire, progettare, mantenere e far funzionare QUALSIASI sistema informatico o di comunicazione per QUALSIASI parte del Dipartimento della Difesa.

Tuttavia, dei tredici di noi, solo sei avevano una laurea in informatica; gli altri sette avevano gradi che vanno dall'aeronautica alla chimica / biologia alla psicologia. Di noi sei laureato in CS, ho appreso che due non avevano mai scritto un programma di alcun tipo e non avevano mai usato un computer più che casualmente (scrivere documenti, giocare, ecc.). Ho imparato che altri due di noi avevano scritto esattamente un programma su un singolo computer durante il loro corso di laurea in CS. Solo un'altra persona e io stessi avevamo scritto più di un programma o usato più di un tipo di computer - in effetti, abbiamo scoperto che noi due avevamo scritto molti programmi e usato molti tipi di computer.

Verso la fine della nostra formazione di cinque mesi, alla nostra classe è stato assegnato un progetto di programmazione e siamo stati divisi in quattro gruppi per intraprenderlo separatamente. I nostri istruttori hanno diviso la classe per diffondere la quot &; Talento di programmazione & Quot; in modo equo e hanno assegnato ruoli di team leader, responsabile tecnico e sviluppatore. A ciascun gruppo è stata data una settimana per implementare (in Ada) un'interfaccia utente a schermo intero, basata su testo (questo era il 1990) per un simulatore di volo sopra una libreria di meccanica di volo fornita dall'istruttore. Sono stato assegnato come responsabile tecnico per la mia squadra di quattro persone.

Il mio team leader (che non aveva una laurea in informatica) ha chiesto agli altri tre di dividere il progetto in compiti e poi ne ha assegnato un terzo a ciascuno di noi. Ho terminato il mio terzo dei compiti entro la metà di quel primo giorno, quindi ho trascorso il resto della giornata aiutando gli altri miei due compagni di squadra, parlando con il mio capo squadra (BSing; ^) e giocando sul mio computer.

La mattina successiva (secondo giorno), il mio team leader mi informò privatamente che i nostri altri due compagni di squadra non avevano fatto progressi (non si poteva effettivamente scrivere un " & se quot; dichiarazione che avrebbe compilato), e mi ha chiesto di assumere il loro lavoro. Ho completato l'intero progetto entro la metà del pomeriggio e il mio team ha trascorso il resto della giornata a pilotare il simulatore.

L'altro ragazzo con il grado CS comparabile è stato anche assegnato come capo tecnico per la sua squadra, e hanno terminato entro la fine del terzo giorno. Hanno anche iniziato a pilotare il loro simulatore. Le altre due squadre non avevano finito, o addirittura fatto progressi significativi, alla fine della settimana. Non ci è stato permesso di aiutare altre squadre, quindi è stato lasciato a questo.

Nel frattempo, a metà giornata, avevo notato che il simulatore di volo sembrava comportarsi con " errato " ;. Dato che uno dei miei compagni di classe era laureato in aeronautica, glielo chiesi. Era sconcertato, poi confessò di non sapere davvero cosa facesse volare un aereo!?! Ero sbalordito! Si scopre che il suo intero corso di laurea riguardava la sicurezza e le indagini sugli incidenti - nessuna vera matematica o scienza dietro il volo. D'altra parte, avevo forse un minore in aeronautica (ricordi USAFA?), Ma avevamo progettato le ali ed eseguito veri e propri test in galleria del vento. Pertanto, ho trascorso tranquillamente il resto della settimana riscrivendo la libreria di meccanica di volo fornita dall'istruttore fino a quando il simulatore ha volato & Quot; right & Quot ;.

Da allora ho trascorso quasi due decenni come appaltatore e occasionalmente come dipendente, facendo sempre sviluppo di software più attività correlate (DBA, architetto, ecc.). Ho continuato a trovare più o meno lo stesso e alla fine ho rinunciato alla mia supposizione giovanile.

Quindi, cosa ho scoperto esattamente? Non tutti sono uguali, e questo va bene - non sono una persona migliore perché posso programmare in modo efficace, ma sono più utile SE è ciò di cui hai bisogno da me. Ho imparato che il mio background era davvero importante: crescere in una famiglia di elettricisti e ingegneri elettrici, kit di elettronica di costruzione, leggendo LETTERAMENTE ogni libro di computer nella scuola / biblioteche pubbliche perché non avevo accesso a un vero computer, poi mi trasferisco in una nuova città dove il mio liceo aveva i computer, quindi ottenere il mio computer come regalo, andare a scuole con computer di dimensioni e tipi diversi (da PC a mainframe), ottenere una laurea accreditata da una scuola di ingegneria MOLTO buona, dover scrivere molti programmi in diverse lingue su diversi tipi di computer, dover scrivere programmi pesanti (come la mia macchina virtuale con un linguaggio assembly personalizzato o un'implementazione di compressione Huffman, ecc.), dover risolvere i problemi da solo, costruendo i miei computer dalle parti e installando TUTTO il software, ecc.

Alla fine, ho appreso che le mie capacità sono costruite su una base di sapere come funzionano i computer dal livello elettrico in su - componenti elettronici discreti, circuiti, sottosistemi, interfacce, protocolli, bit, byte, processori, dispositivi, driver, librerie, programmi, sistemi, reti, fino ai massicci conglomerati di classe enterprise su cui lavoro abitualmente adesso. Quindi, quando la dannata cosa si comporta male, so esattamente COME e PERCHÉ. E so cosa non si può fare così come è possibile. E so molto di ciò che è stato fatto, di ciò che è stato provato e di ciò che è rimasto relativamente inesplorato.

Soprattutto, dopo aver appreso tutto ciò, ho imparato che non conosco una dannata cosa. Di fronte a tutto ciò che c'è potenzialmente da sapere, la mia conoscenza è minuscola.

E ne sono abbastanza contento. Ma ti consiglio di provare.

Altri suggerimenti

Storia vera:

Quando ho ottenuto il mio primo lavoro di programmazione fuori dalla scuola di specializzazione, i ragazzi che possedevano la compagnia per cui lavoravo erano piloti. Alcune settimane dopo essere stato assunto, uno di loro mi ha fatto questa domanda:

Ci sono 106 aeroporti in Arkansas. Potresti scrivere un programma che lo farebbe trova il percorso più breve necessario per atterrare in ognuno di essi?

Pensavo seriamente che mi stesse interrogando sulla mia conoscenza del Problema del commesso viaggiatore e della completezza NP. Ma si scopre che non lo era. Non ne sapeva nulla. Voleva davvero un programma che trovasse il percorso più breve. Fu sorpreso quando gli spiegai che c'erano 106 soluzioni fattoriali e trovare la migliore era un noto problema computazionalmente intrattabile.

Quindi questo è un esempio.

Certo, è utile.

Immagina uno sviluppatore che lavora su un motore modello. Sai il genere di cose ...

Blah blah blah ${MyTemplateString} blah blah blah.

Inizia in modo semplice, con un'espressione sfacciata e regolare per eseguire le sostituzioni.

Ma gradualmente i modelli diventano un po 'più elaborati e lo sviluppatore include funzionalità per la creazione di modelli di elenchi e mappe di stringhe. Per fare ciò, scrive una semplice piccola grammatica e genera un parser.

Diventando molto furbo, il template engine potrebbe eventualmente includere una sintassi per la logica condizionale, per visualizzare diversi blocchi di testo a seconda dei valori degli argomenti.

Qualcuno con un background teorico in CS riconoscerebbe che il linguaggio del modello sta lentamente diventando Turing completo, e forse il modello Interprete sarebbe un buon modo per implementarlo.

Avendo creato un interprete per i template, un informatico potrebbe notare che la maggior parte delle richieste di template sono duplicati, rigenerando gli stessi risultati più e più volte. Quindi viene sviluppata una cache e tutte le richieste vengono instradate attraverso la cache prima di eseguire la trasformazione costosa.

Inoltre, alcuni modelli sono molto più complessi di altri e richiedono molto più tempo per il rendering. Forse qualcuno ha l'idea di stimare l'esecuzione di ciascun modello prima di renderlo.

Ma aspetta !!! Qualcuno del team sottolinea che, se il linguaggio del modello è davvero Turing completo, il compito di stimare il tempo di esecuzione di ogni operazione di rendering è un'istanza del problema Halting !! Yikes, non farlo !!!

La cosa sulla teoria, in pratica, è che tutta la pratica si basa sulla teoria. Teoricamente.

Le cose che uso di più:

complessità computazionale per scrivere algoritmi che si ridimensionano con grazia
comprensione di come funzionano l'allocazione della memoria, il paging e la memorizzazione nella cache della CPU in modo da poter scrivere codice efficiente
comprensione delle strutture di dati
comprensione di threading, blocco e problemi associati

Per quanto riguarda quella roba su macchine di Turing ecc., penso che sia importante perché definisce i vincoli in base ai quali tutti noi operiamo. Questo è importante da apprezzare.

è la differenza tra l'apprendimento dell'algebra e l'insegnamento su come usare una calcolatrice

se conosci l'algebra, ti rendi conto che lo stesso problema può manifestarsi in forme diverse e comprendi le regole per trasformare il problema in una forma più concisa

se sai solo come usare una calcolatrice, potresti perdere molto tempo a premere i pulsanti su un problema che è (a) già risolto, (b) non può essere risolto o (c) è come un altro problema (risolto o irrisolto) che non riconosci perché è in una forma diversa

fingi, per un momento, che l'informatica sia fisica ... la domanda sembrerebbe sciocca?

Un mio amico sta lavorando su una lingua con alcuni modelli. Mi è stato chiesto di fare un piccolo consulto. Parte della nostra discussione riguardava la funzionalità del modello, perché se i modelli fossero Turing completi, avrebbero dovuto davvero considerare le proprietà VM-ish e come / se il loro compilatore l'avrebbe supportato.

La mia storia è a questo punto: la teoria degli automi è ancora insegnata, perché ha ancora rilevanza. Il problema di arresto esiste ancora e fornisce un limite a ciò che puoi fare.

Ora, queste cose hanno rilevanza per un jockey di database che martella il codice C #? Probabilmente no. Ma quando inizi a passare a un livello più avanzato, vorrai capire l'amplificatore di root &; fondazioni.

Sebbene non li applichi direttamente nel lavoro quotidiano, so che la mia educazione all'informatica formale ha influenzato il mio processo di pensiero. Evito certamente alcuni errori fin dall'inizio perché ho insegnato le lezioni apprese dagli approcci formali.

Potrebbe sembrare inutile mentre lo stanno imparando; ma scommetto che il tuo compagno di classe alla fine incontrerà un problema in cui useranno ciò che è stato loro insegnato, o almeno i modelli di pensiero dietro di esso ...

Wax on ... Wax off ... Wax on ... Wax off ... Cosa c'entra comunque con il Karate?

In un lavoro mi è stato assegnato il compito di migliorare l'algoritmo di tracciamento della rete del nostro modello di distribuzione elettrica poiché quello che stavano usando era troppo lento. La rete trifase era essenzialmente tre n-alberi (poiché i circuiti non sono ammessi nelle reti elettriche). I nodi di rete si trovavano nel database e alcuni membri del team originale non riuscirono a capire come costruire un modello in memoria, quindi la traccia veniva eseguita da SELECT di profondità successivi sul database, filtrando su ogni fase. Quindi, per rintracciare un nodo, dieci nodi dalla sottostazione richiederebbero almeno 10 query di database (i membri del team originale erano whizz di database, ma mancava di un background decente negli algoritmi).

Ho scritto una soluzione che ha trasformato le 3 reti n-tree di nodi dal database in una struttura di dati in cui ogni nodo è stato memorizzato una volta in un array di strutture di nodi e la relazione n-tree è stata convertita in tre alberi binari usando doppiamente- puntatori collegati all'interno dell'array in modo che la rete possa essere facilmente tracciata in entrambe le direzioni.

Era almeno due ordini di grandezza più veloce, tre su tracce a valle veramente lunghe.

La cosa triste era che dovevo praticamente insegnare a una classe in n-alberi, alberi binari, puntatori ed elenchi doppiamente collegati a molti altri programmatori che erano stati addestrati su database e VB per far loro capire gli algoritmi.

È una dicotomia classica, tra " how " e " what " ;. I tuoi compagni di classe guardano & Quot; come & Quot; per programmare software e sono molto focalizzati sul focus vicino; da quella prospettiva, quella dell'attuazione, sembra che conoscere cose come l'arresto degli stati e le macchine di Turing non sia importante.

quot; Come quot &; è però molto poco del lavoro effettivo che ci si aspetta che tu faccia con l'Informatica. In effetti, gli ingegneri di maggior successo che conosco probabilmente lo metterebbero a meno del 20 percento del lavoro effettivo. & Quot; Che quot &; fare è di gran lunga più importante; e per questo, i fondamenti dell'informatica sono fondamentali. & Quot; Che quot &; vuoi fare si riferisce molto più alla progettazione che all'implementazione; e il buon design è ... beh, chiamiamolo " non banale " ;.

" Esistono due modi per costruire una progettazione software: un modo è renderlo così semplice che ovviamente non ci sono carenze, e l'altro è renderlo così complicato che non ci sono carenze evidenti. Il primo metodo è molto più difficile. & Quot; - C.A.R. Hoare

Buona fortuna con i tuoi studi!

Penso che la comprensione dei modelli fondamentali di calcolo sia utile: in pratica non sarà mai necessario essere in grado di tradurre una macchina di Turing in una macchina di registro, ma imparare a vedere che due problemi molto diversi sono in realtà esempi dello stesso concetto è un'abilità critica.

La maggior parte della conoscenza non è " pratica " ;, ma ti aiuta a collegare i punti in modi che non puoi anticipare, o ti dà un vocabolario più ricco per descrivere idee più complesse.

Non sono i problemi specifici che studi che contano, sono i principi che impari studiandoli. Uso concetti su algoritmi, strutture dati, linguaggi di programmazione e sistemi operativi ogni giorno nel mio lavoro. Se lavori come programmatore, prenderai sempre delle decisioni che incidono sulle prestazioni del sistema. Devi fare una solida base nei concetti astratti fondamentali per fare le scelte giuste.

Se lavori in un'azienda che fa lavori innovativi, è importante essere in grado di comunicare ad architetti e sviluppatori quali sono i vantaggi. C'è molto clamore su tutti i tipi di tecnologie e posizionarsi può essere difficile. Quando inquadra la tua innovazione in termini scientifici e teorici, sei decisamente avvantaggiato e i clienti percepiscono che sei la cosa reale. Posso dirlo alla gente: esiste un nuovo modo di gestire lo stato, la codifica e il non determinismo (cioè le complessità) e potete sicuramente essere più produttivi di quanto lo sia oggi.

Se consideri a lungo la tua carriera, l'apprendimento della teoria ti darà profondità, la profondità di cui hai bisogno per crescere. Il ritorno sull'investimento nell'apprendimento del 5o o 6o linguaggio di programmazione sarà molto inferiore rispetto all'apprendimento del 2o e 3o. L'esposizione alla teoria ti darà un senso per la vera ingegneria, su dove sono i gradi di libertà e su come puoi fare i giusti compromessi.

I concetti importanti 1) Stato, 2) Codifica, 3) Non determinismo. Se non li conosci, non ti aiuteranno. Ciò che la teoria dovrebbe fornirti è il quadro generale e il senso di come i concetti di base si incastrano. Dovrebbe aiutarti ad affinare il tuo intuito.

Esempio: alcune delle risposte sopra menzionano il problema dell'arresto e le macchine di Turing. Quando mi sono imbattuto nel giornale di Turing al college non mi sono sentito affatto illuminato. Un giorno mi sono imbattuto nel teorema di incompletezza di Goedel e in particolare nella numerazione di Goedel. Le cose hanno iniziato ad avere molto senso. Anni dopo ho letto di Georg Cantor in una libreria. Ora ho iniziato davvero a capire le macchine di Turing e il problema dell'arresto. Prova tu stesso e cerca & Quot; Cantor's Diagonal Argument & Quot; su Wikipedia. È una delle cose più fantastiche che intellettualmente tu abbia mai incontrato.

Spunti di riflessione: una tipica macchina di Turing non è l'unico modo per progettare una macchina di transizione di stato. Una macchina di Turing con due anziché un nastro ti darebbe molta più velocità per un numero di algoritmi. http://www.math.ucla.edu/~ynm/papers/ eng.ps

Puoi esporti a queste intuizioni in modo più efficiente di quello che ho fatto leggendo questo libro. Link in fondo a questo post. (Per lo meno, controlla il sommario su Amazon per avere un'idea di cosa si tratta):

Ho trovato sensazionale il libro di Rosenberg. http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/ dp / 0387096388 Se hai un solo libro sulla teoria IMHO, questo dovrebbe essere quello.

Dopo essermi laureato in CS, ho pensato in modo simile: l'intero gruppo di teorie che abbiamo studiato sono completamente inutili nella pratica. Ciò si è rivelato giusto per un breve periodo di tempo, tuttavia nel momento in cui si affrontano compiti complessi, la teoria è sicuramente PIÙ VALIDA della pratica. ognuno dopo pochi anni di programmazione può scrivere alcuni programmi che " funzionano " ma non tutti sono in grado di capire come. indipendentemente da ciò che la maggior parte di noi tratterà a un certo punto di problemi di prestazioni, ritardi di rete, preclusione, scalabilità ecc. A questo punto la teoria è critica. al fine di progettare una buona soluzione quando si ha a che fare con sistemi complessi è molto importante sapere come funziona la gestione della memoria, i concetti di processo e thread, come viene loro assegnata la memoria o strutture dati efficienti per le prestazioni e così via.

Una volta, ad esempio, stavo lavorando a un progetto che includeva numerosi calcoli matematici e ad un certo punto il nostro software non funzionava. durante il debug ho capito che dopo qualche operazione matematica ho ricevuto un numero DOPPIO di un valore di 1.000000000002 ma dal punto di vista matematico non poteva essere & GT; 1 che in una fase successiva del programma stava dando la leggendaria eccezione NaN . ho trascorso un po 'di tempo a capirlo, ma se avessi prestato maggiore attenzione al " approssimazione di Double e Float " lezione che non avrei perso tempo.

Non lo uso quotidianamente. Ma mi ha dato molta comprensione che mi aiuta ogni giorno.

Ho scoperto che tutto ciò di cui ho bisogno per la felicità quotidiana del mondo teorico CS è l'espressione del mantra " Basso accoppiamento e Alta coesione " ;. Roger S. Pressman lo ha reso accademico prima di Steve McConnell l'ha reso di moda.

Ya, generalmente utilizzo diagrammi di stato per progettare la forma e il flusso del programma. Una volta che funziona in teoria, inizio a scrivere codice e test, controllando gli stati mentre vado.

Trovo che siano anche uno strumento utile per spiegare il comportamento di un processo ad altre persone.

Semplice. Ad esempio: se sto usando RSACryptoServiceProvider mi piacerebbe sapere cos'è e perché posso fidarmi di esso.

Perché i modelli C ++ sono in realtà una sorta di calcolo lambda. Vedi www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf

Sto studiando per il mio corso di algoritmi distribuiti ora. C'è un capitolo sulla tolleranza agli errori e contiene alcune prove sul limite superiore di quanti processi possono fallire (o comportarsi male) in modo che l'algoritmo distribuito possa gestirlo correttamente.

Per molti problemi, il limite per i processi di comportamento scorretto è fino a un terzo del numero totale di processi. Questo è abbastanza utile secondo me perché sai che è inutile cercare di sviluppare un algoritmo migliore (sotto ipotesi date).

Anche se i corsi teorici non verranno utilizzati direttamente, potrebbe aiutarti a pensare meglio a qualcosa.

Non sai cosa ti chiederà di fare il tuo capo, potresti dover usare qualcosa che ritieni non sia vantaggioso, come ha detto Jeffrey L. Whitledge.

Ad essere sincero, non sono d'accordo con molte risposte qui. Ho scritto il mio primo compilatore (per divertimento; davvero ho troppo caffè / tempo libero) senza aver seguito un corso di compilatori; fondamentalmente ho appena scansionato il codice per un altro compilatore e seguito il modello. Potrei scrivere un parser in C dalla parte superiore della mia testa, ma non penso che potrei ricordare come disegnare un automa pushdown se la mia vita dipendesse da esso.

Quando ho deciso che volevo inserire l'inferenza del tipo nel mio linguaggio di programmazione giocattolo (imperativo), ho prima esaminato probabilmente cinque documenti, fissando qualcosa chiamato " digitato lambda calculus " andando cosa .... il .... **** ....? All'inizio ho provato a implementare qualcosa con & Quot; variabili generiche & Quot; e " variabili non generiche " e non avevo idea di cosa stesse succedendo. Poi ho scartato tutto e mi sono seduto lì con un taccuino a capire come potevo implementarlo praticamente con il supporto per tutto ciò di cui avevo bisogno (sotto-digitazione, funzioni di prima classe, tipi parametrizzati, ecc.) Con un paio di giorni di riflessione & amp; scrivendo programmi di test, ho spazzato via più di una settimana per cercare di capire la merda teorica.

Conoscere le basi dell'informatica (ovvero come funziona la memoria virtuale, come funzionano i filesystem, threading / scheduling, SMP, strutture di dati) si è rivelato MOLTO utile. La teoria della complessità e le cose di Big-O si sono talvolta rivelate utili (specialmente utili per cose come la progettazione RDBMS). Il problema di arresto e gli automi / teoria di Turing Machine? Mai.

So che questo è vecchio, ma la mia breve risposta a coloro che affermano che la teoria è "inutile" e che possono esercitare la loro professione senza di essa è questa:

Senza la teoria di base, non esiste nessuna pratica.

Perché la teoria è utile?

La teoria è la base sottostante sulla quale sono costruite altre cose. Quando la teoria è applicata , la pratica è il risultato.

Prendi in considerazione i computer oggi. Il computer comune oggi è modellato e costruito sulla parte superiore della Turing Machine, che, per semplicità, è un modello astratto / teorico per il calcolo. Questo modello teorico si trova alla base dell'informatica e tutti i dispositivi informatici che usiamo oggi, dai server di fascia alta ai telefoni tascabili, funzionano perché la base sottostante è solida.

Considera l'analisi dell'algoritmo. In termini semplici, l'analisi dell'algoritmo e la teoria della complessità temporale sono state utilizzate per classificare i problemi (ad es. P, NP, EXP, ecc.) così come il comportamento degli algoritmi quando si cerca di risolvere problemi diversi in classi diverse.

Supponi che uno dei tuoi amici ottenga un lavoro in un posto X e, mentre è lì, un manager fa alcune semplici richieste, come questi esempi:

Ex 1: abbiamo una vasta flotta di veicoli per le consegne che visitano diverse città in diversi stati. Abbiamo bisogno di tu di implementare un sistema per capire quale sia il percorso più breve per ogni veicolo e scegliere quello ottimale tra tutte le possibilità. Puoi farlo?

Pensando che la teoria sia "inutile" i tuoi amici non si rendono conto di aver appena ricevuto il Problema del commesso viaggiatore (TSP) e iniziano a progettare questo sistema senza pensarci due volte, solo per scoprire il loro ingenuo tentativo di controllarli > tutte le possibilità, come inizialmente richiesto, sono così lente che il loro sistema è inutilizzabile per qualsiasi scopo pratico.

In realtà, non hanno nessuna idea del perché il sistema funzioni con un " accettabile " livello quando si controllano 5 città, ma diventa molto lento in 10 città e si blocca quando si sale a solo 40 città. Ritengono che sia solo & Quot; 2x e 8x città in più rispetto al test di 5 città & Quot; e mi chiedo perché il programma non richiede semplicemente " 2x e 8 volte più tempo " rispettivamente ...

Comprendere la teoria avrebbe permesso loro di realizzare quanto segue, almeno a colpo d'occhio:

È il TSP
Il TSP è NP-difficile
L'ordine di crescita del loro algoritmo è O(n!)

I numeri parlano da soli:

+--------------+-------+-----------------------------------------------------------------+
|  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
+--------------+-------+-----------------------------------------------------------------+

Avrebbero potuto capire fin dall'inizio che il loro sistema non funzionava come immaginavano. Il sistema è stato in seguito considerato poco pratico e cancellato dopo una notevole quantità di tempo, sforzi e altre risorse erano state allocate e alla fine sprecate nel progetto - e tutto perché il pensiero & Quot; la teoria è inutile & Quot ;.

Quindi, dopo questo fallimento, i gestori pensano " Beh, forse quel sistema è stato sottovalutato; dopotutto, ci sono MOLTE città nel nostro paese e i nostri computer non sono così veloci come abbiamo bisogno che siano perché il nostro sistema recentemente annullato abbia avuto successo " ;.

Il team di gestione incolpa i computer lenti come causa del fallimento del progetto. Dopotutto, non sono esperti di teoria CS, non hanno bisogno di esserlo, e quelli che dovrebbero essere gli esperti sull'argomento e avrebbero potuto informarli, non lo hanno fatto.

Ma hanno in mente un altro progetto. Uno più semplice in realtà. Arrivano la settimana dopo e chiedono quanto segue:

Ex 2: Abbiamo solo pochi server e abbiamo programmatori che continuano a presentare programmi che, per motivi sconosciuti, finiscono in cicli infiniti e riducono i server. Abbiamo bisogno di tu scrivere un programma che elaborerà il codice inviato e rilevare se il programma inviato causerà un ciclo infinito durante l'esecuzione o meno e decidere se consentire l'esecuzione del programma inviato su questa base. Puoi farlo?

Il tuo caro amico accetta di nuovo la sfida e si mette subito al lavoro. Dopo diverse settimane di lavoro, non ci sono risultati, il tuo amico è stressato e non sa cosa fare. Ancora un altro fallimento ... il tuo amico ora sente & Quot; stupido & Quot; per non essere stato in grado di risolvere questo " semplice problema " ... dopo tutto, la richiesta stessa ha reso suono semplice.

Sfortunatamente, il tuo amico, pur insistendo sul fatto che " la teoria è inutile " non si rendeva conto che la richiesta, presumibilmente semplice, era in realtà un problema irrisolvibile sulla decidibilità (cioè il problema di arresto stesso) e che non esisteva una soluzione nota per esso. È stato un compito impossibile.

Pertanto, anche iniziare a lavorare per risolvere quel particolare problema è stato un errore evitabile e prevenibile. Se il quadro teorico per capire cosa fosse stato richiesto fosse in atto, avrebbero potuto semplicemente proporre una soluzione diversa e realizzabile ... come implementare un processo di monitoraggio che può semplicemente kill -SIGTERM <id> di qualsiasi processo utente (come da un elenco di utenti) che monopolizza la CPU per un intervallo arbitrario / ragionevole in base a determinati presupposti (ad esempio, sappiamo che ogni esecuzione del programma dovrebbe essere terminata entro 10 minuti, quindi qualsiasi istanza in esecuzione per 20+ minuti dovrebbe essere kill ed).

In conclusione, la pratica senza la teoria è come un edificio senza fondamenta . Prima o poi, la giusta quantità di pressione dall'angolo destro la farà collassare su se stessa . Nessuna eccezione.

Lo usi mai nella tua codifica quotidiana?

Sì, ma non direttamente . Piuttosto, ci affidiamo indirettamente . L'avvertenza qui è che differenti concetti teorici saranno più o meno applicabili a seconda del dominio del problema su cui stai lavorando.

Sicuramente, noi:

utilizza quotidianamente i computer, che si basa su modelli computazionali (ad es. macchine da turismo)
scrivi codice, che si basa sulla teoria della computabilità (ad es. cosa è persino calcolabile) e sul calcolo lambda (ad es. per linguaggi di programmazione)
si affida alla teoria e ai modelli di colore (ad es. modelli di colore RGB e CMYK) per display a colori e stampa, ecc.
Teoremi di Eulero nella computer grafica in modo che possano essere costruite matrici per ruotare oggetti attorno ad assi arbitrari, e così via ...

È un dato di fatto che qualcuno che semplicemente usa un aereo per viaggiare non ha bisogno di capire la teoria che ha persino permesso agli aerei di essere costruiti e volare in primo luogo ... ma quando qualcuno lo è dovrebbe costruire macchine dette e farle funzionare ... puoi davvero aspettarti un buon risultato da qualcuno che non capisce nemmeno i principi del volo?

È stata davvero una coincidenza che, per gran parte della storia, nessuno è stato in grado di costruire una macchina volante (e alcuni addirittura sono morti testando la loro) fino a quando i fratelli Wright non hanno capito alcuni concetti teorici sul volo e sono riusciti a metterli in pratica ?

Non è una coincidenza. Oggi disponiamo di molte tecnologie di lavoro perché le persone che le hanno costruite hanno compreso e applicato i principi teorici che hanno permesso loro di lavorare in primo luogo.

Immagino che dipenda dal campo in cui vai.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow