Thread: Tell me about theoretical computer science

Originally Posted by Xei

I'm reading mathematics at the University of Cambridge so actually I'm pretty well equipped to cope with it, haha!

Ok, to tell the truth, I don't understand the math of it. But I will tell you what else is in the future...

Neural Networks.

I'm too tired to type a whole other wall of text, so I'll just give you a good link :
http://www.ai-junkie.com/ann/evolved/nnt1.html

Transistors and pretty much the whole electronics part of computers is not really part of theoretical computer science, it's part of computer engineering.

As for theoretical computer science, some of the most important topics are (roughly sorted by difficulty):

• formal logic
• automata theory
• formal languages
• computability theory
• complexity theory
• algorithm theory
• formal semantics
• graph theory
• cryptography
• quantum computing

(I apologize if I missed someone's favourite subject here.)

The field is quite complex and many-sided. It doesn't really teach you how to program, though. There a many programmers out there who are purely practice-oriented and have absolutely no clue about theoretical computer science. Don't get me wrong, it's a fascinating field but it's probably a good idea to learn programming first before you tackle any of the heavy theory. I'm saying this because most people already know how to program when they begin to study theoretical computer science. It's not that they wouldn't understand the theory otherwise but that it wouldn't be much use to them.

If you don't just want to learn how to program but also want to understand how computers work, you probably want to learn the basics of computer science and computer engineering. If you really interested in a bottom-up approach (as in from the-very-bottom-up) you start out in physics. Here's my attempt to outline how such an approach might look like:

• All about electricity, power, current, resistance, capacity, basic electric circuits etc.
• Materials and conductivity: The properties of insulators, conductors and semiconductors.
• How to build electrical elements using semiconductors. All about diodes, transistors etc.
• How to perform boolean operations using transistors, i.e. how to build boolean gates.
• How the binary system works. All about boolean functions and how to optimize them. Combinational/sequential logic.
• How to use boolean gates to perform more complex operations such as addition and multiplication.
• All about memory, microprogramming, program execution in hardware, pipelines etc.
• Programming in assembly language. All about registers, instructions, different CPU designs (RISC, CISC, etc).
• All about higher level programming languages and how they are translated to assembly code.
• Programming constructs: statements, conditional statements, loops etc. How does it look like in assembly.
• Simple algorithms (search and sorting algorithms etc.) and programming techniques (recursion, linked lists etc.)

If you get this far, you should have the basic knowledge on how computers work. From there you could move on to more advanced topics.

The topics in theoretical computer science that would be good to know when trying to understand how a computer works are probably just formal logic (for understanding (the optimization of) boolean functions, gates etc.) and automata theory (for understanding sequential circuits).

Computer engineering is as the name suggests more engineery (the focus is on how to accomplish practical tasks), whereas theoretical computer science is highly formal (it's all about definitions, theorems, proofs etc).