Résumé: Building computational systems capable of creating and interpreting narrative content has been an objective of Artificial Intelligence since its beginnings. Its development, however, has been blocked by what is commonly
known as the knowledge acquisition bottleneck, which does not permit story processing in the large.
In this dissertation, a computational system that tries to take one step forward in the target of making
it possible to process narrative content on a larger scale is presented. Two stages of research towards this goal
are detailed. A semantic approach to narrative processing not yielding satisfying results is first explained. Then, a different system modelling a focus shifting towards a structural management that provided better results is shown.
The current state of the art is studied in detail. Empirical validation has been carried out to prove to the possible extent the proposed hypothesis (the plausibility of structural processing for narrative content). Discussion
about the most important aspects and design decisions is also included, and possible future lines of investigation are also exposed.
Éditorial: Universidad Complutense de Madrid, Servicio de Publicaciones
Département: Fac. de Informática - Depto. de Ingeniería de Software e I. A. - Lenguajes y Sistemas Informáticos
ISBN: 978-84-694-2084-3
CDU: 004.43(043.2)
Notes: Tesis de la Universidad Complutense de Madrid, Facultad de Informática, Departamento de Ingeniería de Software e Inteligencia Artificial - Lenguajes y Sistemas Informáticos, leída el 18-11-2010
Résumé: Este trabajo presenta una aproximación formal para crear especificaciones de sistemas de agentes jerarquizados. El funcionamiento permite una automatización de las tareas, a las que el usuario del sistema accederá a través de peticiones. De manera general, lo que se hace es definir los elementos básicos del sistema, los agentes atómicos que son los que están a cargo de realizar las transformaciones de los recursos,y el sistema
recompondrá estos últimos para crear agentes complejos, que actúan como intermediarios entre los agentes atómicos y el usuario. Los agentes se localizan en una estructura conforme el sistema.
[ABSTRACT]
This Master´s Thesis provides a formal approach to create specifications of hierarchical systems of agents. The inner working of the system allows for an automatization of the tasks, that will be accessed by the user through the use of petitions. We will first define the actual transformations of resources, and the system will recompose the latter to create complez agents, that will act as mediators in between the hierarchical stratificacion. The cells conform a tree structure, and this structure conforms the system.
Département: Fac. de Informática - Depto. de Ingeniería de Software e I. A. - Lenguajes y Sistemas Informáticos
CDU: 004.89(043.3)
Notes: Máster en Investigación en Informática, Facultad de Informática, Departamento de Ingeniería del Software e Inteligencia Artificial, curso 2008-2009
Résumé: El campo del e-Learning ha evolucionado y madurado durante las últimas décadas. Poco queda ya de aquellos antiguos repositorios de contenido estático que recibieron
un sonoro fracaso en los 90. Los actuales Sistemas de Administración del Aprendizaje (SAA) son ricas aplicaciones Web que apoyan los procesos de aprendizaje para
múltiples roles y estrategias pedagógicas. Además, los SAA combinan muchas
de las herramientas más comunes que se encuentran disponibles en la Web (por ejemplo foros, chats, wikis, etc.), revisadas y adaptadas para aumentar su potencial educativo. Como consecuencia, los SAA se han convertido en una tendencia muy popular en el
campo del aprendizaje asistido por ordenador.
Sin embargo, los SAA siguen teniendo tareas pendientes. Una de las más importantes concierne a la falta de soporte para el aprendizaje adaptativo de estas plataformas. Aunque la idea de personalizar la experiencia de aprendizaje a las
necesidades de cada alumno ha estado presente en el campo durante décadas, pocos de los conceptos propuestos han llegado a los SAA. Muchas han sido las causas a las
que se ha atribuido esto, a las que nosotros ahora queremos añadir una más: la ausencia de contenido flexible y altamente interactivo en este tipo de entornos. Este
tipo de contenido permitiría por una parte, adaptar de forma más sencilla el contenido educativo, y por otra, facilitaría que el sistema pudiera llegar a “conocer” al
alumno para personalizar su aprendizaje. Según nuestra opinión, muchos de los sistemas adaptativos que han triunfado en otros campos (por ejemplo Amazonâ„¢) lo
han hecho en parte por guardar multitud de información sobre la interacción del usuario para así personalizar los servicios que le ofrecen. Si algún día los SAA tienen
que dar soporte al aprendizaje adaptativo, esto debería tenerse en consideración.
Dentro de este enfoque, proponemos la introducción de contenido altamente interactivo en SAA, y concretamente de video juegos educativos. El potencial del aprendizaje basado en juegos está ya prácticamente fuera de discusión; además su potencial adaptativo está todavía por descubrir. Sin embargo, existe un problema relacionado con la accesibilidad de los juegos, un tema que debe solucionarse dada la importancia de involucrar a todos los alumnos en su educación.
Por ello en este trabajo proponemos un marco de trabajo genérico y flexible que tenga en cuenta estos requisitos:
Que facilite la integración de juegos en SAA. Que permita establecer un canal de comunicación entre distintos SAA y juegos para dotar al SAA de más información sobre la interacción con el usuario. Y que considere accesibilidad desde el momento de su concepción como algo fundamental.
[ABSTRACT]
The field of e-Learning has evolved and matured during the last decades. From the old static repositories of content that achieved a thunderous failure in the 90’s very
little is left. Modern Learning Management Systems (LMS) are now powerful Weboriented environments that support the learning processes for multiple roles and pedagogical strategies. Moreover, LMS brings together most of the common features that are available on the Web (e.g. chats, forums, wikis, etc.), but reviewed and adapted to enhance their educational potential. As a consequence, LMS are probably the most popular trend in computer-supported learning not only within the academia but also in the industry.
Nevertheless, LMS still have some pending tasks. One of the most important is the lack of explicit support for adaptive learning that these systems usually present. While the idea of computer-supported adaptive learning has been around for decades, populating the research field with multiple approaches and pilots, LMS have not incorporated any of those ideas in order to tailor the learning experience for the needs of each student. Many are the reasons that have been related to this issue; nonetheless we would like to point out one more: the absence of highly interactive
and flexible content that could be easily adapted on the one hand, and which could provide LMS with valuable information about the user interaction on the other. In
our opinion, most of the adaptive systems that have achieved success in other fields (e.g. Amazonâ„¢) are known to store all the data that the system can get from the user
in order to personalize their services. If adaptive learning is to be supported by LMS, this should be considered as a mandatory point.
Within this perspective we propose the introduction of highly interactive content in current LMS, and more specifically the introduction of educational adaptive video
games. During the last years the educational potential of video games has been broadly accepted in the academic community, and their adaptive potential is to be unveiled yet for educational purposes. However there is a problem in educational gaming that has not been addressed yet: the lack of “accessibility”, which should be addressed given the importance of involving all the students in learning.
Therefore in this work we present a general and flexible framework that deals with these issues: It facilitates the integration of video games in Learning Management Systems.
It establishes a communication channel between different LMS and games to provide the LMS with information about the user’s interaction. And it considers accessibility as a mandatory requirement since its conception.
Notes: Master en Investigación en Informática, Facultad de Informática, Departamento de Ingeniería del Software e Inteligencia Artificial, curso 2008-2009
Résumé: La programación declarativa es un paradigma de programación con sólidos fundamentos matemáticos que permite diseñar programas con un alto nivel de abstracción; la programación lógico funcional aúna los formalismos lógico y funcional y ha sido un importante campo de investigación en las últimas décadas. En este trabajo se estudia un marco moderno para programación lógico funcional de orden
superior con λ-abstracciones, que es una extensión de los sistemas de reescritura de patrones basada en λ-cálculo para añadir características de orden superior basadas en λ-abstracciones y unificación de orden superior a los lenguages de programación lógico funcional convencionales. En este trabajo presentamos la lógica de reescritura GHRC que tiene un cálculo asociado con el mismo nombre y que especifica formalmente la derivabilidad a partir de la lógica. Después presentamos conceptos semánticos en base a una semántica de modelos y una semántica de punto fijo. Finalmente, presentamos una extensión del marco para permitir la construcción modular de programas de orden superior y definimos una semántica modular adecuada para ello demostrando que es composicional y completamente abstracta con respecto a las operaciones definidas sobre módulos.
[ABSTRACT]
Declarative programming is a programming paradigm with solid mathematical foundations that allow to design programs with a very high level of abstraction; the
functional logic formalism puts together functional and logic formalisms and has been an intense matter of research in the last two decades. In this work we study a modern semantic framework for higher-order functional logic programming with λ-abstractions, as an extension to pattern rewriting systems based on λ-calculus to add higher-order features based on λ-abstractions and higher-order unification to standard functional logic programming languages. We present a declarative rewriting logic GHRC with an associated calculus with the same name that formally specifies derivability from the logic. Then we present declarative semantic concepts in the form of classic model-theoretic semantics and fixed-point semantics. Finally we present an extension of the framework to support modular construction of higherorder programs and we define semantics suitable for this extension proving that they are compositional and fully abstract with respect to the classical operations defined over modules.
Mots-clés: Programación declarativa, Programación lógico funcional, Sistemas de reescritura de términos, Sistema de reescritura de patrones, Lambda cálculo, Semántica de los lenguajes de programación, Semánticas modulares. Declarative programming, Functional Logic progrmming, Term rewriting systems, Pattern rewriting systems, Lambda calculus, Semantics of programming languages, Modular semantics
Résumé: Las aplicaciones multimedia actuales, como las aplicaciones de vídeo digital y los juegos en tiempo real con gráficos en tres dimensiones, se caracterizan por un comportamiento muy dinámico, con una carga de trabajo que puede variar varios órdenes de magnitud en tiempo de ejecución. Además, típicamente estas variaciones dependen de la interacción de las aplicaciones con los usuarios, de los datos de entrada,
o incluso de las interacciones con otras aplicaciones, por lo que frecuentemente no resultan predecibles en tiempo de diseño. Este tipo de aplicaciones comenzaron desarrollándose únicamente para computadores de sobremesa o consolas especialmente optimizadas para ello con una gran capacidad de cálculo. Pero en los últimos años han comenzado a incluirse dentro de sistemas empotrados (como por ejemplo los teléfonos móviles y las PDAs) en los que los recursos disponibles están muy limitados por el reducido tamaño y precio de estos sistemas. Por si fuese poco, frecuentemente existe una segunda limitación impuesta por la dependencia de una batería con una capacidad muy reducida.
Éditorial: Universidad Complutense de Madrid, Servicio de Publicaciones
Département: Fac. de Informática - Depto. de Arquitectura de Computadores y Automática
ISBN: 978-84-693-3362-4
CDU: 004.3(043.2)(0.034)
Notes: Tesis de la Universidad Complutense de Madrid, Facultad de Informática, Departamento de Arquitectura de Computadores y Automática, leída el 16-10-2009
Résumé: En los circuitos tecnológicos diseñados con tecnologías de fabricación por debajo de la micra, las altas temperaturas provocan fallos críticos en la fiabilidad, el temporizado, los costes de refrigeración y la potencia de pérdidas. Hasta el momento se han propuesto varias técnicas de migración de tareas para manejar eficientemente la distribución térmica en los sistemas multiprocesador, pero con
un alto coste en cuanto a la eficiencia del sistema.
Aunque las técnicas tradicionales se han centrado en reducir la temperatura media del chip, no han considerado los efectos que los gradientes térmicos tienen en la fiabilidad del sistema.
En este trabajo, se exploran los beneficios de las técnicas de migración de tareas basadas en la temperatura en sistemas empotrados multiprocesador. En particular se proponen algunas políticas que son capaces de reducir la temperatura media del chip y los gradientes térmicos con un impacto en el rendimiento prácticamente despreciable.
Con nuestras técnicas, la aparición de puntos calientes (hot spots) y variaciones térmicas se ven drásticamente reducidos con respecto a otras propuestas, con lo que la fiabilidad del sistema se mejora significativamente cuando
la comparamos con las técnicas de migración de tareas tradicionales
[ABSTRACT]
In deep submicron circuits, high temperatures have created critical issues in reliability, timing, performance, cooling costs and leakage power. Task migration
techniques have been proposed to manage efficiently the thermal distribution in multi-processor systems but at the cost of important performance penalties.
While traditional techniques have focused on reducing the average temperature of the chip, they have not considered the effect that temperature gradients have in system reliability.
In this work, we explore the benefits of thermal-aware task migration techniques for embedded multi-processor systems. We propose several policies that are able to reduce the average temperature of the chip and the thermal gradients
with a negligible performance overhead.
With our techniques, hot spots and temperature variations are decreased, and the reliability of the system is significantly improved when compared to traditional task migration techniques.
Résumé: En la última década se han realizado grandes avances en la captura de la estructura tridimensional de escenas u objetos reales. Las crecientes capacidades de cálculo hacen que hoy en día sea posible procesar volúmenes de datos anteriormente intratables, mejorando técnicas y haciendo éstas más rápidas y precisas. Esta capacidad de modelar dentro de un computador escenas del mundo real
es muy ventajosa en áreas como la industria, el diseño industrial o las artes gráficas.
En esta memoria se puede encontrar una breve descripción de las técnicas existentes para la captación de información tridimensional, y entre éstas una vista general de las llamadas técnicas de luz estructurada. El tema central de este proyecto trata de estudiar una de las técnicas en auge, three phase shift, analizando su funcionamiento y puntuando las áreas de interés donde enfatizar esfuerzos. Se describe un análisis detallado de sus dos operaciones
principales mediante el cual se evaluarán rendimiento y calidad, describiendo el modo de funcionamiento de los desarrollos actuales y la investigación llevada a cabo en estas dos etapas.
Todo el proyecto ha sido enfocado desde el punto de vista de la computación, estudiando el comportamiento de los algoritmos, en particular las etapas llamadas phase wrap y phase unwrap.
[ABSTRACT]
During last decade significant inprovement has being made capturing the three dimensional structure of real objects or scenes. Increasing computational capabilities now make it
possible to process volumes of data previously intractable, improving technical and making them faster and more accurate. This ability to model inside a computer real-world scenes is very profitable in areas such as manufacturing, industrial design or graphic arts.
In this report you will find a brief overview of existing techniques for capturing threedimensional information, and specifically a description of the so-called structured light techniques. This project aims to study one of the rising techniques, three phase shift, analyzing its performance and scoring areas of interest where more effort has to be done. A detailed analysis of its two main operations will be evaluated by performance and quality, describing the state of current developments and research conducted in this two stages. The whole project has been approached from the point of view of computing, studying
the behavior of algorithms, in particular stages called phase wrap and phase unwrap.
Mots-clés: Escaner 3D, Luz estructurada,Tres cambios de fase, Mapa de profundidad, Phase wrap, Phase unwrap
3D scanner, Structured Light, Three phase shift,Deepmap, Phase wrap, Phase unwrap
Département: Fac. de Informática - Depto. de Ingeniería de Software e I. A. - Lenguajes y Sistemas Informáticos; Fac. de Informática - Depto. de Sistemas Informáticos y Computación
CDU: 004.352(043.3)
Notes: Máster en Investigación en Informática, Facultad de Informática, Departamento de Ingeniería del Software e Inteligencia Artificial, curso 2010-2011
Résumé: Los lenguajes declarativos proporcionan un nivel de programación más alto y abstracto que los lenguajes imperativos tradicionales. Los lenguajes funcionales y los lógicos son los dos paradigmas declarativos más importantes, y su combinación ha sido un tema de investigación en las últimas dos décadas. Los lenguajes lógico funcionales han heredado el clásico sistema Damas & Milner [20] de su parte funcional, debido
a su simplicidad y popularidad, pero esta aproximación directa no funciona correctamente en todos los casos. Es conocido que los patrones de orden superior en los lados izquierdos de
las reglas de programa pueden producir efectos no deseados desde el punto de vista de los tipos. En particular
algunas expresiones pueden perder su tipo tras un paso de cómputo. En este trabajo proponemos una extensión del clásico sistema de tipos Damas & Milner que arregla esta situación. Este problema fue detectado por primera vez en [24], y la solución propuesta fue prohibir los patrones de orden superior opacos. Nosotros proponemos una forma más relajada de abordar este problema, haciendo una distinción
entre variables transparentes y opacas. Una variable es transparente en un patrón si su tipo está unívocamente
determinado por el tipo del patrón, y es opaca en otro caso. Nosotros prohibimos solamente la aparición de variables opacas cuando son usadas en los lados derechos de las reglas. Hemos desarrollado el sistema de tipos tratando de clarificar el comportamiento (desde el punto de vista de los tipos) que las declaraciones locales tienen en diferentes implementaciones de lenguajes funcionales y lógico funcionales.
Éste es un aspecto que varía mucho, y usualmente no está bien documentado ni formalizado.
Aparte del sistema de tipos presentamos algoritmos de inferencia de tipos para expresiones y programas, y proporcionamos un prototipo de implementación en Prolog que será integrado próximamente en el compilador de T OY [45, 69]. Hemos prestado especial atención a los aspectos formales del trabajo. Por ello hemos desarrollado demostraciones detalladas de las propiedades del sistema de tipos, en particular de la propiedad de preservación del tipo o subject reduction (las expresiones mantienen su tipo tras la evaluación), y la corrección y completitud de los algoritmos de inferencia con respecto al sistema de tipos.
[ABSTRACT]
Declarative languages provide a higher and more abstract level of programming than traditional imperative languages. Functional and logic languages are the two most important declarative programming paradigms, and their combination has been a topic of research in the last two decades. Functional logic languages have inherited the classical Damas & Milner type system [20] from their functional part, due to its simplicity and popularity, but this naive approach does not work properly in all cases. It is known that higher order patterns (HO) in left-hand sides of program rules may produce undesirable effects from the
point of view of types. In particular some expressions can lose their type after a step of computation. In this work we propose an extension to the classical Damas & Milner type system that fixes this situation.
This problem was first detected in [24], and the proposed solution was forbidding opaque HO patterns.
We propose a more relaxed way of tackle this problem, making a distinction between transparent and opaque variables. A variable is transparent in a pattern if its type is univocally fixed by the type of the pattern, and opaque otherwise. We prohibit only the occurrence of opaque variables when they are used in the right-hand side of the rules. We have developed the type system trying to clarify the behavior (from the point of view of types) that local definitions have in different implementations of functional
and functional logic languages. This is an issue that varies greatly, and it is not usually well documented or formalized. Apart from the type system we also present type inference algorithms for expressions and programs, and provide a prototype of implementation in Prolog that will be soon integrated into the T OY [45, 69] compiler. We have paid special attention to the formal aspects of the work. Therefore we have developed detailed proofs of the properties of the type system, in particular the subject reduction property (expressions keep their type after evaluation), and the soundness and completeness of the
inference algorithms wrt. the type system.
Mots-clés: Sistemas de tipos, Programación lógico funcional, Patrones de orden superior, Patrones opacos, Polimorfismo paramétrico, Definiciones locales, TOY,Type systems, Functional logic programming, Higher order patterns, Opaque patterns, Parametric polymorphism, Local definitions
Département: Fac. de Informática - Depto. de Sistemas Informáticos y Computación
CDU: 004.42.046(043.3):004.42.047(043.3)
Notes: Máster en Investigación en Informática, Facultad de Informática, Departamento de Departamento de Sistemas Informáticos y Computación, curso 2008-2009
Résumé: Este trabajo describe un algoritmo para estimar parámetros importantes para la gestión de masas forestales, mediante el posicionamiento de los árboles la medición automática de sus dimensiones partiendo de imágenes LiDAR. Este trabajo se basa en estudios previos realizados en Alemania y muestra los problemas que se presentan en la búsqueda de árboles de diferentes tamaños y formas. Con este
algoritmo se pretende mejorar los métodos existentes hasta ahora para este fin. Para llevar a cabo este algoritmo se han usado métodos de clustering y lógica fuzzy. A partir de métodos
de clustering y lógica Fuzzy se decide si un punto pertenece o no a un árbol existente. Finalmente los resultados obtenidos por el algoritmo son satisfactorios para la altura media, mientras que el número de pies por hectárea se sobreestima excesivamente y en consecuencia también la biomasa por hectárea. Estos últimos e pueden mejorar ajustando determinados parámetros. El algoritmo ha sido implementando usando librerías de gvSig y la validación de los resultados obtenidos se ha llevado a cabo con Statgraphics y R.
[ABSTRACT]
This work describes an algorithm to analyze light detection and ranging (LiDAR) datasets with the aim of estimating forest biomass, positioning trees and measuring their heights and crown dimensions. The algorithm is based on previous studies developed in Germany that showed several problems when working with irregularly shaped trees. This algorithm tries to improve existing methods for this purpose. The detection of trees presents numerous challenges that are described in this work. Clustering methods and fuzzy logic have been used to decide whether or not each point stored in the LiDAR dataset belonged to an existing tree. Finally, the results obtained by the algorithm are satisfactory for the average height, while the number of trees per hectare is overestimated and consequently also too biomass per hectare. The last ones can be improved by adjusting certain parameters. The algorithm has been implemented using gvSIG libraries and the evaluation of results has been done by Statgraphics and R.
Département: Fac. de Informática - Depto. de Ingeniería de Software e I. A. - Lenguajes y Sistemas Informáticos
CDU: 004.932(043.3):510.64(043.3)
Notes: Máster en Investigación en Informática, Facultad de Informática, Departamento de Ingeniería del Software e Inteligencia Artificial, curso 2008-2009
