6 ms·

Gee, "15-251 Great Theoretical Ideas in Computer Science" You mean there really are some? I always thought it was the empty set! Okay, I followed the URL to

Gee, "15-251 Great Theoretical Ideas in Computer Science" You mean there really are some? I always thought it was the empty set! Okay, I followed the URL to see these wondrous ideas! So, I saw some 'lecture notes' at: http://server251.theory.cs.cmu.edu/twiki/bin/view/Main/ProbabilityTwo http://server251.theory.cs.cmu.edu/twiki/bin/view/Main/Proba... and there saw: "Random Variables We begin with the notion of a finite probability distribution D, which consists of a finite set S of elements, or samples, where each x in S has a weight, or probability, p(x) in [0,1]." Sorry, guys. They blew it. That sentence is without a doubt the most mixed up, confused, uninformed, misinformed, just plain wrong mess I've ever seen in what purports to be some important mathematics. We're talking total upchuck here. Don't read that garbage. (1) "finite probability distribution" Likely what he means is a discrete distribution. (2) "distribution D, which consists of a finite set S of elements, or samples" Total nonsense. A "distribution" does NOT consist "of a finite set". The rest is also nonsense. He wants to discuss random variables but gets off on distributions far too soon. Here is a much better way to proceed: Suppose we perform an experiment and measure some number X. If we do the experiment again, then the number we get for X might be different. We call X a 'real random variable'. For a real number x, we can consider the probability that X <= x. We write this probability as P(X <= x). We also write as the 'cumulative distribution' of X F_X(x) = P(X <= x). [Note: Here F_X borrows from Knuth's TeX notation for F with a subscript X.] If X takes on only finitely many values, then we might say that X and its cumulative distribution F_X are 'discrete'. Here is a still better way to proceed: We have a non-empty set S (usually denoted by capital omega) of 'trials'. Each experiment we perform is one 'trial' and corresponds to some point s in S (usually a trial is denoted by a lower case omega). Given a subset A of S, we call A an 'event'. We have a probability P defined on events. The 'probability' of an event A is written P(A) and is a number in [0,1]. If in our experiment we observe a number, that number is a real random variable; call it X. Then X is a function from the set of trials S to the set of real numbers R. So, X: S --> R. Then for a real number x, there is the event {s | s is in S and X(s) <= x} with shorthand notation {X <= x}. That is, we usually suppress mention of a trial s. Then the probability that X <= x is written F_X(x) = P(X <= x) and is the 'cumulative distribution' of X. For more details, we ask that the set of all events includes S and is closed under complements and countable unions. Usually the set of all events is denoted by script upper case F. And we ask that for disjoints events A(i), i = 1, 2, ..., the probability of the union of the A(i) is the sum of P(A(i)). That is, we ask that P be 'countably additive'. Suppose X is a real random variable with cumulative distribution F_X, and suppose for some positive integer n and i = 1, 2, ..., n Y(i) is a real random variable. Suppose the set {Y(i) | i = 1, 2, ..., n} is independent. And suppose for each i, the cumulative distribution of Y(i) is F_X. Then we can regard {Y(i) | i = 1, 2, ..., n} as a 'sample' of size n from cumulative distribution F_X. Full details are in each of: M. Loève, 'Probability Theory, I and II, 4th Edition', Springer-Verlag, New York. Jacques Neveu, 'Mathematical Foundations of the Calculus of Probability', Holden-Day, San Francisco. Leo Breiman, 'Probability', ISBN 0-89871-296-3, SIAM, Philadelphia. Kai Lai Chung, 'A Course in Probability Theory, Second Edition', ISBN 0-12-174650-X, Academic Press, New York. Loève was long at Berkeley, and Neveu and Breiman were among his students. Neveu has long been in Paris, and Breiman has long been at Berkeley. Chung has long been at Stanford. Other experts in such math include Avellaneda at Courant, Bertsekas at MIT, Çinlar at Princeton, Dynkin at Cornell, Karatzas at Columbia, Karr at UNC, Shiryaev at Moscow, Shreve at CMU, Wierman at Johns Hopkins, among others. This disaster illustrates an important lesson: Computer science is out of gas, that is, doesn't know what to do next. It really has only one promising way out now, and that way is to 'mathematize' the field. So, the progress needs to be essentially applied math. For this progress, computer science needs to know some appropriate math. Basically each person trying to do such work needs a good undergraduate major in pure math together with some selected graduate work in pure and applied math. However, only a tiny fraction of professors of computer science have these prerequisites. Thus their work that needs math is often upchuck as in the example here although usually not quite this bad. Net, anyone who wants to make progress in computer science should f'get about current academic computer science, study math, and then attack problems in computing as an applied mathematician. Bluntly, the alternative is just upchuck as here. Sorry 'bout that. Any student trying to learn some topics in math in a computer science department is likely wasting time and money and filling in much needed gaps in his knowledge. To learn math, go to a math department. To learn probability, start with one of the books and/or professors above or equivalents.

