Resumen:
La arquitectura de software nació como concepto a fines de los años setenta y durante los años ochenta con el objetivo de refinar el arte del diseño, mediante especificaciones de grandes paquetes de programas. Desde el principio estuvo en el centro de la atención una interacción con un tejido social, frecuentemente llamado “contrato” o “proyecto”. Para tal fin se desarrolló un aparato conceptual con el fin de captar de manera uniforme una gran variedad de situaciones muy diferentes entre sí. Hubo también algunos intentos de modelización matemática, siendo la más destacable y avanzada la lógica de Hoare del asserted programming. Aunque la lógica de Hoare es demasiado restrictiva para su aplicación práctica, tuvo una gran repercusión en la enseñanza de la informática porque formaliza dos aspectos fundamentales de la ingeniería de software: (1) Un programa no es simplemente un algoritmo modelizado mediante un cierto tipo de máquina, sino contiene también una semántica definida en términos de especificaciones y una demostración de su correctitud. (2) La demostración de la correctitud de un programa no tiene la forma de una demostración matemática cualquiera, sino esta sometida a una cierta estandardización. El aspecto (2) representa una piedra fundamental para la visión arquitectónica de la programación por dos razones. Una es la indecidibilidad de la equivalencia de programas en lenguajes mínimamente recursivos y la otra es el requerimiento práctico que no debería ser tarea del programador demostrar la conjetura de Riemann antes de meterse en la implementación de un algoritmo de teoría de números. El ejemplo de la lógica de Hoare nos sirve en esta exposición como testigo para la afirmación de que no todos los aspectos de la ingeniería de software tienen carácter subjetivo o social. Existen también aspectos objetivizables e independientes del individuo. La meta de esta tesis es elaborar algunos de estos aspectos objetivizables y estudiarlos mediante un método científico. Esto requiere una modelización matemática y la justificación informática de la misma. Tal modelización permite la aplicación de herramientas matemáticas para sacar conclusiones matemáticas que a su vez deben ser retraducibles al contexto original informático. La problemática de este procedimiento es la siguiente: la matemática es la ciencia de las trivialidades y tautologías y por lo tanto sus herramientas son inespecíficas. No es de esperar que una modelización exacta de un contexto informático permita sacar grandes conclusiones matemáticas que a su vez conducen a sorprendentes y desconocidas inferencias informáticas. Por otro lado una modelización grosera matemática permitiría solamente conclusiones muy generales e inespecíficas para la informática. Por esta razón el trabajo propuesto se concentra en el “tuning” adecuado de la modelización y no en el aparato matemático (que, sea dicho aparte, es de ninguna manera trivial) para sacar conclusiones informáticas. La ingeniería de software de los años setenta y ochenta tuvo que luchar con estas dificultades. La generalidad del planteo no permitío formular y demostrar conclusiones rigurosas. Por esta razón este trabajo limita la aplicación de conceptos de la ingeniería de software al campo más reducido de la computación científica y recurre a una restricción adicional sobre la arquitectura fijando un nivel de abstracción predeterminado. Dentro de la computación científica el trabajo se concentra en problemas y algoritmos de eliminación e interpolación polinomiales y el nivel de abstracción predeterminado es el modelo algebraico de complejidad en cuerpos como R y C con las operaciones aritméticas (adición, substracción, multiplicación y división) implementadas a costo unidad. La idea es que los programas considerados admitan polimorfismo y puedan ser ejecutados tanto en entorno numérico con precisión finita como en un entorno simbólico con precisión infinita. Este nivel de abstracción impone sus reglas de juego. Divisiones en algoritmos del modelo algebraico conducen a branchings, lo que no es apropiado para una interpretación numérica. Sin embargo, ciertas divisiones de tipo 0/0 pueden ser remplazadas por limites que se adaptan mucho mejor a la interpretación numérica (un ejemplo es la regla de L´Hópital). Esto conduce a un modelo donde se restringen las divisiones a los casos donde ellas representan límites. Para las tareas algorítmicas consideradas en este trabajo esta restricción alcanza y representa adecuadamente el concepto sintáctico de branching– freeness. Sin embargo, detrás de esto se esconde un concepto más profundo: los problemas que se consideran en este trabajo admiten degeneraciones a problemas límites. Por lo tanto es natural pedir que los algoritmos que resuelven estos problemas capten estas degeneraciones. En teoría de interpolación esto se llama informalmente “coalescencia”. La noción de coalescencia permite una modelización nítida, transparente y geométrica que refleja las divisiones admitidas en el modelo bajo consideración. Esta modelización se encuentra realizada por la noción precisa y matemática de la “robustez geométrica” de una aplicación racional. La robustez geométrica representa un atributo de calidad dicotómico (quality attribute) de un software, y tiene su análogo discreto en el aprendizaje de patrones (ver Sección 5.3.1). Uno de los objetivos principales del trabajo es un análisis en profundidad de propiedades de algoritmos como la “coalescencia” o el “branching–freeness” bajo el aspecto de atributo de calidad. Las herramientas matemáticas utilizadas permiten ahora conclusiones sorprendentes. Otro atributo de calidad, esta vez cuantitativo, de un algoritmo o programa es su complejidad contada en cantidad de operaciones aritméticas. Las herramientas matemáticas mencionadas permiten ahora establecer un trade–off entre el atributo de calidad dicotómico de la robustez geométrica y el atributo de calidad cuantitativo de la complejidad: algoritmos generales (”universales”) y geométricamente robustos, que resuelven ciertos problemas naturales de eliminación e interpolación, tienen necesariamente una complejidad que es exponencial en el tamaño de la representación sintáctica de la entrada, y esto con mínimos requerimientos en la arquitectura y sin haber detallado las estructuras o tipos de datos que iban a intervenir. La técnica para demostrar tal resultado representa en si misma una innovación en el campo de la geometría algebraica. Partes del método motivan en este campo preguntas totalmente nuevas como la cuestión de la desingularización de una variedad uniracional dada como imagen de un morfismo (y no por ecuaciones) o cuantos blow ups requiere la transformación de una aplicación racional dada en una polinomial? La sorpresa es que la cuestión de la desingularización y el análisis geométrico de las aplicaciones racionales está íntimamente relacionada con la arquitectura de software en cálculo científico. En ambos campos surgen las mismas preguntas y se aportan las mismas respuestas. La Sección 6.5.5 del trabajo será dedicada a la exposición de esta sorprendente relación entre dos campos que a primera vista están completamente alejados. Necesariamente el trabajo debe contener una parte introductoria donde se explican las herramientas matemáticas. En esta parte las demostraciones estarán remplazadas por referencias a publicaciones recientes. Sin embargo, una parte (más pequeña) de las herramientas es nueva y aparecerá con demostraciones en un apéndice (ver Appendix A) La parte central y más innovativa del trabajo es la Sección 6 donde se introduce un modelo matemático para el análisis general de tareas computacionales del cálculo científico en el contexto de los algoritmos seminuméricos (que usan como estructura de datos básica los circuitos aritméticos). La atención será puesta sobre el caso particular de tareas de eliminación en geometría algebraica efectiva. El aporte principal de esta sección consiste en la fundamentación, motivación y justificación de este modelo matemático mediante criterios que provienen de la ingenieráa de software. Se demuestra que las características matemáticas esenciales son consecuencias directas de los requerimientos funcionales o no– funcionales de software que se encuentran altamente aceptados por la comunidad de ingeniería de software y que se pueden aplicar alternativamente. El primero de estos requerimientos es funcional, el segundo es no–funcional. La conclusión matemática de esta modelización en la forma dada en esta tesis, es nueva y representa un resultado informático sorprendente: en la Sección 6.5.1 se exhibe una familia infinita de problemas básicos de eliminación geométrica tal que cualquier algoritmo de nuestro modelo que calcula los polinomios de eliminación asociados a partir de la entrada dada requiere un tiempo exponencial. Sin embargo, no se responde la pregunta si los polinomios de eliminación, con el algoritmo que sea, fueran difíciles de evaluar. Pretendiendo responder a esta última pregunta, todos los intentos anteriores de atacar el problema resuelto en esta tesis, fracasaron. Una variante decisional de este problema es la conjetura PC 6= NPC en el modelo de las máquinas de Turing continuas de Blum, Shub y Smale [BSS89], el modelo BSS. Como nuestro resultado no se refiere a un contexto decisional, sino al cálculo de un objeto matemático, un polinomio de eliminación, no demostramos esta conjetura, ni siquiera en un modelo de recursos restringidos de máquinas de Turing BSS. Finalmente recalcamos que el resultado principal de la Sección 6 puede ser interpretado como un trade–off entre un atributo de calidad cualitativo (el requerimiento no–funcional de la robustez en combinación con otro requerimiento, llamado isoparametría) y uno cuantitativo (una clase de complejidad algorítmica). En este sentido se trata de una certificación matemática de un trade–off entre dos atributos de calidad. No conocemos otro caso en la literatura.
Abstract:
We introduce a software architecture based computation model for Scientific Computing. Its relevance becomes illustrated by the precise formulation and solution of a more than thirty years open complexity problem in Effective Algebraic Geometry (elimination theory).
Citación:
---------- APA ----------
Rojas Paredes, Andrés. (2011). Complexity as quality attribute in software design. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000365_RojasParedes
---------- CHICAGO ----------
Rojas Paredes, Andrés. "Complexity as quality attribute in software design". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/seminario_nCOM000365_RojasParedes
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000365_RojasParedes.pdf
Distrubución geográfica
