{"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\/es\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Recib\u00ed un cheque de Knuth por 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0es un cient\u00edfico en el campo de la inform\u00e1tica que se preocupa tanto por la precisi\u00f3n de sus libros que ofrece un d\u00f3lar hexadecimal<\/b> ($2.56, 0x$1.00) por cualquier \u00aberror\u00bb encontrado, donde un error se considera todo lo que es \u00abt\u00e9cnicamente, hist\u00f3ricamente, tipogr\u00e1ficamente o pol\u00edticamente incorrecto\u00bb. Ten\u00eda muchas ganas de recibir un cheque de Knuth, as\u00ed que decid\u00ed buscar errores en su obra maestra \u00abEl arte de la programaci\u00f3n\u00bb<\/b> (TAOCP). Logr\u00e9 encontrar tres. Cumpliendo con mi palabra, Knuth envi\u00f3 un cheque por 0x$3.00<\/b>.<\/p>\n

\"Recib\u00ed
\n
\nComo pueden ver, este no es un cheque real. Antes, Knuth enviaba cheques reales, pero dej\u00f3 de hacerlo en 2008 debido a fraudes desenfrenados<\/a><\/noindex>. Ahora env\u00eda \u00abcertificados de dep\u00f3sito personales\u00bb en el Banco San Serrif<\/a><\/noindex> (BoSS). Dice que est\u00e1 dispuesto a enviar dinero real si es necesario, pero parece que eso es demasiado engorroso.
\n<\/a><\/noindex>
\nEncontr\u00e9 dos erratas y un error hist\u00f3rico. Los enlistar\u00e9 en orden de trivialidad decreciente.<\/p>\n

Errata n\u00ba 1<\/h1>\n

\nLa primera errata se encuentra en la p\u00e1gina 392 del tercer volumen \u00abOrdenaci\u00f3n y b\u00fasqueda\u00bb, octava l\u00ednea desde abajo: \u00abDespu\u00e9s de una b\u00fasqueda fallida, a veces (sometime) es recomendable ingresar un nuevo registro en la tabla que contenga K<\/i>; el m\u00e9todo que realiza esto se llama algoritmo de b\u00fasqueda e inserci\u00f3n. El error es que en vez de sometime<\/i><\/b> debe ser sometimes<\/i><\/b>.<\/p>\n

Por supuesto, no hay nada sorprendente en tal error. Solo en este art\u00edculo, seguramente habr\u00e1 varios errores tipogr\u00e1ficos (sin recompensas por encontrarlos). Lo que realmente es sorprendente es que no haya sido notado durante tanto tiempo. La p\u00e1gina 392 no est\u00e1 enterrada profundamente en la secci\u00f3n de matem\u00e1ticas, es la primera p\u00e1gina<\/b> del cap\u00edtulo seis \u00abB\u00fasqueda\u00bb! Tal vez, una de las secciones m\u00e1s le\u00eddas del libro. Te\u00f3ricamente, deber\u00eda haber menos errores all\u00ed, pero no es as\u00ed.<\/p>\n

A prop\u00f3sito, si alguna vez has pensado en leer TAOCP, int\u00e9ntalo. Muchos dir\u00e1n que es un manual<\/b>, no dise\u00f1ado para lectura directa, pero eso no es cierto. El autor tiene una clara visi\u00f3n y un estilo peculiar. Lo \u00fanico que obstaculiza la legibilidad es la complejidad de las matem\u00e1ticas. Sin embargo, hay una soluci\u00f3n simple: lee hasta que llegues a las matem\u00e1ticas que no entiendes, salt\u00e9ate esa parte y abre la siguiente secci\u00f3n que puedas comprender. Leyendo de esta manera, me salto al menos el 80% del libro, \u00a1pero el resto del 20% es magn\u00edfico!<\/p>\n

Tambi\u00e9n se dice que TAOCP no es relevante<\/b>, obsoleta o de alguna manera irrelevante para la \u00abprogramaci\u00f3n real\u00bb. Esto tambi\u00e9n es falso. Por ejemplo, en la primera secci\u00f3n despu\u00e9s de la introducci\u00f3n se analiza la b\u00fasqueda de un elemento en un array desordenado. El algoritmo m\u00e1s sencillo es conocido por todos los programadores. Inicie el puntero al principio del array y luego realice las siguientes acciones en un ciclo:<\/p>\n

    \n
  1. Verifique si el elemento actual es el deseado. Si es as\u00ed, devu\u00e9lvalo; de lo contrario,\n<\/li>\n
  2. Verifique si el puntero est\u00e1 fuera del array. Si es as\u00ed, devuelva un error; de lo contrario,\n<\/li>\n
  3. Aumente el puntero y contin\u00fae.<\/li>\n<\/ol>\n

    \nAhora consideremos: \u00bfcu\u00e1ntas verificaciones de l\u00edmites requiere este algoritmo en promedio? En el peor de los casos, cuando el array no contiene el elemento, cada elemento de la lista requerir\u00e1 una verificaci\u00f3n, y en promedio esto ser\u00e1 algo as\u00ed como \"Recib\u00ed. Un algoritmo de b\u00fasqueda m\u00e1s inteligente puede requerir solo una verificaci\u00f3n de l\u00edmites. Adjunte el elemento deseado al final del array, luego inicie el puntero al principio del array y realice las siguientes acciones en un ciclo:<\/p>\n

      \n
    1. Verifique si el elemento actual es el deseado. Si es as\u00ed, devuelva la respuesta si el puntero est\u00e1 dentro del array, o un error si no lo est\u00e1. De lo contrario,\n<\/li>\n
    2. Aumente el puntero y contin\u00fae.<\/li>\n<\/ol>\n

      \nDe una manera u otra, el elemento se encontrar\u00e1 garantizado, y la verificaci\u00f3n de l\u00edmites se realiza solo una vez, cuando esto ocurre. Esta es una idea profunda, pero es lo suficientemente simple incluso para un programador principiante. Probablemente no puedo hablar sobre la relevancia del trabajo para otros, pero pude aplicar inmediatamente esta sabidur\u00eda tanto en mi c\u00f3digo personal como profesional. El libro TAOCP est\u00e1 lleno de estas joyas (y para ser justos, tambi\u00e9n hay muchas cosas extra\u00f1as, como ordenamiento burbuja<\/a><\/noindex>).<\/p>\n

      \u00abBuscar, buscar
      \nTanto tiempo
      \nBuscar, buscar
      \nSolo quer\u00eda bailar\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abSearch\u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Error tipogr\u00e1fico #2<\/h1>\n

      \nLa segunda errata se encuentra en el volumen 4A, \"Algoritmos Combinatorios\", parte 1. En la p\u00e1gina 60 se describe un problema sobre la planificaci\u00f3n de las presentaciones de comediantes en varios casinos. Como ejemplo, se mencionan varios comediantes reales, incluyendo a Lily Tomlin, \"Weird Al\" Yankovic y Robin Williams, quien a\u00fan estaba vivo cuando se public\u00f3 el libro. Knuth siempre incluye los nombres completos en el \u00edndice, as\u00ed que Williams se menciona en la p\u00e1gina 882 como \"Williams, Robin Mac-Lorin\". Pero su segundo nombre termina en \"n\", no en \"m\", es decir, Mac-Lorin.<\/p>\n

      Mac-Lorin es el apellido de soltera de su madre. Ella era bisnieta de Anselm Joseph Mac-Lorin, el 34\u00ba gobernador de Mississippi. Su mandato, aparentemente, no fue recordado por nada bueno. Del libro \"Mississippi: Historia\"<\/a><\/noindex>:<\/p>\n

      \"El evento m\u00e1s importante durante la administraci\u00f3n de Mac-Lorin fue la declaraci\u00f3n de guerra de los Estados Unidos a Espa\u00f1a en la primavera de 1898... Desafortunadamente, la guerra puede haber dado a algunos funcionarios estatales la oportunidad de practicar la corrupci\u00f3n. Mac-Lorin fue acusado de varias pr\u00e1cticas dudosas, incluyendo nepotismo y abuso excesivo de su poder de indulto. En la \u00e9poca del movimiento por la sobriedad, los cr\u00edticos acusaron al gobernador de embriaguez, lo cual \u00e9l admiti\u00f3 p\u00fablicamente.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Error hist\u00f3rico<\/h1>\n

      \nConsideremos algoritmo tradicional de multiplicaci\u00f3n<\/b> del programa escolar. \u00bfCu\u00e1ntas operaciones de multiplicaci\u00f3n de un solo d\u00edgito requiere? Supongamos que multiplicas \"Recib\u00edun n\u00famero de -d\u00edgitos \"Recib\u00ed en \"Recib\u00edde -d\u00edgitos. \"Recib\u00edPrimero multiplicas el primer d\u00edgito \"Recib\u00ed por cada d\u00edgito \"Recib\u00ed uno por uno. Luego multiplicas el segundo d\u00edgito \"Recib\u00ed por cada d\u00edgito \"Recib\u00ed uno por uno y as\u00ed sucesivamente, hasta que hayas pasado por todos los d\u00edgitos. \"Recib\u00edDe este modo, la multiplicaci\u00f3n tradicional requiere \"Recib\u00ed multiplicaciones primitivas. En particular, multiplicar dos n\u00fameros de \"Recib\u00ed d\u00edgitos requiere \"Recib\u00ed multiplicaciones de un solo d\u00edgito.<\/p>\n

      Es malo, pero se puede optimizar el proceso usando un m\u00e9todo desarrollado por el matem\u00e1tico sovi\u00e9tico Anatoly Alexeyevich Karatsuba. Supongamos que \"Recib\u00ed y \"Recib\u00ed\u00a0son n\u00fameros decimales de dos d\u00edgitos; es decir, existen n\u00fameros \"Recib\u00ed, \"Recib\u00ed, \"Recib\u00ed, \"Recib\u00ed tales que \"Recib\u00ed y \"Recib\u00ed (la generalizaci\u00f3n de este algoritmo a cifras mayores requiere ciertas manipulaciones; aunque no es muy complicado, pero para no equivocarme en los detalles, mejor seguir\u00e9 con un ejemplo simple). Entonces \"Recib\u00ed, \"Recib\u00ed, \"Recib\u00ed. La multiplicaci\u00f3n de binomios da \"Recib\u00ed. Hasta ahora, todav\u00eda tenemos \"Recib\u00ed multiplicaciones de un solo d\u00edgito: \"Recib\u00ed, \"Recib\u00ed, \"Recib\u00ed, \"Recib\u00ed. Ahora sumemos y restemos. \"Recib\u00ed. Despu\u00e9s de varios reordenamientos, que dejar\u00e9 como ejercicio para el lector, se obtiene \"Recib\u00ed\u00a0\u2014 \u00a1solo tres multiplicaciones de un solo d\u00edgito! (Hay algunos coeficientes constantes, pero se pueden calcular solo con suma y desplazamiento de d\u00edgitos).<\/p>\n

      No pidas pruebas, pero el algoritmo de Karatsuba<\/b> (generalizado recursivamente del ejemplo anterior) mejora el m\u00e9todo tradicional de multiplicaci\u00f3n de \"Recib\u00ed operaciones a \"Recib\u00ed. Ten en cuenta que esta es una mejora real del algoritmo y no una optimizaci\u00f3n para c\u00e1lculos mentales. De hecho, el algoritmo no es adecuado para hacer c\u00e1lculos mentales, ya que implica grandes sobrecargas por las operaciones recursivas. Adem\u00e1s, el efecto no se manifestar\u00e1 completamente hasta que los n\u00fameros sean lo suficientemente grandes (afortunadamente, en lugar del algoritmo de Karatsuba han surgido m\u00e9todos a\u00fan m\u00e1s r\u00e1pidos: en marzo de 2019 se public\u00f3 un algoritmo que requiere solo n log n<\/i><\/a><\/noindex> multiplicaciones; la aceleraci\u00f3n es aplicable solo a n\u00fameros inconcebiblemente grandes).<\/p>\n

      Este algoritmo est\u00e1 descrito en la p\u00e1gina 295 del segundo volumen de \u00abAlgoritmos generados\u00bb. All\u00ed, Knuth escribe: \u00abCuriosamente, esta idea fue descubierta solo en 1962<\/b> a\u00f1o\u00bb, cuando se public\u00f3 el art\u00edculo que describe el algoritmo de Karatsuba. \u00a1Pero! En 1995, Karatsuba public\u00f3 un art\u00edculo titulado \u00abComplejidad de los c\u00e1lculos\u00bb, en el que menciona varias cosas: 1) alrededor de 1956 Kolmogorov supuso que la multiplicaci\u00f3n no podr\u00eda llevarse a cabo en menos de \"Recib\u00ed pasos; 2) en 1960<\/b> a\u00f1o, Karatsuba asisti\u00f3 a un seminario donde Kolmogorov expuso su hip\u00f3tesis n\u00b2. 3) \u00abJusto hace una semana\u00bb Karatsuba desarroll\u00f3 el algoritmo de \u00abdivide y vencer\u00e1s\u00bb; 4) en 1962 Kolmogorov escribi\u00f3 y public\u00f3 un art\u00edculo en nombre de Karatsuba<\/i> describiendo el algoritmo. \u00abSolo supe de este art\u00edculo despu\u00e9s de que fue reimpreso\u00bb.<\/p>\n

      Por lo tanto, el error radica en que en lugar de 1962<\/i> deber\u00eda indicarse 1960<\/i> el a\u00f1o. Eso es todo.<\/p>\n

      An\u00e1lisis<\/h1>\n

      \nBuscar errores no requer\u00eda habilidades especiales.<\/b><\/p>\n

        \n
      1. El primer error fue tan b\u00e1sico como es posible y estaba en un lugar relativamente visible (al comienzo del cap\u00edtulo). Cualquiera podr\u00eda haberlo encontrado; simplemente yo fui ese cualquiera.\n<\/li>\n
      2. La b\u00fasqueda del segundo error tipogr\u00e1fico requiri\u00f3 suerte y esfuerzo, pero no habilidad. El \u00edndice para \"Williams\" se encuentra en la pen\u00faltima p\u00e1gina del volumen, una parte bastante notable del libro. Justo estaba hojeando el \u00edndice (no es tan doloroso como parece, ya que en los \u00edndices de Knuth se esconden huevos de Pascua. Por ejemplo, hay entradas en \u00e1rabe y hebreo, ambas apuntando a la p\u00e1gina 66. Pero en esa p\u00e1gina no se menciona ninguno de los idiomas; en cambio, se mencionan \"idiomas que se leen de derecha a izquierda\"). Y mi atenci\u00f3n fue capturada por el segundo nombre. Dado que normalmente leo Wikipedia, verifiqu\u00e9 a Robin Williams y not\u00e9 una discrepancia.\n<\/li>\n
      3. Me gustar\u00eda decir que hice una investigaci\u00f3n seria para encontrar un error hist\u00f3rico, pero en realidad solo eche un vistazo a la p\u00e1gina de Wikipedia sobre el algoritmo Karatsuba.<\/a><\/noindex>En las primeras l\u00edneas dice: \"El algoritmo Karatsuba es un algoritmo de multiplicaci\u00f3n r\u00e1pida. Descubierto por Anatoliy Karatsuba en 1960 y publicado en 1962\". Despu\u00e9s de eso, solo quedaba sumar dos m\u00e1s dos.<\/li>\n<\/ol>\n

        \nEn el futuro, me gustar\u00eda encontrar un error m\u00e1s sustancial, especialmente en el c\u00f3digo de Knuth. Tambi\u00e9n me gustar\u00eda encontrar un fallo en el primer volumen de \"Algoritmos Fundamentales\". Quiz\u00e1s lo hubiera encontrado, pero en la biblioteca local por alguna raz\u00f3n solo hay disponibles los vol\u00famenes 2, 3 y 4A.<\/p>\n

        Hechos financieros:<\/b><\/p>\n