10 ms·

Theoretical Computer Science – An Introduction [pdf]

76 points by lainon 9y ago

itsmemattchung 9y ago
This document stretches a little over 200 pages and it would be helpful if it included a table of contents so we can get a feel for what it's all about.
- ice109 9y ago
  it's a theory of computation/formal languages textbook. thw canonical reference is sipser's intro to theory of computation but i like hopcroft, ullman's intro automata, languages, computation much more.
ricw 9y ago
God. I did all this years ago, even wrote a masters thesis on formal verification. And I can actually not remember a single time when this was actually useful, other than perhaps really obnoxious interviews. Don't get me wrong, it's interesting, and if you get through this and understand the matter it will make you a better computer scientist. But it's really not very applicable at all. It's the computer science analog to latin for modern day languages... Perhaps less than.
- yorwba 9y ago
  I think a better analogy would be modern languages : software development (applications) linguistics : theoretical computer science (theory) Latin : Turing machines (classic models) If all you are interested in is applications, you can mostly ignore the theory, but sometimes theoretical considerations help you think more abstractly about your application to gain more insights. The classic models are mostly only relevant to theorists who can use them as objects of study, if they so choose.
  - elcapitan 9y ago
    I think it's closer to think of it in terms of Software Engineering = Mechanical Engineering Computer Science = Science/Physics A lot of the mess we have in software development comes from thinking that you can build massive bridges without understanding of physics. Or by imitating other massive bridges without understanding why they are the way they are. Yes, you will work 99% of the time on other things that physics, like building materials and design and use cases, but it can get really really nasty without the foundation.
    - sidlls 9y ago
      I disagree. I think many of the problems in software development as practiced today originate from thinking that the theory is all that is necessary. To take your analogy, my view is that in practice it is considered that we should hire physicists or mathematicians to design and engineer bridges. "Engineering" is almost sneered at as being somehow inferior or a trivially learned skill.
      - treehau5 9y ago
        > I disagree. I think many of the problems in software development as practiced today originate from thinking that the theory is all that is necessary. This is such horseshit. Computer Science gives you the intuition needed to guide you to making more correct decisions you make in building your software rather than wrong. When you have these practitioners hitting the scene all of a sudden who just simply learn xyz latest framework/tool/fad and then are faced with a new and interesting complex challenge (for example, computers all of a sudden now have multiple cores! surprise!), they do not have the background to adapt and spend much time cutting their teeth, creating many bugs in their wake. If you think that having the theory makes you write worse software, I feel bad for you because your computer science education must have been shit and you probably wasted your money. In that sense I understand the bitterness that a lot of people have.
        Bbowen100 9y ago
        Common dude, tell us how you really feel. I don't disagree with you but I think your response could be less aggressive.
- leovonl 9y ago
  > And I can actually not remember a single time when this was actually useful [..] This tells a lot about what is wrong with software development and why industry is constantly plagued with security issues, misbehaving systems, buggy behaviour on edge-cases, etc. There was a thread on HN some time ago about software engineering, and I remember mentioning that if "software engineering" was really to be taken seriously, we'd be using theorem proving to guarantee software is correct. The best analogy is the bricklayer vs structural engineer: you can build something simple very quickly without really putting too much thought about soundness, but once you go past a few floors the risks are too big to be ignored - which is why we have the latter. It usually boils down to cost - some people like to spread the idea that formal methods are sorcery or are limited in scope, specially people outside of computer science that have no strong background on mathematical methods, which sometimes do a disservice to the efforts of researchers and the ones that had exposure to the theoretical foundations of CS. In any case, I don't want to go on a huge rant here - so if you don't know, it doesn't hurt to spend some time reading about modern tools and applications for this, maybe even playing with available tools, and.. who knows, maybe learn something new.
deleted 9y ago
[deleted]
znpy 9y ago
Can't get the document to load. The webserver is probably down due to HN's hug of death. Anyone has a copy mirrored somewhere ?
- cbHXBY1D 9y ago
  I downloaded it but I'm currently on mobile. I'll link to it when I get back to my desktop in an hour.
- imsky 9y ago
  archive.org has a copy: https://web.archive.org/web/20170707011101/http://www-cc.cs.uni-saarland.de/media/lectures/W1415/L-Grundz%C3%BCgederTheoretischenInformatik/ti_FfSJlCM.pdf https://web.archive.org/web/20170707011101/http://www-cc.cs....

