Publication details
Emergence of measuring a computational procedure
| Authors | |
|---|---|
| Year of publication | 2018 |
| Type | Appeared in Conference without Proceedings |
| MU Faculty or unit | |
| Citation | |
| Description | Presentation of research results. Abstract: How do we quickly compare the efficiency of two computational procedures? Such a comparison can be enabled, or hindered, by the language used. When a computational procedure is described in plain language, ambiguities arise, making comparison difficult. Thus the call for finding a uniform way to describe them may be interpreted as a natural consequence of these difficulties. I take the example of the minimum spanning tree (shortest spanning subtree), problem in discrete mathematics. The principal task lies in connecting points through lines of non-negative lengths in such a way that the total length of those lines is minimal. Diverse plain-language formulations of the problem appeared before WWII, and the mathematicians asking to deal with the problem also provided several plain-language and intuitively clear solutions to the problem. However, it was not until April 1972 that a minimum spanning tree algorithm appeared in the Algorithms section of the Communications of the ACM, a decade after the section was established. From the point of view of mathematicians, there are two, maybe three, significantly distinct ways to find the correct solution, whose use can be a matter of taste. Taste, however, was not a good enough measure for programmers. Their attempts to measure the taste resulted in a more engaged discussion than the intuitive solution of the rather banal problem, from which mathematicians run away after having solved it, leading to re-assessment and re-formulations of the old solutions, as will be shown in the talk. |