4 ms·
Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?
by komali2 10y ago
Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?
- marcoperaza 10y agoTheory of Computation
- deleted 10y ago[deleted]
- stratfordfellow 10y agoWhat you're looking at is the theory of computational complexity. Here's a short-ish overview: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Hogan.pdf http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/... For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous: http://amzn.to/2fy9tKZ http://amzn.to/2fy9tKZ, Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introduction+to+theory+of+computation https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti...).
- sjclemmy 10y agoI bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;) Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental model .
- imakecomments 10y agoIt's been mentioned elsewhere but I recommend: https://www.youtube.com/playlist?list=PL601FC994BDD963E4 https://www.youtube.com/playlist?list=PL601FC994BDD963E4 Seems like a few lectures are missing but if you google around you might be able to find them somewhere.
- groovy2shoes 10y agoThe Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library... I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand. One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).
- mettamage 10y agoPart 1 of 9 by Shai Simonson -- Finite State Machines The rest of computational theory will follow. https://www.youtube.com/watch?v=HyUK5RAJg1c https://www.youtube.com/watch?v=HyUK5RAJg1c
- austinl 10y agoThis 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science). Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?" https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s
- deathgrindfreak 10y agoI'd start with an algorithms course, then progress deeper into Complexity theory. Perhaps a bit of discrete mathematics depending on your background.
- deckar01 10y ago"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable. [0] https://books.google.com/books?id=Z6FJbwggW1sC https://books.google.com/books?id=Z6FJbwggW1sC [1] https://en.m.wikipedia.org/wiki/Computability_theory https://en.m.wikipedia.org/wiki/Computability_theory
- menssen 10y agoGary Bernhardt's new Destroy All Software series on computation [1] is basically designed for this. Not all that in-depth, but it's a great starting point. [1]: https://www.destroyallsoftware.com/ https://www.destroyallsoftware.com/