wisty 15y ago
I don't really agree. There are a number of things that "computer science" can be: - The study of algorithms. Mathy. - Numerical analysis. Mathy. - Compilers, computational reasoning, automated proofs. Mathy. - Data mining and AI. Mathy. - Systems, especially performance testing. Needs some statistics, but it's not hardcore math. No more than psychology or economics. - Systems architecture. Not at all mathy. More like the biology of computer systems. - Best practices. Software engineering. Not really mathy. Not really science either. - OOP. Theology? Of course, if you are good at math, then the most mathematical parts of computer science may be the ones that catch your eye. So you equate computer science with math + a bit of fluff. But there are things to study that aren't just math, even in the field of computer science.
- NY_USA_Hacker 15y ago
  "the study of algorithms" Well, can do what Knuth did in TACP. There he did a lot with combinatorial formulas. To make much more progress, will have to get serious about math. E.g., the leading question in algorithms is just P versus NP, and that is now darned serious math. Don't attack that or even parts of it without a good background in math. Other new and challenging questions in algorithms promise to need math for progress. As I look at algorithms in 'advanced computer science', commonly they want to treat optimization. Tilt! Optimization is a huge field from applied math, operations research, and electrical engineering. There is deterministic and stochastic optimal control, Kalman filtering, integer linear programming, and much more. It's darned good applied math, and the math background I outlined is needed. "numerical analysis" That's a field of applied math. E.g., quickly get into advanced parts of matrix theory. E.g., consider R. Horn's books. E.g., quasi Newton quickly becomes an exercise in matrix norm theory. Long one of the more important tools in numerical analysis has been functional analysis. Likely the leading reason to pursue numerical analysis is just to get solutions to partial differential equations, and don't go there without a good background in math and likely the corresponding mathematical physics. "compilers, computational reasoning, automated proofs" For the last two, they are just fields of applied math. "Data mining and AI" The way computer science pursues these two, they are nonsense fields. The first should be just mathematical statistics, and for that the background I gave in probability is crucial. E.g., will want to know sufficient statistics, and that is based on the Radon-Nikodym theorem, and that is graduate pure math. For AI, if someone can write a computer program that really has 'intelligence', fine. If all they use are intuitive ideas, good for them. But so far, the field of AI is very far from this goal in spite of decades of DARPA funding. For now, if want a system that solves a problem well enough to look 'intelligent', then just engineer the system with the usual role for applied math. I gave a paper at an AAAI IAAI conference with the "25 best applications of AI in the world", and the best applications, really, were just good engineering. "Systems, especially performance testing. Needs some statistics, but it's not hardcore math. No more than psychology or economics." For some simple applications, yes, can just borrow statistics from the social sciences. But for progress, it's back to "hardcore math": E.g., I published a paper on 'performance monitoring', that is, zero day anomaly detection in server farms and networks, and the math was based on some of the more advanced parts of the texts I listed. Basically I found a collection of multivariate, distribution free hypothesis tests. The social sciences have been using univariate distribution free hypothesis tests for over 60 years; my work was apparently the first good progress to multivariate distribution free tests. Multivariate tests are just crucial for analyzing performance data. I used a finite group (from abstract algebra) of measure preserving transformations something like in ergodic theory. My work was similar to some of what Diaconis at Stanford has done with exchangeability in distribution free statistics. This material needs all the background I outlined and more. "Systems architecture" For the future, before we build a large system, we will want the 'architecture' to have some known properties. We do this for bridges, buildings, dams, ships, airplanes, etc. So, we will want to do it for systems. We will want to know about reliability and security, at least. And we may want to 'optimize', that is, get what we need at minimum price. E.g., consider part of the core of the Internet: Suppose we are given nodes and flows at the nodes. Then our mission, should we decide to accept it, is to connect the nodes at minimum cost to provide desired capacity, performance, and reliability. Dean of Engineering at MIT T. Magnanti gave a Goldman lecture at Johns Hopkins on this problem; first-cut it's a super tough problem in integer linear programming. Actually, it was such problems in network design, and integer linear programming, that got Bell Labs going on the work that resulted in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. which is one of the key books early in the problem P versus NP. It is common now to throw together a system, have various intuitive approaches to parallelism and redundancy, and then get a problem and see the whole server farm go south. Recall that this is just what happened at Amazon a few weeks ago. Maybe some people, say, in national security, finance, or air traffic control would like such things not to happen? A common situation is parallelism that is not more reliable but worse: E.g., there was a parallel transaction processing system. The load balancing sent the next transaction to the least busy computer. Then one day, one of the computers got a little sick, started throwing all its work into the bit bucket, was not very busy, was getting nearly all the transactions, and, thus, killed the whole 'cluster'. Bummer. Something similar happened with Google's e-mail servers. Instead, we need some theory with some theorems and proofs that provide some guarantees that we are getting the performance and reliability we need. That work will be mathematical; without a good background in math, don't try. And, yes, likely the work will need probability such as I discussed. "Best practices. Software engineering. Not really mathy. Not really science either." Not really computer science research either. "OOP. Theology?" There have been some connections with category theory, but I'm reluctant to take those seriously. Mostly OOP in practice is simple and works well for some simple things. Otherwise OOP is not well thought out. And long OOP was a 'theology'. My old view of programming languages is that they should be designed so that they 'admit' some source code transformations that have some useful properties. E.g., suppose we have such a language with such properties and have two pieces of code. Can we use the transformations to check if the two pieces of code are equivalent? So, right, we will have 'equivalence classes' of code. Some of these will do better on processor time, main memory usage, exploitation of multiple cores, etc. than others. So, with some code and these transformations, we have an optimization problem: Transform the code to equivalent code with the 'resource' properties we need. Sounds like math to me. "But there are things to study that aren't just math, even in the field of computer science." The problems are from computer science. But the good solutions are necessarily applied math because our civilization knows no other way to proceed. This situation is much that same as in all fields that have been 'mathematized', especially theoretical physics.

