7 ms·
Fantastic summary of some of the math pertinent to theoretical computer science.
- iskander 15y agoStrangely, not one word about probability.
- p4bl0 15y agoWhich is odd, because many CS fields require probabilities (for instance information theory and quantum computing).
- nphrk 15y agoAlso, pattern recognition/machine learning.
- currywurst 15y agohe 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.
- niels_olson 15y agoProbability 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.
- iskander 15y ago>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.
- dimitar 15y agoThis is math used in "logic, linguistics, and computer science". As I understood it in all those fields.
- swah 15y agoDoes the OP follows @debasishg on twitter?
- br1 15y agoAlgorithm 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.
- warmfuzzykitten 15y agoFormal Concept Analysis leads to the conclusion that Cola is a subtype of Mineral Water?
- chalst 15y agoNo, 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.
- jasonkostempski 15y agoIf "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?
- currywurst 15y agolooks like a bug .. good catch !
- Apocryphon 15y agoShould we email him about this? It'd be helpful to have this be an accurate guide.
- mhewett 15y agoI'm sure John would appreciate the chance to correct an error. His email address is at the bottom of the page.
- niels_olson 15y agoAs someone now grinding through the second half of Learning Python, and starting project Euler, this is great stuff.
- motxilo 15y agoAnd where is Number Theory?