Theses and Dissertations



Departmento de Informática 
Pontifícia Universidade Católica do Rio de Janeiro - PUC-Rio
Rio de Janeiro - Brazil

This file contains the list of the MSc. Dissertations and PhD. Thesis presented to the Departmento de Informática, Pontifcia Universidade Católica do Janeiro - PUC-Rio, Brazil, in 2005.  They are all available in  print format and, according to the authors' preference, some of them are freely available for download, while others are freely available for download to the PUC-Rio community exclusively(*). 

For any requests, questions, or suggestions, please contact:
Rosane Castilho

Last update: 28/JUNE/2006


Aluízio HAENDCHEN FILHO. Um framework de middleware para sistemas multi-agentes na Internet. [Title in English: A Middleware Framework for Multi-Agent Systems on the Intenet]  Ph.D. Thesis. Port. Presentation: 13/09/05  175 p. Advisor: Carlos José Pereira de Lucena.

Abstract: The increasing widespread and evolution of the Internet have stimulated the demand for agent-based applications, and the search for standards and tools to support the development of these applications. MIDAS (Middleware for Intelligent and Distributed Agent-based Systems) defines a flexible, adaptable, and loosely coupled servise-oriented architecture, that provides an agent platform and a framework to facilitate the development of multi-agent systems in the Internet. The framework architecture adheres and extends the specifications of the WSA (Web Services Architecture) reference model, being composed by two basic structures: a concrete and an abstract one. The concrete struture is composed by a set of dynamic and pro-actives agents, which provide infrastructure services. These services enable the developer to abstract complex functionalities, such as communication, concurrency, management and interoperability. The second structure is composed by abstract classes, which represent the agents and components of applications. The abstract classes define the hot-spots from which the specific particularities of the application can be implemented, and regulate the interaction flow between the concrete implementation of agents and the architecture. The proposed architecture extends the current concepts defined by the WSA reference model, introducing the concept of abstract agent and complementary mechanisms to provide support for the agent's workflow and communication model.

Anarosa Alves Franco Brandão. Um método para estruturação e análise de modelos de sistemas multi-agentes baseado em ontologias. [Title in English: An ontology-based method for structuring and analysing the design of multi-agent-systems]  Ph.D. Thesis. Port. Presentation: 22/12/05  245 p. Advisor: Carlos José Pereira de Lucena.

Abstract: Agents are becoming a popular technology for the development of distributed, heterogeneous and always available systems. The application of agent technologies requires extensions to the existing object-oriented modeling languages to accommodate agent-related abstractions such as roles, organizations and environments. If it is difficult to analyze and establish the wellformedness of a set of diagrams of a UML-like object-oriented modeling language, it gets far more complex when the language is extended to add a set of agency related abstractions. This thesis presents an ontology-based method for structuring and analyzing multiagent systems (MAS) design models. The method proposes the analyses of MAS designs based on a two-phase approach that covers different sets of MAS design properties. These properties are the ones related to each individual diagram and the ones associated with pairs of diagrams. The later take into consideration the interdependencies between diagrams. The method also provides features that allow the suggestion of some design guidelines which may improve the design quality.

Ângela Brígida ALBARELLO. fGrupos - um framework multi-agente para a formação de grupos de interesse. [Title in English: fGrupos - a multi-agent framework for the interest groups formation]  M.Sc. Diss. Port. Presentation: 31/03/05 140 p. Advisor: Carlos José Pereira de Lucena.

Abstract: The current growth on the use of information technology exerts great influence on the behavior of the society. That is partially due to the application of new organization strategies which assist people and institutions on the development of their activities. A tendency which can be currently observed is associated with the benefits that occur when people with the same interest are grouped together for the accomplishment of a common task. This dissertation presents a Multi Agent framework that allows for the instantiation of applications that generate interest groups reports from any database, user profile definition heuristic, group formation strategy and data presentation format.

Ântonio Carlos Theóphilo COSTA JUNIOR. Soluções para a travessia de firewalls/NAT usando CORBA. [Title in English: Firewall/NAT traversal solutions using CORBA]  M.Sc. Diss. Port. Presentation: 16/08/05 140 p. Advisor: Markus Endler e Renato Fontoura de Gusmão Cerqueira.

Abstract: Applications that use CORBA as the communication layer often face some restrictions for multi-domain deployment. This is particulary true when they have to face firewall/NAT traversal. Furthermore, nowadays there is no well-accepted unique or standardized solution adopted by all ORBs, compelling applications using this type of middleware to use proprietary solutions that sometimes do not address the environment restrictions in which they are deployed (e.g. impossibility to open firewall ports). This work presents and compares three solutions for firewall/NAT traversal by CORBA-based distributed applications, each one suitable for a specific situation and exploring its advantages. Examples of such situations are the possibility of open firewall ports or the possibility of start a TCP connection to the outside network.

Antônio Luiz Vitalo CALOMENI. Navegação automática e assistida em reservatórios naturais de petróleo baseada em grafos de guias probabilísticos. [Title in English: Automatic and assisted navigation on black oil reservoirs based on probabilistic roadmaps]  M.Sc. Diss. Port. Presentation: /04/05  61 p. Advisor: Waldemar Celes Filho.

Abstract: There are many virtual reality applications that require navigation on 3D environments. Usually, this feature is offered by allowing the user to control all the six degrees of freedom of the virtual camera. However, it is difficult in this way, even for experienced users, to reach areas of interest with smooth and collision-free paths. It becomes necessary to provide an assisted navigation, in which the user guides the camera more easily, without restricting the environment exploration. Moreover, it is interesting to provide a fully automatic navigation, in which the user selects a target and the system computes a smooth, collision-free path throughout the environment. This work proposes a specific solution for navigation on models used in numerical simulations of black oil reservoirs, based on probabilistic roadmaps. Commonly used in robotics applications, probabilistic roadmaps tend to capture, by random sampling, the conectivity of the free space of the scene, being constructed in a pre-processing stage and queried in execution time. This work proposes a roadmap construction algorithm specific to reservoirs and two techniques to use the obtained roadmap as the basis to provide assisted and automatic navigation.

Antônio Tadeu de Azevedo GOMES. LindaX: uma linguagem de descrição de sistemas de comunicação adaptáveis. [Title in English: LindaX: a language for describing adaptable communication systems]  Ph.D Thesis. Port. Presentation: 21/03/05  194 p. Advisor: Luiz Fernando Gomes Soares.

It is increasingly noticeable, in the current telecommunications market, a trend towards using communication systems that allow rapid and cheap deployment of new services. In pursuit of network architectures that keep up with such trend, significant research has been carried out on programmable networks. This field is set to gain further impetus from developments in network processor-based equipment. In this context, it is crucial that service creation processes be well structured and, as far as possible, systematic. This thesis, which is part of an ongoing project at the TeleMídia Laboratory, PUC-Rio, adopts a service creation approach in which techniques from Software Architecture and Component-Based Software Development are uniformly and ubiquitously applied at all levels of a communication system, ranging from high-level service specifications to low-level software implementation running in network processors. The main aim is to express adaptibility in cross-cutting service aspects and, meanwhile, cut down on the cognitive overhead usually imposed upon designers and programmers due to such multiplicity of concerns. For the sake of the aforementioned aim, an XML-based specification language, called LindaX, has been developed. Such language allows various system aspects to be architecturally described – by means of a single syntactic framework for DSLs – as well as adaptable in a constrained way – through style structures. Complementing the work, a toolset for handling LindaX architecture descriptions has been defined, which allows their refinement to different formal languages or their synthesis onto system  configurations and adaptation controlling mechanisms for diverse platforms.

