• Inicio

    Consideraciones Generales

    El curso tiene el propósito de explorar distintos modelos alternativos de cómputo que han sido desarrollados en el curso de los últimos cuatro décadas en la literatura, incluyendo también los más recientes. Se espera desarrollarlos en un nuevo modelo universal de cómputo y de complejidad uniforme que represente adecuadamente el "arte" de la ingeniería de software aplicada a un fragmento apropiado del cálculo científico (sistemas de ecuaciones polinomiales). Este modelo de "algoritmo programable" deberá dar cabida a la semántica (especificaciones y pruebas de correctitud) y deberá permitir la derivación (de manera fácil) de cotas de complejidad no triviales para problemas fundamentales de la geometría elemental subyacente a los sistemas de ecuaciones polinomiales (geometría algebraica, semialgebraica y diofántica efectiva y más específicamente teoría de eliminación).

    Este análisis nos permitirá precisar la observación de que los llamados programas con anotaciones ("asserted programs") basados en especificaciones conducen necesariamente a obstrucciones considerables de complejidad, que solamente pueden ser evitadas mediante técnicas de programación ad-hoc no certificada (comúnmente conocidas como "hacking"). En particular no se conoce un método eficiente para la deforestación de programas compuestos.

    Mi enfoque difiere sustancialmente de la línea tradicional de investigación de la informática teórica, cuestionando el status quo acerca de qué es un "algoritmo", y cuál es la noción adecuada de "complejidad" de un problema. Tomo como punto de partida la observación de que en la ingeniería de software la noción de algoritmo comúnmente utilizada es más restrictiva que la idealización de máquina "abstracta" proveniente de la informática teórica clásica de los años 1930's (máquinas de Turing, o cualquiera de sus formulaciones equivalentes). La ingeniería de software utiliza "algoritmos programables", que vienen con especificaciones, programas con anotaciones y demostraciones de correctitud. La noción de algoritmo o máquina abstracta del enfoque tradicional carece de una semántica asociada; se trata exclusivamente de una manipulación sintáctica que pone (inocentemente) al problema de la codificación de los datos (codificación del input y del output) en un rol meta-teórico. En contraste, la codificación de los datos es central en ingeniería del software, donde a diario se seleccionan cuidadosamente tanto los algoritmos como sus inputs y outputs, para resolver los problemas eficientemente. Creo que la disociación entre las máquinas abstractas y la computación de la vida real inhiben la formulación correcta de las preguntas de complejidad correspondientes. Mi intención es dar un paso importante para integrar la teoría con la vista real, mediante la formulación de un nuevo modelo de cómputo y complejidad aplicable al cálculo científico.

    Como la ingeniería de software (SI) interactúa con un supuesto contexto real, modelizado por una hipotética relación “cliente-programador” o “usuario-interfaz” (detrás de cada proyecto SI hay una o varias “aplicaciones”), se utilizan diferentes niveles de abstracción representados por lenguajes de especificación adecuados con su propia semántica. Esto conduce a una “arquitectura” que al principio (al nivel más abstracto de la relación “cliente-programador” no debería estar ya predeterminada. Para comparar diferentes tipos de arquitecturas y distinguirlas se introducen criterios (generalmente dicotómicos) de “calidad de software” que en caso de ser cuantificables se llaman “métricas”.

    Los más usuales criterios de cualidad de software están formulados de manera descriptiva y mezclan criterios subjetivos con objetivos. Uno de las metas del curso es ganar más claridad sobre el aspecto objetivo de estos criterios.

    Por otra parte en el cálculo científico el attributo predominante de calidad de software es cuantitativo: la complejidad de ejecución de un programa (en sus diferentes variantes). Pero solamente en su forma aparente la complejidad representa un attributo cuantitativo, en realidad se trata de un attributo cualitativo. Otro attributo de calidad de una arquitectura es el del polimorfismo (se exige que los programas sean eficientes ejecutados como proceduras numéricas con precisión finita o como proceduras exactas con precisión infinita). Pensando en este polimorfismo llegamos a un tercer attributo de calidad, motivado por la ejecución del programa en un entorno numérico: la robustez o la parsimonía en branchings.

    Que es el efecto de la combinación de estos criterios? La experiencia dice por ejemplo que una arquitectura flexible y transparente como la de los frameworks tiene como contraparte un alto costo en recursos a la hora de ejecución. En el caso que nos interesa, la robustez implica para problemas naturales del ccálculo científico, como la interpolación de polinomios dados por circuitos aritméticos, una alta complejidad en run time. Con otras palabras, tenemosd un tradeoff entre dos attributos de calidad. Para demostrar tal enunciado hay que construir un modelo que admite la noción de la arquitectura como parámetro.

    La teoría clásica de complejidad ignora todos estos aspectos, es decir que trabaja con una arquitectura de un solo nivel, el de los bits.

    Todo esto es una fuerte razón para desprenderse del riñón de la informática, del mundo de los circuitos booleanos y máquinas de Turing y tomar en cuenta también otros modelos, como los circuitos aritméticos, bases de datos (relacionales y continuas) para la representación de la interacción entre memoria y cómputo etc.

    Con otras palabras, si limitamos la informática al mundo bit , cortamos de cuajo toda referencia a la una posible semántica, necesaria para poder formular un proyecto de ingeniería de software.

    Por esta razón, en el curso los circuitos booleanos van a jugar un papel de menor importancia, más que nada didáctico, y los circuitos aritméticos, que son mas próximos a la semántica del computo científico, van a remplazarlos como modelo algorítmico, pero también como estructuras y tipos de datos.

    Modalidad y temas concretos del curso

    En concreto, el curso no va a ser más, como los anteriores, un recuento exhaustivo de librerías básicas de algoritmos para el computo científico con unas ventanas a la cuestión de las cotas inferiores de complejidad para problemas selectos del campo. Tampoco va a ser un curso donde el único que habla es el profesor y los alumnos ingieren la lección sin posibilidad de aportar un pensamiento propio.Los participantes van a exponer, y no solamente temas que el profesor ya sabe y no tiene ganas de preparar y tampoco al final de curso en remplazo de un examen.

    Como tema del curso tengo dos paradigmas en mente.

    El paradigma preparado arranca de un problema computacional que en la práctica es importante, pero como tema en si no me despierta pasiones: la interpolación Lagrange- Hermite de polinomios multivariados. Este problema tengo estudiado y modelizado a fondo desde el punto de vista del papel de la complejidad algorítmica en ingeniería de software y me servirá para ejemplificar de manera exacta mis conceptos. Las técnicas matemáticas que he tenido que desarrollar para tal fin son todas nuevas (y no triviales).

    El otro paradigma es la resolución de ecuaciones sobre los números complejos y de desigualdades sobre los reales (problema fundamental de la optimización no-lineal global).

    Joos Heintz