Theses and Dissertations

2008

ABSTRACTS

Departamento 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, Pontifícia Universidade Católica do Janeiro - PUC-Rio, Brazil, in 2008.  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 bib-di@inf.puc-rio.br

Last update: 14/AUGUST/2009
 

INDEX

[08_MSc_araujo]
Aletéia Patrícia Favacho de ARAÚJO. Paralelização autonômica de metaheurísticas em ambientes de grid. [Title in English: Autonomic paralelization of metaheuristics in computational grids] M.Sc. Diss. Port. Presentation: 07/04/08. 177 p. Advisors: Celso da Cruz Carneiro Ribeiro, Eugene Francis Vinod Rebello and Maria Cristina Silva Boeres.

Abstract: The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheuristic should be seen as an application. For this, the autonomic metaheuristic should be seen as an application on two independent levels: middleware and strategy. The middleware is responsible for managing the entire execution environment, according to the characteristics of the application. The distributed hierarchical strategy enables the cooperation between all processes involved, without degrating the performance of the application due to increased communication between processes. To validate this proposal, two parallel implementations of metaheuristics were developed, one for the mirrored traveling tournament problem and the other for the diameter constrained minimum spanning tree problem. For both problems, the developed implementations were tested in the grid Synergy environment, formed by machines located in three different cities in the state of Rio de Janeiro. The paralelizations improved, for several instances, the best known results in the literature.


[08_MSc_gazola]
Alexandre GAZOLA. Uma infra-estrutura de software para alinhamento de catálogos heterogêneos. [Title in English: Software infrastructure for catalog matching] M.Sc. Diss. Port. Presentation: 27/03/08. 87 p. Advisor: Marco Antonio Casanova.

Abstract: Most databases are independently designed and, therefore, are usually implemented using different conceptual schemas, which creates a context of syntactic, structural and semantic-level heterogeneity. Nevertheless, when a set of databases refers to a common domain, it may become necessary to integrate them into a single database, or to intermediate access to the databases in a transparent way. To deal with the heterogeneity problem, it becomes necessary to align the conceptual schemas. This process is usually carried out by domain specialists, and tends to be tedious and error-phone. This dissertation presents the CatalogMatcher, a software infrastructure for catalog matching. A catalog stores data about a set of objects from a specific domain, typically classified by some sort of taxonomy or thesaurus. The CatalogMatcher contains components that implement instance-based alignment strategies.


[08_MSc_duarte]
Alexandre Rocha DUARTE. Atribuição de árbitros em competições esportivas: algoritmos e aplicações mono e multi-critério. [Title in English: Referee assignment in sport tournaments: mono and multi-criterium algorithms and applications] M.Sc. Diss. Port. Presentation: 05/07/08. 130 p. Advisor: Celso da Cruz Carneiro Ribeiro.

Abstract: Optimization in sports is a field of increasing interest. Combinatorial optimazition techniques have been applied e.g. to game scheduling and playoff elimination. A problem that arises in competition management is the assignment. A problem that arises in competition management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address two mono-objective versions of a Referee Assignment Problem (RAP) common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the RAP, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions, based on the metaheuristics iterated local search. Numerical results on realistic instances are presented and discussed. This work also investigates the solution of a bi-objective version of the RAP, which combines both objective functions used in the mono-objective versions. Exact and heuristic approaches are proposed to solve this bi-objective version and its computational results are discused.


[08_MSc_skyrme]
Alexandre Rupert Arpini SKYRME. Um modelo alternativo para programação concorrente em Lua. [Title in English: An alternative model for concurrent programming in Lua] M.Sc. Diss. Port. Presentation: 28/02/08. 111 p. Advisor: Noemi de La Rocque Rodriguez.

Abstract: The popularization of multi-core processors and of technologies such as hyper-threading indicates a different approach to the evolution of processors. This new approach brings about an increased interest in concurrent programming and the exploration of parallelism in order to achieve better performance. However, concurrent programming models now in use are subject to recurring criticism, which stimulates the development of alternative proposals. This work presents a critical analysis of preemptive multithreading with shared memory, which is a widely used model for concurrent programming, and briefly summarizes some studies that deal with alternatives for concurrent programming. It then, proposes a model for concurent programming structured with the Lua programming language and describes its main characteristics and advantages. Finally, it presents the results of an evaluation of several aspects of a library developed to implement the proposed model.


[08_MSc_silvaneto]
Algemiro Augusto da SILVA NETO. Uma abordagem baseada em SPH para animação interativa de águas rasas em jogos. [Title in English: A SPH based approach to interactive animation of shallow-water on games] M.Sc. Diss. Port. Presentation: 05/12/08. 40 p. Advisor: Waldemar Celes Filho

Abstract: In this work is presented an approach to shallow-water animation on interactive applications based on a physic model. For the simulation, was employed a Lagrangian method known a Smoothed Particle Hydrodynamics (SPH). Based on the work of Muller et al. (Muller et al., 2003), which applied SPH in Computer Graphics, and on the work of Rodriguez-Paz (Rodriguez-Paz; Bonet, 2005) which proposes a variation of this method to shallow-water simulation on engineering applications, we have proposed a simple and efficient approach for shallow-water simulation on games under the influence of irregular terrains.


[08_MSc_araujo]
Ana Carolina Innecco Cantuária de ARAÚJO. Apoio ao design e à interpretação de modelos de interação humano-computador representados em MoLIC. [Title in English: Supporting the design and the interpretation of human-computer interaction diagrams represented in MoLIC] M.Sc. Diss. Port. Presentation: 26/03/08. 293 p. Advisor: Clarisse Sieckenius de Souza.

Abstract: Personal computer users frequently view an interactive computacional system as the user interface itself. Therefore, it's desirable that such interface be developed in a way they can understand what the system is for, what it allows their users to do and in which way, for whom it's made etc. Based on Semiotic Engineering, which is the theoretical foundation of this work, such isues are being conveyed to the users in a metamessage from the designer, communicated by its user interface, through conversations between the user and the designer - this one through his deputy at interaction time, the designer's deputy. Before the concrete user interface is developed, Semiotic Engineering proposes to model the user-system interaction as a dialogue. In this stage, the designer models all the possible ways he anticipates that the users will be able to accomplish their goals. For this stage, a modeling language called MoLIC (Modeling Language for Interaction as Conversation) was created in 2003 to represent the interaction as the possible conversations between the user and the designer. Although it has been proposed as an epistemic tool, until now MoLIC had not its epistemic features explored explicitly. This work aims to explore the epistemic value of MoLIC, supporting the designer's reflection through a set of questions that he moght ask for himself about the interaction representation, in order to accomplish two goals. The first one is to support the (re)design activity itself, by making explicit the consequences of the design decisions represented in MoLIC. The second one is to support the interpretation of the human-computer interaction represented in MoLIC, so that the designer or any other reader would be able to understand and explain MoLIC diagrams based on the conversation metaphor.


[08_MSc_marins]
André Luiz Almeida MARINS. Modelos conceituais para proveniência. [Title in English: Provenance conceptual models] M.Sc. Diss. Port. Presentation: 18/03/08. 189 p. Advisor: Marco Antonio Casanova.

Abstract: Information systems, developed for several economic segments, increasingly demand data traceability functionality. To endow information systems with such capacity, we depend on data provenance modeling. Provenance enables legal compliance, experiment validation, and quality control, among others. Provenance also helps identifying participants (determinants or immanents) like people, organizations, software agents among others, as well as their association with activities, events or processes. It can also be used to establish levels of trust for data transformations. This dissertation proposes a generic conceptual model for provenance, designed by aligning fragments of upper ontologies, international standards and broadly recognized projects. The contributions are in two directions: a provenance conceptual model - extensively documented - that facilitates interoperability and the application of a design methodology based on ontology alignment.


[08_MSc_costa]
Andrew Diniz da COSTA. Um sistema híbrido de diagnóstico e recomendação para sistemas multi-agentes. [Title in English: A hybrid diagnostic-recommendation approach for multi-agent systems] M.Sc. Diss. Port. Presentation: 03/09/08. 104 p. Advisors: Carlos José Pereira de Lucena and Viviane Torres da Silva