Beatriz Alves DE MARIA. Usando a abordagem MDA no desenvolvimento de sistemas multi-agentes. [Title in English:
MDA based approach for developing multi-agent systems] M.Sc. Diss. Port. Presentation:  13/04/05  153 p. Advisor: Carlos José Pereira de Lucena and Viviane Torres da Silva.

Multi-agent systems (MAS) differ from non-agent systems because agents are intended to be autonomous units capable of flexible and intelligent actions.  For this reason it is proposed in the literature a great number of methodologies frameworks and languages to support the development of these systems.  Several methodologies and their tools come from artificial intelligent community and are focused in a specific agent architecture. This work proposes the use of the Model Driven Architecture (MDA), described by OMG, in the development process of MAS. MDA specifies a structured software development process in modeling stages that supports all system development life cycle. The proposed development process is divided according to the MDA stages. In PIM stage, where platform independent models are specified, we propose the use of MAS-ML modeling language for MAS. In PSM stage, where platform specific models are  specified, we propose the use of UML modeling language. The MASML models defined on PIM stage are transformed in UML models at PSM stage, based on an object-oriented framework for implementing MAS. In the last development stage, the application code is generated from UML models. This work details the PIM and PSM stages of the MAS development process and the models transformations to generate source code. To exemplify the applicability of the proposed MAS development process, two different MAS applications were developed based on the process. Finally, a MAS-ML tool is presented. Such tool was developed to support the proposed development process. The tool implements all stages presented in the process, allowing the modeling and implementation of MAS.

Börje Felipe Fernandes KARLSSON. Um middleware de inteligência artificial para jogos digitais. [Title in English: An artificial intelligence middleware for digital games]  M.Sc. Diss. Port. Presentation: 08/09/05     126 p. Advisor: Bruno Feijó.

Abstract: The usage of artificial intelligence (AI) techniques in digital games is currently facing a steady need of improvements, so it can cater to players higher and higher expectations that require realism and believability in the game environment and in its characters' behaviours. In order to ease the fulfillment of  these goals, software engineering techniques and methodologies have started to be used during game development. However, the use of such techniques and the creation of AI middleware are still far from being a generic and flexible enough tool for developing this kind of application. Another important factor to be mentioned in this discussion is the lack of available literature related to studies in this field. This dissertation discusses the research effort in developing a flexible architecture that can be applied to different game styles, provides support for several game AI functionalities and serves as basis for the introduction of more powerful techniques that can gameplay and user experience. This work presents: design issues of such system and its integration with games; a study on AI middleware architecture for games; an analysis of the state-of-the-art in the field; and a "survey" of the available relevant literature. Taking this research as starting point, the design and implementation of the proposed AI middleware architecture was conducted and is also described here. Besides the implementation itself, a study on the use of design patterns in the context of the development and evolution of an AI framework for digital games is also presented.

Bruno Oliveira SILVESTRE. Autenticação e controle de acesso interinstitucional. [Title in English: Interinstitutional access: authentication and access control]  M.Sc. Diss. Port. Presentation: 21/03/05  56 p. Advisor: Noemi da La Rocque Rodriguez.

Abstract: Distributed computing has been expanding his scope from local area network to wide-area applications, involving different organizations.  This expansion implies in several new security challenges, such as the identification of users originating from different organizations and the deffinition of their access rights.  Common approaches involves replicating user data in several institutions or sharing identities among set of users.  However, these approaches have several limitations, such as the increased management effort of administrators or problems with privacy policies.  This work proposes a framework for inter-institutional authetication.  The framework is based on the concept of RBACS (role-based access control) and trust between organizations.

Bruno Santana da SILVA. MoLIC segunda edição: revisão de uma linguagem para modelagem da interação humano-computador. [Title in English: MoLIC Second Edition: revision of a modeling language for human-computer interaction] M.Sc. Diss. Port. Presentation: 12/08/05 175 p. Advisor: Simone Diniz Junqueira Barbosa.

Abstract: Day after day, we discover new ways to use computation in various domains and for a variety of purposes: entertainment, medicine, education communication, etc. Large-scale hardware production has made computers and mobile devices (for example, cell phones, PDAs and Tablet PCs) more accessible to an increasing number of users. The wide use of computation requires software to be developed not just with high "internal" and functional quality, but also with high quality of use. In face of this need, Human  Computer-Interaction (HCI) researchers have researched ways to design user interface with high quality of use. In particular, some HCI researchers propose model-based user interface design. The MoLIC language (Modeling Language for Interaction as Conversation) was proposed in 1991 to model the human-computer interaction, grounded in 2005 on semiotic engineering. Since its proposal, MoLIC has been used in case studies in different domains and platforms. These studies have raised questions about the use of the language that have remained unsuitable or that still had not been addressed in the first edition of the language. Some of these questions gave rise to extension proposals to MoLIC. As there are still opened questions raised from these case studies and the extension proposals were not sufficiently sound to be definitely incorporated into MoLIC, there was the need of a work to address those questions and to organize the extensions, as well as additional proposals that may be found necessary, with te concern of keeping the language consistent with its theoretical grouding. Therefore, this work presents a revision of the first edition of MoLIC, pointing out and answering open issues. As a result of the revision, it defines the second edition of MoLIC, which incorporates several extension proposals. And, finally, it concludes by raising additional questions to be addressed in future MoLIC editions.

Carlos Bazílio MARTINS.
Análise formal de protocolos e algoritmos distribuídos: uma abordagem baseada em linguagem. [Title in English: Formal analysis of protocols and distributed algorithms: a based-Language approach] M.Sc. Diss. Port. Presentation: 09/09/05 175 p. Advisor: Edward Hermann Haeusler.

Abstract: In this work we propose an architecture for the formal verification of protocols and distributed  algorithms. This can be seen as a more abstract layer over the ordinary process of formal verification, where we have just the specification of the protocol and properties to be verified, and the formal tool. Our goal is to simplify the specification and formal verification of protocols and distributed algorithms through a dedicated environment. The core of the architecture is its input specification language (LEP), which provides domain-specific constructions for simplifying the specification of those systems. With LEP the specification of the protocol and the specification of the topology to be referred to the protocol are given separetely. We feel that this division improves the legibility of both and allows the reuse of the specification of a topology among distinct protocols. Using this approach we try to offer a language whose specifications should be similar to the descriptions of the algorithms found on the didactic book. Moreover, in order to have the input and output of the architecture compatible, we also propose a way of processing the result of the formal verification tool. Then we could have the result on the abstrac level of LEP.

Cássia Blondet Baruque. Desenvolvimento de bibliotecas digitais de objetos de aprendizagem utilizando técnicas de data warehousing e data mining. [Title in English: Development of learning objects digital libraries using data warehousing and data mining techniques] Ph.D. Thesis. Port. Presentation: 14/05/05 191 p. Advisor: Rubens Nascimento Melo.

Abstract: This work aims at the development of Learning Objects Digital Libraries (LO-DLs), using Data Warehousing (DWing) and Data Mining (DMining) techniques. By using the Data Warehousing approach, we will be able to correlate the main steps of this technique, which area Extraction, Transformation, Loading and OLAP, with the main services of a Traditional Library which are Acquisition, Subject Classification, Cataloging, and Searching, so that they will work in an automatic way. Data Mining techniques are incorporated in some of these processes automating the process of the development of the library. Besides integrating multiple LOs sources, which are stored in diverse DBMSs (Data Base Management Systems) and catalogued in different metadata languages, this approach contributes to providing the user with a sophisticated query to the library that is more comprehensive than the usual "author", "subject" or "title" options, since OLAP allows multidimensional access. Furthermore it also contributes to the improvement of the library, since OLAP and data mining techniques are used to analyze LOs data and the access to them. An automatic "refresh" of the library is made when users' profile changes.

