Timeline for Probabilistic (randomized) algorithms before "modern" computer science appeared
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2012 at 19:24 | history | made wiki | Post Made Community Wiki by Kaveh | ||
| Sep 13, 2012 at 17:39 | comment | added | Suresh Venkat | It seems to me that decimation is a good example of a randomized technique, albeit a grisly one | |
| Sep 13, 2012 at 16:48 | comment | added | Niel de Beaudrap | I agree that it's concievable, and that it isn't even very far-fetched -- aside, of course, from the fact that we don't seem to have any record of the Greeks talking about probability per se. But if there's an actual record of it, you should be able to actually point it out. Otherwise, it's speculation, not history. | |
| Sep 13, 2012 at 16:44 | comment | added | vzn | its clear that there are many basic beginnings of TCS concepts in greek number theory, some of them with near-astonishing sophistication by modern standards, including things like primality, algorithms, euclids GCD algorithm etc (with recursion! possibly one of the earliest cases!) but few in the TCS field seem to recognize/realize/appreciate that at times. maybe its rarely taught in CS classes. there are however good math history classes in college. | |
| Sep 13, 2012 at 16:36 | comment | added | Niel de Beaudrap | Your 'hint' to me about evolution, nor your casting me as wasting time on a question I don't like, nor your evasion of my earlier question, were respectful. And in fact, your speculating that the Greeks probably knew about what you're talking about but didn't bother to write about it is exactly one of the things which "historical revisionism" can refer to. (Maybe Archimedes invented decimal notation, but didn't bother to make any record; after all, the Sand Reckoner is quite close to place notation, and the Greeks did use a base-10-like system. But should we take the idea seriously? No.) | |
| Sep 13, 2012 at 16:30 | comment | added | vzn | think its actually the above observation about the sieve of eratosthenes that is near-trivial, & that euclid or eratosthenes or some other brilliant greek like diophantus probably understood it intuitively but did not necessarily write it down, or perhaps it was written down but lost. and, civilized people can respectfully disagree. or in games, call a draw. | |
| Sep 13, 2012 at 16:25 | comment | added | Niel de Beaudrap | "soft question" doesn't mean a question with infinitely flexible boundaries; "historical overview" is not the same as historical revisionism. | |
| Sep 13, 2012 at 16:20 | comment | added | vzn | ah, so, soft-question and ho.history-overview are admittedly not your thing! | |
| Sep 13, 2012 at 16:17 | comment | added | Niel de Beaudrap | I'm afraid I'm not interested in vague generalities, and it seems quite obvious that we disagree fundamentally in what an "algorithm" is. I'm interested in more than just "phenomena". Otherwise, we may as well cite all quantum mechanical events after the Big Bang as examples of "randomized algorithms", which makes the whole subject trivial. | |
| Sep 13, 2012 at 16:14 | comment | added | vzn | hint: algorithms have evolved. think Homo sapiens vs Homo sapiens neanderthalensis vs Homo neanderthalensis | |
| Sep 13, 2012 at 16:03 | comment | added | Niel de Beaudrap | That's not what I'm asking about; I'm asking about whether they reasoned about the relative frequency of composite numbers in the way that you describe. | |
| Sep 13, 2012 at 15:58 | comment | added | vzn | fyi the greeks did have a term for composite numbers, apparently they called them "rectangular" because they could be laid out in a $m$ by $n$ rectangular grid. | |
| Sep 13, 2012 at 15:51 | comment | added | Niel de Beaudrap | The Church-Turing thesis is about algorithms to compute functions and relations. It's not clear to me that a dice game represents an algorithm any more than me punching random keys on a pocket calculator represents an algorithm. | |
| Sep 13, 2012 at 15:49 | comment | added | vzn | admittedly the concept of "algorithm" has some subtle nuances but it seems to be similar to the Church-Turing thesis where one can take an expansive view. in other words if anyone accepts the C-T thesis (which is the majority of CS practitioners), they are basically taking the broad view of algorithms, which yes, is a lens, yet nevertheless has implications on interpreting the history of CS "pre modern era". and of course we cant have any strong certitude about long lost history in the sands of time, only suggestion. | |
| Sep 13, 2012 at 15:39 | comment | added | Niel de Beaudrap | It's not clear whether the first is an example where the ancients understood that randomness could play a role: did they make the connection between "most composite numbers" and "any randomly chosen number, with high probability", and did they actually recognize the assertion about 'most' composite numbers to begin with? (Priorities in mathematics have changed a lot since 300 BCE, we should avoid trying to read our values into how they thought of their work.) And it's not clear to me that the latter three are 'algorithms' at all (see my comment on Marzio's response). | |
| Sep 13, 2012 at 15:25 | history | edited | vzn | CC BY-SA 3.0 |
nuance the warfare concept a little
|
| Sep 13, 2012 at 15:18 | history | edited | vzn | CC BY-SA 3.0 |
nuance the warfare concept a little
|
| Sep 13, 2012 at 15:12 | history | answered | vzn | CC BY-SA 3.0 |