Abstract: Multi-agent systems are societies with autonomous and heterogeneous agents that can work together to achieve similar or different goals. Agents executing in such systems may not be able to achieve their goals due to failures during system execution. When an agent tries to achieve its desired goals, but faces failures during execution, it becomes important to understand why such failures occurred and what can be done to remedy the problem. The distributed, dynamic and nature of multi-agent systems calls for a new form of failure handling approach to address its unique requirements, which involves both diagnosing specific failures and recommending alternative plans for successful agent execution and goal attainment. We discuss solutions to the main challenges of creating a system that can perform diagnoses and provide recommendations about agent executions to support goal attainment, and propose a hybrid diagnostic-recommendation framework that provides support for methods to address such challenges. From the framework, instances of different domains can be created, such as, applications based on ubiquitous computing and different diagnoses and recommendations can be provided.

[08_PhD_milanesbarrientos]
Anolan Yamilé MILANÉS BARRIENTOS. Suporte de linguagens de programação para a migração heterogênea de computações. [Title in English: Language support for the heterogeneous migration of computations]. Ph.D. Thesis. Port. Presentation: 11/07/08. 97 p. Advisors: Noemi da La Roque Rodriquez and Roberto Ierusalimschy.

Abstract: The heterogeneous migration of computations allows computations to move between different platforms. It is a difficult procedure, that demands mechanisms for the capture and restoration of the state of the execution allowing for the identification of the structure of the computation and its data. This support, when offered, commonly appears in the form of ad-hoc solutions which are difficult to tailor or adapt to different needs. This thesis discusses the need for this support in current programming languages. This support must allow the implementation of different applications that can profit from the ability of capturing and restoring computations heterogeneously, like migration and persistence. To experiment with this idea, we extend the Lua programming language with an API that allows the programmer to reify the internal structures of execution into manipulable language entities, to explore the basic mechanisms a language should provide in order to support the implementation of different policies.

[08_PhD_costa]
Antonio de Padua Albuquerque OLIVEIRA. Engenharia de requisitos intencional: um método de elicitação, modelagem e análise de requisitos. [Title in English: Intentional requirements engineering: a method for requirements elicitation, modeling, and analysis]  Ph.D. Thesis. Port. Presentation: 27/03/08. 261 p. Advisors: Julio Cesar Sampaio do Prado Leite and Luiz Marcio Cysneiros.

Abstract: Nowadays, much more than in the past, it is known that the success of software projects depends critically on the requirements. Goal Oriented Requirements Engineering - GORE, for example i* Framework, says that requirements must represent the intentionality of large number of social actors, which can be people or systems. Several Multi-Agent Systems (MAS) methods mention goals elicitation but they do not provide details of how this is performed, they mainly focus on goals modeling. In this context, there is still a lack of methods to cover the goal elicitation process. Only after eliciting goals, requirements engineers will be able to deal properly with goal models. Typically, this is a difficult task to carry on since requirements engineers are not familiarized with the domain from the early stages of software development. And intentionality models, for example i* Framework, can be complex and incompreensible. This thesis proposes a method called ERI*c - "Engenharia de Requisitos IntenCional" which provides an inquire process that can identify goals and softgoals in a bottom-up and simple elicitation approach together with one solution to reduce the problem of scalability of i* models. The method ERi*c also includes heuristics for modeling specification and a diagnoses aproach in order to analyze i* models.