Cecília CAMACHO. Gerenciando conflitos em reuniões: uma estratégia para a elicitação de requisitos de software. [Title in English: Conflit management in meetings: a strategy for software requirements elicitation]  M.Sc. Diss. Port. Presentation: 05/04/05  168 p. Advisor: Julio Cesar Sampaio do Prado Leite.

Abstract: This work reports a research on the automation support for requirements elicitation performed by means of meetings. In order to provide this support, we ground our work on conflict management, stimulating functional conflicts and controlling non-functional conflicts in order to increase the volume of elicited knowledge. This is based on cooperative work among the stakeholders of the demanded system or demanded changes on an existing system. The method is an evolution of a previous work on the topic and is based on conflict management over a cycle of meetings. This management is performed by a feedback process enacted by the meeting participants by means of a questionnaire for the provision of information. A Web tool to support the method was built to collect the information and analyze the conflicts.

Cezar Tadeu POZZER. Um sistema para geração, interação e visualização 3D de histórias para TV interativa. [Title in English: A system for generation, interaction and 3D visualization of stories for interactive TV]  Ph.D Thesis. Port. Presentation: 30/03/05  156 p. Advisors: Bruno Feijó, Antonio L. Furtado, Angelo Ernani Maia Ciarlini.

Abstract: This thesis aims at the development of an integrated tool for managing both the generation and representation of dynamic interactive stories (storytelling). The story generation is accomplished by a simulation process resulting in a set of partially ordered operations that define the plot of the story. This story should then be graphically represented by means of a 3D engine. It has been used cinematographic techniques to capture the essence of the scenes, which are composed by a virtual 3D environment, including characters and objects. Characters, implemented as reactive agents, interact among each other in a multi-agent system and with the scene to accomplish the plot of the narrative. Each agent encapsulates resources that allow them to graphically represent typical events of stories. The overall architecture is designed as a source for Interactive TV content.

Cidiane Aracaty LOBATO. Um framework orientado a aspectos para mobilidade de agentes de software. [Title in English:
An aspect-oriented framework for software agents mobility] M.Sc. Diss. Port. Presentation: 01/12/05 157 p. Advisor: Carlos José Pereira de Lucena and Alessandro Fabrício Garcia.

Abstract: Software engineers of multi-agent systems (MASs) are concerned with the design and implementation of the mobility issues in addition to the agents' basic functionalities and other agent-related concerns. As the agents' complexity increases, mobility issues cannot be modularized based only on object-oriented (OO) abstractions and mechanisms. Besides, some programmers frequently evidence the presence of mobility tangling and scattering problems on their systems. Despite these problems, MAS developers have mostly relied on application programming interfaces (APIs) OO from mobility platforms and on the use of the Java programming language. The result is the production of MASs that are difficult to understand, maintain, and reuse. This work presents three main contributions. Firstly, an analysis of existent solution for modularization of mobility issues. Besides, the proposal of the ArchM software architecture and the AspectM framework, both based on aspects, which support: (i) improved modularization of the mobility issues, that is a clean separation between the mobility-specific concerns and other agent concerns, (ii) a seamless introduction of code mobility into stationary agents, and (iii) a flexible integration with multiple platforms. The aspect-oriented software development (AOSD) is a new paradigm with abstractions and composition mechanisms that support an improvement of reuse and maintainability of systems. The benefits of the AspectM framework are illustrated through two case studies and through use of two mobility platforms

Cristina Nader VASCONCELOS. Segmentação de vídeo no domínio comprimido baseada na história da compactação. [Title in English: Video segmentation in the compressed domain based on the compression history] M.Sc. Diss. Port. Presentation: 30/03/05  97 p. Advisor: Bruno Feijó and Dilza de Mattos Szwarcman.

Abstract: This works presents a proposal for finding shot cuts in MPEG-1 and MPEG-2 videos. The proposed approach is based on heuristics for eliminating similar frames and thus extracting a set of frames positioned at cuts points. These heuristics analyze de compressed data, retrieved from MPEG video streams, without any decompression, thus saving time and space during the shot finding process. The existence of false cut patterns is noticed by studying the data returned by the chosen metrics. In face of such false positives (related to choices made during the history of the video encoding process), the analysis of the compressed data tries to identify patterns in the encoded stream, considered as compressor signatures. To distinguish between cut frames and frames characterized by the encoding process, some filters are proposed in order to alleviate the compressor influence on the similarity metrics results.

Daniel ALOISE. Heurísticas para o projeto de redes com funções de custo discretas. [Title in English: Heuristics for the network design problem with discrete cost functions] M.Sc. Diss. Port. Presentation: 25/04/05  76 p. Advisor: Celso da Cruz Carneiro Ribeiro.

Abstract: Multicommodity flow problems arise widely as basic models in the context of network flows applications such as telecommunication networks, transportation problems, and logistic. In these applicatons, the flows that cross the networks share the same avaiable resources simultaneously and are defined by their own constraints. Each edge connecting two nodes in the network has an associated cost that is either fixed or proportional to its use. This work focuses on a network design problem in which the cost are associated with the capacities installed in the edges. Particularly, the network design problem studied has discrete and step increasing cost functions on the edges, for which exact methods are inefficient. Heuristics are proposed for the approximate memory algorithm. An intensification mechanism, known in the literature as vocabulary building, is also explored and applied. Finally, computational experiments are performed and the results obtained with the proposed solution method are evaluated. The method obtains the best known solutions for some instances in the literature.

Daniela Francisco BRAUNER. Uma arquitetura para catálogos de objetos baseada em ontologias. [Title in English: An architecture to ontology based object catalog] M.Sc. Diss. Port. Presentation: 14/04/05  141 p. Advisor: Carlos José Pereira de Lucena and Marco Antonio Casanova.

Abstract:  Data sharing is a critical factor for the success of organizations due to the increasing need to facilitate communication with business partners. However, data source heterogeneity proved to be a barrier for the effective interoperability between information systems. The concept of an Ontology- based Object Catalog (OnOC) is first introduced as a strategy to address the interoperability problem between heterogeneous data sources. An OnOC offers support for the definition and maintenance of a common vocabulary, called a reference ontology, that facilitates data interchange among different sources. Then, an architecture for OnOCs is proposed that combines concepts such as metadata catalogs, ontology servers, mediators and database federations.

Demétrius Arraes NUNES. HyperDE - um framework e ambiente de desenvolvimento dirigido por ontologias para aplicações hipermídia. [Title in English: HyperDE - a framework and development environment driven by ontologies for hypermedia applications] M.Sc. Diss. Port. Presentation: 30/03/05  198 p. Advisor: Daniel Schwabe.

Abstract: HyperDE, presented in this dissertation, is a combination of a Model-View-Controller framework and a visual development environment for building prototype applications modeled through the OOHDM and SHDM methods. As a MVC framework, HyperDE provides the reusable and extensible components for the model, vision and control layers, specified as ontologies in RDFS. As a visual development environment, HyperDE provides, through its graphical interface and support tools, an interactive and dynamic way for building and prototyping a hypermedia application, making it possible to visualize the results on each step of the development process. The development architecture promoted by the environment is model-driven, in which the definition of the navigational models effectively generate the application implementation. Using data models based on RDF and RDFS, the navigational models produced in HyperDE can be used as ontologies, through semantic web languages and technologies. Also, the use of a dynamic programming language makes it possible for HyperDE to dynamically generate domain-specific languages for each application built, which results in a programming model much more concise and natural.

Eraldo Luís Rezende FERNANDES. Heurísticas para o problema de seqüenciamento de DNA por hibridação. [Title in English: Heuristics for the DNA sequencing by hybridization problem] M.Sc. Diss. Port. Presentation: 30/03/05  80 p. Advisor: Celso da Cruz Carneiro Ribeiro.

