Fantastic summary of some of the math pertinent to theoretical computer science. | Hacker News Reader

Fantastic summary of some of the math pertinent to theoretical computer science.

jfsowa.com

158 pointscurrywurst17 comments

Strangely, not one word about probability.

Which is odd, because many CS fields require probabilities (for instance information theory and quantum computing).

Also, pattern recognition/machine learning.

he he .. this is why I was careful to add "some of the math" :) I really liked the short, to the point summary, with some historical pointers thrown in for good measure.

Probability is not the sort of math this guy is aiming at. Stats may be insanely common in practice, but they are small, disjointed subsets in a few of these big, categoric areas.

>Probability is not the sort of math this guy is aiming at.

I get that, I'm just not sure there's a good reason for it. Extending discrete models to their probabilistic versions is often very useful. Probabilistic knowledge representation is much less brittle than a logic-based system. Stochastic grammars and probabilistic automata have been essential to both language modeling and bioinformatics. Game graphs are nice for perfectly observable systems, but stochastic games are much more common in real life (and have to be modeled using some probabilistic mechanism).

This page has some good fundamentals, it's just weird to me that probabilistic extensions weren't also presented.

This is math used in "logic, linguistics, and computer science". As I understood it in all those fields.

Algorithm efficiency is studied with generating functions, which are solved with complex calculus. That route includes most math stuff one normally thinks as unnecessary for CS.

Formal Concept Analysis leads to the conclusion that Cola is a subtype of Mineral Water?

No, nor does it prove that champagne and beer are the same drink as the discussion indicates. The point is that the example uses a very limited set of attributes: you can add attributes, say "sweet" or "made from grapes" to distinguish nodes still further. Without enough distinguishing power in the attributes chosen, a particular concept analysis may be unsound: it may identify things that are not identical. So you need to prove soundness if you want to make this kind of inference based on the model.

The limit of this operation gives you something similar to Leibniz's rule, where two things are identical if the same class of (first-order observable) predicates are true of them.

As someone now grinding through the second half of Learning Python, and starting project Euler, this is great stuff.

If "Graphs" fig. 1 and fig. 2 represent the same thing, shouldn't the fig. 2 C,D arc point the other way? Or was that done to demonstrate something I'm missing?

looks like a bug .. good catch !

Should we email him about this? It'd be helpful to have this be an accurate guide.

I'm sure John would appreciate the chance to correct an error. His email address is at the bottom of the page.

And where is Number Theory?

Does the OP follows @debasishg on twitter?

Reply on news.ycombinator.com