6
$\begingroup$

I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would it help to also know automata (for compilers, types, programming languages), computability and complexity?

If it would be wise to obtain more knowledge, what references can I read. For undergraduate education, I know basic stuff such as Hopcroft, Sipser, Ullman.

$\endgroup$
  • 10
    $\begingroup$ It is at least widely believed that more knowledge of any kind helps with just about anything. A better question would be the the contrapositive form: Is there a practical application which is impossible (or at least very difficult) without in depth theoretical knowledge? $\endgroup$ – François G. Dorais Apr 5 '13 at 14:10
  • 2
    $\begingroup$ yes, its a symbiosis. eg analyzing complexity of algorithms can be very theoretical and yet very applied/practical at the same time. note, similar to this question from opposite angle, how important is it to know how to program for TCS $\endgroup$ – vzn Apr 5 '13 at 18:05
  • $\begingroup$ I would have to say no, as a practitioner, you mostly need experience, and the theory of computation is not that helpful. It might be helpful to have some experience in deductive reasoning, but you don't need to study theory of computation for that, you can study just about anything which has a critical component. $\endgroup$ – Yuval Filmus Apr 5 '13 at 18:27
  • 1
    $\begingroup$ I think you should ask this from practitioners as you want to know if it helps them. I think the question is kind of off-topic here. If you want to ask for books to read, then again it is more suitable for Computer Science or Software Engineering. $\endgroup$ – Kaveh Apr 8 '13 at 21:22
  • $\begingroup$ I've found being able to do simple reductions by hand to be pretty helpful. Garey & Johnson is a really good reference. In general, it is certainly good to know whether the problem you're trying to solve is NP-complete, for example. $\endgroup$ – cannedprimates Apr 14 '13 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.