Argomenti importanti nella teoria del calcolo

Question

Durante i miei studi universitari ho dovuto imparare molto sulla teoria del calcolo. Ho studiato l'argomento per tre termini. Ho avuto un momento difficile e devo ammettere che ho dimenticato molto.

Mi chiedo se questo sia un problema personale, o se solo abbiamo dovuto imparare molte cose (più o meno) inutili.

Quindi la mia domanda è: Quali argomenti nel campo della teoria della computazione ritieni siano più importanti, quali parti meritano di essere studiate e quali argomenti utilizzi durante il tuo normale lavoro?

Personalmente, sono contento che ho sentito parlare le theory of languages (soprattutto i linguaggi regolari => espressioni regolari - quando possono essere applicati e quando non) sulle diverse time (and space) complexities, in particolare gli O (n) notazioni e.

ma abbiamo dovuto studiare molto di più, tra cui:

• teoria della computabilità
  • problema della terminazione
  • problemi semidecidibili
• teoria della complessità
  • p = NP?
• teoria della logica
  • calcolo proposizionale
  • logica dei predicati

E 'stato interessante sentire su questi argomenti, ma non sono sicuro di come necessario è di studiarli in profondità

So che questa domanda è soggettiva e le risposte differiranno molto a seconda del tuo lavoro quotidiano e dell'esperienza personale. Ma mi piacerebbe che lo sapesse di argomenti che potrebbero essere più interessanti di quanto ricordi.

Answer 1

Non sono sicuro di utilizzare direttamente sul lavoro tutto ciò che ho appreso in teoria delle classi di calcolo. Ma non penso che sia proprio questo il punto. Neanch'io uso direttamente tutto ciò che ho imparato nella geometria euclidea nelle scuole superiori. Ma quella era la lezione più importante che ho frequentato in tutte le scuole elementari.

La teoria del calcolo è un argomento molto interessante e saperlo bene può aiutarti solo nella vita. Non posso provarlo, ma so che è vero.

Scusate se non è molto di una risposta.

Answer 2

Quali argomenti nel campo della teoria della computazione pensi che siano più importanti

la domanda è vaga. Importante per chi?

quali parti vale la pena di conoscere?

Tutti valgono la pena di essere informati. Questo è un caso particolare del fatto che tutti gli sforzi umani sono intrinsecamente degni di essere appresi.

Se la tua domanda è "quali argomenti mi danno benefici maggiori del costo del mio tempo e degli sforzi per studiarli?" allora questa è una domanda alla quale solo tu puoi rispondere da solo. Il vantaggio per me di studiare, per esempio, la storia dell'antica Grecia, non ha nulla a che fare con il modo in cui influisce sulla mia capacità di portare a termine il mio lavoro.

Quali argomenti utilizzi durante il tuo normale lavoro?

Uso tutti gli argomenti elencati: teoria del linguaggio, analisi degli ordini asintotici, decidibilità, teoria della complessità, sistemi di dimostrazione del teorema e così via.

Non li uso in un formale senso; Non sono seduto alla mia scrivania usando il Teorema Master per derivare l'analisi degli ordini per algoritmi specifici. Li uso nel senso che è molto utile essere in grado di prendere una caratteristica linguistica proposta e capire rapidamente se implementarla richiederebbe al compilatore di risolvere un problema che è lineare, polinomiale, esponenziale, NP-rigido o equivalente a il problema dell'arresto.

Ad esempio, è abbastanza facile calcolare che la risoluzione di sovraccarico in C# 3 su lambda nidificata sia NP-difficile, ma non equivalente al problema di interruzione. Sappiamo quindi che (1) è uno spreco del nostro tempo persino provare a risolvere il problema in tempo polinomiale, e (2) almeno sappiamo che una soluzione può essere trovata in un certo periodo di tempo, e (3) noi potrebbe venire con una semplice euristica per rilevare gli scenari sbagliati e fallire velocemente se fosse necessario.

Io personalmente non uso molto i sistemi di prove, anche se è utile pensare ai problemi come a un caso speciale di un dimostratore di teoremi. Ci sono tutti i tipi di caratteristiche del linguaggio che sono equivalenti ai problemi che si presentano a un dimostratore di teoremi, in particolare nel campo dell'inferenza di tipo e dell'analisi del flusso. Fortunatamente nessuna delle caratteristiche di C# in realtà richiede l'implementazione di un dimostratore di teoremi; altre lingue implementate in questo edificio hanno quella proprietà, come F #.