wisty 15y ago

I don't really agree. There are a number of things that "computer science" can be: - The study of algorithms. Mathy. - Numerical analysis. Mathy. - Compilers, computational reasoning, automated proofs. Mathy. - Data mining and AI. Mathy. - Systems, especially performance testing. Needs some statistics, but it's not hardcore math. No more than psychology or economics. - Systems architecture. Not at all mathy. More like the biology of computer systems. - Best practices. Software engineering. Not really mathy. Not really science either. - OOP. Theology? Of course, if you are good at math, then the most mathematical parts of computer science may be the ones that catch your eye. So you equate computer science with math + a bit of fluff. But there are things to study that aren't just math, even in the field of computer science.

NY_USA_Hacker 15y ago
"the study of algorithms" Well, can do what Knuth did in TACP. There he did a lot with combinatorial formulas. To make much more progress, will have to get serious about math. E.g., the leading question in algorithms is just P versus NP, and that is now darned serious math. Don't attack that or even parts of it without a good background in math. Other new and challenging questions in algorithms promise to need math for progress. As I look at algorithms in 'advanced computer science', commonly they want to treat optimization. Tilt! Optimization is a huge field from applied math, operations research, and electrical engineering. There is deterministic and stochastic optimal control, Kalman filtering, integer linear programming, and much more. It's darned good applied math, and the math background I outlined is needed. "numerical analysis" That's a field of applied math. E.g., quickly get into advanced parts of matrix theory. E.g., consider R. Horn's books. E.g., quasi Newton quickly becomes an exercise in matrix norm theory. Long one of the more important tools in numerical analysis has been functional analysis. Likely the leading reason to pursue numerical analysis is just to get solutions to partial differential equations, and don't go there without a good background in math and likely the corresponding mathematical physics. "compilers, computational reasoning, automated proofs" For the last two, they are just fields of applied math. "Data mining and AI" The way computer science pursues these two, they are nonsense fields. The first should be just mathematical statistics, and for that the background I gave in probability is crucial. E.g., will want to know sufficient statistics, and that is based on the Radon-Nikodym theorem, and that is graduate pure math. For AI, if someone can write a computer program that really has 'intelligence', fine. If all they use are intuitive ideas, good for them. But so far, the field of AI is very far from this goal in spite of decades of DARPA funding. For now, if want a system that solves a problem well enough to look 'intelligent', then just engineer the system with the usual role for applied math. I gave a paper at an AAAI IAAI conference with the "25 best applications of AI in the world", and the best applications, really, were just good engineering. "Systems, especially performance testing. Needs some statistics, but it's not hardcore math. No more than psychology or economics." For some simple applications, yes, can just borrow statistics from the social sciences. But for progress, it's back to "hardcore math": E.g., I published a paper on 'performance monitoring', that is, zero day anomaly detection in server farms and networks, and the math was based on some of the more advanced parts of the texts I listed. Basically I found a collection of multivariate, distribution free hypothesis tests. The social sciences have been using univariate distribution free hypothesis tests for over 60 years; my work was apparently the first good progress to multivariate distribution free tests. Multivariate tests are just crucial for analyzing performance data. I used a finite group (from abstract algebra) of measure preserving transformations something like in ergodic theory. My work was similar to some of what Diaconis at Stanford has done with exchangeability in distribution free statistics. This material needs all the background I outlined and more. "Systems architecture" For the future, before we build a large system, we will want the 'architecture' to have some known properties. We do this for bridges, buildings, dams, ships, airplanes, etc. So, we will want to do it for systems. We will want to know about reliability and security, at least. And we may want to 'optimize', that is, get what we need at minimum price. E.g., consider part of the core of the Internet: Suppose we are given nodes and flows at the nodes. Then our mission, should we decide to accept it, is to connect the nodes at minimum cost to provide desired capacity, performance, and reliability. Dean of Engineering at MIT T. Magnanti gave a Goldman lecture at Johns Hopkins on this problem; first-cut it's a super tough problem in integer linear programming. Actually, it was such problems in network design, and integer linear programming, that got Bell Labs going on the work that resulted in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. which is one of the key books early in the problem P versus NP. It is common now to throw together a system, have various intuitive approaches to parallelism and redundancy, and then get a problem and see the whole server farm go south. Recall that this is just what happened at Amazon a few weeks ago. Maybe some people, say, in national security, finance, or air traffic control would like such things not to happen? A common situation is parallelism that is not more reliable but worse: E.g., there was a parallel transaction processing system. The load balancing sent the next transaction to the least busy computer. Then one day, one of the computers got a little sick, started throwing all its work into the bit bucket, was not very busy, was getting nearly all the transactions, and, thus, killed the whole 'cluster'. Bummer. Something similar happened with Google's e-mail servers. Instead, we need some theory with some theorems and proofs that provide some guarantees that we are getting the performance and reliability we need. That work will be mathematical; without a good background in math, don't try. And, yes, likely the work will need probability such as I discussed. "Best practices. Software engineering. Not really mathy. Not really science either." Not really computer science research either. "OOP. Theology?" There have been some connections with category theory, but I'm reluctant to take those seriously. Mostly OOP in practice is simple and works well for some simple things. Otherwise OOP is not well thought out. And long OOP was a 'theology'. My old view of programming languages is that they should be designed so that they 'admit' some source code transformations that have some useful properties. E.g., suppose we have such a language with such properties and have two pieces of code. Can we use the transformations to check if the two pieces of code are equivalent? So, right, we will have 'equivalence classes' of code. Some of these will do better on processor time, main memory usage, exploitation of multiple cores, etc. than others. So, with some code and these transformations, we have an optimization problem: Transform the code to equivalent code with the 'resource' properties we need. Sounds like math to me. "But there are things to study that aren't just math, even in the field of computer science." The problems are from computer science. But the good solutions are necessarily applied math because our civilization knows no other way to proceed. This situation is much that same as in all fields that have been 'mathematized', especially theoretical physics.