{"id":2934,"date":"2025-07-21T11:01:47","date_gmt":"2025-07-21T14:01:47","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2934"},"modified":"2025-07-31T09:31:12","modified_gmt":"2025-07-31T12:31:12","slug":"en-busca-de-algoritmos-optimos","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/en-busca-de-algoritmos-optimos\/","title":{"rendered":"En busca de algoritmos \u00f3ptimos"},"content":{"rendered":"

Ver\u00f3nica Becher es investigadora principal de CONICET en el ICC y directora de KAPOW, un grupo de teor\u00eda de la computaci\u00f3n con foco en problemas combinatorios y aleatoriedad. Recientemente fue designada editora asociada del <\/b>Journal of Complexity<\/i><\/b>, una prestigiosa publicaci\u00f3n internacional que se enmarca en la complejidad desde un punto de vista matem\u00e1tico y computacional. En esta nota nos cuenta sobre los desaf\u00edos de edici\u00f3n en la revista y algunas de las dificultades te\u00f3ricas que surgen a la hora de resolver problemas complejos.<\/b><\/p>\n

La complejidad computacional es un concepto fundamental en inform\u00e1tica que cuantifica\u00a0 los recursos necesarios para resolver problemas computacionales. Claramente en computaci\u00f3n cient\u00edfica, investigar los aspectos te\u00f3ricos de la complejidad computacional resulta crucial para desarrollar algoritmos eficientes y escalables.<\/span><\/p>\n

En este caso la complejidad temporal mide qu\u00e9 tan r\u00e1pido puede ejecutarse un algoritmo, mientras que la complejidad espacial mide cu\u00e1nta memoria necesita un algoritmo. A veces, se puede mejorar uno a expensas del otro, pero no siempre. Por ejemplo, una tabla <\/span>hash<\/span><\/i> acelera la b\u00fasqueda de un elemento en una matriz, pero tambi\u00e9n consumir\u00e1 m\u00e1s memoria.\u00a0\u00a0<\/span><\/p>\n

Medidas de la complejidad computacional<\/b><\/p>\n

La compleijidad de objetos matem\u00e1tico-computacionales es una funci\u00f3n tal que a cada objeto le asigna un valor num\u00e9rico.\u00a0\u00a0<\/span><\/p>\n

Por ejemplo, una medida de complejidad de polinomios es el grado del polinomio. Otra medida de complejidad es la altura (o magnitud) de sus coeficientes. Luego tenemos problemas definidos sobre esos objetos, por ejemplo evaluar un polinomio, sumar dos polinomios, derivar un polinomio, etc. En definitiva, la complejidad de estos problemas se expresa en funci\u00f3n de la complejidad de la entrada.<\/span><\/p>\n

En este contexto, la revista <\/span>Journal of Complexity<\/span><\/i> -fundada en 1985 por Joseph F. Traub- publica art\u00edculos de investigaci\u00f3n originales que contienen resultados matem\u00e1ticos sustanciales sobre la complejidad y los sistemas complejos en su concepci\u00f3n amplia. Es la revista de mayor impacto en el \u00e1rea de la complejidad computacional y su enfoque se centra en la complejidad sobre los n\u00fameros reales, con \u00e9nfasis en los cotas inferiores y algoritmos \u00f3ptimos.<\/span><\/p>\n

Y el a\u00f1o pasado la doctora <\/span>Ver\u00f3nica Becher<\/b> fue designada editora asociada, en complemento con su amplia tarea de edici\u00f3n en diversas revistas de matem\u00e1tica y computaci\u00f3n te\u00f3rica. Uno de los prop\u00f3sitos de esta revista es poder encontrar estas joyas matem\u00e1ticas que se denominan \u201calgoritmos \u00f3ptimos\u201d, aquellos que resuelven problemas o ecuaciones en el menor tiempo posible, con el menor costo posible, y donde existe una demostraci\u00f3n matem\u00e1tica de que no puede haber un algoritmo mejor.<\/span><\/p>\n

\u201c<\/span>Una cota inferior de complejidad indica que todo algoritmo que resuelva el problema necesitar\u00e1 al menos la cantidad de tiempo indicado por la cota, expresado como una funci\u00f3n del tama\u00f1o de la entrada. Y existen tambi\u00e9n las cotas superiores de complejidad, que es una funci\u00f3n que describe el comportamiento del peor caso de un algoritmo, es decir predice el peor escenario posible de un algoritmo<\/span><\/i>\u201d, explica la investigadora y profesora Veronica Becher. Y existe lo que se llama \u201ccomplejidad promedio\u201d, que es lo que m\u00e1s interesa en la vida real: \u201c<\/span>Si viene una entrada que no sabes de qu\u00e9 tipo va a ser, \u00bfa cu\u00e1nto apost\u00e1s? \u00bfC\u00f3mo se distribuye la complejidad sobre tu problema? Y esos son los temas que le interesa a esta revista<\/span><\/i>\u201d.<\/span><\/p>\n

Supongamos que debemos calcular el tiempo \u00f3ptimo que nos lleva viajar en auto a Mar del Plata: sabemos que lleva al menos 2 horas, pero existen algoritmos que nos llevan en 3 horas. El problema es, \u00bfexiste alguna soluci\u00f3n real entre 2 horas y 3? Entonces encontrar ese punto entre la cota inferior y los mejores resultados hasta el momento es muy dif\u00edcil. \u00bfC\u00f3mo se consigue dar resultados \u00f3ptimos? Cuando la cota inferior coincide con la instancia que uno tiene, dando cotas inferiores cada vez m\u00e1s cercanas al \u00f3ptimo.\u00a0\u00a0<\/span><\/p>\n

Esas soluciones se tienen que demostrar matem\u00e1ticamente. Y si un investigador determina esa medida de complejidad, ese costo de recursos para resolver un problema le tiene que dar una distribuci\u00f3n de que la mayor\u00eda de las instancias del problema son complejas y muy pocas son simples.\u00a0<\/span><\/p>\n

Si bien los art\u00edculos cient\u00edficos de esta \u00e1rea son muy espec\u00edficos y la investigadora recibe del editor en jefe (Erich Novak) unos pocos trabajos por mes para evaluar, la tarea le resulta demandante, considerando que el rango de temas es muy amplio de indagar ya que es complejidad en todas las posibles \u00e1reas. \u201c<\/span>No s\u00f3lo tengo que sumergirme en el tema desde cero sino tratar de dialogar con los principales referentes o pioneros en la tem\u00e1tica<\/span><\/i>\u201d, comenta entusiasmada Becher.<\/span><\/p>\n

Y aclara que si bien tradicionalmente el <\/span>Journal of Complexity<\/span><\/i> se ocupa del mundo continuo (n\u00fameros reales, funciones sobre n\u00fameros reales, ecuaciones diferenciales), \u201c<\/span>me incorporaron para ampliar el conjunto editorial y darle mi impronta respecto a mi trabajo en el mundo discreto (n\u00fameros naturales, s\u00edmbolos, grafos) con una aplicaci\u00f3n al mundo continuo<\/span><\/i>\u201d, detalla.<\/span><\/p>\n

Becher destaca que a nivel local, quien impuls\u00f3 la complejidad matem\u00e1tica y computacional en el mundo continuo y tuvo un enorme protagonismo en el \u00e1rea fue <\/span>Joos Heintz<\/b>, doctor en filosof\u00eda con orientaci\u00f3n matem\u00e1tica, profesor titular y em\u00e9rito en Exactas e investigador superior del CONICET,\u00a0 tanto en matem\u00e1ticas como en computaci\u00f3n. Motivado por su idea de integrar la matem\u00e1tica con temas netamente computacionales, sus contribuciones en complejidad computacional para resolver problemas de geometr\u00eda algebraica fueron muy profundas (<\/span>ver recuadro<\/b>).<\/span><\/p>\n

\u201c<\/span>El hecho de formar parte de esta\u00a0 revista de alto impacto, se lo debo principalmente a Joos, quien, entre varios logros de su trayectoria, se convirti\u00f3 en especialista en cotas inferiores de complejidad para resolver ecuaciones polinomiales y obtuvo dos premios en esta revista. Fue una persona brillante. Y poder continuar con ese legado me llena de orgullo<\/span><\/i>\u201d, comenta emocionada Becher, quien fue una de sus disc\u00edpulas.\u00a0\u00a0\u00a0\u00a0<\/span><\/p>\n

Algoritmos \u00f3ptimos: la b\u00fasqueda binaria y los aut\u00f3matas finitos<\/b><\/p>\n

Encontrar estos algoritmos \u00f3ptimos en el mundo real no es nada sencillo. Pero a\u00fan as\u00ed se pueden lograr algunas aproximaciones que permitan comprender c\u00f3mo estos problemas netamente te\u00f3ricos se conectan con aplicaciones actuales de la inform\u00e1tica.<\/span><\/p>\n

\u201c<\/span>Esos algoritmos \u00f3ptimos son extraordinarios y para eso realmente estudiamos e investigamos en computaci\u00f3n. Siempre les remarco a nuestros estudiantes que tenemos la responsabilidad de que cada vez que hay un algoritmo \u00f3ptimo debemos usarlo<\/span><\/i>\u201d, plantea la investigadora.<\/span><\/p>\n

En este sentido, Becher remarca algunos ejemplos sumamente interesantes:<\/span><\/p>\n

1) La b\u00fasqueda binaria<\/b>: supongamos que tenemos que encontrar el apellido Sadosky en el padr\u00f3n de electores para una votaci\u00f3n. Encontrar la palabra en la lista dada, que sabemos que est\u00e1 ordenada alfab\u00e9ticamente, tiene complejidad temporal de peor caso del orden de logar\u00edtmico en el tama\u00f1o de la lista<\/span> ya que <\/span>el <\/span>\u00e1rbol de decisi\u00f3n del problema tiene una altura logar\u00edtmica en el tama\u00f1o de la lista (para distinguir entre cada una de las posibles entradas).\u00a0\u00a0<\/span><\/p>\n