Abstract: Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature

Felipe Fortes NASCIMENTO. Um framework de sistemas multi-agentes para aplicações RFID. [Title in English: A multi-agents systems framework for RFID applications]  M.Sc. Diss. Port. Presentation: 08/08/05 118 p. Advisors: Carlos Jose Pereira de Lucena and Viviane Torres da Silva.

Abstract: Radio Frequency Identification (RFID) technology along with the Electronic Product Code (EPC) created a new complex environment for warehouses systems and supply chain systems in general. The EPC specification created one more level of identification: the product instance. This new level of identification had blown the volume of data being managed by applications. That facts, along with the deployment of distributed RFID readers, causes the necessity of new applications capable of interacting with this infrastructure and capable of processing, filtering and interpreting these new data. This work proposes a framework for distributed multi-agent systems capable of interacting with a deployed RFID infrastructure.

Fernando Ney da Costa NASCIMENTO. Um servico para inferência de localização de dispositivos móveis baseado em redes IEEE 802.11. [Title in English: A Location inference service for mobile devices based on IEEE 802.11 networks] M.Sc. Diss. Port. Presentation: 08/08/06 74 p. Advisor: Markus Endler

Abstract: Portable devices and wireless networks are becoming common place in our daily lives. This has created a demand for the development of location-based services and applications, i.e. Location-based Services. In parallel, several positioning technologies enabling such services have been developed, where GPS is the most popular one. The main drawback of this and other technologies is that they require the deployment of a specific infra-structure for the positioning, such as sensors and satellites, which in turn raises their cost or restricts their applicability. Therefore, other positioning technologies, which are based merely on the wireless infra-structure, have been explored. In this work we present a service which infers the location of mobile devices using the radio-frequency signal strength of Access Points of IEEE 802.11 wireless networks.  We have also verified the viability of its use by applications that require location information in terms of symbolic regions, instead of coordinates, and which tolerate inference errors of a few meters. The service also supports the aggregation of regions into larger symbolic regions using the notion of a hierarchy of symbolic regions.

Francisco BENJAMIM FILHO. XHITS: estendendo o algoritmo HITS para extração de tópicos na WWW. [Title in English: XHITS: extending the hits algorithm for distillation of broad search topic on WWW]  M.Sc. Diss. Port. Presentation: 04/04/05  76 p. Advisor: Ruy Luiz Milidiú and Raul Renteria.

Abstract:  The network structure of a hyperlinked environment can be a rich source of information about the content of this environment. Jon Kleinberg developed a set of algorithms, called HITS (Hyperlink Induced Topic Search), for extracting information from the hyperlink structures of those environments. The aim of these algorithms is the distillation of broad search topics, through the discovery of related authoritative information sources. The notion of authority is based on the hyperlink structure relationship between a set of relevant authoritative pages and the set of hubs. Thus, hubs and authorities exhibit what could be called a mutually reinforcing relationship: a good hub is a page that points to many good authorities; a good authority is a page that is pointed by many good hubs. In this work, we present the XHITS (Extended Hyperlink Induced Topic Search) algorithm, an extension of the HITS algorithm by introducing new concepts on the mutually reinforcing relationship. In XHITS, a good authority is a page that is pointed by many good hubs, some good portals and points to good novels; a good hub is a page that points to many good authorities, some good novels and is pointed by some good portals; and a good novel is a page that is pointed by good authorities, some good hubs and some good portals; a good portal is a page that points to some good authorities, some good hubs and some good novels. In addition, we show that XHITS converges and, through some experiments, the improved quality of the hyper documents retrieved.

Frederico dos Santos LIPORACE. Planejadores para transporte em polidutos. [Title in English: Pipeline transportation planners]  Ph.D. Thesis.  Port. Presentation: 14/09/05  120 p. Advisor: Ruy Luiz Milidiú.

Abstract: Pipelines have an important role in oil and its derivatives transportation, since they are the most effective way to transport high volumes through long distances. The motivation for this work is that a non negligible part of the final price for those products are due to transportation costs. Few authors have addressed this problem, with most of the previous work using integer programming techniques. This work analyses the use of Artificial Intelligence techniques, discrete event simulators and software frameworks for building automated planners that are able to deal with real-world oil pipeline transportation instances. The first contribution of this thesis is the specification of a new planning domain called PIPESWORLD. This  domain is inspired by the oil pipeline transportation problem, and is defined in PDDL. Due to its original structure, the PIPESWORLD domain has been incorporated to the 4th International Planning Competition benchmark. Even being a simplification of the original problem, PIPESWORLD instances in the benchmark are challenging to state of art solvers. It is also shown that decision problems based on PIPESWORLD configurations are NP-Hard. The second contribution of this thesis is the PLANSIM open-source framework. This framework incorporates a search engine that may use several different strategies, and defines a structure that facilitates the construction of automated planners based on heuristic forward search that use discrete event simulators as the model for the process to be planned. The third contribution of this thesis is a PLANSIM instantiation that results in an automated planner able to deal with real-world oil pipeline transportation instances, called PLUMBER 2. The use of dicrete event simulation techniques for the model of the system to be planned allows this model to be very close to the original problem. This, in conjunction with PLANSIM usage, facilitates the construction of planners that are able to cope with real-world instances.

Frederico Rodrigues ABRAHAM. Visualização distribuída utilizando agrupamentos de PCs. [Title in English: Distributed visualization using clusters of PCs] M.Sc. Diss. Port. Presentation: 04/03/05  64 p. Advisor: Waldemar Celes Filho.

Abstract: This work presents a new distributed rendering system destined for PC clusters. The conventional graphics pipeline is extended to a distributed pipeline that parallelizes the operations done on the CPU, the GPU and the network by using multiple threads. This system was the base for the implementation of three distributed rendering architectures: a sort-first architecture, a sort-last architecture for volume rendering, and a hybrid architecture that seeks to combine the advantages of both sort-first and sortlast architectures. A new load-balancing algorithm based on the rendering times of the previous frame is proposed. The algorithm is very simple to be implemented and works well for both geometry- and rasterization-bound models. A new strategy to assign tiles to rendering nodes is proposed which e ectively uses the available graphics resources, thus improving rendering performance. A new parallel model partition algorithm is proposed for the hybrid architecture.

Gabriel Tavares Malízia ALVES. Um estudo das técnicas de obtenção de forma a partir de estéreo e luz estruturada para engenharia. [Title in English: A study of techniques for shape acquisition using stereo and structured light aimed for engineering] M.Sc. Diss. Port. Presentation: 22/06/05  88 p. Advisors: Marcelo Gattass and Paulo Cezar Pinto Carvalho.

Abstract: There has been a growing demand for creation of computer models based on real models for engineering projects. A cheap and effective alternative consists in using Computer Vision techniques based on cameras and projectors available at the personal computer market. This work evaluates a stereo optic system for capturing geometric shapes from objects using a pair of cameras and a single digital projector. The system is based on former works and a pair of contributions is obtained at this dissertation. The first contribution is a more robust technique for finding corners and points at cameras calibration patterns. And the second one consists on a new method for cylinder fit for inspecting industrial piping facilities with the studied system. The final conclusions evaluate the robustness and precision from the proposed system as a measurement tool for Engineering.

Hedlena Maria de Almeida BEZERRA. Colorização 3D para animação 2D. [Title in English: 3D colorizing for 2D animation] M.Sc. Diss. Port. Presentation: 06/06/05  82 p. Advisors: Bruno Feijó and Luiz Carlos Pacheco R. Velho.

