15
$\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?

Improve this question
$\endgroup$
5
  • 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 Steinke
    Commented Nov 27, 2015 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
    Commented Nov 27, 2015 at 22:38
  • $\begingroup$ What did you study in the college? $\endgroup$
    – Omar Shehab
    Commented Nov 28, 2015 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
    Commented Nov 29, 2015 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
    Commented Dec 2, 2015 at 23:46

4 Answers 4

Reset to default
8
$\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.

Improve this answer
$\endgroup$
5
  • 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.
    Commented Nov 27, 2015 at 21:18
  • $\begingroup$ Then you'll be able to work through it very quickly :) $\endgroup$
    – Kate F
    Commented Nov 27, 2015 at 21:21
  • $\begingroup$ its a difference but not the difference. CS entails many other principles etc $\endgroup$
    – vzn
    Commented Nov 29, 2015 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
    Commented Nov 30, 2015 at 8:51
  • 2
    $\begingroup$ @JanJohannsen I'd quite disagree - for example, see Undefined Behaviour for C. $\endgroup$
    – Kate F
    Commented Nov 30, 2015 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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 23, 2015 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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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