2) Los aut\u00f3matas finitos<\/b> son las m\u00e1quinas m\u00e1s sencillas de aceptaci\u00f3n de secuencias finitas. Computan en tiempo lineal en el tama\u00f1o de la entrada. Se usan para much\u00edsimas aplicaciones. Por ejemplo, la asistente virtual Siri incluye una composici\u00f3n de aut\u00f3matas finitos que leen y escriben (transductores finitos), los cuales realizan el reconocimiento de voz: las se\u00f1ales de voz que recibe del usuario se codifican en s\u00edmbolos que se van traduciendo a un c\u00f3digo intermedio y de ese c\u00f3digo a otro c\u00f3digo intermedio, hasta que finalmente le queda una representaci\u00f3n interna en palabras de la pregunta o la afirmaci\u00f3n que se le hizo. Es una m\u00e1quina muy sencilla que tarda tantos pasos como la cantidad de s\u00edmbolos de entrada. Por lo tanto, el c\u00f3mputo tiene complejidad temporal lineal en el tama\u00f1o de la entrada. <\/span>
\n<\/span>
\n<\/b>El resurgimiento de <\/b>la computaci\u00f3n anal\u00f3gica\u00a0<\/b><\/p>\n

Continuando con lo anterior, si bien estamos acostumbrados a la m\u00e1quina de Turing, esta l\u00ednea de investigaci\u00f3n retoma La M\u00e1quina Anal\u00f3gica de Prop\u00f3sito General (<\/span>The General Purpose Analog Computer de Claude Shannon)<\/span><\/i>.\u00a0 Esos modelos de c\u00f3mputo trabajan usando n\u00fameros reales, en vez de n\u00fameros naturales. Se trata de m\u00e1quinas anal\u00f3gicas que exist\u00edan mucho antes que las m\u00e1quinas discretas. Desde el punto de vista matem\u00e1tico estas m\u00e1quinas son sistemas de ecuaciones diferenciales ordinarias.<\/span><\/p>\n