Abstract: This dissertation discusses the 3D colorization effects usage over a 2D animation, which has been produced through frame-by-frame techniques. Normal vector maps approximates the drawing geometry and provide the ability to perform shading effects by applying digital image processing algorithms, avoiding 3D geometry scene transformation. A set of photorealistic and non-photorealistic renderization techniques, which can be adapted to normal approximation usage, is proposed in the colorization process. Also, a method based on interframe dependence is presented, aiming to reduce the thoroughgoing effort of colorizing each individual frame within an animation. This colorization process considers possible human interventions to ensure image's result quality. Finally, this dissertation provides a comprehensive study regarding several topics, such as normal approximations, shading techniques, image segmentation and object tracking.

Heron Villela de Oliveira e SILVA. X-SMIL: aumentando reuso e expressividade em linguagens de autoria hipermídia. [Title in English: X-SMIL: improving reuse and expressiveness in hypermedia authoring languages] M.Sc. Diss. Port. Presentation: 04/04/05  210 p. Advisors: Luiz Fernando Gomes Soares e Rogério Ferreira Rodrigues.

Abstract: This work is related to hypermedia authoring and execution environments, and its main focus is declarative document authoring. Aiming at improving the expressiveness and reuse in the specification of hypermedia documents, this work introduces the hypermedia authoring languages X-SMIL and NCL - Nested Context Language - version 2.1. Exploiting the concept of templates, X-SMIL allows the definition of new semantics for SMIL compositions, besides its usual seq, par and excl elements. X-SMIL templates are specified using an XTemplate profile, which extends the original idea of the NCL XTemplate language. Bringing new facilities for template definitions, this new profile is used to further improve the NCL language. X-SMIL also offers support for handling hypermedia relations as first-class entities, through the use of hypermedia connectors - brought to X-SMIL via the NCL XConnector module. Another important goal of this work is to present a framework to facilitate the development of XML documents parsing and processing tools. Based on this framework, several compilers were implemented, permitting, among other features, the conversion of NCL documents into SMIL or X-SMIL specifications and vice- versa

José Alberto Rodrigues Pereira SARDINHA. MAS-School e ASYNC: Um método e um framework para construção de agentes inteligentes.  [Title in English: MAS-School e ASYNC: a method and a framework for building intelligent agents] Ph.D Thesis. Port. Presentation: 18/03/05  152 p. Advisors: Ruy Luiz Milidiú and Carlos José Pereira de Lucena.

Abstract: The agent technology is used to develop systems that perform several complex tasks. This thesis presents the MAS-School method for modeling and implementing intelligent agent-based systems. The method presents a systematic approach to support a disciplined introduction of machine learning techniques in multi-agent systems from an early stage of design. The proposed approach encompasses guidelines to both the design and implementation phases of an agent-based system. It is based on an incremental development strategy that largely relies on simulation and testing techniques. This thesis also presents the ASYNC framework that is composed of software engineering tools for building agent based system for asynchronous, cooperative and intelligent agents. This thesis presents four complex applications that used the proposed method and framework in the design and implementation phase. The first case study presents an application that discovers the most appealing offerings for consumers in a retail market. The second case study presents a virtual marketplace for buying and selling goods with automatic negotiation. The third case study is a multi-agent system for a complex procurement scenario with interdependent and simultaneous auctions. This system achieved the third place in the 2004 TAC Classic competition. The fourth case study is a multi-agent system for a PC manufacturer scenario based on sourcing of components, manufacturing of PC's and sales to customers


José Antonio Fernandes de MACEDO. Um modelo conceitual para biologia molecular. [Title in English: A conceptual model for molecular biology]  Ph.D. Thesis. Port. Presentation: 25/08/05 93 p. Advisors: Sérgio Lifschitz and Edward Hermann Haeusler

Abstract: Genomic and molecular biology projects are generating knowledge data whose volume and complexity are unparalleled in this research area. In addition, data and knowledge sources produced and  used by research groups have terminological differences (synonyms, aliases and formulae), syntactic differences (file structure, separators and spelling) and semantic differences (intra-and interdisciplinary homonyms). In this context, data management techniques play a fundamental role for biological applications development because it offers adequate abstractions to design, implement, access and manage data, in order to generate knowledge.  In this work, we study the representation problems presented in traditional languages. Following, we raise the main requirements for a new conceptual data model specially conceived for molecular biology. Finally, we propose a new conceptual data model with special types of constructor trying to solve some of the representation problems discussed before. In addition, we formalize our proposed model using first-order logic and we use this logical description to infer some properties that may help database designer during the elaboration of database schema.

Kleder Miranda GONÇALVES. A framework para comunicação baseada em localização.  [Title in English:  A framework for location-based communication]  M.Sc. Diss. Port. Presentation: 07/07/05  91 p. Advisor: Markus Endler. 

Abstract:  The combination of mobile wireless computing and location technology enabled the emergence of a new computing paradigm known as Location-Based Services, whose goal is to study how to provide personalized services to users depending on the their location. Among these services, very useful are the ones which support different kinds of communication between mobile users. Although several services have been developed with this goal, only few work aimed at identifying the common characteristics of these systems, with the goal of designing a generic infrastructure that serves as the basis for the development of new services. This was the main motivation for this thesis work, in which we designed an object framework facilitating the construction of applications for location-based communication among mobile users. As main case studies, we instantiated an application called Nita (Notes In The Air), which provides both synchronous and asynchronous communication between co-located users, and a location-enhanced instant messaging application similar to BuddySpace.

Lucas Euzébio MACHADO. Técnicas de distribuição para jogos multijogador em massa. [Title in English:  Distribution techniques for massive multiplayer games] M.Sc. Diss. Port. Presentation: 12/08/05 80 p. Advisors: Bruno Feijó and Lauro Eduardo Kozovits.

Abstract: This dissertation presents several techniques and technologies that are helpfull in the creation of distributed virtual environments with thousands of connected players. Explanations about the proper use of TCP and UDP are given. Some optimization techniques in the use of sockets are also given. Technologies that allow many sockets to be handled at once are explained, such as poll and kqueue from Unix and IO Completion Ports from Windows. Specific techniques for distributed virtual environments are presented. A tool that uses many of these techniques is proposed.


Luiz Gustavo Bustamante MAGALHÃES. Multi-resolução de geometria de terrenos armazenados em memória secundária. [Title in English: Multi-resolution of out-of-core terrain geometry]  M.Sc. Diss. Port. Presentation: 13/12/05 62 p. Advisor: Waldemar Celes Filho.

Abstract: The visualization of large terrains is a challenging Computer Graphics issue. The number of polygons required to faithfully represent a terrain's geometry can be too high for real-time visualization. To solve this problem, a multi-resolution algorithm is used to feed the graphics processor only with the most important polygons, without visual quality loss. The amount of data is another important problem, as it can easily exceed a computer's RAM. Thus, a system to manage out-of-core data is also required. The present work proposes a simple and scalable solution to visualize the geometry of large terrains based on three key points: a data structure to represent the terrain in multi-resolution, an efficient visualization system and a data paging and prediction system. Similarly to other works, the system uses a quadtree data structure due to its simplicity, along with the efficiency and the low memory use of an array-based implementation. Each node of the quadtree represents a tile of the terrain. The implementation is divided in two threads, one to manage the tiles and the other for visualization. The tile-management thread is responsible for loading/unloading tiles into/from the memory. This thread uses a camera-movement prediction mechanism to load tiles that can be used in the near future and remove tiles that probably will not be necessary. The visualization thread is responsible for viewing the terrain, computing the projected error, eliminating tiles that are not visible and balancing the quadtree structure in order to eliminate cracks or T-vertices on the terrain's surface. The visualization can be made by means of a fidelity-based or a budget-approach.

