{"id":12781,"date":"2026-07-21T11:33:47","date_gmt":"2026-07-21T14:33:47","guid":{"rendered":"http:\/\/laf5.publisher.highstack.com.ar\/?p=12781"},"modified":"2026-07-21T11:33:47","modified_gmt":"2026-07-21T14:33:47","slug":"las-computadoras-llevan-decadas-usando-trucos-matematicos-cada-vez-mas-complejos-para-contar-cuantas-cosas-distintas-pasan-frente-a-ellas-tres-cientificos-encontraron-una-solucion-basada-en-lanzar-mo","status":"publish","type":"post","link":"https:\/\/laf5.publisher.highstack.com.ar\/?p=12781","title":{"rendered":"Las computadoras llevan d\u00e9cadas usando trucos matem\u00e1ticos cada vez m\u00e1s complejos para contar cu\u00e1ntas cosas distintas pasan frente a ellas. Tres cient\u00edficos encontraron una soluci\u00f3n basada en lanzar monedas que podr\u00eda acabar en todos los libros de inform\u00e1tica"},"content":{"rendered":"
\n

Contar parece una de las operaciones m\u00e1s sencillas que puede realizar una computadora. Basta con sumar uno, despu\u00e9s otro y continuar hasta alcanzar el final. El problema comienza cuando la pregunta cambia ligeramente: \u00bfcu\u00e1ntas cosas distintas han aparecido dentro de una corriente de datos gigantesca?<\/p>\n

Una plataforma puede recibir millones de visitas, aunque muchas pertenezcan al mismo usuario. Una red puede procesar incontables conexiones procedentes de direcciones repetidas. Un sistema de ventas puede registrar millones de operaciones realizadas con unos cuantos miles de productos. Para obtener el n\u00famero exacto de elementos \u00fanicos, la m\u00e1quina tendr\u00eda que recordar todo lo visto y comprobar continuamente si cada dato ya hab\u00eda aparecido.<\/p>\n

Ese desaf\u00edo, conocido como el problema de los elementos distintos o estimaci\u00f3n de F0, lleva m\u00e1s de cuatro d\u00e9cadas ocupando a los investigadores. Ya exist\u00edan algoritmos muy eficientes, pero sus demostraciones recurr\u00edan a herramientas como funciones hash universales e independencia por pares, conceptos dif\u00edciles de explicar fuera de cursos avanzados. Tres cient\u00edficos encontraron una alternativa sorprendentemente directa: conservar una muestra aleatoria y reducirla mediante el equivalente digital de lanzar monedas.<\/p>\n

El verdadero problema no es contar: es recordar todo lo que ya apareci\u00f3<\/h2>\n

Imaginemos una lista formada por millones de palabras. Contar cu\u00e1ntas contiene es sencillo, porque cada nueva entrada aumenta el contador. Identificar cu\u00e1ntas son diferentes exige saber si cada palabra ya apareci\u00f3 anteriormente.<\/p>\n

La soluci\u00f3n exacta consiste en guardar todos los elementos \u00fanicos dentro de una estructura de memoria. Funciona bien mientras la lista sea peque\u00f1a, pero deja de ser pr\u00e1ctica cuando los datos llegan continuamente y su variedad supera con creces la capacidad disponible. Por eso los algoritmos de streaming intentan procesar cada dato una sola vez y conservar \u00fanicamente una representaci\u00f3n compacta del conjunto.<\/p>\n

Sourav Chakraborty, N. V. Vinodchandran y Kuldeep S. Meel presentaron en el European Symposium on Algorithms de 2022 un m\u00e9todo basado \u00fanicamente en muestreo y probabilidad elemental. El objetivo no era superar todas las soluciones existentes en cada m\u00e9trica, sino conseguir un algoritmo con un uso reducido de memoria cuya l\u00f3gica y demostraci\u00f3n pudieran entender estudiantes universitarios sin dominar t\u00e9cnicas matem\u00e1ticas especializadas.<\/p>\n

Por tanto, el avance no consiste en que las computadoras hayan aprendido repentinamente a contar. Consiste en que pueden estimar cu\u00e1ntos elementos diferentes han visto sin guardar una copia de cada uno ni depender de una maquinaria criptogr\u00e1fica o estad\u00edstica dif\u00edcil de implementar y analizar.<\/p>\n

El algoritmo guarda una muestra y lanza monedas cuando la memoria se llena<\/h2>\n
\"Las
\u00a9 Nico Roper \/ Quanta Magazine.<\/figcaption><\/figure>\n

El funcionamiento b\u00e1sico del CVM resulta casi desconcertante por su sencillez. El sistema comienza guardando los elementos distintos que encuentra con una probabilidad de uno: en otras palabras, conserva inicialmente todo.<\/p>\n

Tambi\u00e9n mantiene una variable llamada p, que representa la probabilidad con la que cada elemento ha sido incluido en la muestra. Cuando el espacio disponible alcanza su l\u00edmite, el algoritmo lanza una moneda virtual para cada elemento almacenado y descarta aproximadamente la mitad. Despu\u00e9s divide tambi\u00e9n entre dos la probabilidad de muestreo.<\/p>\n

Si vuelve a llenarse, repite el proceso. La memoria vuelve a reducirse aproximadamente a la mitad y la probabilidad pasa, por ejemplo, de 1\/2 a 1\/4, despu\u00e9s a 1\/8 y as\u00ed sucesivamente. Cuando termina de procesar los datos, divide la cantidad de elementos conservados entre esa probabilidad.<\/p>\n

La intuici\u00f3n puede explicarse sin f\u00f3rmulas. Si una persona guarda una de cada cuatro flores que encuentra y termina sosteniendo cinco, probablemente ha visto unas veinte. El algoritmo realiza esencialmente ese mismo c\u00e1lculo, pero incorpora reglas para gestionar duplicados y mantener una muestra estad\u00edsticamente v\u00e1lida mientras los datos contin\u00faan llegando.<\/p>\n

Eso no significa que entregue exactamente el mismo resultado en todas las ejecuciones. Es un algoritmo aleatorio y, con muy poca memoria, su estimaci\u00f3n puede desviarse. Al aumentar el tama\u00f1o del espacio reservado, el margen de error disminuye. El trabajo original demuestra c\u00f3mo ajustar ese tama\u00f1o para obtener una aproximaci\u00f3n dentro de un error determinado y con una probabilidad de fallo controlada.<\/p>\n

Donald Knuth lo vio y pens\u00f3 inmediatamente en los futuros libros de inform\u00e1tica<\/h2>\n

La propuesta llam\u00f3 la atenci\u00f3n de Donald Knuth, una de las figuras m\u00e1s influyentes de la inform\u00e1tica te\u00f3rica. En mayo de 2023 public\u00f3 una extensa nota sobre el m\u00e9todo, lo bautiz\u00f3 como algoritmo CVM por las iniciales de Chakraborty, Vinodchandran y Meel, y asegur\u00f3 que no pod\u00eda evitar explic\u00e1rselo a casi todas las personas con las que hablaba.<\/p>\n

Knuth consider\u00f3 que su combinaci\u00f3n de sencillez y profundidad lo convert\u00eda en un candidato natural para aparecer en futuros libros de texto. Tambi\u00e9n detect\u00f3 un problema sutil en una formulaci\u00f3n inicial y present\u00f3 una versi\u00f3n modificada que conserva la idea central, pero ajusta la manera en que se gestiona el desbordamiento de la memoria.<\/p>\n

El inter\u00e9s no termin\u00f3 all\u00ed. En 2025, otro equipo formaliz\u00f3 matem\u00e1ticamente el algoritmo mediante Isabelle\/HOL, un asistente inform\u00e1tico utilizado para verificar demostraciones. El trabajo confirm\u00f3 sus propiedades y present\u00f3 una variante adicional que siempre produce un resultado y mantiene una estimaci\u00f3n sin sesgo.<\/p>\n

El CVM no vuelve irrelevantes a los m\u00e9todos anteriores ni resuelve el conteo exacto sin coste. Su importancia es m\u00e1s silenciosa: demuestra que un problema estudiado durante d\u00e9cadas todav\u00eda pod\u00eda admitir una soluci\u00f3n radicalmente m\u00e1s comprensible.<\/p>\n

A veces, la inform\u00e1tica avanza construyendo sistemas cada vez m\u00e1s complejos. Otras veces lo hace descubriendo que bastaba con guardar unas pocas cosas, lanzar algunas monedas y multiplicar lo que sobrevivi\u00f3.<\/p>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

Contar parece una de las operaciones m\u00e1s sencillas que puede realizar una computadora. Basta con sumar uno, despu\u00e9s otro y continuar hasta alcanzar el final. El problema comienza cuando la pregunta cambia ligeramente: \u00bfcu\u00e1ntas cosas distintas han aparecido dentro de una corriente de datos gigantesca? Una plataforma puede recibir millones de visitas, aunque muchas pertenezcan […]<\/p>\n","protected":false},"author":1,"featured_media":12782,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-12781","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-sin-categoria"],"_links":{"self":[{"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/posts\/12781","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=12781"}],"version-history":[{"count":0,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/posts\/12781\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=\/wp\/v2\/media\/12782"}],"wp:attachment":[{"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=12781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=12781"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laf5.publisher.highstack.com.ar\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=12781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}