Si bien la teor\u00eda es de 1930, se demor\u00f3 m\u00e1s de siete d\u00e9cadas en demostrar: alcanza con considerar solamente a las ecuaciones diferenciales ordinarias polinomiales. Y el hecho de que las m\u00e1quinas anal\u00f3gicas computan en tiempo polinomial corresponde a los sistemas de\u00a0 ecuaciones diferenciales ordinarias polinomiales, de longitud polinomial. Estos resultan teoremas importantes demostrados por Bournez, Gra\u00e7a y Pouly (2017, 2020).<\/span><\/p>\n

\u00a0<\/span><\/p>\n

\"\"

Representaci\u00f3n del chip de computaci\u00f3n anal\u00f3gica de la Universidad de Tsinghua. Cr\u00e9dito: Universidad de Tsinghua.<\/p><\/div>\n

Los algoritmos que computan en tiempo polinomial se llaman algoritmos tratables y contrastan con algoritmos de tiempo exponencial, que se vuelven intratables r\u00e1pidamente a medida que aumenta el tama\u00f1o de la entrada (un tiempo que para los humanos no es posible, suele abordarse con paralelismo masivo y tal vez pueda abordarse con m\u00e1quinas cu\u00e1nticas).<\/span><\/p>\n

\"\"

Dra. Ver\u00f3nica Becher. Cr\u00e9dito fotogr\u00e1fico: Silvio Fabrykant<\/p><\/div>\n

Seg\u00fan Becher, a partir de la caracterizaci\u00f3n de la clase polinomial de las m\u00e1quinas anal\u00f3gicas, podemos pensar que van a ser parte del plantel computacional.\u00a0 \u201c<\/span>Por ejemplo, son las se\u00f1ales de audio donde la habitual discretizaci\u00f3n requiere energ\u00eda (y pierde algo de informaci\u00f3n). En cambio, al incorporar en cualquier aut\u00f3mata discreto, sea una computadora o un celular, un dispositivo m\u00e1s peque\u00f1o que pueda sensar las se\u00f1ales directamente, evita el gasto de energ\u00eda que hubiera requerido discretizar las ecuaciones<\/span><\/i>\u201d, concluye.<\/span><\/p>\n