Manuel Eduardo LOAIZA FERNANDEZ. Implementação de um dispositivo de rastreamento óptico com 6 graus de liberdade para interação com aplicações de realidade virtual. [Title in English: Implementation of an optical tracking device with 6 degrees of freedom for interacting with virtual reality applications]  M.Sc. Diss. Port. Presentation: 01/04/05  105 p. Advisor: Marcelo Gattass and Alberto Barbosa Raposo.

Abstract: Tracking systems are a fundamental technology in virtual reality systems. They provide a continuous detection of the position and orientation of markers or specific objects that the user employs to interact with the system. One of the technologies most commonly used to implement these types of systems is the optical tracking, which allows the users to have more freedom in their movements because it does not need cables or mechanical elements that can restrict or hinder the immersion sensation that is tried to create in the interaction with virtual reality environments. This work presents the construction and implementation of an input device that is based on optical tracking that is used for interaction with semiimmersive virtual reality applications on ordinary desktop environments. This device has the capability to get the six degrees of freedom of the movements made by a set of markers that are controlled by the user hand. Based on the six degrees of freedom recovered, the device is complemented with the ability to emit events that allow the interaction of the user with the application. Finally, an application is presented for demonstrating the use of the generated events and the performance of our device

Marcus Amorim LEAL. Finalizadores e referências fracas: interagindo com o coletor de lixo. [Title in English:  Finalizers and weak references: interacting with the garbage collector] Ph.D. Thesis. Port. Presentation: 15/09/05 140 p. Advisor: Roberto Ierusalimschy.

Abstract: Most mainstream programming languages support finalizers and weak references. In spite of that, these abstractions are still modestly known by programmers in general. Even among language designers there seems to be no common view on how to define their semantics, and language implementations certainly reflect that. In this thesis we explore the concepts of finalizer and weak reference by discussing several important issues that, as far as we know, have not been explored by other authors. After presenting a survey on how finalizers and weak references are supported by actual programming languages, we thoroughly examine their semantics and discuss alternative implementation strategies. We also use an operational approach to develop a formal model for reasoning about garbage collection and its interaction with client programs. By explicitly representing low-level details, such as heap memory and its addresses, we were able to clearly specify memory management actions, and prove several important memory-related language invariants. Using this model we describe a formal semantics for finalizers and weak references, exploring some of its many subtleties. We believe that the topics covered here can serve as a relevant reference for further investigations, and also help to guide actual implementations.

Mark Stroetzel GLASBERG. ActivePresentation: Um Sistema para apresentações distribuídas em ambientes de computação ubíqua. [Title in English: ActivePresentation: a system for distributed multimedia presentations in ubiquitous computing environments]  M.Sc. Diss. Port. Presentation: 09/11/05     p. Advisor: Renato Fontoura de Gusmão Cerqueira.

Abstract: The diminishing costs and the diversity of computational devices are creating increasingly complex and sophisticated computational environments. Nonetheless, such environments still lack integration software to simplify their use and to better explore their potential. In response to this issue, ubiquitous computing systems are being developed to create remote control mechanisms of applications and devices. At the same time, research groups in the area of multimedia deal with other issues, such as synchronization between devices, resource management and document standard definitions. The purpose of this work is to join the e orts of both areas in order to build presentations using the ubiquitous computing paradigm. In this work, we introduce the ActivePresentation infrastructure, based and developed through the study of di erent prototypes. In addition, we propose a multimedia document format called NCLua to orchestrate such presentations.

Michel Alain QUINTANA TRUYENQUE. Uma aplicação da visão computacional que utiliza gestos da mão para interagir com o computador
. [Title in English: A computer vision application for hand-gestures human computer interaction] M.Sc. Diss. Port. Presentation: 28/03/05  100 p. Advisor: Marcelo Gattass.

Abstract: Computer Vision can be used to capture gestures and create more intuitive and faster devices to interact with computers. Current commercial gesture-based interaction devices make use of expensive equipment (tracking devices, gloves, special cameras, etc.) and special environments that make the dissemination of such devices to the general public difficult. This work presents a study on the feasibility of using Web cameras as interaction devices based on hand-gestures. In our study, we consider that the hand is clean, that is, it has no (mechanical, magnetic or optical) device. We also consider that the environment where the interaction takes place has the characteristics of a normal working place, that is, without special lights or backgrounds. In order to evaluate the feasibility of such interaction mechanism, we have developed some prototypes of interaction devices. In these prototypes, hand gestures and the position of fingers were used to simulate some mouse and keyboard functions, such as selecting states and objects, and defining directions and positions. Based on these prototypes, we present some conclusions and suggestions for future works.

Patrícia Seefelder de ASSIS. Arquitetura para adaptação e meta-adaptação de sistemas hipermídia. [Title in English: An Architecture for adaptation and meta-adaptation in hypermedia systems]  Ph.D. Thesis. Port. Presentation: 12/08/05 130 p. Advisor: Daniel Schwabe

Abstract: This dissertation defines an architecture for adaptation and meta-adaptation in hypermedia systems, using models proposed for the Semantic Web. Adaptative application are able to alter some of their characteristics, such as its navigation model or presentation model, according to the adaptation context. This context may include information about the user, such as her preferences, navigation history, etc., and about the execution environment, such as access device, bandwidth, etc. Meta-adaptive applications are able to alter both its models and its adaptation process according to the adaptation context. The proposal extends the SHDM model with a context model, adaptation rules and execution  architecture. It is shown, by comparison, that the major adaptation models described in the literature can be seen as particular cases of the proposed model and architecture.

Paulo Roberto de Oliveira BASTOS JUNIOR. Elicitação de requisitos de software através da utilização de questionários. [Title in English: Software requirements elicitation through the use of questionnaires] M.Sc. Diss. Port. Presentation: 26/04/05 88 p. Advisor: Julio Cesar Sampaio do Prado Leite.

Abstract: Questionnaire is one of the techniques available for requirements elicitation. A questionnaire is a document used to guide one or more people to answer one or more questions. The elaboration of a questionnaire is a process more complex than it can make look like. A questionnaire that is not well formulated can lead to unreliable information and may be harmful to the project in question. Although there is no standard method for the construction of questionnaires, there are recommendations from diverse authors with regard to this important task in the process of eliciting information. The work presented here details a technique for identifying the necessary and common stages for the creation of a questionnaire. A method for the construction of questions is proposed, which uses as base a list of requirements for the construction of quality questionnaires, obtained from the literature in the areas of social sciences and marketing. A tool for the elicitation of software requirements, by means of
questionnaires is presented.

Reinaldo Xavier de MELLO. Um modelo de escalonamento colaborativo de eventos baseado em corrotinas. [Title in English: A collaborative model for event scheduling using coroutines]  M.Sc. Diss. Port. Presentation: 14/09/05 64 p. Advisor: Renato Fontoura de Gusmão Cerqueira

Abstract: Event oriented systems are becoming present on many domains of applications. Distributed systems and graphical interactive systems are classical examples of environments that adapt well to the concept of event oriented programming. There are also emerging scenarios like cellphone runtime environments.  Despite the growing presence on the computational systems, some challenges still remain, like efficient method dispatch models and the management of concurrent processing of the event handlers. This work propose a model for an event scheduler using collaborative routines. We introduce a study on some mainstream scheduler models and propose a model where the scheduler holds the responsibility to encapsulate the complexity of managing multiple lines of execution, minimizing the CPU time wasted with blocking methods.  The coroutine model allows the management of these multiple lines of execution using a general control abstraction, which allows seamless context switching during the multiple suspending and
resuming of the routine. Also, without preemption, there is no overhead due to access control of the shared resources. The proposed model is tested on two different scenarios: one programming framework designed to be run on mobile phones, a fully asynchronous environment with low processing power and severe memory constraints; and a CORBA middleware written in LUA, where the communication between distributed objects is based on the remote procedure call model.