[08_MSc_bueno]
Ariane Moraes BUENO. Apoiando o designer de IHC na tomada de decisão sobre o design de interfaces extensíveis. [Title in English: Supporting the HCI designer's decision-making about the design of extensible user interfaces] M.Sc. Diss. Port. Presentation: 28/03/08. 196 p. Advisor: Simone Diniz Junqueira Barbosa.

Abstract: One of the major problems of software development is to pay attention to all soecific needs of each user in a domain. The proposal to use extensible applications tries to solve this problem. Extensible systems are developed so that they can be shaped by end-users, adding, modifying or removing functionalities, and so evolve in time. A research area related to extensible applications for domain expert users who are not programming professionals is that of End User Development - EUD. However, it is not found in the literature, research that specifically support the designer in making decisions about when it is interesting to extend the system and which part of it can be extended. The purpose of this work is to inform the designer about different extension opportunities related to the result of user
and task analysis. It presents a classification, based on Semiotic Engineering, which encompasses the investigated techniques and the extensible applications. Then, it identifies, in the user and task analysis questions, those related to the techniques described in this classification. Therefore, the designer can identify which approaches can be used in which situations to extend the system. To evaluate this proposal, we developed a case study to re-build an authoring tool for interactive multimedia programs called Composer. The study goal was to keep the application flexible and extensible without requiring from users too much knowledge about the application's underlying language - the NCL (Nested Context Language).


[08_MSc_schroeder]
Bruno SCHROEDER. A graph based theorem proving platform with strategies. [Title in Portuguese: Uma plataforma de demonstração de teoremas baseada em grafos] M.Sc. Diss. Port. Presentation: 13/08/08. 91 p. Advisor: Edward Hermann Haeusler.

Abstract: Proofs in logic can become very big and complex. For problem solving, and to teach logic, it is common the use of proof assistants. A general proof assistant should integrate tools to help users on specifying the logics, the formulas, the sets of rules, and the very strategy to perform (semi) automatic proof search. The Automatic Theorem Provers community is aware of some tools that were designed to fulfill these requirements. However, these tools do not take the (possibly) huge size of a proff. Recent works have pointed out that a good way to achieve shorter proofs is the use of graphs, instead of trees, to represent proofs. This dissertation describes and implements a graph-based virtual machne and a compiler for the production of graph-based theorem provers. Some case studies, standard as
well as graph-based theorem prover, are illustrated in order to validate the tool.


[08_MSc_augusto]
Carlos Eduardo Lara AUGUSTO. Uma infra-estrutura para a execução distribuída de componentes de software. [Title in English: An infrastructure for distributed execution of software components] M.Sc. Diss. Port. Presentation: 03/09/08. 109 p. Advisor: Renato Fontoura de Gusmão Cerqueira.

Abstract: Support infrastructures for component-based software systems usually include facilities for installation, execution and dynamic configuration of the system component's dependencies. Such facilities are specially important when those system components execute in a distributed environment. In this work, we investigate some of the problems that must be handled by runtime infrastructures for distributed systems based on software components. To perform such investigation, we developed a set of services for the OpenBus middleware, aiming to provide facilities for execution of distributed applications. To illustrate and evaluate the use of the developed services, we present some examples where the infrastructure is used for executing test scenarios of a distributed application.


[08_MSc_felicissimo]
Carolina Howard FELICISSIMO. An approach to operationalize regulative norms in multiagent systems. [Title  in Portuguese: Uma abordagem para operacionalizar normas regulativas em sistemas multiagentes] Ph.D. Thesis. Port. Presentation: 13/08/08. 170 p. Advisors: Carlos José Pereira de Lucena and Jean-Pierre Briot.

Abstract: A major challenge in the research of multiagent systems (MAS) is the design and implementation of open MAS in which norms can be effectively applied to their agents and easily managed. These tasks are arduous because norms are usually written for general purposes, hindering a more precise regulation. The motivation for this research came forth from the need to resolv this challenge, providing an approach applicable in open systems. In such systems, heterogeneity and autonomy rule out any assumption concerning the way third-party entities are implemented and behaved. A viable solution for regulation in open MAS should not be hard coded inside agents' original implementations and must allow, for some degree of precision and flexibility, to update data (e.g., norms) during
the system execution. In this thesis, our DynaCROM approach for dealing with norms in open MAS is presented. From the induvidual agents' perspective, DynaCROM is an information mechanism that makes application agents aware of the norms they are bound to at a given moment. From the system developers' perspective, DynaCROM is a methodology for the application and management of norms in open MAS so developers are able to embody abstract norms with domain values. Therefore, norms are contextualized in the application domain wherein they hold, facilitating regulation. Considering that a regulated MAS should have its norms enforced, the integration of DynaCROM with two distinct enforcement mechanisms is also presented. In summary, the result of this thesis is our DynaCROM approach, which operationalizes regulative norms in MAS.


[08_PhD_sant'anna]
Cláudio Nogueira de SANT'ANNA. Modularidade de software orientado a aspectos: uma abordagem de medição dirigida por interesses. [Title in English: On the modularity of aspect-oriented design: a concern-driven measurement approach] Ph.D. Thesis. Eng. Presentation: 11/04/08. 250 p. Advisors: Carlos José Pereira de Lucena and Alessando Fabricio Garcia.

Abstract:  Several modularity problems in software designs are related to the inadequate modularization of key broadly-scoped concerns, such as exception handling, distribution, and persistence. However, most of the current quantitative assessment approaches are not sensitive to concerns that drive the design, thereby leading to a number of shortcomings in the modularity evaluation process. Therefore, there is a need for measurement approaches that support a more effective identification of modularity anomalies related to crosscutting concerns. Also, this necessity becomes more apparent in an age that a number of different forms of design decompositions, such as aspect-oriented software development, are emerging. In this context, this thesis aims at investigating a novel approach for quantitative modularity assessment of software design by promoting the concept of concern as a measurement abstraction. Our concern-driven measurement approach encompasses a set of mechanisms for assessing software modularity from architectural to detailed design. The proposed concern-sensitive approach includes: (i) a suite of architectural metrics, (ii) a suite of detailed design metrics, (iii) a suite of design heuristic rules for supporting the interpretation of metrics in meaningful ways, and (iv) a tool, called COMET, that supports both concern-driven notation and measurement of architectural designs. We evaluated the usefulness of our concern-oriented measurement technique in a series of empirical studies, comparing the modularity of conventional and aspect-oriented software design.


[08_MSc_moises]
Cynthia Luiza Rigo MOISÉS. Fidedignidade em sistemas multi-agentes abertos: uma abordagem através de contratos. [Title in English: Dependability of open multi-agent system: a contract approach].  M.Sc. Diss. Port. Presentation: 20/06/08. 102 p. Advisor: Arndt von Staa and Jean-Pierre Briot.

Abstract: In this work, we propose a model for applying contracts in open multi-agent systems. The main idea in a multi-agent system is that an intelligent global behavior can be reached from the individual behavior of the agents. In this context, it is difficulty to guarantee that agents are correctly cooperating to reach the organization objectives in which they are inserted. The model considered in this work expands the contract concepts in components to open
multi-agent system. Contracts can be understood as a negotiation form between components, which entails obligations and benefits for both parties. However, when the subject is multi-agent systems, there are a few available literatures. This is explained because contracts for components, guided on object paradigm, are hard to be translated to the characteristics of the agents. Components have methods and well defined interfaces, while agents hide their internal structures and perhaps they present complex bahaviors. A framework was developed based on the conceptual model we are proposing. The result demostrates the viability of applying contracts for components to the open multi-agents environments. The main goal is to manage and to inquire the cooperation between agents, considering the agents roles in the organization and respecting the individual agent characteristics.


[08_PhD_brauner]
Daniela Francisco BRAUNER. Alinhamento de esquemas baseado em instâncias. [Title in English: Instance-based schema matching].  Ph.D. Thesis.  Port. Presentation: 09/06/08. 83 p. Advisor: Marco Antonio Casanova.

Abstract: A mediator is a software component that helps accessing data sources. With the advent of the Web, the design of mediators imposes important challenges, such as the ability of providing integrated access to independent and dynamic data sources and the ability of resolving the semantic heterogeneity between different data source schemas. To deal with these challenges, schema matching is a fundamental issue. In this thesis, matching approaches for classification schemas (thesauri) and conceptual schemas are proposed, using instances as evidences for the mappings. The proposed approaches are classified as adaptative and a priori, referring to, respectively, the discovery of the mappings in an incremental way or the definition of the mappings before the deployment of the mediator. Finally, experiments to validate and test the proposed approaches are presented.


[08_PhD_filippo]
Denise Del Re FILIPPO. Suporte a coordenação em sistemas colaborativos: uma pesquisa-ação com aprendizes e mediadores atuando em fóruns de discussão de um curso a distância. [Title in English: Coordination support in collaborative systems: action research with learners and mediators acting in discussion forums in a distance course] Ph.D. Thesis. Port. Presentation: 26/03/08. 281 p. Adivisor: Hugo Fuks.

Abstract: In this thesis tools for the coordination support of discussion forums in a distance course are investigated. The research is conducted from the point of view of collaborative learning and the 3C Collaboration Model and uses action research as a method. In a forum carried out as a collaborative activity, learning takes place mainly through the exchange of messages among learners, which demands coordination. Coordination in this thesis is understood as one of the 3 dimensions of collaboration as made evident in the 3C Model: communication, coordination and cooperation. The results of this thesis, which include data, analyzes, procedures, reflections and implementation of the services and functionalities investigated, were obtained in the course of 3 years of action research. In action research the researcher performs successive actions aiming at minimizing a specific problem in a real environment. In this thesis, the real environment is the Information Technologies Applied to Education course at PUC-Rio and the problem identified is a difficulty in the coordination of the course's forums. The action is the offering of support tools for coordination in the AulaNet, the web-based education and learning environment used in the course. The common characteristic of the tools investigated is the offering of information on the progress of the forum without the need to use the AulaNet's desktop web interface: with this objective, graphs, statistical data and notifications are presented through PDAs, cell-phones SMSs and pop-up windows in the desktop. An assessment of the tools is carried out every semester: through the evaluation of the use of the tools by learners and mediators, improvements or new tools are proposed for the following semester, in a cyclical process.


[08_PhD_mendonça]
Diogo Silveira MENDONCA. Análise probablística de semântica latente aplicada a sistemas de recomendação. M.Sc. Diss. Port. Presentation: 12/09/08. 69 p. Advisor: Ruy Luiz Milidiu

Abstract: Recommender systems are a constant research topic because of their large number of practical applications. There are many approaches to address these problems, one of the most widely used being collaborative filtering, in which in order to recommended an item to a user, data of other users' behaviors are employed. However, collaborative filtering algorithms do not always reach levels of precision required for the use in real applications. Within this context, the present work aims to evaluate the performance of the probabilistic latent semantic analysis (PLSA) applied to recommender systems. This model identifies groups of users with similar behaviors through latent attributes, allowing the use of these behavios in the recommendation. To check the effectiveness of the method, there were presented experiments with problems of both web ad recommending and film recommending. An improvement of 18,7% were found in the accuracy of the recommendation of ads on the web and we also found 3.7% of improvement in Root Mean Square Error over Means of Means baseline system for the Netflix corpus. Apart from the aforementioned experiments, the algorithm was implemented in a flexible and reusable way, allowing its adaptation to other problems with reduced effort. This implementation has been incorporated as a module of LearnAds, a framework for the recommendation of ads on the web.


[08_MSc_moraes]
Edson Andrade de MORAES. Utilização de uma estratégia para identificação de fontes de informação na fase de elicitação. [Title in English: Using an information source identification strategy in the elicitation step].  M.Sc. Diss. Port. Presentation: 09/05/08. 147 p. Advisor: Julio Cesar Sampaio do Prado Leite.

Abstract: This dissertation studies means to identify and select information sources to be used in the requirements elicitation phase. We used an information sources identification and selection strategy based on the modeling of a Universe of Discourse with the use of a graphical representation language and a classification technique of the sources which compose such Universe. The full process is done with the use of a software tool which supports the application of the method. The tool helps in the recording of elicited information sources and its consolidation,
besides aiding in the production of somo artifacts with a considerable rework reduction. A case study was carried out in a world problem in an energy company, with the aim of evaluating the gains obtained from the usage of a structured approach for the identification of information sources instead of the use of an ad-hoc approach.


[08_MSc_portilho]
Eduardo Pilla PORTILHO. Um estudo de técnicas para a adaptação de componentes de software em Java. [Title in English: A study of techniques for the adaptation of software components in Java]  M.Sc. Diss. Port. Presentation: 04/04/08. 97 p. Advisor: Renato Fontoura de Gusmão Cerqueira.

Abstract: Software systems will inevitably need to suffer modifications during its existence, in order to receive both error corrections and evolutionary changes that address new requirements. This kind of maintenance processes typically involves the interruption of the systems for an amount of time that varies with the complexity of the change and with the used technology. This interruption may be unacceptable in the case of applications that demand a high degree of availability. In this case, any modification must be made dynamically, without interrupting the application. In the case of distributed systems, this difficult is significantly increased due to the typical greater number of users and to the distribution of their modules. Replacement or addition of features dynamically in applications developed with the major middleware platforms, such as CORBA or RMI, is a fairly complex process, which requires both the replaced modules and those that interact with them to be interrupted until the new modules are available. Furthermore, the implementation of dynamic adaptation mechanisms that circumvent these limitations is beyond of the scope of most applications, due to its highly complex nature. We believe that the increasing demand for such mechanisms justifies that they should be offered as services on the middleware layer. In this disertation we evaluate the implementation of dynamic adaptation mechanisms in a component system developed using the Java programming language. These mechanisms should allow changing applications in a simple and structured way, without the need to interrupt its operation. We compare the developed solution with a similar solution developed using the Lua programming language, in order to evaluate the advantages and disadvantages presented by this two types of languages in the implementation of dynamically adaptable systems. We also evaluate the performance of the proposed solution.

[08_MSc_cirilo]
Elder José Reioli CIRILO. GenArch: uma ferramenta baseada em modelos para derivação de produtos de software. [Title in English: GenArch: a model-based product derivation tool] M.Sc. Diss. Port. Presentation: 11/04/08. 100 p. Advisors: Carlos José Pereira de Lucena and Uirá Kulesza.

Abstract: This work presents a model-based tool for product derivation, called GenArch, which aims to enable the mainstream software developer community to use the concepts and foundations of the SPL approach, whitout the need to understand complex concepts or models. The tool approach is build on top of model-diven development techniques. It is centered on the definition of three models (feature, implementation and configuration models), which enable the automatic instantiation of software product lines (SPL) or frameworks. A set of specific Java annotations are also defined to allow generating automatically many of the models, based on existing implementations elements of SPL architectures. The Eclipse platform, and EMF and openArchitectureWare technologies are used as the base for the implementation of the tool. The dissemination also presents a GenArch extension that addresses the new abstractions provided by the Spring and OSGi component models. Different kinds of customizations are provided by
this extension varying from fine-grained configuration of component properties to the automatic selection of components that will compose the final product. As part of the approach validation, the tool was used in the derivation of three case studies: (i) JUnit framework; (ii) a J2ME games SPL; (iii) a service oriented Web application. Several lessons learned and discussions resulting from the use of the tool also are described.


[08_MSc_guerra]
Fabio Wanderley GUERRA. Engenharia de estórias: um estudo sobre a geração e narração automática de estórias. [Title in English: Story engineering: a study of the automatic story generation and telling]. M.Sc. Diss. Port. Presentation: 28/03/08. 106 p. Advisor: Antonio L. Furtado.

Abstract: This dissertation investigates the problem of story telling and generation, whose increasingly recognized relevance is mostly due to the popularization of interactive media, such as digital TV and video-games. The work initiates with a state of the art survey, detailing the major story representation models and the most used methods in literary work production. The use of the term 'story engineering' was proposed to emphasize that story telling and generation should be viewed as an engineering process. The fundamental problem was divided into three subproblems. The first one is how to generate stories, the second is how to tell them to the public and the last is how to create, store and query the knowledge base used for story engineering. Finally, as a case study, a prototype capable of automatically generating and telling stories was designed and programmed. Generation is done by a planner, using the Hierarchical Task Network algorithm. Storytelling applies a natural language generation tool. The knowledge base is stored under the form of XML documents, and a tool was implemented simplify their preparation.


[08_MSc_portella]
Felipe Albuquerque PORTELLA. Um serviço de captura e acesso para espaços ativos. [Title in English: A capture and access service for active spaces] M.Sc. Diss. Port. Presentation: 11/04/08. 133 p. Advisor: Renato Fontoura de Gusmão Cerqueira.

Abstract: One of the areas of most evidence in Ubiquitous Computing is multimedia applications of Capture & Access (C&A). This kind of application allows the capture of a live experience, usually in smart rooms, for future access. In this way, the responsibility for recording the event is transferred to the computing infrastructure, allowing users to focus their attention in the comprehension and interpretation of the experience itself, without worrying about registering the information. The literature presents many software systems allowing the automatic generation of hypermedia documents as the result of an event capture, using the same documents as the basis for navigation and search of the archived content. Typically these C&A applications generate documents that offer only a timeline navigation of the captured event. This dissertation proposes a general C&A infrastructure, based on reusable and interchangeable services, which explores the features offered by the NCL language (standard language of the Brazilian Digital TV) to investigate new paradigms in C&A documents engineering. This is accomplished by structuring the generated documents in conceptual, navigation and presentation models. The NCL language is used to represent the synchronism between the different recorded media as well as to generate different ways to navigate and present the recorded content. These models of navigation and presentations are based on metadata provided by the user or automatically extracted from the recorded content.


[08_MSc_rochanetto]
Geraldo da Silva ROCHA NETTO. Escalonamento flexível de workflows com restrições temporais. [Title in English: Flexible workflow scheduling with temporal restrictions] M.Sc. Diss. Port. Presentation: 15/04/08. 75 p.  Advisor: Marco Antonio Casanova.

Abstract: Any realistic plan specification must take into account temporal and resource restrictions for actions. The classical approach for executing plans with restrictions works in two alternating phases. During the first phase, the set of actions that are ready to be executed is determined. In the second phase, temporal and resource restrictions are taken into account to generate a viable scheduling for the ready actions. This separation into two phases may lead to inefficiencies, when inconsistencies in the second phase force backtracking to the first phase.
This dissertation first proposes a plan model that incorporates a rich language to specify temporal restrictions. Then, it introduces a plan execution algorithm that integrates the two phases mentioned above, thereby reducing as much as possible the need for backtracking.


[08_MSc_moreira]
Gustavo Costa Gomes MOREIRA. Reconhecedor de objetivos em vídeos digitais para aplicações interativas. M.Sc. Diss. Port. Presentation: 22/08/08. 70 p. Advisor: Bruno Feijo

Abstract: Object detection and recognition are an important issue in the field of Computer Vision, where its accomplishment in both real time and low false positives rates has became the main goal various research works, including the ones related to new interactivity forms in Digital TV. This dissertation proposes a software system based on machine learning that allows an efficient training for new objects and performs their subsequent recognition in real time, for both static images and digital videos. The proposed system is based on the use of Haar features of the object, which require a low computation time for their calculation, and on the usage of a cascade of classifiers, which allows a quick discard of image areas that does not contain the desired object while having a low occurence of false positives. Through the use of image segmentation techniques, the system turns the search for objects into an extremely fast operation in high-resolution videos. Furthermore, through the use of parallelism techniques, one can simultaneously detect varoius objects without losing performance.


[08_MSc_nunes]
Ian Monteiro NUNES. Agrupamento de registros textuais baseado em similaridade entre textos. [Title in English: Clustering text structured data based on text similarity]  M.Sc. Diss. Port. Presentation: 04/04/08. 69 p. Advisor: Ruy Luiz Milidiú.

Abstract: This document reports our findings on a set text clustering experiments, where a wide variety of models and algorithms were applied. The objective of these experiments is to investigate which are the most feasible strategies to process large amounts of information in face of the growing demands on data quality in many fields. The process of deduplication was accelerated through the division of the data set into individual subsets of similar items. In the best case scenario, each subset contain all duplicates of each produced register, mitigating to zero the cluster's errors. It is established, although, a tolerance of 5% after the clustering process. The experiments show that the processing time is significantly lower, showing a 98.92% precision. The best accuracy/performance relation is achieved with the K-Means Algorithm using a trigram based model.

[08_MSc_silva]
Jordan Janeiro Lopes da SILVA. Um protocolo sensível ao contexto para adaptação coordenada de servicos de comunicação em redes sem fio. [Title in English: A context-aware protocol for coordinated adaptation of communication services in groups] M.Sc. Diss. Port. Presentation: 05/05/08. 96 p. Advisor: Markus Endler

Abstract: Research in mobile networks and pervasive computing has shown that dynamic adaptation and context-awareness are basic requirements for applications executing in such environments. Many of the works about context-awareness dynamic adaptation found in the literature use the device's context information to execute an adaptation only locally at the device. For distributed, context-aware applications composed of a group of portable devices (executing in a wireless network) sometimes it is necessary to perform a collective and coordinated adaptation at all the devices of the group, and where this adaptation depends on the global context of the group. This thesis presents Moratus, a protocol that processes the global context of a group and executes a unique adaptation of a communication service at all devices in the group in a coordinated way. This protocol also handles unplanned disconnections of group members during the adaptation ´process. Moratus in the central element of a middleware named SACS, which allows that such coordinated adaptation is performed transparently and without disruption for the distributed application based on this middleware.


[08_MSc_monteirofilho]
Jose Maria da Silva MONTEIRO FILHO. Uma abordagem nao-intrusiva para a manutenção automática do projeto físico de bancos de dados. Ph.D. Thesis. Port. Presentation: 09/10/08. 201 p. Adivisors: Sergio Lifschitz and Angelo Roncalli Alencar Brayner

Abstract: The physical design of a database plays a critical role in performance. There has been considerable work on automated physical design tuning for database systems. Existing solutions require offline invocations of the tuning
tool and depend on DBAs identifying representative workloads manually. However, in dynamic environments involving various ad-hoc queries it is difficult to identify potentially useful physical design in advance. Recently, a few initiatives present brief descriptions of prototypes that address some aspects of online physical tuning. Nevertheless, these references work in an intrusive manner and work only with a specific DBMS. In this work, we propose a non intrusive approach to automated and on-the-fly physical design problems, in order to speed up processing of subsequent queries. Specifically, we design algorithms that are always-on and continuously modify the current physical design, reacting to changes in the query workload. To prove the viability of the presented ideas, the proposed approach was instantiated to solve two major problems related to the database physical design: indexing and alternative data clusters automatic maintenance.


[08_MSc_dias]
Klessis Lopes DIAS. Um framework orientado a aspectos para monitoramento e análise de processos de negócio. [Title in English: An aspect-oriented framework for monitoring and analysing business process] M.Sc. Diss. Port. Presentation: 10/04/08. 68 p. Advisors: Carlos José Pereira de Lucena and Uirá Kulesza.

Abstract: Over the last years, many mechanisms and techniques to monitor web applications have been proposed, such as, mining of log files from web servers and insertion of monitoring code directly in web applications. The adoption of these techniques presents several limitations such as: obstacles to correlate information from different web requests and/or requires several intrusive changes in the code of existing web applications. This dissertation presents an aspect-oriented framework to monitoring and analysing business processes. Aspect-oriented technologies are used to implement crosscutting variabilities of monitoring of web business processes. The framework has been developed using Java and AspectJ programming languages. It was instantiated and validated through the development of two different web applications.


[08_MSc_nazareth]
Leandro dos Santos NAZARETH. Sistema para consultas sobre banco de dados relacional baseado em palavras-chave. [Title in English: System for keyword search in relational database]  M.Sc. Diss. Port. Presentation: 04/04/08. 110 p. Advisor: Marco Antonio Casanova.

Abstract: This dissertation describes a developed system that allows the creation and execution of searches from keywords in a relational database. The system receives any keywords and tries to create queries that can be executed in database. To perform this automatic generation of queries the system uses the information of the catalogue of the source database. The system allows to make queries in a database without the knowledge of a language queries, like SQL, and the model from the database.


[08_MSc_maciel]
Leonardo Sant'Anna Antunes MACIEL. Um estudo sobre instrumentação da máquina virtual de Lua para análise de desempenho. M.Sc. Diss. Port. Presentation: 24/09/08. 91 p. Advisor: Renato Fontoura de Gusmão Cerqueira

Abstract: Recently there has been a significant rise in the popularity of the so called dynamic languages. Today a myriad of such languages can be found on a wide range of applications, from Web programming, through game development, up to critical space missions. This phenomenon is partially due to high-level constructs that they offer to the programmer, such as powerful and flexible data structures, automatic memory management and dynamic typing, to name a few. However, the same abstractions that ease the development with such languages, also introduce costs often difficult to identify by application developers. Garbage collection is probably the best example of such an abstraction. While relieving the programmer from manual memory management, it also introduces a non-deterministic cost. For those reasons there has been an increasing interest in tools to support the process of performance analysis of programs written in such languages. This work aims to study techniques for instrumentation of virtual machines of dynamic languages. To accomplish this, we implemented a solution for the instrumentation of the virtual machine of the Lua language. Throughout this study we present some instrumentation techniques, then describe the design decisions and experience acquired during the development of this solution. Furthermore, we evaluate the performance impact and present some examples of use of the proposed solution. We conclude with a critical review of this work, as well as suggestions for future work.


[08_PhD_lorenzamoreno]
Lorenza Leão Oliveira MORENO. On routing problems with splittable demands. Ph.D. Thesis. Eng. Presentation: 15/09/08. 98 p. Adivisors: Marcus Vinicius Soledade Poggi de Aragão and Eduardo Uchoa Barboza

Abstract: This thesis is concerned with routing problems in which a client can be attended by more than one vehicle. These problems are particularly interesting because, by splitting demands, transportation costs can be reduced. At first, the thesis focuses on the most elementary version of such problems, the Split Delivery Vehicle Routing Problem (SDVRP). This problem has received much attention on the last few years. Most algorithms proposed are heuristics and the few exact approaches are able to solve only small instances with up to 23 vertices. This thesis introduces a new extended formulation for SDVRP and a branch-cut-and-price algorithm. Experiences have shown that the lower bounds provided by this new approach are superior than the previous ones. Besaides, some instances with 51 and 76 vertices were solved to optimality for the first time. The thesis also shows a real routing problem with splittable demands. This problem consists in planning flights of helicoptres to attend transport requests between continent and offshore
platforms. The problem is solved by a MIP based heuristic that uses column generation procedures. The resulting algorithm finds solutions that improve safety and reduce tansportation costs.


[08_MSc_afonso]
Luiz Marques AFONSO. Um estudo sobre contratos em sistemas de componentes de software. M.Sc. Diss. Port. Presentation: 10/09/08. 132 p. Advisor: Renato Fontoura Gusmao Cerqueira

Abstract: Contract-based programming is one of the techniques used to improve the quality of software by enhancing the formalism of interface specifications. In the context of distributed software components, the use of contracts presents new challenges that make it different from its traditional use. This work intends to evaluate the use of contracts in the development of component-based distributed systems, identifying the current approaches and analyzing its advantages and disadvantages. It also covers topics like robustness, performance, flexibility, ease of use and limitations. As a case study, s contract subsystem was developed over a CORBA middleware using Lua, serving as the basis for experiments in our study.
 

[08_PhD_moreno]
Marcelo Ferreira MORENO. Gerenciamento de recursos dirigido por modelos: adaptabilidade e interoperabilidade no suporte a QoS fim-a-fim. [Title in English: Model-driven resource management: adaptability and interoperability on end-to-end QoS support].  Ph.D. Thesis. Port. Presentation: 08/04/08. 165 p. Advisor: Luiz Fernando Gomes Soares.

Abstract: The evoluation of codification techniques for continuous media is making distributed multimedia applications even more popular. This kind of application has performance requirements that must be met in an end-to-end fashion, which can be achieved only if quality-of-service (QoS) provisioning mechanisms are applied on each participant subsystem. These mechanisms try to provide some control on distributed resource sharing, but the heterogeneity of resources and platforms turns management into a very complex task. Uniformization of resource access plays a key role to solve the problem, as it provides platform-independent abstractions that can represent not only a given resource, but also the distribution of them. It is also important to consider the continuous evolution of applications,
which creates a demand for adptable mechanisms, and the participation of multiple actors, which creates a demand for cooperative environments for resource configuration and maintenance. This work proposes a technique for resource management with end-to-end QoS support called MDRM (model-driven resource management), inspired on MDSD's (model-driven software development) concepts and processes. Particulary, MDRM includes the specification of its own meta model, called Virtual Resource Trees (VRT), which provides the abstractions neede to address uniformization, interoperability, adaptability and cooperation requirements on building resource management models. Resource management models are instances of the meta model specified using a domain-specific language (DSL) called Pan. Pan is able to express the formalism of VRT as platform-independent code, proving an easy to learn notation for any actors possible present on general distributed environents. MDRM also considers the design of modeling environments composed of tools that help on validation, transformation and deployment of resource management models. The constructs of the Pan language allow the same tools to be used for maintenance of models already instantiated, and thus adaptation actions can be promptly propagated to concerned platforms. A framework for MDRM support on general-purpose operating systems is also presented to illustrate how the concepts of the VRT meta model must be mirrored internally in target platforms.


[08_MSc_molinaro]
Marco Serpa MOLINARO. Algoritmos aproximativos para o problema de atribuição de hotlinks e para busca binária em árvores. [Title in English: Improved approximations for the k-Hotlink assignment problem and for binary searching in trees]. M.Sc. Diss. Eng. Presentation: 28/03/08. 89 p. Advisor: Eduardo Sany Laber.

Abstract: Here we present a study on two optimization problems in trees: the k-Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follow. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned from each node, we prove the existence of an FPTAS, improving upon the constant factor algorithm recently obtained. In addition, we develop the first constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(long n)-approximation.


[08_MSc_silva]
Marcos Cesar da SILVA. Uma arquitetura de software para medição flexível de web services. M.Sc. Diss. Port. Presentation: 30/07/08. 98 p. Advisor: Marco Antonio Casanova. 

Abstract:  The Service Oriented Architecture (SOA) adoption has been enabling the raise of business networks in which each partner gets automatically the information needed to achieve maximum efficiency. When there is more than one partner providing the same service on a business network, comes the challenge of determining which one is best suited to receive a given request. This dissertation presents a software architecture and a prototype implementation that allows the definition of complex criteria to service mediation, based on both technical (availability, response time) and functional data (price, reputation, geographical location, etc.) Our goal is to explore the practical aspects of this mediation, the technologies used and the solution flexibility.


[08_PhD_machado]
Marcos de Carvalho MACHADO. Geração de malhas de falhas em dados sísmicos por aprendizado competitivo. [Title in English: Fault meshing generation in seismic data by competitive learning]. Ph.D. Thesis. Port. Presentation: 14/03/08. 203 p. Advisor: Marcelo Gattass.

Abstract: Manual fault mapping from 3D seismic data is a time-consuming task. A plethora of seismic attributes has been proposed to enhance the discontinuity measures associated with faults. However, faults viewed trhough these attributes appear more like trends than well-defined, continuous surface, posing obstacles to the automation of the fault modeling process. This thesis explores the use of Competitive Learming techniques in fault extraction and visualization. The proposed strategy starts with a pre-computed fault attribute and consists of three steps. In the first, the uniformly sampled 3D fault attribute data are converted into a graph using Growing Neural Gas, a Competitive Learning algorithm. In the second step, the graph is submitted to a segmentation process in order to extract a set of subgraphs, each one compatible with a fault surface. In the third step, the Open Neural Meshes algorithm is used to build a triangulated mesh for each previously identified surface. Open Neural Meshes is a Competitive Learning algorithm proposed in this thesis, which builds a mesh from a probability function with no-hole open surface topology. Examples with 2D and 3D, synthetic and real data are presented. Another Competitive Learning application introduced in this thesis is the generation of geologic meshes. These meshes can be used to simulate fluid flows in subsurface reservoirs.


[08_MSc_roenick]
Maria Claudia ROENICK. A implementação de um módulo HIP na ferramenta OMNeT++ para avaliação de desempenho de handoff. [Title in English: A HIP module implementation of in the OMNeT++ simulator for handoff performance evaluation].  M.Sc. Diss. Port. 287 p. Presentation: 10/04/08.  Advisor: Sérgio Colcher.

Abstract: In mobile IP networks, a connection of transport established with a mobile device may be interrupted due to a possible exchange of IP addresses caused by a change of network. The period between the moment when device realizes that the network is changing - time in which begins the process of changing its IP address - until the moment that it restores all connections with other devices is called period of handoff, and this period is called the latency of handoff . Some protocols specifications allow us to remain accessible while mobile move in IPv6 network, as the MIPv6 (Mobility for IPv6). But even with the use of MIPv6, during the handoff, exchanged packages with the mobile device could be delayed more than desired or even be lost. This effect diminish the quality of communication, especially when it is dealing with multimedia data. The focus of this work is the implementation of the Protocol Host Identity Protocol (HIP) in a tool for simulation to evaluate the protocol with the goal of establishing, quantitative way, the impact of disruption and restoration of communication in mobile environments. The proposed protocol ensures the mobility using a new identity for the hosts that is independent IP address. The latency and loss of packages are studied, by simulation, during the handoff of HIP protocol in order to justify further investigation.


[08_MSc_ferreira]
Maurício Azevedo Lage FERREIRA. Vigilância e monitoramento em tempo real de veículos em rodovias com câmeras não-calibradas. [Title in English: Surveillance and monitoring of vehicles in real time at highways with non-calibrated cameras].  M.Sc. Diss. Port. Presentation: 20/06/08. 69 p.   Advisor: Marcelo Gattass.

Abstract: Abstract: Vehicle surveillance computerized systems have grown great interest due to the automatizing duties demand, which recently executed by computer vision like shadows, occlusion and light variation have to be solved. The present work proposes real time algorithms for low cost machines focused on tracking, classifying and
determining each vehicle's speed on a highway.
.


[08_MSc_elias]
Pablo Carneiro ELIAS. Calibração e posicionamento de câmera utilizando fotos e modelos de edificações. [Title in English: Camera Calibration and Positioning Using Photographs and Models of Buildings]. M.Sc. Diss. Port. Presentation: 28/04/08. 103 p. Advisor: Marcelo Gattass.

Abstract: Camera reconstruction is one of the major problems in computer vision. Software systems in that field uses mathematical camera models, or virtual cameras, for example, to interpret and reconstruct the tridimensional structure of a real scene from a set of digital pictures or videos or to produce synthetic images with realistic looking. Computer vision technics are applied together with virtual reality technics in order to originate new types of applications called augmented reality applications, which use virtual cameras to combine both real and synthetic images within a single digital image. Among the many uses of these types of applications, this work has particular interest in those concerning augmented visits to buildings. In these cases, pictures of buildings - typically old structures os ruins - are reconstructed from virtual models that are inserted into such pictures allowing one to have the vision of how those buildings were on they original appearance. Within this context, this work proposes a semi-automatic and efficient method to perform such reconstructions and to register virtual cameras from real pictures and models of buildings, allowing comparing them through direct superposing and making possible to navigate in a tridimensional fashion between the many registered pictures. Such method requires user interaction, but it is designed to be simple and productive.


[08_MSc_cunha]
Pedro de Moura CUNHA. Planejamento tático no transporte rodoviário de cargas fracionadas: modelos e algoritmos. [Title in English: Tactical less-than-truckload transportation planning: models and algorithms]. M.Sc. Diss. Port. Presentation: 14/04/08. 79 p.  Advisor: Marcus Vinicius Soledade Poggi de Aragão.

Abstract: Less-than-truckload transportation problems are great candidates for the application of optimization techniques as a form to obtain a better exploitation of resources. This thesis introduces integer programming models and the developed algorithms for the proper resolution of the studied problems in this context. The focal point is the vehicle's dislocation planning for the ideal attendance of the demands during a certain time period. Different forms of vehicle contract are considered. There are time windows for the attendances and demands can share a same vehicle in one or more parts of its route until his destination. Connections are allowed, that is demands can use more than one vehicle for its attendance, respecting the operational capacities of the centers (collection and distribution stations). The goals embraces the sizing of the proper fleet which has a fixed cost, and the operation's planning during the period. This one should determine which demands are transported by which vehicles in what instants and where on routes. The resolution's method proposed uses algorithms for the graph's construction and pre-processing which represents the problem and allows that the formulation, as an integer program, to have a resolution more efficient. Furthermore, the corresponding algorithm solves a sequence of integer programs to obtain feasible quality solutions
for the differents versions of the considered problem. Improvements on the lower bounds gotten are also proposed. The resulting code was tested in a set of proposed instances that were based on the operation of an important brazilian trucking company. Results were acquired such for conditions of real utilization, in other words, with a limited time of execution, as to test the limits of the proposed method. In both cases, solutions of comproved high quality were obtained.


[08_MSc_rocha]
Rafael Machado da ROCHA. Um framework para simulação da negociação de servicos em redes sem fio de nova geração. [Title in English: A service negotiation simulation framework for next generation wireless networks]. M.Sc. Diss. Port. Presentation: 03/04/08 105 p. Advisor: Carlos Jose Pereira de Lucena

Abstract: The wireless communication networks are increasingly present in people's lives. Talking to friends, listening music, watching television, buying things, are examples of activities that nowadays can be accomplished by a great variety of wireless networks. Modern mobile devices have a diversity of network interfaces, for users to choose from. Due to mobility offered by mobile devices, different types and scenarios of networks appear at every new location. Some proposals and solutions are been studied to allow users to choose the best network connection for a specific service utilization, depending on the current user's task. But, few proposals are presented to allow network and service providers to provide these best connection. Mobility, user's freedom of choice, variety of network connections and types of service are challenges that the providers are beginning to find. Moreover, the ability to attract new customers, increase your services sales volume and its consequent market share, are opportunities that arise in this new scenario. A multi-agent systems framework is proposed with the aim to examine this new scenario and exercise solutions that are useful both for customers, and for wireless network providers. Context-Aware strategies for provider's service pricing and for customer's best choice of service provided are subject to review. In the solution, context information is represented in the ontology model proposed by DynaCIP and an algorithm for decision-making used by the agent is proposed, although the framework flexible the use of other algorithms. A framework instantiation for a next generation wireless networks scenario is implemented and discussed in the proposal.


[08_MSc_leal]
Ricardo Augusto Boiteux Mendes LEAL. Teste funcional baseado em modelos gramaticais. [Title in English: Grammar model-based functional test] M.Sc. Diss. Port. Presentation: 17/03/07. 132 p. Advisor: Arndt von Staa.

Abstract: Software functional test is a challenge faced by developers for a long time. The growing complexity of computing systems turns this challenge even greater. Model-based testing is a trend pointed out by the academia and the industry as a possible solution to this matter. Inspired by this paradigm, this dissertation depicts a research made on the use of grammars as functional test models. Grammar models can capture concepts and behaviors of a system and its environment at a level of abstraction according to the test goal. They also can be applied to describe functional test cases and guide the execution of the generated test cases against a system under test. The result of this execution, represented as a verdict, reveals the system conformity with its requirements and specifications. In order to explore grammar models potential, this work defined a systematic way to generate and execute a mass of tests. This solution allowed the implementation of different test strategies. It also assisted test adjustment to requirements change and promoted existing tests reuse. As a side-effect of this study, a functional test process was developed and the supporting architecture introduced here may be reused or extended by future functional test solutions.


[08_MSc_clemente]
Ricardo Gomes CLEMENTE. Uma arquitetura para processamento de eventos de log em tempo real. M.Sc. Diss. Port. Presentation: 21/08/2008. 77 p. Advisor: Marco Antonio Casanova.

Abstract: Logs are, nowadays, a rich source of information for system administrators and business analysts. In environments with a high access volume and hundreds of servers, to process every generated information and correlate it, in order to identify interesting technical and business situations in real time, is considered a challenge. Considering that, concepts related to log files and systems that aim to manage it, besides methods and tools for real time event correlation are presented, in order to propose a system architecture capable of overcoming the stated
challenge. At last, a prototype is developed and a concept prove based on a real case is done.


[08_MSc_clemente]
Ricardo Niederberger CABRAL. Um estudo de recomendadores baseados em conteúdo e redes sociais. M.Sc. Diss. Port. Presentation: 28/11/08. 90 p. Advisor: Daniel Schwabe.

Abstract: This dissertation offers two major contributions: (1) to evaluate the suitability of recommender algorithms for social networks. Such recommender algorithms may receive as input not only the social graph of these networks but also content-based data from recommended items. For such, the relevant characteristics of social networks and the most important recommender techniques for these tasks will be surveyed. Special attention is given to the web-based system for social photo-sharing called Flickr and to the employment of visual metrics for image similarity. The second contribution (2) is the construction of a framework for the modeling and analysis of social networks, as well as aiding the empirical study of recommender algorithms on these contexts. Also part of this framework are the best practices adopted throughout the work done on this dissertation, such as: techniques for the gathering, analysis and visualization of data; social networks classification; identification and modeling of recommending tasks within these
contexts; implementation of algorithms and their architecture. The relevance of such contributions lies on the enormous amount of information available online and on the ever-growing complexity of the relationships between this data. In this context, recommender systems may provide a great aid for end-user.

[08_PhD_coelho]
Roberta de Souza COELHO. Analyzing exception flows of aspect-oriented programs. [Title in Portuguese: Analisando o fluxo de exceções em programas orientados a aspectos] Ph.D. Thesis. Eng. Presentation: 11/06/08. 203 p. Advisors: Arndt von Staa and Awais Rashid.

Abstract: It has been empirically observed that aspect-oriented (AO) decompositions promote the modularity and the design stability of software systems containing crosscutting concerns. However, must of this exixting empirical research has focused on the positive and negative impacts of AO programming in the modularization of crosscutting concerns in the context "normal" control flow of programs. Consequently, most of these works do not account for the exceptions that may flow from aspect: when an aspect adds a new functionality to specific poinst in the code, this
additional behavior may also bring new exceptions. An aspect also has the ability to handle exceptions that were previously handled inside the base code. Moreover, the exceptions that escape form aspects also flow inside the program, and may lead tounexpected error-prone scenarios, such as: unintended handler actions and uncaught exceptions. This thesis presents an empirical study to evaluate the impact of aspects on the exception flow of programs. To support the reasoning about the flow of exceptions on AO programs, a static analysis tool called SAFE (Static Analysis for the Flow of Exceptions) was implemented. Based on data empirically collected during the study we characterized a catalogue of bug patterns related to the exceptions handling code of AO programs. To help AO developers to check the reliability of the exception handling code, this work presents verification approach - supported by the SAFE tool - which provides guidelines to counter these bug patterns. Our findings show that the exception handling code in aspect-oriented programs tends to be error-prone, but that a verification approach based on static
analysis can lead to significant improvements.

[08_MSc_cavalcante]
Roberto Pereira CAVALCANTE. Filtragem colaborativa aplicada à publicidade direcionada. [Title in English: Collaborative filtering applied to targeted advertising] M.Sc. Diss. Port. Presentation: 03/04/2008. 62 p. Advisor: Ruy Luiz Milidiú.

Abstract: The emergence of the World Wide Web represented a new advertising opportunity available to any company: the possibility of global exposure to a large audience at a very small cost. As a result, a whole new industry has emerged by offering services related to search advertising, in which an advertiser pays for a prominent position in lists of ads. In order to maintain the credibility and market share of the service that conveys them - for example, a search engine -, such ads must be displayed only to users who are interested in them, on what is called Targeted Advertising. Therefore, those services need to use a recommendation system that can choose which ads show to which users. Recommendation systems based on collaborative filtering use the preferences of other users as features to a learning system, since such preferences can be quite detailed, generating recommendations not only for the most popular items but also to item niches. In this work, we develop an ads recommendation system that applies Collaborative Filtering based on matrix factorization to the problem of predicting the Click-Through Rate, a Targeted Advertising metric that expresses the relevance of a particular ad for the users searching for a specific keyword. In order to validate the proposed method of Click-Through Rate prediction, we carry out several experiments on a synthetic data set. Additionally, the work contributes to the desig of LearnAds, a framework for ads recommendation systems based on Machine Learning.


[08_MSc_azevedo]
Sérgio Ciglione de AZEVEDO. MASSES (Sistema de Multi-Agente para Simulação de Negociações de Ações). M.Sc. Diss. Port. Presentation: 13/09/08. 60 p. Advisor: Carlos José Pereira de Lucena.

Abstract: Due to technological advancements in IT, access to information is becoming simpler and faster every day, thus facilitating the decision-making processes. These changes affect the behavior of all kinds of businesses and the society in general. In the economic scenario, Stock Exchange Market is a good example of this transformation and therefore was chosen as the application domain to be explored by a Multi-Agent System for Stock Exchange Simulation (MASSES). Inspired by success stories about Multi-Agent Systems applied to competitions, MASSES is a simulator where software agents play the role of investors. Through MASSES simulations, it is possible to perform studies among different strategies and its results can be analyzed to verify how they behave in different situations. MASSES main contribution is to encourage researchers to develop Software Engineering for Multi-Agents Systems using artificial intelligence techniques, thus strenghtening the relationship between information technology and the financial market. the present dissertation aims to explain MASSES, in addition to showing test results based on the investment strategies used in the real world.


[08_MSc_kolaric]
Sinisa KOLARIC. Manipulação espacial direta de objetos virtuais 3D usando rastreamento e reconhecimento de gestos da mão baseado em visão computacional. [Title in English: Towards direct spatial manipulation of virtual 3D objects using vision-based tracking and gesture recognition of unmarked hands]  M.Sc. Diss. Eng. Presentation: 28/03/2008.   120 p. Advisors: Marcelo Gattass and Alberto Barbosa Raposo.

Abstract: The need to perform spatial manipulations (like selection, translation, rotation, and scaling) of virtual 3D objects is common to many types of software applications, including computer-aided design (CAD), computer-aided modeling (CAM) and scientific and engineering visualization applications. In this work, a prototype application for manipulation of 3D virtual objects using free-hand 3D movements of bare (that is, unmarked, uninstrumented) hands, as well as using one-handed manipulation gestures, is demonstrated. The user moves his hands in the work volume situated immediately above the desktop, and the system effectively integrates both hands (their centroids) into the virtual environments corresponding to this work volume. The hands are being detected and their posture recognized
using the Viola-Jones detection method, and the hand posture recognition thus obtained is then used switching between manipulation modes. Full 3D tracking of up to two hands is obtained by a combination of 2D "flocks-of-KLT-features" tracking and 3D reconstruction based on stereo triangulation.


[08_MSc_ponte]
Thiago Costa PONTE. LuaCharm: um modelo híbrido utilizando linguagens de script para programação paralela. [Title in English: LuaCharm: A hybrid model using scripting languages for paralel programming]  M.Sc. Diss. Port. Presentation: 07/04/2008. 77 p. Advisor: Noemi da La Roque Rodriguez.

Abstract: Recently, scripting languages have become very important in many fields of computer science. One area in which these languages have not been explored is paralel programming. Paralel programming has always been strongly associated with scientific usage, but recently, with the growth in popularity of multi core systems, it has gained a new field of action. With this change, the development of new programming paradigms of paralel programming become necessary in order to make development easier and applications more dynamic. Scripting languages may be used
for this, bringing dynamics, flexibility and simplicity to applications. This dissertation aims to study a hybrid programming model with two programming languages, Charm++ and Lua.


[08_MSc_bastos]
Thiago de Almeida BASTOS. Campos de distância amostrados adaptativamente com aceleração por placa gráfica. [Title in English: GPU-accelerated adaptively sampled distance fields] M.Sc. Diss. Port. Presentation: 5/03/08.  70 p. Advisor: Waldemar Celes Filho.

Abstract: Shape representation is a fundamental problem in Computer Graphics. Among known representations for three-dimensional objects, adaptively sampled distance fields (ADFs) are noted for their versatility. ADFs combine the concepts of geometry with volume data, allow objects to be represented with arbitrary precision, and consolidate several operations - such as visualization, level-of-detail modeling, collision detection, proximity tests, morphing and boolean operations | into a single representation. This work proposes methods to accelerate the reconstruction of static ADFs, to improve the quality of reconstructed fields, and to visualize ADF isosurfaces, making use of the massive computational power found in modern graphics hardware (GPUs). In order to eciently represent ADFs on graphics cards, a hierarchical structure based on perfect spatial hashing is proposed. Rendering of ADFs is done completely on GPUs, using a ray casting technique based on sphere tracing. Means to overcome the C0 and C1 discontinuities inherent to ADFs are suggested in order to attain smoothly shaded iso-surfaces. Finally, a new reconstruction method for ADFs, which can better represent curved surfaces, is proposed. Results are presented through simple interactive visualization applications, with ADFs generated from both triangle meshes and primitive solids.


[08_PhD_noronha]
Thiago Ferreira NORONHA. Algoritmos para problemas de otimização aplicados a roteamento e atribuição de comprimentos de ondas. Ph.D. Thesis. Port. Presentation: 05/09/08 89 p. Advisors: Celso da Cruz Carneiro Ribeiro and
Carlos José Pereira de Lucena.

Abstract: The problem of routing and wavelength assignment in WDM optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lighpaths whose routes share a common fiber
are assigned to different wavelengths. The objective is to minimize the total number of wavelengths used for routing all connections. This problem is called min-RWA and was shown to be NP-hard. In this thesis, we first propose efficient implementations of the state-of-art heuristics in the literature and reevaluate them on a broader set of test instances. Following, we propose a random-keys genetic algorithm for min-RWA. This algorithm extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results showed that the new heuristic improves the state-of-art algorithms in the literature even when they were close to the optimal solution. Finally, we propose a branch-and-cut algorithm for the Partition Coloring Problem (PCP), which is a generalization of the graph coloring problem. Algorithms for PCP have ben used in the literature as building blocks for algorithms for min-RWA. An integer programming formulation, valid inequalities, and a cutting plane procedure are proposed.
Computational experiments are reported for random graphs and for PCP instances originating from min-RWA instances.


[08_MSc_anibolete]
Túlio Jorge de Alcântara Neves de Souza ANIBOLETE. Boosting para sistemas de recomendação. M.Sc. Diss. Port. Presentation: 29/08/08. 60 p. Advisor: Ruy Luiz Milidiu.

Abstract: With the amount of information and its easy availability on the Internet, many options are offered to the people and they, normally, have little or almost no experience to decide among the existing alternatives. In this scene, the Recommendation System appear to organize and recommend automatically, through Machine Learning, the interesting items. One of the great recommendation challenges is to match correctly what is being recommended and who are receiving the recommendation. This work presents a Recommendation System based on Collaborative Filtering, technique whose essence is the exchange of experiences between users with common interests. In Collaborative Filtering, users rate each experimented item indicating its relevance allowing the use of ratings by other users of the same group. Our objective is to implement a Boosting algorithm in order to optimize a Recommendation System performance. For this, we use a database of advertisements with validation purposes and a database of movies with testing purposes. After adaptations in the conventional Boosting strategies, improvements of 3% were
reached over the original algorithm.

[08_PhD_almendra]
Vinicius da Silva ALMENDRA. Um estudo de identificação de fraudadores em mercados eletrônicos através da computação humana. [Title in English: Study on fraudster indetification in electronic markets through human computation] Ph.D. Thesis. Port. Presentation: 18/09/08 122 p. Advisor: Daniel Schwabe.

Abstract: Fraudulent behavior is an increasing problem for electronic markets, in particular for online auction sites, causing several types of loss. Fraud loss reduction measures generally have as an undesirable by-product the harassment and even exclusion of bona fide users, creating a difficult trade-off between losses with fraudsters and losses due to excessive constraints on market participants. The objective of this thesis is to show the viability of a novel approach to fraud loss reduction in online auction sites, the "catch the thief" game. This approach takes explicity into account the aforementioned trade-off and is based on the paradigm of human computation, where people do computational tasks for fun or profit. The methodology used was an exploratory research on fraudulent activity in a real electronic market, a pilot test of fraudster detection by human agents, and the development and simulation of the proposed game's core element, the fraudster identification mechanism. The exploratory research presents a profile of non-delivery fraud in the biggest Brazilian online auction site, showing it as real, recurring and measurable problem; the pilot test displays positive evidence that unspecialized human agents can indeed distinguish fraudulent sellers from normal ones by a significant margin; the simulatiom supports the usefulness of the proposed
mechanism for fraud loss reduction. The results obtained confirm "catch the thief" game as a viable approach to reduce fraud loss in electronic markets.

[08_MSc_cruz]
Vitor Medina CRUZ. Ginga-NCL para dispositivos portáteis.[Title in English: Ginga-NCL for portable devices] M.Sc. Diss. Port. Presentation: 13/06/08. 84 p. Advisor: Luiz Fernando Gomes Soares.

Abstract: The advent of the Digital TV brings many advantages, such as image and sound improvement and interactivity support. A Digital TV system defines codification and transmission techniques for content to be transmitted from broadcasters to receiver devices belonging to viewers. An important element defined for such systems is the middleware. In the Digital TV context, the middleware provides a programming language to be used on the creation of interactive applications. The middleware specified by the Sistema Brasileiro de TV Digital (SBTVD), known as Ginga, is composed by two environments: one declarative, the Ginga-NCL, and another imperative, the Ginga-J. Only Ginga-NCL is mandatory in portable devices. Among the advantages of Ginga-NCL, stands out the fact of its language, the NCL, has a set of characteristics that are suitable for creation of interactive television content. However, it is important to make a Ginga-NCL reference implementation that can be used as proof of concept of the specification, which shows its use viability in practice. This work presents the first Ginga-NCL reference implementation for portable devices, based upon its reference implementation for fixed terminals. Among the studied
platforms, the one provided by Symbian operating system was chosen to carry out the proposed implementation, since it has the greatest benefits. The problems found during the development of the proposed implementation are presented together with the solutions given. At the end, systemic test were used on the identification and correction of errors of the implementation resulted from this work.