New Articles (Page 388)
To stay up to date you can also follow on Mastodon.
π Two Generals' Problem
In computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. In the experiment, two generals are only able to communicate with one another by sending a messenger through enemy territory. The experiment asks how they might reach an agreement on the time to launch an attack, while knowing that any messenger they send could be captured.
It is related to the more general Byzantine Generals Problem and appears often in introductory classes about computer networking (particularly with regard to the Transmission Control Protocol, where it shows that TCP can't guarantee state consistency between endpoints and why this is the case), though it applies to any type of two-party communication where failures of communication are possible. A key concept in epistemic logic, this problem highlights the importance of common knowledge. Some authors also refer to this as the Two Generals' Paradox, the Two Armies Problem, or the Coordinated Attack Problem. The Two Generals' Problem was the first computer communication problem to be proved to be unsolvable. An important consequence of this proof is that generalizations like the Byzantine Generals problem are also unsolvable in the face of arbitrary communication failures, thus providing a base of realistic expectations for any distributed consistency protocols.
Discussed on
- "Two Generals' Problem" | 2014-03-09 | 97 Upvotes 28 Comments
- "The Two Generals' Problem (wikipedia)" | 2010-06-25 | 34 Upvotes 19 Comments
π VA-111 Shkval
The VA-111 Shkval (from Russian: ΡΠΊΠ²Π°Π», squall) torpedo and its descendants are supercavitating torpedoes originally developed by the Soviet Union. They are capable of speeds in excess of 200 knots (370Β km/h or 230 miles/h).
Discussed on
- "VA-111 Shkval" | 2014-03-08 | 12 Upvotes 5 Comments
π Hapax legomenon
In corpus linguistics, a hapax legomenon ( also or ; pl. hapax legomena; sometimes abbreviated to hapax) is a word that occurs only once within a context, either in the written record of an entire language, in the works of an author, or in a single text. The term is sometimes incorrectly used to describe a word that occurs in just one of an author's works, but more than once in that particular work. Hapax legomenon is a transliteration of Greek αΌ ΟΞ±ΞΎ λΡγΟμΡνον, meaning "(something) being said (only) once".
The related terms dis legomenon, tris legomenon, and tetrakis legomenon respectively (, , ) refer to double, triple, or quadruple occurrences, but are far less commonly used.
Hapax legomena are quite common, as predicted by Zipf's law, which states that the frequency of any word in a corpus is inversely proportional to its rank in the frequency table. For large corpora, about 40% to 60% of the words are hapax legomena, and another 10% to 15% are dis legomena. Thus, in the Brown Corpus of American English, about half of the 50,000 distinct words are hapax legomena within that corpus.
Hapax legomenon refers to a word's appearance in a body of text, not to either its origin or its prevalence in speech. It thus differs from a nonce word, which may never be recorded, may find currency and may be widely recorded, or may appear several times in the work which coins it, and so on.
Discussed on
- "Hapax legomenon" | 2014-03-06 | 87 Upvotes 40 Comments
π Stick bomb
A stick bomb is a (mechanical) spring-loaded device constructed out of flat sticks woven together under a bending moment. Other names for stick bombs include Chinese stick puzzles, Cobra wave, and frame bombs. Stick bombs are created for fun and as art, not for any practical use.
Discussed on
- "Stick bomb" | 2014-03-05 | 255 Upvotes 57 Comments
π Wallpaper group
A wallpaper group (or plane symmetry group or plane crystallographic group) is a mathematical classification of a two-dimensional repetitive pattern, based on the symmetries in the pattern. Such patterns occur frequently in architecture and decorative art, especially in textiles and tiles as well as wallpaper.
The simplest wallpaper group, Group p1, applies when there is no symmetry other than the fact that a pattern repeats over regular intervals in two dimensions, as shown in the section on p1 below.
Consider the following examples of patterns with more forms of symmetry:
Examples A and B have the same wallpaper group; it is called p4m in the IUC notation and *442 in the orbifold notation. Example C has a different wallpaper group, called p4g or 4*2 . The fact that A and B have the same wallpaper group means that they have the same symmetries, regardless of details of the designs, whereas C has a different set of symmetries despite any superficial similarities.
The number of symmetry groups depends on the number of dimensions in the patterns. Wallpaper groups apply to the two-dimensional case, intermediate in complexity between the simpler frieze groups and the three-dimensional space groups. Subtle differences may place similar patterns in different groups, while patterns that are very different in style, color, scale or orientation may belong to the same group.
A proof that there were only 17 distinct groups of such planar symmeries was first carried out by Evgraf Fedorov in 1891 and then derived independently by George PΓ³lya in 1924. The proof that the list of wallpaper groups was complete only came after the much harder case of space groups had been done. The seventeen possible wallpaper groups are listed below in Β§Β The seventeen groups.
Discussed on
- "Wallpaper group" | 2014-03-04 | 62 Upvotes 7 Comments
π Secretary Problem
The secretary problem is a problem that demonstrates a scenario involving optimal stopping theory. The problem has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.
The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.
The shortest rigorous proof known so far is provided by the odds algorithm (Bruss 2000). It implies that the optimal win probability is always at least (where e is the base of the natural logarithm), and that the latter holds even in a much greater generality (2003). The optimal stopping rule prescribes always rejecting the first applicants that are interviewed and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). Sometimes this strategy is called the stopping rule, because the probability of stopping at the best applicant with this strategy is about already for moderate values of . One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.
Discussed on
- "Secretary Problem" | 2014-03-04 | 90 Upvotes 64 Comments
π Ski rental problem
In computer science, the ski rental problem is a name given to a class of problems in which there is a choice between continuing to pay a repeating cost or paying a one-time cost which eliminates or reduces the repeating cost.
Discussed on
- "Ski rental problem" | 2014-02-21 | 11 Upvotes 3 Comments
π Wikipedia: Are you evil?
Congratulations, you have discovered Wikipedia, one of the most popular sites on the Internet and probably the leading informational resource in the world today.
Unfortunately some people are evil and have to be banned. In order to save time, we have compiled this easy questionnaire. It's multiple choice, one answer only.
Q: You have discovered a website which has enormous reach and is used by millions of people every day. You think:
- Wow, this is awesome! How can I help?
- Wow, this is awesome! How can I use this to my advantage?
Scoring:
- 1 point
- 0 points
Marking: 0 points: Fail. Please die in a fire. 1 point: Pass. Welcome!
It seems like the authors of this 'test' are evil, willing people to die and in a most horrible manner.
Discussed on
- "Wikipedia: Are you evil?" | 2014-02-19 | 26 Upvotes 8 Comments
π The fastest pulsar spins at 716Hz; its equator spins at 24% the speed of light
PSR J1748β2446ad is the fastest-spinning pulsar known, at 716 Hz, or 716 times per second. This pulsar was discovered by Jason W. T. Hessels of McGill University on November 10, 2004 and confirmed on January 8, 2005.
If the neutron star is assumed to contain less than two times the mass of the Sun, within the typical range of neutron stars, its radius is constrained to be less than 16Β km. At its equator it is spinning at approximately 24% of the speed of light, or over 70,000Β km per second.
The pulsar is located in a globular cluster of stars called Terzan 5, located approximately 18,000 light-years from Earth in the constellation Sagittarius. It is part of a binary system and undergoes regular eclipses with an eclipse magnitude of about 40%. Its orbit is highly circular with a 26-hour period. The other object is at least 0.14 solar masses, with a radius of 5β6 solar radii. Hessels et al. state that the companion may be a "bloated main-sequence star, possibly still filling its Roche Lobe". Hessels et al. go on to speculate that gravitational radiation from the pulsar might be detectable by LIGO.
Discussed on
- "The fastest pulsar spins at 716Hz; its equator spins at 24% the speed of light" | 2014-02-17 | 122 Upvotes 78 Comments