Richard Werneck de CARVALHO. Um ambiente de suporte para uma linguagem de modelagem de sistemas multi-agentes. [Title in English: An environment of support for a modeling language of multi-agents systems] M.Sc. Diss. Port. Presentation: 11/03/05   155 p. Advisor: Carlos José Pereira de Lucena.

Abstract: This work considers the creation of an environment that gives computational support to the development of multi-agents systems, assisting the developer during the cycle of life of construction (the modeling to the implementation) of these systems. We will be using ANote as modeling language for specification and analysis of multi-agents systems and the architecture ASYNC for the development process. Thus occurring, a transformation of the diagrams of ANote for architecture ASYNC.

Rodrigo de Barros
PAES. Regulando a interação de agentes em sistemas abertos - uma abordagem de leis. [Title in English: Regulating agent's interaction - a law enforcement approach] M.Sc. Diss. Port. Presentation: 18/03/05  119 p. Advisor: Carlos José Pereira de Lucena and Paulo Sérgio Conceição Alencar.

In this work, we propose an approach for regulating agents’ interaction on an open multi-agent system. In open systems, agents are immersed in a highly unpredictable environment, they can be self-interested, and other agents are frequently unknown beforehand. We argue that, in some applications, unexpected behavior may lead to system faults. For this reason, we propose a law enforcement approach to build open multi-agent systems where a certain degree of control over agents’ behavior is desirable. A conceptual model is proposed to specify how the interactions of an open multi-agent system should happen. This model deals with concepts such as norms, constraints and scenes in a integrated way. We also propose a declarative language that allows the interaction’s specification according to the elements that compose the conceptual model, and a software infrastructure that acts as a mediator monitoring and enforcing agents’ interaction.

Rodrigo de Proença Gomes HERMANN. Controle automático de câmera em ambientes virtuais dinâmicos. [Title in English: Automatic camera control in virtual dynamic environments] M.Sc. Diss. Port. Presentation: 13/09/05 54 p. Advisor: Waldemar Celes Filho.

Abstract: With the evolution in graphics processing power and the popularization of electronic games, new forms of entertainment, such as being a game spectator. The requirements for positioning the camera for the spectators to view the games are different from those applied to players. The camera for the players must fulfill playability requirements, while the camera for the spectators must explore different viewing angles in order to increase the immersion in the game environment and to explore the thrill of the scenes. The cinema has evolved a whole cinematographic language that optimizes the scene interpretation. Recent research has been seeking to apply cinematography to game visualization. The main challenge in the adaptation of the cinematographic language for games lies in the existence of a dynamic environment in which the story's progress cannot be anticipated. Three modules can be identified to adopt the cinematographic language in games: screenwriter, responsible for identifying what is happening  in the scene; director/editor, responsible for defining the best takes to capture the scene; and cinematographer, responsible for positioning the camera in the dynamic environment to better comply with the director/editor's demands. The present work proposes the implementation of a cinematographer module. Based on camera position requirements obtained from an external module, we propose a camera model that automatically positions the camera. The positioning requirements are expressed by a set of constraints that must be respected by the camera model. The camera uses a physical model based on a particle system oriented by Verlet's method, and employs the relaxation method to obtain the system's convergence in order to comply with imposed constraints. Computational experiments have demonstrated the capacity of the proposed module to comply with sophisticated camera positioning rules based on compositions of simple constraints. Cinematography principles such as framing , camera position and movement, and respecting the line of action are easily accomplished by the  proposed module.

Rodrigo de Souza Lima ESPINHA. Visualização volumétrica interativa de malhas não-estruturadas utilizando placas gráficas programáveis. [Title in English: Interactive volume visualization of unstructured meshes using programmable graphics cards] M.Sc.Diss. Port. Presentation: 18/03/05  86 p. Advisor: Waldemar Celes Filho.

Abstract: Volume visualization is an important technique for the exploration of threedimensional complex data sets, such as the results of numerical analysis using the finite elements method. The efficient application of this technique to unstructured meshes has been an important area of research in the past few years. There are two basic methods to visualize volumetric data: surface extraction and direct volume rendering. In the first, the iso-surfaces of the scalar field are explicitly extracted. In the second, which is the one used in this work, scalar data are classified by a transfer function, which maps the scalar values to color and opacity, to be visualized. With the evolution of personal computer graphics cards (GPU), new techniques for volume visualization have been developed. The new algorithms take advantage of modern programmable graphics cards, whose processing power increases at a faster rate than the one observed in conventional processors (CPU). This work evaluates and compares two GPU- based algorithms for volume visualization of unstructured meshes: view- independent cell projection (VICP) and ray-tracing. In addition, two adaptations of the studied algorithms are proposed. For the cell projection algorithm, we propose a GPU data structure in order to eliminate the high costs of the CPU to GPU data transfer. For the raytracing algorithm, we propose to integrate the transfer function in the GPU, which increases the quality of the generated image and allows to interactively change the transfer function

Rodrigo Prestes MACHADO. Um serviço de matchmaking de interesses dependentes de localização. [Title in English: A service for matchmaking of location-dependent interests] M.Sc. Diss. Port. Presentation: 19/05/05  93 p. Advisors: Carlos José Pereira de Lucena and Markus Endler.

Abstract: This work presents a matchmaking service (MMS) to enable meetings among co-localized people sharing similar interests. To make possible meetings and collaborations, the MMS analyses profiles of co-localized users using mobile devices, and indicates which users have a high degree of similarity among their profiles. The profiles are described using ontologies in OWL format (web ontology language), where the subjects of interest may be related with symbolic regions. The information about localization is obtained through interactions of MMS with a location service (Location Inference Service - LIS) present in MoCA architecture (Mobile Collaboration Architecture). The MMS service is built in a client/ Server architecture. The MMS provides the matchmaking service in two modes: synchronous and asynchronous. The synchronous mode allows users to request MMS to find people with similar interest in the same location. The asynchronous mode allows users to subscribe to the MMS service to receive automatic notifications when the MMS finds people in the neighborhood with similar interests. The MMS client provides access to the service and allows edition of users' profiles of interest for each localization.

Romualdo Monteiro de Resende COSTA. Integração e interoperabilidade de documentos MPEG-4 e NCL. [Title in English: Integration and interoperability of MPEG-4 and NCL documents] M.Sc. Diss. Port. Presentation: 06/04/05  180 p. Advisor: Luiz Fernando Gomes Soares.

Abstract: The MPEG-4 standard object-oriented approach, employed to the encoding of audiovisual content, is similar to those used on many models and languages for multimedia/hypermedia document specification. Among those languages, the NCL (Nested Context Language), used in the HyperProp system, introduces a series of new concepts that can be integrated to the standard, with advantages.  Initially, the proposal of this work is to convert NCL to MPEG-4 (XMT-O) documents and vice versa, allowing authoring and formatting tools to be used in the specification and presentation of documents in both languages. This work also proposes both the placing of MPEG-4 scenes as media objects and NCL language compositions, allowing the establishment of relationships among scenes. In order to allow displaying these new NCL objects, an MPEG-4 player is incorporated to the HyperProp Formatter. The MPEG-4 player is able to report to the controller the occurrence of events that, among other things, allows the synchronization between MPEG-4 scenes and othe r NCL objects, including other MPEG-4 scenes.  Finally, exploring the concept of templates, introduced by the NCL language, the authoring in the MPEG-4 is improved, by means of the definition of new semantics for XMT-O language compositions and the design of compilers for this language.

Sean Wolfgand Matsui SIQUEIRA. EDUCO - modelando conteúdo educacional. [Title in English: EDUCO: modelling educational content] Ph.D Thesis. Port. Presentation: 14/03/05  138 p. Advisor: Rubens Nascimento Melo and Maria Helena Lima Baptista Braz.

Abstract: In e-learning, the development of multimedia educational content material has been a success factor. However, as these processes are expensive and timeconsuming, there is a need for making the content reuse easier and institutions are establishing partnerships in order to share content and services. In this context, Learning Objects (LO) and standard metadata have been grown in acceptance. In spite of this, several developers have found it difficult to use and reuse LOs. Then there is still a need for providing mechanisms that promote LO reuse. The current trend is on making these LO even smaller, structured according to a hierarchy of interconnected nodes. Some recent approaches are based on the use of topic maps, ontology and knowledge bases in order to work with the content that are embedded into the educational material. This thesis presents a model for structuring and representing this content according to the involved information and conceptual unities. In addition, we also present an architecture that allows the different semantic levels of information to be considered in an e-learning environment. This architecture is based on related work on data integration and it establishes a context for the proposed modeling approach for representing educational content and therefore contributes for its acceptance and use by the e-learning community.

Sebastian Alberto URRUTIA.
Otimização em esportes: programação de tabelas e problemas de classificação. [Title in English: Optimization in sports: timetabling and qualification problems]  Ph.D. Thesis. Port. Presentation: 20/10/05  93 p. Advisor: Celso da Cruz Carneiro Ribeiro.

Abstract: Sports management is a very attractive and not very explored area for applications of Operations Research. Problems in this area use to have simple formulations and reach a big coverage by the media. Although their formulations are simple, in general these problems are difficult to be solved in computational terms. The results of many academic works in this area have been accepted as solutions for real problems and some solutions are being implemented. This thesis has the main objective of studying two types of problems that appear in the sports area: the fixture creation and the qualification problems. Fixture creation (also known as sport scheduling) for sport competitions is a difficult task, in which several combinatorial optimization techniques has been applied. In this thesis, the Mirrored Traveling Tournament Problem is formulated as a graph optimization problem. The problem is solved using approximation algorithms. Two heuristics are introduced for this problem. The first one is very fast and is used to supply initial solutions for the second one which is able to obtain high quality solutions in reasonable computation times. Dual limits are deduced for a particular type of instances. These limits allow to prove the optimality of the heuristically obtained solutions for instances that are much bigger than those solved in the literature. Finally, an integer programming model is introduced in which valid inequalities are added. The qualification problems aim to obtain necessary and sufficient conditions for the playoffs qualification of a given team in terms of the number of points to be obtained.  Integer programming models are introduced which allow solving these problems in the context of the Brazilian Football Championship.


Sérgio Alves CAVENDISH.
Algoritmos de ajuste elástico para vídeo em fluxos MPEG-2. [Title in English: Elastic time algorithms for video in MPEG-2 Flows]  M.Sc. Diss. Port. Presentation: 08/11/05     p. Advisor: Luiz Fernando Gomes Soares.

In hypermedia presentations, one of the main tasks provided by the orchestrator is the synchronization of all presentation objects, which may be achieved by elastic time adjustment of period of exhibition of the objects, or simply timescale adaptation. This technique can be applied at compilation time, in order to keep track of synchronism relationships specified by authors, or at presentation time, to prevent any temporal mismatch caused by transmission or execution environments. This work presents a set of mechanisms to carry out timescale adaptation in MPEG-2 Systems and Video streams, proposing algorithms to perform compression and expansion of exhibition period, also called playback dilation, rate control, inter-media synchronization and clock reconstruction. In order to be performed at execution time, timescale operations are realized directly in compressed MPEG-2 streams, requiring no transcodification.

Sérgio Mateo BADIOLA. Integração de suporte para geração de carga dinâmica ao ambiente de desenvolvimento SAMBA. [Title in English: Support integration of dynamic workload generation to SAMBA framework] M.Sc. Diss. Port. Presentation: 04/02/05 93 p. Advisor: Noemi de La Rocque Rodriguez.

Abstract: Alexandre Plastino's thesis presents a framework for the development of SPMD parallel applications, named SAMBA, that enables the generation of different versions of a parallel application by incorporating different load balancing algorithms from an internal library. This dissertation presents a dynamic workload generation's tool, integrated to SAMBA, that affords to create, at execution time, different external workload profiles to be applied over a parallel application in study. The objective is to enable that a parallel application developer selects the most appropriated load balancing algorithm based in its performance under variable conditions of external workload. In order to validate this integration, two SPMD applications were implemented.

Simone Leal de MOURA. Uma arquitetura para integração de repositórios de objetos de aprendizagem baseada em mediadores e servicos Web. [Title in English: An architecture based on mediators and Web services for integrating learning object repositories]  M.Sc. Diss. Port. Presentation: 19/08/05 157 p. Advisors: Rubens Nascimento Melo and Sean Wolfgand Matsui Siqueira.

Abstract: In web-based education there is an emphasis on reusing and sharing instructional content due to the complexity of the development process of high-quality learning materials. It leads to the learning  objects orientation as well as to partherships among institutions to promote sharing of these objects. In order to contribute to these efforts, we propose an architecture based on the mediators and wrappers for integrating learning objects repositories. The components of this architecture were implemented by the use of web-services and the integration processes were enriched by ontologies.  The use of mediators allows a query to be redefined as sub-queries that are distributed to the data sources and the results to be integrated. The wrappers allow the data sources to understand the sub-queries and the mediator to understand the respective answers. The implementation of the architecture components as web services allows more flexibility and interoperability among the participants of the community. The formalism of ontologies is used to deal with the semantic heterogeneity as the metadata concepts of each repository are described and the equivalences are established. The development of this architecture is called LORIS, an integration system of learning objects' repositoires.  LORIS is beings adopted by PGL, an international parthership project for promoting web-based education.

Tatiana Almeida Souza Coelho VIEIRA. Execução flexível de workflows. [Title in English: Flexible workflow execution]  Ph.D. Thesis. Port. Presentation: 11/08/05 429 p. Advisor: Marco Antonio Casanova.

Abstract: Workflow management systems usually interpret a workflow definition rigidly, allowing no derivations during execution. However, there are real life situations where users should be allowed to deviate from the prescribed static workflow definition for various reasons, including lack of information about parameter values and unavailability of the required resources. To flexiblilize workflow execution, this thesis proposes an exception handling mechanism that allows the execution to proceed when otherwise it would have been stopped. The proposal is introduced as a set of extensions to OWL-S, the language adopted to define workflows, and is based on process and resource ontologies that capture the semantic information needed for the flexibilization mechanism. The thesis also defines an operational semantics for a fragment of OWL-S and the proposed extensions, as well as a distributed architecture for a workflow management system. In particular, the semantics define a form of transactional behavior for the execution of a workflow instance, in the sense that it guarantees that either all actions executed by the instance terminate correctly or they are all abandoned.

Télvio Martins de MELLO. Uma biblioteca para criação de máquinas virtuais baseadas em processadores de rede. [Title in English: A library for the creation of network-processors-based virtual machines] M.Sc. Diss. Port. Presentation: 28/03/05  104 p. Advisor: Sérgio Colcher.

Abstract: The aim of this work is to study, propose and implement a tool that allows the experimentation with architectures that follow the Network Processors (NP) paradigm. A generic object library was implemented, allowing the emulation of the various hardware components, such as memories, registers, arithmetic-and-logical units, control units etc., that are commonly used within specific architectures for protocol processing. The integrated usage of these components will provide an environment where virtual machines can be created and tested to verify the behavior of many different operations. Besides the library itself, three use cases are presented to validate and show the utility of the tool: the first is an implementation of a processor created just for the sake of testing and the other two are implementations of architectures based on the MCS85 processor and on the ARM kernel of the Intel IXP Network Processor.