76 points by lainon 9y ago

This document stretches a little over 200 pages and it would be helpful if it included a table of contents so we can get a feel for what it's all about.

ice109 9y ago
it's a theory of computation/formal languages textbook. thw canonical reference is sipser's intro to theory of computation but i like hopcroft, ullman's intro automata, languages, computation much more.

ricw 9y ago

God. I did all this years ago, even wrote a masters thesis on formal verification. And I can actually not remember a single time when this was actually useful, other than perhaps really obnoxious interviews. Don't get me wrong, it's interesting, and if you get through this and understand the matter it will make you a better computer scientist. But it's really not very applicable at all. It's the computer science analog to latin for modern day languages... Perhaps less than.

yorwba 9y ago
I think a better analogy would be modern languages : software development (applications) linguistics : theoretical computer science (theory) Latin : Turing machines (classic models) If all you are interested in is applications, you can mostly ignore the theory, but sometimes theoretical considerations help you think more abstractly about your application to gain more insights. The classic models are mostly only relevant to theorists who can use them as objects of study, if they so choose.
- elcapitan 9y ago
  I think it's closer to think of it in terms of Software Engineering = Mechanical Engineering Computer Science = Science/Physics A lot of the mess we have in software development comes from thinking that you can build massive bridges without understanding of physics. Or by imitating other massive bridges without understanding why they are the way they are. Yes, you will work 99% of the time on other things that physics, like building materials and design and use cases, but it can get really really nasty without the foundation.
  - sidlls 9y ago
    I disagree. I think many of the problems in software development as practiced today originate from thinking that the theory is all that is necessary. To take your analogy, my view is that in practice it is considered that we should hire physicists or mathematicians to design and engineer bridges. "Engineering" is almost sneered at as being somehow inferior or a trivially learned skill.
    - treehau5 9y ago
      > I disagree. I think many of the problems in software development as practiced today originate from thinking that the theory is all that is necessary. This is such horseshit. Computer Science gives you the intuition needed to guide you to making more correct decisions you make in building your software rather than wrong. When you have these practitioners hitting the scene all of a sudden who just simply learn xyz latest framework/tool/fad and then are faced with a new and interesting complex challenge (for example, computers all of a sudden now have multiple cores! surprise!), they do not have the background to adapt and spend much time cutting their teeth, creating many bugs in their wake. If you think that having the theory makes you write worse software, I feel bad for you because your computer science education must have been shit and you probably wasted your money. In that sense I understand the bitterness that a lot of people have.
      - Bbowen100 9y ago
        Common dude, tell us how you really feel. I don't disagree with you but I think your response could be less aggressive.
leovonl 9y ago
> And I can actually not remember a single time when this was actually useful [..] This tells a lot about what is wrong with software development and why industry is constantly plagued with security issues, misbehaving systems, buggy behaviour on edge-cases, etc. There was a thread on HN some time ago about software engineering, and I remember mentioning that if "software engineering" was really to be taken seriously, we'd be using theorem proving to guarantee software is correct. The best analogy is the bricklayer vs structural engineer: you can build something simple very quickly without really putting too much thought about soundness, but once you go past a few floors the risks are too big to be ignored - which is why we have the latter. It usually boils down to cost - some people like to spread the idea that formal methods are sorcery or are limited in scope, specially people outside of computer science that have no strong background on mathematical methods, which sometimes do a disservice to the efforts of researchers and the ones that had exposure to the theoretical foundations of CS. In any case, I don't want to go on a huge rant here - so if you don't know, it doesn't hurt to spend some time reading about modern tools and applications for this, maybe even playing with available tools, and.. who knows, maybe learn something new.

deleted 9y ago

[deleted]

znpy 9y ago

Can't get the document to load. The webserver is probably down due to HN's hug of death. Anyone has a copy mirrored somewhere ?

cbHXBY1D 9y ago
I downloaded it but I'm currently on mobile. I'll link to it when I get back to my desktop in an hour.
imsky 9y ago
archive.org has a copy: https://web.archive.org/web/20170707011101/http://www-cc.cs.uni-saarland.de/media/lectures/W1415/L-Grundz%C3%BCgederTheoretischenInformatik/ti_FfSJlCM.pdf https://web.archive.org/web/20170707011101/http://www-cc.cs....