En los problemas de optimización combinatoria se estudian colecciones finitas de objetos que satisfacen unos criterios específicos y se persigue determinar si cierto objeto ``óptimo'' existe. En la mayoría de las ocasiones, a pesar de que el dominio de búsqueda es finito, éste puede ser de dimensiones exponenciales. En la actualidad es posible solucionar un gran número de problemas combinatorios presentes en la vida real empleando técnicas basadas en programación entera. Sin embargo, en numerosas ocasiones no es posible resolverlos de forma exacta debido a la gran dificultad que presentan algunos problemas de optimización combinatoria y sólo es posible encontrar soluciones cercanas al óptimo. Para estas ocasiones, los esfuerzos de investigación se han centrado en la aplicación de técnicas meta-heurísticas. En este último caso se enmarca el presente trabajo, es decir, en la resolución de problemas combinatorios complejos, de grandes dimensiones, donde explorar todas las posibilidades a fin de encontrar el óptimo es inabordable, ya sea por motivos económicos (probar cada combinación sea caro) o por motivos computacionales (temporalmente sea intratable). En concreto, en esta tesis se propone una arquitectura de búsqueda independiente del dominio de aplicación y capaz de abordar problemas combinatorios de grandes dimensiones, de los que se disponga de poca información de partida. Esta arquitectura está basada en técnicas Soft Computing, pues combina un algoritmo genético basado en codificación real con modelos basados en redes neuronales, concretamente en perceptrones multicapa. Así, el algoritmo genético emplea, en los casos en los que sea necesario, modelos aproximados de las funciones de aptitud mediante perceptrones diseñados para tal fin. El sistema obtenido ofrece la flexibilidad y versatilidad requeridas para poder adaptarse a los requisitos propios de cada problema combinatorio a tratar, sea cual sea su dominio. / Valero Cubas, S. (2010). Arquitectura de búsqueda basada en técnicas soft computing para la resolución de problemas combinatorios en diferentes dominios de aplicación [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8329 / Palancia

Para los sistemas de computaci�on actuales, la habilidad de utilizar din�amicamente los recursos que se alojan en la red se ha convertido en un factor clave de �exito. Conforme la red sigue creciendo se hace cada vez m�as dif�ÿcil encontrar soluciones a los problemas que los usuarios plantean al sistema computacional. Los usuarios saben habitualmente qu�e quieren hacer, pero no c�omo hacerlo. Si el usuario conoce el objetivo que desea alcanzar es m�as sencillo ayudarle mediante el uso de una aproximaci�on diferente. Nuestra propuesta se orienta en incrementar los niveles de abstracci�on proporcionados por el sistema operativo y sus servicios. Esto nos permitir�a ofrecer una capa de ejecuci�on del sistema operativo perfectamente integrada en la red y con mecanismos de seguridad y fiabilidad que no pueden estar disponibles en niveles m�as bajos de abstracci�on de los sistemas operativos actuales. Esta evoluci�on comienza por cambiar el paradigma utilizado en el dise �no del SO. Cambiar las abstracciones que el SO utiliza est�a �ÿntimamente relacionado con el paradigma utilizado, y al cambiar este paradigma necesitamos proponer un nuevo m�odulo de ejecuci�on para el SO que soporte dicho paradigma. Este m�odulo de ejecuci�on es presentado tambi�en en este trabajo. Para solventar estos problemas presentamos un nuevo paradigma de Computaci�on Distribuida basada en Objetivos. Para implementar el paradigma se ha dise �nado una arquitectura de sistema operativo orientado a objetivos. En este SO el usuario expresa sus objetivos y el SO se encarga de ayudar al usuario a alcanzar sus objetivos por medio de una aproximaci�on orientada a servicios. Adem�as se presenta un simulador que da soporte a este paradigma, siguiendo los requisitos planteados en este trabajo. Algunos de estos requisitos son par�ametros que comprenden c�omo definirlas propiedades de un objetivo o los que definen la bondad de un plan que cumple dichos objetivos. Algunos de los par�ametros que est�an implicado / Palanca Cámara, J. (2012). Computación distribuida basada en objetivos [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17702 / Palancia

Esta tesis se ha centrado en el estudio de las políticas basadas en la extracción de holgura y en la asignación dual de prioridades, ambas orientadas a dar servicio a tareas aperiódicas en sistemas real estricto. Estas políticas constituyen una interesante alternativa a las políticas basadas en servidores de carga aperiódicas y han sido ampliamente estudiadas en numerosos trabajos. No obstante, la posibilidad de ser aplicables en la práctica todavía no había sido evaluada en detalle, y éste ha sido el principal objetivo de esta tesis. En este trabajo, ambas políticas son revisadas en profundidad. En el caso de la política basada en la extracción de holgura, algunas de sus principales debilidades han sido corregidas. En particular, se muestra que es posible compartir recursos entre tareas críticas y aperiódicas de una forma sencilla y eficiente, utilizando para ello los mismos protocolos de herencia de prioridad que pueden aplicarse en sistemas en los que sólo existen tareas críticas. La aplicabilidad de estas políticas ha sido valorada incorporándolas en los dos entornos más relevantes hoy en día para la programación de sistemas de tiempo real estricto, el lenguaje de programación Ada y los servicios POSIX. Con este fin se han definido nuevas interfaces para ambas políticas en estos entornos, coherentes con sus principios de diseño y con los servicios que actualmente ofrecen. El diseño de estas interfaces ha supuesto una adaptación de ambas políticas buscando, en todo momento, un equilibrio entre prestaciones y eficiencia. Como parte de este diseño, estas interfaces han sido implementadas en el sistema operativo MaRTE OS. El proceso de implementación ha servido para validar las distintas alternativas qu ehan sido consideradas. Un aspecto importante de una política de planificación en su eficiencia, por lo que este aspecto ha sido evaluado en detalle. Se ha caracterizado de forma analítica el efecto / ABSTRACT: This thesis is centered on the study of slack stealing and dual priority scheduling policies, both oriented to serve aperiodic tasks in hard real-time systems. These polices, largely studied in previous work, constitute an interesting alternative to policies based on aperiodic servers. However, the possibility of actually being put into practice had not been yet exhaustively evaluated. This has been the main objective of this thesis. Both policies are profoundly revised in this dissertation. In the case of the slack stealing policy, some of its weaknesses have been solved. In particular, this thesis shows that it is possible to share resources between hard and aperiodic tasks in a simple and efficient manner. This can be done by using the same priority inheritance protocols which are used in systems comprising hard tasks only. The applicability of these scheduling policies has been evaluated by means of their incorporation into the two most relevant hard real-time programming environments in use nowadays, the Ada programming language and the POSIX set of services. In order to fulfill this purpose, new interfaces for both policies have been defined in these two environments. These interfaces have been designed in order to be coherent with the environments¿ design principles and the services they currently support. This design has involved the adaptation of the original scheduling policies, trying to optimize the balance between performance and efficiency. As a part of this design, both interfaces have been implemented in the MaRTE OS operating system. These implementations have been useful for validating the different alternatives which have been considered throughout the design process. Since efficiency is an important aspect of any scheduling policy, this aspect has been extremely evaluated in this work. The effect of the implementation of both policies to the task response times has been analytically characterized. This effect has also been quantified, and then the efficiency of both policies has been compared with the fixed-priority preemptive scheduling policy, which is the one normally used in hard real-time systems. The results of this comparative study show that, although the overhead introduced by any VIII ABSTRACT of the two new policies is significant, this overhead lies in a reasonable range. The recently approved POSIX trace services have also been studied in this thesis. The necessity of having some analysis and measurement tools available for the efficiency studies carried out in this thesis led to the incorporation of these services into MaRTE OS. Related to this, a new POSIX/Ada interface for the trace services has also been proposed. In addition, the problem of obtaining temporal metrics of the system from the information of the traces has also been covered. / Espinosa Minguet, AR. (2003). EXTENSIONES AL LENGUAJE ADA Y A LOS SERVICIOS POSIX PARA PLANIFICACIÓN EN SISTEMAS DE TIEMPO REAL ESTRICTO [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17743

Internet es, tal vez, el avance científico más relevante de nuestros días. Entre otras cosas, Internet ha permitido la evolución de los paradigmas de computación tradicionales hacia el paradigma de computaciónn distribuida, que se caracteriza por utilizar una red abierta de ordenadores. Los sistemas multiagente (SMA) son una tecnolog a adecuada para abordar los retos motivados por estos sistemas abiertos distribuidos. Los SMA son aplicaciones formadas por agentes heterog eneos y aut onomos que pueden haber sido dise~nados de forma independiente de acuerdo con objetivos y motivaciones diferentes. Por lo tanto, no es posible realizar ninguna hip otesis a priori sobre el comportamiento de los agentes. Por este motivo, los SMA necesitan de mecanismos de coordinaci on y cooperaci on, como las normas, para garantizar el orden social y evitar la aparici on de conictos. El t ermino norma cubre dos dimensiones diferentes: i) las normas como un instrumento que gu a a los ciudadanos a la hora de realizar acciones y actividades, por lo que las normas de nen los procedimientos y/o los protocolos que se deben seguir en una situaci on concreta, y ii) las normas como ordenes o prohibiciones respaldadas por un sistema de sanciones, por lo que las normas son medios para prevenir o castigar ciertas acciones. En el area de los SMA, las normas se vienen utilizando como una especi caci on formal de lo que est a permitido, obligado y prohibido dentro de una sociedad. De este modo, las normas permiten regular la vida de los agentes software y las interacciones entre ellos. La motivaci on principal de esta tesis es permitir a los dise~nadores de los SMA utilizar normas como un mecanismo para controlar y coordinar SMA abiertos. Nuestro objetivo es elaborar mecanismos normativos a dos niveles: a nivel de agente y a nivel de infraestructura. Por lo tanto, en esta tesis se aborda primero el problema de la de nici on de agentes normativos aut onomos que sean capaces de deliberar acerca / Criado Pacheco, N. (2012). Using Norms To Control Open Multi-Agent Systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17800 / Palancia

En la nueva era de tecnologías de la información, los sistemas tienden a ser cada vez más dinámicos, compuestos por entidades heterogéneas capaces de entrar y salir del sistema, interaccionar entre ellas, y adaptarse a las necesidades del entorno. Los sistemas multiagente han contribuído en los ultimos años, a modelar, diseñar e implementar sistemas autónomos con capacidad de interacción y comunicación. Estos sistemas se han modelado principalmente, a través de sociedades de agentes, las cuales facilitan la interación, organización y cooperación de agentes heterogéneos para conseguir diferentes objetivos. Para que estos paradigmas puedan ser utilizados para el desarrollo de nuevas generaciones de sistemas, características como dinamicidad y capacidad de reorganización deben estar incorporadas en el modelado, gestión y ejecución de estas sociedades de agentes. Concretamente, la reorganización en sociedades de agentes ofrece un paradigma para diseñar aplicaciones abiertas, dinámicas y adaptativas. Este proceso requiere determinar las consecuencias de cambiar el sistema, no sólo en términos de los beneficios conseguidos sinó además, midiendo los costes de adaptación así como el impacto que estos cambios tienen en todos los componentes del sistema. Las propuestas actuales de reorganización, básicamente abordan este proceso como respuestas de la sociedad cuando ocurre un cambio, o bien como un mecanismo para mejorar la utilidad del sistema. Sin embargo, no se pueden definir procesos complejos de decisión que obtengan la mejor configuración de los componentes organizacionales en cada momento, basándose en una evaluación de los beneficios que se podrían obtener así como de los costes asociados al proceso. Teniendo en cuenta este objetivo, esta tesis explora el área de reorganización en sociedades de agentes y se centra principalmente, en una propuesta novedosa para reorganización. Nuestra propuesta ofrece un soporte de toma de decisiones que considera cambios en múltiples / Alberola Oltra, JM. (2013). Reorganization in Dynamic Agent Societies [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/19243 / Palancia

La evaluación parcial dirigida por narrowing (NPE: Narrowing-driven Partial Evaluation) es una técnica potente para la especialización de sistemas de reescritura, i.e., para el componente de primer orden de muchos lenguajes declarativos (lógico) funcionales como Haskell, Curry o Toy. Los evaluadores parciales se clasifican en dos grandes categorías: online y offline, de acuerdo al momento temporal en que se consideran los aspectos de terminación del proceso de especialización. Los evaluadores parciales online son usualmente más precisos ya que tienen más información disponible. Los evaluadores parciales offline proceden comúnmente en dos etapas; la primera etapa procesa un programa (e.g., para identificar aquellas llamadas a función que se pueden desplegar sin riesgo de no terminación) e incluye anotaciones para guiar las computaciones parciales; entonces, una segunda etapa, la de evaluación parcial propiamente dicha, sólo tiene que obedecer las anotaciones y por tanto el especializador es mucho más rápido que en la aproximación online. En esta tesis se presenta un nuevo esquema de evaluación parcial dirigido por narrowing, más eficiente y que asegura la terminación siguiendo el estilo offline. Para ello, identificamos una caracterización de programas cuasi-terminantes a los que llamamos "no crecientes". En tales programas, las computaciones por narrowing necesario presentan sólo un conjunto finito de términos diferentes (módulo renombramiento de variables). La propiedad de la cuasi-terminación es importante toda vez que su presencia es regularmente una condición suficiente para la terminación del proceso de especialización. Sin embargo, la clase de programas cuasi-terminantes es muy restrictiva, por lo que introducimos un algoritmo que acepta programas inductivamente secuenciales---una clase mucho más amplia sobre la que está definido el narrowing necesario---y anota aquellas partes que violan la caracterización de programas no crecientes. Para procesar de mane / Ramos Díaz, JG. (2007). Una aproximación offline a la evaluación parcial dirigida por narrowing [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1888 / Palancia

El problema de la integración d ela programación lógica y funcional estaá considerado como uno de los más importantes en el área de investigación sobre programación declarativa. Para que los lenguajes declarativos sean útiles y puedan utilizarse en aplicaciones reales, es necesario que el grado de eficiencia de su ejecución se aproxime al de los lenguajes imperativos. Para ello, es imprescindible el desarrollo de herramientas potentes para el análisis y transformacón de los programas, capaces de optimizar las implementaciones existentes. Esta tesis se centra en el desarrollo de tales técnicas, adoptándose la aproximación conocida como "reglas + estrategias" para la optimización de programas en un tentexto lógico-funcional unificado. Las reglas básicas que se usan son el plegado y el desplegado que aquí se definen en términos del Narrowing y sus refinamientos. Gracias a la propagación bidireccional de parámetros realizadas por el mecanismo de unificación del narrowing, se obtienen optimizaciones apreciables y es posible explotar la sinergía existente entre la sintaxis funcional (anidamientos funcionales, evaluaciones perezosas, etc.) y el uso de variables lógicas. Esta fisión unificada de ejecución y transformación de programas nos permite explotar los resultados conocidos en ambos campos, funcional y lógico, y desarrollar un esquema simple y potente para mejorar un programa con respecto a su capacidad para computar tanto valores a funciones como respuestas a objetivos. Presentamos algunas aplicaciones de las reglas de plegado y desplegado (semánticas formales pr desplegado y relaciones con las técnicas de evalación parcial). Además, mostramos que su combinación con otras reglas para la introducción y eliminación de difiniciones y reglas de abstracción permite obtener programas eficicientes cuando son dirigidas por estrategias adecuadas como son la composición o la formación de Tuplas. El esquema presentado constituye la primera aproximación correcta y completa .... / Moreno Valverde, GD. (2000). Reglas y estrategias de transformación para programas lógico-funcionales [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/4701 / Palancia

El objetivo general de todo sistema de Procesamiento del Lenguaje Natural (PLN) es el de obtener alguna representación del mensaje contenido de las frases. el tratamiento automático de una lengua es un problema de gran complejidad en el que intervienen diversas y complejas fuentes de conocimiento: fonética, morfología, sintaxis, semántica, pragmática, conocimiento del mundo, etc. Aunque en algunos casos estas fuentes de información se pueden considerar independientes, en general, presentan una interrelación, sin la cual, no se puede conseguir una correcta interprestación del significado y de la función de las palabras de una oración. Debido a esta complejidad, para abordar el problema de comprensión de una lengua se suele seguir una de las siguientes vias: 1) Se resuelven ciertos subproblemas más sencillos que, en algunos casos, deben aportar simplificaciones para poder ser tratados de manera automática, tales como:análisis morfológico, etiquetado léxico de textos, análisis sintáctico superficial de oraciones ligamiento preposicional, sesambiguación del sentido de las palabras, tratamiento de fenómenos lingüistícos especificos como la anáfora, elipsis, etc. 2) se simplifica el lenguaje considerando tareas restringidasm en la talla del vocabulario, la complejidad de las estructuras sintácticas utilizadas o el dominio semántico de la aplicación. Durante los últimos años podemos encontrar una gran cantidad de ejemplos que toman alguna de las vías comentadas. En reconocimiento del habla hay aplicaciones que se restringen a vocabularios acotados, sonsultas a bases de datos específicas, sistemas de diálogo sobre tareas concretas, etc. En otros campos, más directamente relacionados con el PLN, encontramos aplicaciones de traducción automática, extracción y recuperación de información, resúmenes de textos, etc, en las que, en mayor o menor medida, se restringen a dominios específicos para sonseguir resultados aceptables. Por otra parte, el echo de disponer de grandes corpus de datos, textuales u orales, anotados con información lingüística de diferente naturaleza- información morfosintáctica, análisis sintáctico total o parcial, información semantica - junto con operativos, ha proporcionado la aparición y uso de aproximaciones inductivas o métodos basados en corpus, dentro del campo de la Lingüística Computacional, que aplicamos a diferentes tareas de PLN obtienen un alto grado de prestaciones. Las aproximaciones inductivas, con o sin información estadística, resultan de gran interés para conseguir la desambiguación del Lenguaje Natural (LN) ya que, además de proporcionar resultados aceptables, utilizan modelos relativamente sencillos y sus parámetros se pueden estimar a partir de datos. Esto las hace especialmente atractivas, puesto que en el cambio de una tarea a otra, o incluso de lengua, se reduce substancialmente la intervención humana. No obstante, algunos casos de ambigüedad no pueden ser resueltos de esta forma y se debe recurrir a un experto humano para introducir, por ejemplo, ciertas reglas o restricciones que ayuden a su resolución. / Pla Santamaría, F. (2000). Etiquetado léxico y análisis sintáctico superficial basado en modelos estadísticos [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/5646 / Palancia

En un sistema de base de datos, el cambio en el mundo real se modela mediante la ejecución de transacciones de usuario que modifican un estado generando otro que representa la nueva situación. Este nuevo estado puede violar las restricciones de integridad del esquema, restricciones que representan las propiedades de ese mundo. La reacción más frecuente de los sistemas de bases de datos ante la violación de la integridad consistente en rechazar la transacción que la ha provocado, devolviendo la base de datos al estado anterior a su ejecución. Esta solución tan simple es, sin embargo, usualmente poco satisfactoria para sistemas reales. Una alternativa a este comportamiento consiste en que el sistema modifique el estado inconsistente de forma que se repare la violación provocada por la transacción de usuario respetanto los cambios propuestos por ésta. Se dice entonces que el sistema ha restaurado la consistencia de la base de datos. En esta tesis se ha propuesto un método para la restauración de la consistencia en bases de datos relacionales con vistas (o bases de datos deductivas) que utiliza el lenguaje de reglas de un sistema activo. Así a partir del conjunto de restricciones de integridad y del conjunto de reglas deductivas del esquema, el método genera un conjunto de reglas de actividad que restaura la consistencia de la base de datos cuando, como consecuencia de la ejecución de una transacción de usuario, se ha producido la violación de alguna restricción. Estas reglas se han denominado reglas restauradoras. / Mota Herranz, L. (2001). Generación de reglas restauradoras de la consistencia en esquemas relacionales con vistas [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/5760 / Palancia

El trabajo incluido en la presente tesis se enmarca dentro del campo de la demostración automática de teoremas y consiste en la estudio, definición y desarrollo de un paradigma de resolución lineal, denominado Resolución SL*. La razón para utilizar la denominación de paradigma reside en el hecho de que en sí misma resolución SL* no es un procedimiento, sino que se puede entender como una forma de razonamiento con ciertos parámetros cuya instanciación da lugar a diferentes procedimientos que son adecuados para el tratamiento de distintos tipos de problemas. Por otro lado, se le ha dado el nombre de resolución SL* porque, como posteriormente se explicará, está muy cercano a Eliminación de Modelos y a resolución SL (de ahí la primera parte del nombre). El asterisco final quiere denotar su parametrización, de forma que los procedimientos instancias de resolución SL* serán denominados con una letra más en vez del asterisco, como posteriormente se verá. La tesis ha sido dividida en cuatro capítulos que se describen brevemente a continuación. En el primero se realiza una breve introducción histórica a la demostración automática, que va desde los orígenes de la lógica con el uso de las primeras notaciones matemáticas formales en el siglo XVI hasta la aparición de los resultados más importantes de la lógica descubiertos por Herbrand, Gödel, Church, etc. Se hace un especial hincapié en este capítulo en la demostración automática realizando un recorrido desde sus orígenes a finales del siglo XVIII hasta el momento actual, en el cual es posible ver cuál ha sido la evolución de este campo y qué descubrimientos y resultados se pueden presentar como los principales puntos de inflexión. En el segundo capítulo se presentan la resolución lineal y algunos de sus principales refinamientos, ya que resolución SL* es un variación de resolución SL y por tanto de resolución lineal. Para ello se introduce el principio de resolución, viendo los problemas de su mecanización, y posteriormente se ven dos refinamientos de resolución: resolución semántica y resolución lineal. Para concluir se estudian los principales refinamientos de resolución lineal: resolución de entrada, resolución lineal con fusión, resolución lineal con subsumción, resolución lineal ordenada, resolución MTOSS y TOSS, Eliminación de Modelos, resolución SL y el sistema MESON. En el tercer capítulo se presentan y estudian con profundidad las principales aportaciones al campo de la demostración automática que se han producido en los últimos años y que están cercanas a la aproximación del presente trabajo. Se han incluido los siguientes trabajos: el demostrador PTTP de Stickel, el sistema MESON basado en secuencias de Plaisted, el demostrador SATCHMO de Manthey y Bry, los procedimientos Near-Horn Prolog de Loveland y otros autores y, por último, el demostrador SETHEO de Bibel y otros autores. Obviamente no se han incluido todos los demostradores y procedimientos, pero sí aquellos que se han considerado como los más interesantes y cercanos a resolución SL* de manera que sea posible realizar comparaciones, de forma que queden patentes las aportaciones realizadas. En el cuarto capítulo se presenta resolución SL*. Se da la definición formal de la misma y se introduce el concepto fundamental de elección de ancestros. La elección de ancestros es el mecanismo que permite controlar la aplicación de la resolución de ancestro haciendo posible una reducción del coste de su aplicación y una adecuación de resolución SL* al tipo de problema a tratar. Posteriormente se ven las principales instancias de resolución SL*, los procedimientos SLT y SLP. En este capítulo se hace un especial hincapié en la elección de ancestros, ya que es la principal aportación de resolución SL*, analizando tanto las ventajas que aporta asociadas al incremento de la eficiencia como el hecho de dotar a resolución SL* la capacidad de adaptarse a los problemas que trata. También en este capítulo se presenta una implementación de resolución SL*, en particular del procedimiento SLT, y se incluyen resultados sobre un conjunto extenso de problemas del campo de la demostración automática. En la última sección de este capítulo se realiza una comparación de resolución SL* con los demostradores y sistemas más cercanos, tanto a nivel de características como de resultados. / Casamayor Rodenas, JC. (1996). Resolución SL*: Un paradigma basado en resolución lineal para la demostración automática [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/6023 / Palancia