Estos son algunos de los problemas de inter\u00e9s que fundamentalmente demuestran que la teor\u00eda matem\u00e1tica-computacional en torno a la complejidad se conecta con usos pr\u00e1cticos y desarrollos de la tecnolog\u00eda de vanguardia actual.<\/span><\/p>\n

\n

En homenaje a Joos Heintz<\/b><\/p>\n

\"\"Joos Heintz naci\u00f3 el 27 de octubre de 1945 y falleci\u00f3 el 3 de octubre de 2024. Heintz naci\u00f3 en Z\u00farich, Suiza, donde pas\u00f3 su infancia y juventud. Se form\u00f3 como ling\u00fcista (turcolog\u00eda) y matem\u00e1tico en la Universidad de Zurich. En la misma universidad hizo su doctorado en Filosof\u00eda con orientaci\u00f3n matem\u00e1tica, con la direcci\u00f3n de Volker Strassen. Hizo su Habilitaci\u00f3n en Ciencias Matem\u00e1ticas con Venia Lengendi, en la Facultad de Matem\u00e1ticas de la Universidad J.W. von Goethe, Frankfurt\/Main. A mediados de la d\u00e9cada de 1980, por decisi\u00f3n personal, se mud\u00f3 a Argentina y se nacionaliz\u00f3 argentino. Fue profesor de la Universidad de Buenos Aires e investigador superior del CONICET y al mismo tiempo ejerci\u00f3 como profesor titular en Cantabria (Espa\u00f1a) donde pasaba una parte del a\u00f1o. Joos Heintz combin\u00f3 su labor cient\u00edfica con un fuerte compromiso social<\/span>, <\/span>\u00a0siendo especialmente significativa su incisiva dedicaci\u00f3n al colectivo de los cartoneros de Buenos Aires.<\/span><\/p>\n

Fue una figura heterodoxa en el \u00e1mbito matem\u00e1tico. Sus contribuciones matem\u00e1ticas se inspiraron en su vasta formaci\u00f3n sociol\u00f3gica y cultural, as\u00ed como en sus extraordinarias habilidades pol\u00edglotas, lo que le confiri\u00f3 un aura de innovaci\u00f3n cient\u00edfica inclasificable. Heintz afirmaba creer en la ciencia como producto del esfuerzo colectivo de cient\u00edficos comprometidos y, en consonancia con esta creencia, sol\u00eda publicar con coautores y, ocasionalmente, bajo seud\u00f3nimos colectivos como Noa\u00ef Fitchas o D. Franck Le Plateau. En consecuencia, su extraordinaria personalidad le permiti\u00f3 atraer a j\u00f3venes talentosos a su universo cient\u00edfico. Leg\u00f3 una impresionante escuela cient\u00edfica argentina e influy\u00f3 notablemente en grupos de investigaci\u00f3n de Par\u00eds, Berl\u00edn y Cantabria, entre otros.<\/span><\/p>\n

El perfil del Dr. Heintz tiene car\u00e1cter excepcional por su creatividad para atravesar problemas profundos de la matem\u00e1tica y la computaci\u00f3n. Su obra contiene contribuciones de tipo fundamental en \u00e1reas de la matem\u00e1tica (pura y aplicada) y de la computaci\u00f3n (te\u00f3rica y pr\u00e1ctica), principalmente en geometr\u00eda algebraica, en computaci\u00f3n simb\u00f3lica y seminum\u00e9rica, y en complejidad algebraica.<\/span><\/p>\n

Sus aportes en geometr\u00eda algebraica son claves para la resoluci\u00f3n de sistemas polinomiales sobre los n\u00fameros complejos y reales. En el campo de la computaci\u00f3n te\u00f3rica Joos Heintz fue pionero en el uso de circuitos como estructuras de datos y es una autoridad indiscutida en t\u00e9cnicas de cotas inferiores de complejidad para la evaluaci\u00f3n de polinomios.<\/span><\/p>\n<\/blockquote>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"

Ver\u00f3nica Becher es investigadora y directora de KAPOW, un grupo de teor\u00eda de la computaci\u00f3n con foco en problemas combinatorios y aleatoriedad. Recientemente fue designada editora asociada de la prestigiosa publicaci\u00f3n Journal of Complexity. En esta nota nos cuenta sobre los desaf\u00edos de edici\u00f3n en la revista y algunas de las dificultades te\u00f3ricas a la hora de resolver problemas complejos.<\/p>\n","protected":false},"author":9,"featured_media":2935,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[45,25,59],"class_list":["post-2934","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-noticias","tag-algoritmos","tag-computo","tag-sistemas-complejos"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2934","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=2934"}],"version-history":[{"count":5,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2934\/revisions"}],"predecessor-version":[{"id":2953,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2934\/revisions\/2953"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2935"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2934"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2934"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2934"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}