{"id":34164,"date":"2019-10-31T21:56:44","date_gmt":"2019-10-31T18:56:44","guid":{"rendered":"https:\/\/prohoster.info\/blog\/ya-poluchil-ot-knuta-chek-na-0x-3-00\/"},"modified":"2019-10-31T21:56:44","modified_gmt":"2019-10-31T18:56:44","slug":"ya-poluchil-ot-knuta-chek-na-0x-3-00","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/novosti-interneta\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Ich habe von Knuth einen Scheck \u00fcber 0x$3,00 erhalten.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0ist ein Informatiker, der so sehr auf die Genauigkeit seiner B\u00fccher achtet, dass er einen hexadezimalen Dollar<\/b> (2,56 $, 0x$1,00) f\u00fcr jeden gefundenen \u201eFehler\u201c anbietet, wobei als Fehler alles angesehen wird, was \u201etechnisch, historisch, typografisch oder politisch inkorrekt\u201c ist. Ich wollte unbedingt einen Scheck von Knuth erhalten, also beschloss ich, nach Fehlern in seinem herausragenden Werk \u201eDie Kunst des Programmierens\u201c<\/b> (TAOCP) zu suchen. Es gelang mir, drei zu finden. Wahrhaftig, Knuth schickte einen Scheck \u00fcber 0x$3,00<\/b>.<\/p>\n

\"Ich
\n
\nWie Sie sehen, handelt es sich nicht um einen echten Scheck. Fr\u00fcher schickte Knuth echte Schecks, stellte dies jedoch 2008 aufgrund von unerbittlichem Betrug<\/a><\/noindex>ein. Jetzt verschickt er \u201epers\u00f6nliche Einlagenzertifikate\u201c bei der Bank San Serriffe<\/a><\/noindex> (BoSS). Er sagt, dass er im Bedarfsfall echtes Geld senden kann, aber es scheint ihm zu umst\u00e4ndlich zu sein.
\n<\/a><\/noindex>
\nIch fand zwei Tippfehler und einen historischen Fehler. Ich werde sie der Reihenfolge nach auflisten, beginnend mit dem unbedeutendsten.<\/p>\n

Tippfehler Nr. 1<\/h1>\n

\nDer erste Tippfehler befindet sich auf Seite 392 des dritten Bandes \u201eSortierung und Suche\u201c, achte Zeile von unten: \u201eNach einem erfolglosen Suchvorgang ist es manchmal (sometime) w\u00fcnschenswert, einen neuen Eintrag in die Tabelle einzuf\u00fcgen, der enth\u00e4lt K<\/i>; die Methode, die dies tut, wird als Einf\u00fcge- und Suchalgorithmus bezeichnet. Der Fehler besteht darin, dass anstelle von manchmal<\/i><\/b> sollte sein manchmal<\/i><\/b>.<\/p>\n

Nat\u00fcrlich ist es nicht \u00fcberraschend, dass ein solcher Fehler auftritt. In diesem Artikel werden sicherlich einige Tippfehler zu finden sein (keine Auszeichnungen f\u00fcr deren Auffindung). Was wirklich erstaunlich ist, ist, dass man sie so lange nicht bemerkt hat. Seite 392 ist nicht tief im Mathematikabschnitt vergraben; das ist die erste Seite<\/b> des sechsten Kapitels \u201eSuche\u201c! Wahrscheinlich einer der am h\u00e4ufigsten gelesenen Abschnitte des Buches. Dort sollten eigentlich die wenigsten Tippfehler zu finden sein, aber dem ist nicht so.<\/p>\n

\u00dcbrigens, wenn Sie jemals gedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass es ein Nachschlagewerk<\/b>, das nicht zum direkten Lesen gedacht ist, aber das stimmt nicht. Der Autor hat eine klare Perspektive und einen eigenen Stil. Das einzige, was die Lesbarkeit behindert, ist die Komplexit\u00e4t der Mathematik. Es gibt jedoch eine einfache L\u00f6sung: Lesen Sie, bis Sie zur Mathematik gelangen, die Sie nicht verstehen, \u00fcbergehen Sie diese und \u00f6ffnen Sie das n\u00e4chste Kapitel, das Sie verstehen k\u00f6nnen. Durch dieses Vorgehen \u00fcberspringe ich mindestens 80 % des Buches, aber die restlichen 20 % sind gro\u00dfartig!<\/p>\n

Es wird auch gesagt, dass TAOCP irrelevant ist<\/b>, ist veraltet oder auf andere Weise nicht anwendbar auf \u201eechte Programmierung\u201c. Das stimmt ebenfalls nicht. Zum Beispiel wird im ersten Abschnitt nach der Einf\u00fchrung die Suche nach einem Element in einem unsortierten Array behandelt. Der einfachste Algorithmus ist allen Programmierern bekannt. Starten Sie den Zeiger am Anfang des Arrays und f\u00fchren Sie dann folgende Schritte in einer Schleife aus:<\/p>\n

    \n
  1. \u00dcberpr\u00fcfen Sie, ob das aktuelle Element das gew\u00fcnschte ist. Wenn ja, geben Sie es zur\u00fcck; andernfalls\n<\/li>\n
  2. \u00dcberpr\u00fcfen Sie, ob der Zeiger au\u00dferhalb des Arrays liegt. Wenn ja, geben Sie einen Fehler zur\u00fcck; andernfalls\n<\/li>\n
  3. Erh\u00f6hen Sie den Zeiger und fahren Sie fort.<\/li>\n<\/ol>\n

    \nNun betrachten wir: Wie viele Grenz\u00fcberpr\u00fcfungen erfordert dieser Algorithmus im Durchschnitt? Im schlimmsten Fall, wenn das Array kein Element enth\u00e4lt, ist f\u00fcr jedes Element in der Liste eine \u00dcberpr\u00fcfung erforderlich, und im Durchschnitt wird es etwa \"Icherfordern. Ein ausgekl\u00fcgelterer Suchalgorithmus k\u00f6nnte nur eine Grenz\u00fcberpr\u00fcfung ben\u00f6tigen. F\u00fcgen Sie das gesuchte Element ans Ende des Arrays an, starten Sie dann den Zeiger am Anfang des Arrays und f\u00fchren Sie folgende Schritte in einer Schleife aus:<\/p>\n

      \n
    1. \u00dcberpr\u00fcfen Sie, ob das aktuelle Element das gew\u00fcnschte ist. Wenn ja, geben wir eine Antwort zur\u00fcck, wenn der Zeiger im Array liegt, oder einen Fehler, wenn nicht. Andernfalls\n<\/li>\n
    2. Erh\u00f6hen Sie den Zeiger und fahren Sie fort.<\/li>\n<\/ol>\n

      \nWie dem auch sei, das Element wird garantiert gefunden, und die Grenz\u00fcberpr\u00fcfung erfolgt nur einmal, wenn dies geschieht. Es ist eine tiefgreifende Idee, aber sie ist einfach genug, selbst f\u00fcr einen Anf\u00e4ngerprogrammierer. Vielleicht kann ich nicht \u00fcber die Relevanz der Arbeit f\u00fcr andere sprechen, aber ich konnte diese Weisheit sofort sowohl in meinem pers\u00f6nlichen als auch in meinem beruflichen Code anwenden. Das Buch TAOCP ist voll von solchen Perlen (um fair zu sein, es gibt auch viele seltsame Sachen darin, wie Bubble Sort<\/a><\/noindex>).<\/p>\n

      \u201eSuchen, suchen\u201c
      \nSo lange
      \nSuchen, suchen
      \nIch wollte einfach nur tanzen\u201c<\/i>
      \n\u2014 Luther Vandross, \u201eSuchen\u201c (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Tippfehler Nr. 2<\/h1>\n

      \nDer zweite Druckfehler befindet sich im Band 4A, \"Kombinatorische Algorithmen\", Teil 1. Auf Seite 60 wird das Problem der Planung von Auftritten von Comedians in verschiedenen Casinos beschrieben. Als Beispiel werden mehrere echte Comedians genannt, darunter Lily Tomlin, \"Weird Al\" Yankovic und Robin Williams, der noch am Leben war, als das Buch ver\u00f6ffentlicht wurde. Knuth f\u00fchrt im Index immer vollst\u00e4ndige Namen an, weshalb Williams auf Seite 882 als \"Williams, Robin McLaurin\" erw\u00e4hnt wird. Doch sein zweiter Vorname endet auf \"n\" und nicht auf \"m\", also McLaurin.<\/p>\n

      McLaurin ist der M\u00e4dchenname seiner Mutter. Sie war die Ururenkelin von Anselm Joseph McLaurin, dem 34. Gouverneur von Mississippi. Seine Amtszeit ist anscheinend nicht durch etwas Positives in Erinnerung geblieben. Aus dem Buch \"Mississippi: Geschichte\"<\/a><\/noindex>:<\/p>\n

      \u201eDas wichtigste Ereignis w\u00e4hrend der Amtszeit von MacLorin war die Kriegserkl\u00e4rung der Vereinigten Staaten an Spanien im Fr\u00fchjahr 1898... Leider bot der Krieg m\u00f6glicherweise einigen Regierungsbeamten die Gelegenheit, Bestechung auszunehmen. MacLorin wurde verschiedener fragw\u00fcrdiger Praktiken beschuldigt, einschlie\u00dflich Nepotismus und \u00fcberm\u00e4\u00dfigen Einsatz der Begnadigungsbefugnisse. In der \u00c4ra der Abstinenz warf man dem Gouverneur Trunkenheit vor, was er \u00f6ffentlich einr\u00e4umte.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historischer Fehler<\/h1>\n

      \nLassen Sie uns betrachten traditioneller Multiplikationsalgorithmus<\/b> aus dem Lehrplan. Wie viele eindimensionale Multiplikationsoperationen sind erforderlich? Angenommen, Sie multiplizieren \"Ich-stellige Zahl \"Ich findet man \"Ich-stellig \"Ich. Zuerst multiplizieren Sie die erste Ziffer \"Ich mit jeder Ziffer \"Ich nacheinander. Dann multiplizieren Sie die zweite Ziffer \"Ich mit jeder Ziffer \"Ich nacheinander und so weiter, bis Sie alle Ziffern durchlaufen haben. \"Ich. Auf diese Weise erfordert die traditionelle Multiplikation \"Ich primitive Multiplikationen. Insbesondere die Multiplikation zweier Zahlen nach \"Ich Stellen erfordert \"Ich eindimensionale Multiplikationen.<\/p>\n

      Das ist nicht ideal, aber der Prozess kann durch eine Methode optimiert werden, die von dem sowjetischen Mathematiker Anatoli Alexejewitsch Karazub entwickelt wurde. Angenommen, dass \"Ich und \"Ich\u00a0es zweistellige Dezimalzahlen gibt; das hei\u00dft, es existieren Zahlen \"Ich, \"Ich, \"Ich, \"Ich sodass \"Ich und \"Ich (die Generalisierung dieses Algorithmus f\u00fcr gr\u00f6\u00dfere Ziffern erfordert bestimmte Manipulationen; obwohl das nicht allzu kompliziert ist, halte ich es f\u00fcr besser, bei einem einfachen Beispiel zu bleiben, um Missverst\u00e4ndnisse zu vermeiden). Dann \"Ich, \"Ich, \"Ich. Das Multiplikation von Binomen ergibt \"Ich. Bis jetzt haben wir immer noch \"Ich einfache Multiplikationen: \"Ich, \"Ich, \"Ich, \"Ich. Jetzt addieren und subtrahieren wir \"Ich. Nach mehreren Umstellungen, die ich dem Leser als \u00dcbung \u00fcberlasse, erh\u00e4lt man \"Ich\u00a0\u2014 insgesamt drei einfache Multiplikationen! (Es gibt einige feste Koeffizienten, die nur durch Addition und Verschiebung der Stellen berechnet werden k\u00f6nnen).<\/p>\n

      Bitte verlangen Sie keinen Beweis, aber der Karazuba-Algorithmus<\/b> (rekursiv aus dem obigen Beispiel generalisiert) verbessert die traditionelle Multiplikationsmethode von \"Ich Operationen auf \"Ich. Bitte beachten Sie, dass dies eine tats\u00e4chliche Verbesserung des Algorithmus ist und keine Optimierung f\u00fcr das Kopfrechnen. In der Tat ist der Algorithmus nicht f\u00fcr das Kopfrechnen geeignet, da er hohe Overheadkosten f\u00fcr rekursive Operationen erfordert. Dar\u00fcber hinaus wird der Effekt nicht vollst\u00e4ndig sichtbar, bis die Zahlen gro\u00df genug sind (zum Gl\u00fcck kamen nach dem Karatsuba-Algorithmus noch schnellere Methoden: Im M\u00e4rz 2019 wurde ein Algorithmus ver\u00f6ffentlicht, der nur n log n<\/i><\/a><\/noindex> Multiplikationen ben\u00f6tigt; die Beschleunigung ist nur f\u00fcr unvorstellbar gro\u00dfe Zahlen anwendbar).<\/p>\n

      Dieser Algorithmus wird auf Seite 295 des zweiten Bandes von \u00abDie Kunst des Programmierens\u00bb beschrieben. Dort schreibt Knuth: \u201eEs ist merkw\u00fcrdig, dass diese Idee erst im 1962<\/b> Jahr entdeckt wurde\u201c, als ein Artikel ver\u00f6ffentlicht wurde, der den Karatsuba-Algorithmus beschreibt. Aber! Im Jahr 1995 ver\u00f6ffentlichte Karatsuba den Artikel \u201eDie Komplexit\u00e4t der Berechnungen\u201c, in dem er mehrere Dinge sagt: 1) etwa 1956 vermutete Kolmogorov, dass Multiplikation nicht in weniger als \"Ich Schritten durchgef\u00fchrt werden kann; 2) in 1960<\/b> Im Jahr pr\u00e4sentierte Karatsuba auf einem Seminar, wo Kolmogorov seine Hypothese n\u00b2 darlegte. 3) \u201eGenau eine Woche sp\u00e4ter\u201c entwickelte Karatsuba den Algorithmus \u201eTeile und herrsche\u201c; 4) 1962 schrieb und ver\u00f6ffentlichte Kolmogorov einen Artikel. im Namen von Karatsuba<\/i> mit der Beschreibung des Algorithmus. \u201eIch erfuhr von diesem Artikel erst, nachdem er nachgedruckt wurde.\u201c<\/p>\n

      Somit liegt der Fehler darin, dass anstelle von 1962<\/i> das Jahr angegeben werden sollte. 1960<\/i> Das ist alles.<\/p>\n

      Analyse<\/h1>\n

      \nDie Fehlersuche erforderte kein besonderes Geschick.<\/b><\/p>\n

        \n
      1. Der erste Fehler war so banal, wie es nur sein konnte, und befand sich an einer relativ auff\u00e4lligen Stelle (Anfang des Kapitels). Jeder Idiot h\u00e4tte ihn gefunden; nur ich war der Idiot.\n<\/li>\n
      2. Die Suche nach dem zweiten Fehler erforderte Gl\u00fcck und Flei\u00df, aber nicht unbedingt K\u00f6nnen. Das Verzeichnis f\u00fcr \u201eWilliams\u201c befindet sich auf der vorletzten Seite des Bandes, ein ziemlich bemerkenswerter Teil des Buches. Ich bl\u00e4tterte gerade durch das Inhaltsverzeichnis (es ist nicht so traurig, wie es scheint, denn in Knuths Verzeichnissen sind einige Easter Eggs versteckt. Zum Beispiel gibt es Eintr\u00e4ge in Arabisch und Hebr\u00e4isch, die beide auf Seite 66 verweisen. Aber auf dieser Seite wird keine der Sprachen erw\u00e4hnt; stattdessen wird von \u201eSprachen, die von rechts nach links gelesen werden\u201c gesprochen). Und meine Aufmerksamkeit wurde auf den zweiten Namen gelenkt. Da ich normalerweise Wikipedia lese, habe ich Robin Williams \u00fcberpr\u00fcft und eine Diskrepanz bemerkt.\n<\/li>\n
      3. Ich w\u00fcnschte, ich k\u00f6nnte sagen, dass ich ernsthaft recherchiert habe, um den historischen Fehler zu finden, aber tats\u00e4chlich habe ich einfach nur einen Blick auf die Wikipedia-Seite \u00fcber den Karatsuba-Algorithmus<\/a><\/noindex>. In den ersten Zeilen steht: \u201eDer Karatsuba-Algorithmus ist ein Algorithmus f\u00fcr schnelles Multiplizieren. Er wurde von Anatoli Karatsuba 1960 entdeckt und 1962 ver\u00f6ffentlicht.\u201c Danach blieb nur noch, zwei plus zwei zu addieren.<\/li>\n<\/ol>\n

        \nIn Zukunft m\u00f6chte ich einen bedeutenderen Fehler finden, insbesondere im Knuth-Code. Ich w\u00fcrde auch gerne einen Fehler im ersten Band von \u201eDie Kunst der Programmierung\u201c finden. Vielleicht w\u00fcrde ich das finden, aber in der \u00f6rtlichen Bibliothek gibt es aus irgendeinem Grund nur die B\u00e4nde 2, 3 und 4A.<\/p>\n

        Finanzielle Fakten:<\/b><\/p>\n