14
$\begingroup$

I am a pretty proficient software engineer, but I don't know much theory. I want to learn more theory. Particular topics that I am interested in are: computational complexity, formal languages, and type theory. But I am at a loss as for how to begin learning about these fields.

What resources would you recommend to someone who wants to learn more theory through self-study? Are there any theoretical computer science self-study guides for software engineers?

$\endgroup$
  • 3
    $\begingroup$ It depends what you want to learn about. Arora-Barak gives a thorough introduction to computational complexity theory (and is freely available online). So that is a good place to start. $\endgroup$ – Thomas Nov 27 '15 at 18:52
  • 4
    $\begingroup$ Have you taken theory courses at college/university like data structures, algorithms, etc.? If you haven't taken typically required undergraduate theory courses then textbooks for those courses would be a good starting point. After that you can have a look at wikipedia articles, our list of books and list of videos, online courses at Coursera/Udacity/EdX/... Coursera has pretty nice theory courses. $\endgroup$ – Kaveh Nov 27 '15 at 22:38
  • $\begingroup$ What did you study in the college? $\endgroup$ – Omar Shehab Nov 28 '15 at 7:09
  • $\begingroup$ What sort of languages do you program in? Much of theoretical CS can be learned in tandem with something concrete. For instance if you want to learn more about formal languages, regular languages/expressions (i.e. regexp's) are a good place to start as is learning about for compilers. For type theory, you might want to play with a statically typed language like haskell, F# or ML. $\endgroup$ – Baby Dragon Nov 29 '15 at 7:03
  • $\begingroup$ try New Turing Omnibus by Dewdney as a broad/ accessible intro ref/ survey/ cross section. see also pop science books that inspire TCS $\endgroup$ – vzn Dec 2 '15 at 23:46
7
$\begingroup$

It's a wide field with a few quite different areas.

I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation."

The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference between writing programs and being scientific.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I don't know if this changes anything, but I do actually have some background in proof-based mathematics (I probably should have mentioned that in the question). I've done proof-based real analysis, point-set topology, and abstract algebra. $\endgroup$ – Henry H. Nov 27 '15 at 21:18
  • $\begingroup$ Then you'll be able to work through it very quickly :) $\endgroup$ – Kate F Nov 27 '15 at 21:21
  • $\begingroup$ its a difference but not the difference. CS entails many other principles etc $\endgroup$ – vzn Nov 29 '15 at 1:09
  • $\begingroup$ I don't think that the need for rigor is really a difference between programming and math. Programming and proving theorems are imho very related tasks (cf. Curry-Howard Isomorphism), and hardly any non-mathematical task requires more rigor than programming. Compilers are much less forgiving about errors than humans who read proofs. $\endgroup$ – Jan Johannsen Nov 30 '15 at 8:51
  • 2
    $\begingroup$ @JanJohannsen I'd quite disagree - for example, see Undefined Behaviour for C. $\endgroup$ – Kate F Nov 30 '15 at 14:40
9
$\begingroup$

There are several ways to learn about type theory. For a working programmer, Types and Programming Languages by B. Pierce is a good start. Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics, I recommend G. Winskel's, The Formal Semantics of Programming Languages: An Introduction. With T. Nipkow, G. Klein, Concrete Semantics, a variant of Winskel's book has been formalised for the Isabelle/HOL interactive proof assistant. I suspect it's really difficult to get to grips with a prover just from this (or any) book, you'd want an expert nearby to ask questions. If you want a more mathematical approach to type-theory, you could look at J. R. Hindley, J. P. Seldin, Lambda-Calculus and Combinators: An Introduction, or H. Barendregt's, Lambda Calculi with Types. Although I wouldn't recommend starting from Barendregt.

If you want a single recommendation, I'd say read all of Pierce except Part VI (Higher-Order Systems), and implement the toy languages the book discusses. You'll end up with a strong grounding in type theory, and probably a better programmer too.

$\endgroup$
2
$\begingroup$

I recommend Computability, Complexity, and Languages by Martin Davis, Ron Sigal and Elaine Weyuker.

$\endgroup$
  • $\begingroup$ That's a beautiful book for old-skool TCS. Except for the part of domain theoretic semantics, which can be skipped. $\endgroup$ – Martin Berger Dec 23 '15 at 18:49
1
$\begingroup$

I am big fan of Theory and Algorithms. I had once an opportunity to visit Theoretical Computer Science at Indian Institute of Technology, Madras (IIT-M), India. I have got a know about a lot theoreticians there at IIT-M. When I went there I didn't have any idea about what Theory was, but today I am total love with it.

Thanks to @Kate F for the pointer, yes Hopcroft and Ullman is an excellent place to start.

However here is how I have started,

  1. Read the Introduction to Algorithms by Cormen.<\br> This is an excellent place to start. When you study try to understand each proof in as much length as possible. If you understand the proof well, try to code the same logic in any language of your choice. (It takes a bit longer but its worth a try)

  2. Follow the top conferences in Theory like
    FOCS
    SODA
    STOC
    EC (Electronic Commerce) -- Algorithmic Game Theory
    COLT (Conference on Learning Theory) -- Learning Theory
    CRYPTO -- Cryptography
    SOCG (Symposium on Computational Geometry) -- Computational Geometry
    CCC (Conference on Computational Complexity) -- Complexity Theory

Even if you don't understand much try to read and THINK as much as possible. You have to do as much proofs as possible..

  1. This is a wonder place to look at if you are thinking of Computational complexity in particular (This is from Stanford).
  2. Follow Prof. Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Sudan
  3. Here is a set of synthesized information in the field of Computational Complexity
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.