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 2004. They are all available in print format and, according to the authors' preference, some of them are freely available to download, while others are freely available to download to the PUC-Rio community exclusively(*).
For any requests, questions, or suggestions, please contact:
Rosane Castilho firstname.lastname@example.org
Last update: 31/AUGUST/2005
Alessandro Fabricio GARCIA. Objetos e agentes: uma abordagem orientada a aspectos. [Title in English: From objects to agents: an aspect-oriented approach] Ph.D. Thesis. Port. Presentation: 02/04/04 322 p. Advisor: Carlos José Pereira de Lucena.
Abstract: Software engineers of Multi-Agent Systems (MASs) are faced with different concerns (properties), such as autonomy, adaptation, interaction, collaboration, learning, and mobility. Many of these agent concerns cannot be modularized based only on object-oriented abstractions. MAS developers however have relied mostly on
object-oriented design techniques and on object-oriented programming languages, such as Java. As the agent complexity increases, the agent concerns tend to spread across several system components at the architectural, design and implementation levels. It often leads to a poor separation of agent concerns in the software system, and in turn to the production of MASs that are difficult to maintain and reuse. This thesis presents an innovative aspect-oriented approach for the seamless integration of agents into object-oriented software engineering from the architectural stage to the implementation stage. Aspect is the abstraction used to modularize agent concerns that crosscut several system components. The proposed approach encourages the separate handling of agent properties, and provides a disciplined scheme for their composition. The approach is composed of an architectural method, a pattern language, and an assessment framework. The architectural method and the pattern language provide aspect-oriented solutions for modularizing the agent concerns at different stages of design and implementation. The purpose of the assessment framework is to support the evaluation of the reusability and maintainability of aspect-oriented solutions based on a metrics suite and a quality model. Experimental studies in different application domains have been conducted to assess the produced approach based on qualitative and quantitative criteria. The use of the aspect-oriented solutions resulted in fewer lines of code, fewer design and implementation components, lower internal complexity of system components, and lower coupling.
Alexandre Rocha DUARTE. Novas heurísticas e uma abordagem por programação inteira para um problema de correspondência inexata de grafos. [Title in English: New heuristics and an integer programming approach to an inexact graph matching problem] M.Sc. Diss. Port. Presentation: 30/01/04 85 p. Advisor: Celso Carneiro Ribeiro.
Abstract: This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium-size instances.
Amanda Vieira LOPES. RXQEE - uma máquina de execução de consultas em um ambiente de integração de dados relacionais e XML. [Title in English: RXQEE – a relational-XML query execution engine] M.Sc. Diss. Port. Presentation: 30/07/04 98 p. Advisor: Rubens Nascimento Melo.
Abstract: In the traditional approach for the evaluation of data integration queries, heterogeneous data in data sources are converted into the global data model by wrappers before being delivered to algebraic operators. Consequently, query executions plans (QEPs) are composed exclusively by operations in accordance to the global data model. This work proposes a new data integration query evaluation strategy, named Moving Wrappers, in which data conversion is considered as an operation placed in any part of the QEP, based on a query optimization process. This permits the use of algebraic operators of the data source's data model. So, a QEP may include fragments with operations in different data models converted to the global data model by inter-algebraic operators. Based on this strategy, a query execution engine (QEE), named RXQEE (Relational-XML Query Execution Engine), was developed as an instance of QEEF (Query Execution Engine Framework). In particular, RXQEE explores integration queries over Relational and XML data, and therefore it implements algebraic operators, in XML and Relational models, and inter-algebraic operators, permiting the execution of integration QEPs.
Ana Lúcia de MOURA. Revisitando co-rotinas. [Title in English: Revisiting coroutines] Ph.D. Thesis. Port. Presentation: 10/09/2004 102 p. Advisor: Roberto Ierusalimschy.
Abstract: The purpose of this work is to defend the revival of coroutines as a powerful and convenient control construct, which can replace both first-class continuations and threads with a single and simplier concept. In order to provide an adequate and precise definition of the concept of coroutines, we propose a new classifying system, and introduce the concept of complete coroutines, for which we provide a formal definition based on an operational semantics. We then demostrate that complete symmetric coroutines and complete asymmetric coroutines have equivalent expressive power, as well as complete coroutines and one-shot traditional and partial continuations. We also discuss the advantages of using complete asymmetric coroutines instead of symmetric coroutines or first-class continuations. Finally, we analyse the benefits and problems associated with different concurrency models, and argue in favor of the replacement of multithreading with alternative concurrency models and the provision of coroutines as a basic concurrency construct, adequate for the implementation of these alternative models.
Anolan Yamilé Milanés BARRIENTOS. Uma arquitetura para auto-sintonia global de SGBDs usando agentes. [Title in English: An agent-based architecture for DBMS global self-tuning] M.Sc. Diss. Port. Presentation: 14/04/04 82 p. Advisor: Sergio Lifschitz.
Abstract: The increasing complexity of the commercial DBMSs as well as the workload they manage, besides the fact that many users do not have deep knowledge about database administration, among other reasons, strongly suggests the introduction of techniques that automates the database tuning process. Self-tuning, or auto-tuning, is a feature that makes systems adaptable in order to keep a good overall performance, reducing as possible the interaction between the administrator and the system. This work proposes an approach for the automatic tuning of DBMSs parameters using an achitecture based on software agents. We consider tuning as a global issue, given that changes of a single parameter can be refleted in others. The architecture details, its implementation and a practical evaluation are also dicussed in this dissertation.
Aristófanes Corrêa SILVA. Algoritmos para diagnóstico assistido de nódulos pulmonares solitários em imagens de tomografia computadorizada. [Title in English: Algorithms for assisted diagnosis of solitary lung nodules in computerized tomography images] Ph.D. Thesis. Port. Presentation: 09/02/04 140 p. Advisors: Marcelo Gattass and Paulo Cezar Pinto Carvalho.
Abstract: The present work seeks to develop a computational tool to suggest about the malignancy or benignity of Solitary Lung Nodules by the analysis of texture and geometry measures obtained from computadorized tomography images. Four groups of methods are proposed with the purpose of suggesting the diagnosis for such nodule. The groups of methods are divided according to their common characteristics. Group I includes methods based on texture adapted for 3D, such as the histogram, the Spatial Gray Level Dependence Method, the Gray Level Difference Method and Gray Level Run Lenght Matrices. Group II also deals with the texture of nodules, but uses four statistical functions denominated semivariogram, semimadogram, covariogram and correlogram. Group III describes measures based only on the geometry of the nodule, such as convexity, sphericity, and measures based on the curvature. Finally, Group IV analyzes the Gini coefficient and nodule skeleton methods, which take into account both the nodule's geometry and its texture. A sample with 36 nodules, 29 benign and 7 malignant, was analyzed and the preliminary results of this approach are very promising in characterizing lung nodules. Most groups of proposed methods have the area under the ROC curve value above 0.800, using Fisher's Linear Discriminant Analysis and Multilayer Perceptron Neural Networks. This means that the proposed methods have great potential in the discrimination and classification of Solitary Lung Nodules.
Carolina Howard FELICÍSSIMO. Interoparabilidade semântica na web: uma estratégia para o alinhamento taxonômico de ontologias. [Title in English: Semantic Web interoperability: one strategy for the taxonomic ontology alignment] M.Sc. Diss. Port. Presentation: 19/08/04 180 p. Advisors: Julio Cesar Sampaio do Prado Leite and Karin Koogan Breitman.
Abstrac: With the Web evolving towards a Semantic Web, it is belived that the available information will be presented in a meaningful way to allow machines to automatically process its content. Besides the individual processing, a better information exchange among Web applications is desired. For this purpose, mechanisms are called for guarantee the semantic interoperability, that is, the identification and compatibility of information. In this direction, ontologies are used as one resource to make available a structured vocabulary, free of ambiguities. Ontologies provide a well-defined standard to structure the information and to promote formalism for automatic processing. In this work, we propose one strategy for ontology interoperability. The Ontology Taxonomic Alignment Component - CATO, which is the result of the implementation of this proposed strategy, provides an automatic taxonomic ontologies alignment. In this way, the alignment is obtained by a three-step process. The first step is the lexical comparison between the concepts from the entries ontologies. It uses a trimming mechanism of the related associated concepts as a stop condition. The second step is the structural comparison of the ontologies structures used to identify the similarities between common sub-trees. The third step refines the results of the previous step, classifying the similar identified concepts as very similar or little similar, according to a pre-defined similarity measurement.
Christian Jacques RENTERÍA. Uma abordagem geral para quantificadores em dedução natural. [Title in English: A general approach to quantifiers in natural deduction] Ph.D Thesis. Port. Presentation: 05/04/04 147 p. Advisor: Edward Hermann Haeusler.
Abstract: There are many kinds of deductive calculus. The axiomatic ones are the more usual. However, from the point of view of proof theory, Natural Deduction systems seem to be more interesting. This is the motivation for developping a technique that aims to ease the transformation from deductive calculus to Natural Deduction style. This work concentrates on the aspect of modeling the rules for the quantifiers of the logic considered, and, for this purpose, labels are used. After an intuitive presentation of the technique developed, some logical systems are treated by the method: ultrafilter logic, filter logic, CTL, Keisler's logic and CTL*. For each one of them proof-theoretical aspects are analysed.
Christina von Flach Garcia CHAVEZ. Um enfoque baseado em modelos para o design orientado a aspectos. [Title in English: A model-driven approach for aspect-oriented design] Ph.D Thesis. Port. Presentation: 02/04/04 298 p. Advisor: Carlos José Pereira de Lucena.
Abstract: Aspect-Oriented Programming (AOP) is a new programming paradigm that promotes advanced separation of concerns by introducing a new modular unit, called aspect, for the modularization of crosscutting concerns. As an emerging programming paradigm, there are many different approaches to AOP, with distinct and varying sets of abstractions and composition mechanisms, specific terminology, properties and languages constructs. In this thesis, we shift the focus from the mechanisms that support the aspect-oriented programming technology to the concepts and properties that characterize it as an emerging paradigm for software development. In particular, we focus on how these concepts and properties can be exploited at an early design stage to build systems that are easier to comprehend, evolve and reuse. This thesis addresses current issues related to aspect-oriented design and modeling, and proposes: (i) the aspect model, an unifying conceptual framework for AOP that provides consistent terminology and basic semantics for thinking about a problem in terms of AOP core concepts and properties, (ii) the aSideML, a modeling language for specifying and communicating aspect-oriented designs. The aSideML provides notation, semantics and guidelines that enable the designer to build models in which aspects are explicitly treated as first-class citizens, and (iii) the aSide metamodel, a logical model that defines the semantics of structural and behavioral models supported by the aSideML.
Cláudio Nogueira SANT'ANNA. Manutenibilidade e reusabilidade de software orientado a aspectos: um framework de avaliação. [Title in English: Maintainability and reusability of aspect-oriented software: an assessment framework] M.Sc. Diss. Port. Presentation: 26/03/04 113 p. Advisors: Carlos José Pereira de Lucena and Arndt von Staa.
Abstract: Aspect-oriented software development (AOSD) is gaining wide attention both in research environments and in industry. Aspect-oriented systems encompass new software engineering abstractions and different complexity dimensions. As a consequence, AOSD poses new problems to empirical software engineering. It requires new assessment mechanisms to measure the maintainability and reusability degrees of aspect-oriented systems. This dissertation presents an assessment framework for AOSD, which is composed of two components: a suite of metrics and a quality model. These components are based on well-known principles and existing metrics in order to avoid the re-inventation of well-tested solutions. The proposed framework has been evaluated in the context of two different empirical studies with different characteristics, diverse domains, varying control levels and different complexity degrees. The first study compared an object-oriented approach and an aspect-oriented approach to the design and implementation of a multi-agent system. The second study involved the application of the proposed framework to evaluate Java and AspectJ implementations of the GoF design patterns.
Críston Pereira de SOUZA. Algoritmos eficientes para atribuição de hotlinks em diretórios Web. [Title in English: Efficient hotlinks assigment algorithms for Web directories] M.Sc. Diss. Port. Presentation: 23/03/04 63 p. Advisors: Eduardo Sany Laber and Artur Alves Pessoa.
Abstract: An approach to search an information in a large and chaotic data like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the Web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the Web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in Web directoires, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for Web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming, model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.
Dalessandro Soares VIANNA. Heurísticas híbridas para o problema da filogenia. [Title in English: Hybrid heuristics for the phylogeny problem] Ph.D Thesis. Port. Presentation: 27/02/04 101 p. Advisor: Celso Carneiro Ribeiro.
Abstract: A phylogeny is a tree that relates taxonomic units, based on their similarities over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. The main goal of this work is to develop hybrid heuristics for this problem. Two strategies are proposed. The first combines the GRASP metaheuristic using a new neighborhood structure (k-SPR) proposed in this work with a VND local search procedure. The second hybrid strategy combines genetic algorithms with an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originally applied in the context of other metaheuristics such as tabu search and GRASP. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristics are quite robust and outperform the other algorithms in the literature in terms of solution quality and computational time.
Élbio Renato Torres ABIB. Escalonamento de tarefas divisíveis em redes estrela. [Title in English: Divisible job scheduling in star networks] M.Sc. Diss. Port. Presentation: 30/06/04 106 p. Advisor: Celso Carneiro Ribeiro.
Abstract: The problem of divisible job scheduling consists of determining how to divide the data to be processed among processors and in which order each fraction should be sent to them. In this dissertation, we consider the divisible load scheduling problem in star networks with heterogeneous computers and links. Original mixed integer linear programming formulations of this problem are proposed, as well as a new algorithm with complexity O(n) to find the optimal solution for a special case. We also propose two fast heuristics that achieve good results for instances representing large scale computing systems.
Esteban Walter GONZALEZ CLUA. Impostores com relevo. [Title in English: Relief impostors] Ph.D. Thesis. Port. Presentation: 02/04/04 128 p. Advisors: Bruno Feijó and Marcelo Dreux.
Abstract: The present work introduces the concept of relief impostors: an efficient manner of representing objects by images in systems that require real time rendering, such as 3D games and virtual reality environments. For this purpose, typical methods of image-based rendering are mixed with traditional geometry based rendering methods. This technique only requires from the user the geometric modeling of the entity to be represented. After this, the system synthesizes relief textures, dynamically refreshed when necessary, and renders them using the method of relief texture mapping. This approach allows complex models to be inserted into the real time pipeline system. This complexity arise either from the geometric nature of the model or its process of visualization. Also the relief impostors try to use the idle time or parallel resources available on the processor, in order to balance the work to be done between the CPU and GPU. Furthermore, they make possible the representation of any kind of geometric object by the relief texture mapping technique.
Fábio Mascarenhas de QUEIROZ. Integração entre a linguagem Lua e o Common Language Runtime. [Title in English: Integrating the Lua language and the common language runtime] M.Sc. Diss. Port. Presentation: 19/03/04 68 p. Advisor: Roberto Ierusalimschy.
Abstract: The Common Language Runtime (CLR) is a platform that aims to make the interoperability among different programming languages easier, by using a common language (the Common Intermediate Language, or CIL) and a common type system (the Common Type System, or CTS). Lua is a flexible scripting language with a simple syntax; scripting languages are frequently used to join components written in other languages, to build application prototypes, and in configuration files. This work presents two approachs for integration between the Lua language and the CLR, with the objective of allowing Lua scripts to instantiate and use components written for the CLR. The first approach is to create a bridge between the Lua interpreter and the CLR, without changing the interpreter. The features and implementation of this bridge are shown, and it is compared with other work following the same approach. The second approach is to compile the virtual-machine instructions of the Lua interpreter to instructions of the CLR's Common Intermediate Language, without introducing changes to the Lua language. The implementation of a Lua instruction to CIL compiler is shown, and the performance of scripts compiled by it is compared with the performance of the same scripts run by the Lua interpreter and with the performance of equivalent scripts compiled by compilers of other scripting language to the CLR.
Felipe Gomes de CARVALHO. Comportamento em grupos de personagens do tipo Black&White. [Title in English: Group behavior for Black&White characters] M.Sc. Diss. Port. Presentation: 31/03/04 124 p. Advisor: Bruno Feijó.
Abstract: Recently the game industry has been demonstrating much interest in the development of games that use more powerful Artificial Intelligence (AI) techniques. In this way, many games have developed with more realistic graphics and character behavior. The game Black&Wite (B&W), developed by Lionhead Studios, is considered an important example of the use of AI techniques in games, and has resulted in a great success, disclosing a very interesting deliberative architecture for computational agents. Such architecture is based on the deliberative model called BDI (Belief, Desire and Intention). The present work aims to develop a study on the architecture used in game B&W, and also on the interaction of characters that use the techniques applied in this architecture. This interaction will use a protocol inspired on the communication language KQML (Knowledge Query and Manipulation Language).
Fernando Náufel do AMARAL. Teoria de modelos para heurísticas baseadas em Topoi. [Title in English: Topos-based Model Theory for heuristics] Ph.D. Thesis. Port. Presentation: 29/03/04 152 p. Advisor: Edward Hermann Haeusler.
Abstract: This work employs concepts and tools from Category Theory and Topos Theory to construct a mathematical model for problems, reductions between problems, heuristic search spaces and strategies. More precisely, a search space construction strategy is represented by a functor from a certain category of problems to a certain category of forests. The collection of all such functors forms a topos, a specific model equipped with its own internal logic. This internal logic is then used to define search strategies and heuristics in Local Set Theory. Possible applications of this work include (1) the logical specification and classification of heuristics and metaheuristics used in practice and (2) a more abstract and general rendering of specific results relating the structure of problems to adequate problem-solving methods.
Francisco Mauro Alves FONSECA. Texturas com relevo utilizando iluminação por pixel e processamento paralelo. [Title in English: Relief textures using per pixel lighting and parallel processing] M.Sc. Diss. Port. Presentation: 23/01/04 110 p. Advisors: Bruno Feijó and Marcelo Dreux.
Abstract: The main motivation for this work is to verify the feasibility of using relief texture mapping in high-demand real-time applications, such as computer games. This dissertation presents an extension to relief texture mapping that supports the representation of effects that depend of viewpoint and illumination direction, which could not be represented with previous techniques. Moreover, it proposes a way to parallelize relief texture mapping between CPU and GPU, using Hyper-Threading technology. In this new approach, each element that belongs to a relief texture is augmented to include three scalar values representing the normal vector of the reproduced surface. So, the illumination can be calculated per pixel. In the proposed approach, the parallelization of the relief texture mapping represents an acceleration of up to 37% when compared to conventional techniques.
Geíza Maria Hamazaki da SILVA. Extração de conteúdo computacional de provas intuicionistas. [Title in English: Computational contents extraction from intuitionist proofs] Ph.D. Thesis. Port. Presentation: 26/03/04 143 p. Advisor: Edward Hermann Haeusler.
Abstract: One of the main problems in Computer Science is to assure that programs are implemented in such a way that they satisfy a given specification. There are many studies about methods to prove correctness of programs. This work presents a method, belonging to the constructive synthesis or proofs-as-programs paradigm, that comes from the Curry-Howard isomorphism and extracts the computational contents of intuitionist proofs. The synthesis process proposed produces a program in an imperative language from a proof in many-sorted intuitionist logic, where the axioms define the abstract data types using Natural Deduction as deductive system. It is proved the correctness, as well as the completeness of the method regarding the Heyting arithmetic with w-rule (in its computational version). A discussion about the use of the finitary induction instead of computational w-rule concludes the work.
Gilliard Lopes dos SANTOS. Máquinas de estados hierárquicas em jogos eletrônicos. [Title in English: Hierarchical state machines in electronic games] M.Sc. Diss. Port. Presentation: 23/01/04 54 p. Advisor: Bruno Feijó.
Abstract: This work comprehends the use of Hierarchical State Machines in the definition and control of behavior pertaining to intelligent agents in electronic games. This type of State Machine permits drastic reductions in the number of transitions when compared to a non-hierarchical State Machine that implements the same behavior: besides, it offers a more intuitive manner for defining and understanding graphical representations of State Machines consisting of many states, a typical scenario in game agents that need to exhibit complex reactive behavior.
Guilherme Araújo SZUNDY. Modelagem e implementação de aplicações hipermídia governadas por ontologias para a Web semântica [Title in English: Modeling and implementation of ontology driven hypermedia applications for the semantic Web]. M.Sc. Diss. Port. Presentation: 10/11/2004. 154 p. Advisor: Daniel Schwabe.
Abstract: This dissertation proposes a
development model for hypermedia applications on the Semantic Web extending the
Semantic Hypermedia Design Method (SHDM), and presents an implementation
architecture for this model. In the proposed extension applications are seen as
navigational views over conceptual models defined by any Semantic Web ontology.
Navigational classes are characterized by a retrieval pattern of conceptual
ontology data from a specific resource, and can also incorporate rules for
instances filtering. Access structures are now distinguished by their data
source, and are categorized as arbitrary, query based, context based or faceted.
Links specialize conceptual relationships based on the data types of its origin
and destination, and can also map relationship compositions. A vocabulary
defined as an ontology is used for the specification of the navigational model,
making it independent from the query and inference environment used by any
implementation of the model. The implementation architecture specified and
implemented generates applications directly from the data contained in the
Hélcio Bezerra de MELLO. Proxies inteligentes - monitoração e adaptação automáticas. [Title in English: Smart proxies: automatic adaptation and monitoring] M.Sc. Diss. Port. Presentation: 10/09/04 55 p. Advisor: Noemi de La Rocque Rodriguez.
Abstract: In the contex of distributed applications, the need for adapting to changes in the execution environment is growing steadily. Several works deal with dynamic reconfiguration of clients and servers in response to such changes, including situations where provision of Quality of Service (QoS) is concerned. This thesis proposes the use of reflexivity in a popular middlaware architecture (CORBA) and other tools to develop a smart proxy. One of its main points is usage simplicity, for the proxy requires few parameters to be instantiated and reacts to external events automatically. That behavior is achieved by combining the flexibility of the LuaOrb binding and the convenience of the LuaTrading and LuaMonitor libraries; the statement of properties relevant to the dynamic adaptation is accomplished by simple and easy-to-reuse descriptors. Finally, this work offers mechanisms to upload and download specialized stubs as to carry out more specific adaptation procedures. In order to demonstrate a possible application of the smart proxy, we present a simple game that employs it to automatically adapt to simulated resource shortage events.
Heloísa Reis LEAL. Operações booleanas na modelagem por pontos. [Title in English: Boolean operations on point-based 3D models] M.Sc. Diss. Port. Presentation: 03/08/04 74 p. Advisors: Waldemar Celes Filho and Luiz Velho.
Abstract: Boolean operations are used to create or modify models. These operations in the majority of 3D object representations are very complex. In the last years a significant trend in Computer Graphics has been the shift towards point sampled 3D models due to their advantages over other representations, such as simplicity and efficiency. Two recent works present algorithms to perform interactive boolean operations on point-based models: the work by Adams and Dutre and the work by Pauly et al. Due to great importance of this novel representation and of the use of boolean operations, the present work makes an introduction to point-based representation, implements the algorithm proposed by Adams and Dutre with some improvements, and compares this implementation with the work by Pauly et al.
Humberto José LONGO. Técnicas para programação inteira e aplicações em problemas de roteamento de veículos. [Title in English: Integer programming techniques and applications to vehicle routing problems] Ph.D. Thesis. Port. Presentation: 30/08/04 123 p. Advisors: Marcus Vinicius Poggi de Aragão and Eduardo Uchoa Barboza.
Abstract: Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and-bound algorithm and its variations branch-and-cut, branch-and-price and branch-and-cut-and-price are presented. The second part of this text addresses the application of the methodologies described in part one to routing problems where capacity constraints are considered. First, a technique named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistribution is described together with a column generation approach for its resolution. Computational results
for all applications are presented.
João Coutinho MACHADO. Um estudo sobre o desenvolvimento orientado a serviços. [Title in English: A study on service-oriented development] M.Sc. Diss. Port. Presentation: 01/04/04 89 p. Advisor: Roberto Ierusalimschy.
Abstract: Several studies point that service-oriented development will have, in some years, great influence on the development of systems. This work shows what service-oriented development actually presents as technological innovation, through the discussion of all its relevant characteristics for construction of an application based on the concept of services. Characteristics as black-box reuse, distribution and environment heterogeneity support, among others, are discussed in intention to identify its advantages and features, and mainly, its importance for the service-oriented development. It is also discussed the concept represented for the term "service", that have distinct interpretations in the industry and academic publications. In addition some frameworks are presented that support device-oriented Development, such as Vinci, Jini and the XML Web Services. Finally, a proposal for a new framework is presented which offers support for Service-Oriented Development. Unlike the other frameworks previously mentioned, this is based on the extension of J2EE application server infrastructure.
João Felipe Santos CONDACK. Swell: um ambiente para seleção de Web services semânticos. [Title in English: Swell - a semantic Web-services selection environment] M.Sc. Diss. Port. Presentation: 30/07/04 142 p. Advisor: Daniel Schwabe.
Abstract: Swell is an environment that helps Web Based Systems development, having as a cornerstone the semantic selection of Web services. It is a tool whose objective is to help in the application design and development tasks, aiming to reach a high degree of reuse. This is achieve through the support for the description, search and selection of Web services for application composition. Initially the Internet was a communication channel and a text-based content dissemination vehicle. With the advent of e-commerce and Web's unfolding, it became a systems deployment platform. At the same time, software development also evolved, through the use of new software engineering concepts, such as components reuse and design patterns. This work aims at helping to develop practices and technologies that improve software development by conciliating these two evolution trends. The Swell environment was conceived as a framework with support for the evolution of Web components technologies. It provides hot spots that allow for adaptation of new Web services descriptions and reflection of these changes in the search engine.
José Carlos Tavares da SILVA. Um modelo para avaliação de aprendizagem no uso de ferramentas síncronas em ensino mediado pela Web. [Title in English: A model for learning evaluation using synchronous tools in Web-based learning] Ph.D. Thesis. Port. Presentation: 05/04/04 181 p. Advisor: Bruno Feijó.
Abstract: This work presents a model for learning evaluation to be used in web-based learning systems. This model is constructed to provide conditions for a correct use of three learning paradigms: Learner centered learning, Cooperative Learning and Problem Based Learning. A finite state machine is proposed to support the evaluation of the apprentice's participation under the Vinculum Theory by Enrique Pichon Riviere. As designed, the teacher can do a judgement of the observable behavior of each student and make an evaluation of the knowledge learning in a collective construction process based on the PBL (Problem Based Learning) strategy. The AulaNet TM environment is used in this work because it has a well-designed content server structure and is strongly oriented towards collaborative learning. The binding of the proposed model with the AulaNet TM environment follows the guidelines of simplicity and dependence of both systems. A blackboard architecture is implemented to get the characteristics of independence and low
complexity described above.
Lauro Eduardo KOZOVITS. Otimização de mensagens e balanceamento de jogos multi-jogador. [Title in English: Message optimization and balancing of multiplayer games] Ph.D. Thesis. Port. Presentation: 03/03/04 175 p. Advisor: Bruno Feijó.
Abstract: Multiplayer game technology is a specialized field in networked virtual environments (Net-VE). With the increasing popularity of Internet games, the analysis of their main problems and the search for an architecture for these environments has become interesting in order to adapt them to the specific needs of these games. A hybrid architecture using both client-server and peer-to-peer approach is proposed and implemented in this work for a certain class of multiplayer games. In order to provide an efficient transmission of user created objects among players during a session, a change in its geometrical representation is proposed. It is showed that the use of higher level object representation such as CSG or Metaball modeling techniques can be used to provide this efficient transmission under certain circumstances. It is also proposed the use bitfields as a efficient way to both represent and transmit coordinates of the virtual world.
Leandro Ribeiro DAFLON. Um framework para a representação e análise de processos de software. [Title in English: A framework for software engineering process representation and analysis] M.Sc. Diss. Port. Presentation: 22/03/04 153 p. Advisors: Carlos José Pereira de Lucena and Arndt von Staa.
Abstract: Many organizations search for standards and guidance to achieve a mature process. However, change and evolution of business and technology imply constant change and evolution of development processes. In this dissertation we propose a framework that offers an infrastructure allowing organizations to define and analyze software engineering process at organization level or project level. Besides that, it facilitates integration, change and process evolution. The definition of a process is based on a concept Process Units. These represent building blocks for tailoring integrated development processes, by reusing or not parts of existing process models. The process analysis is based on quality standards or maturity models, such as SW-CMM, CMMI, ISO 12207.
Lúcia Blondet BARUQUE. eLGORM: um modelo de referência para governança de e-Learning. [Title in English: eLGORM: a reference model for e-Learning Governance] Ph.D. Thesis. Port. Presentation: 10/08/04 167 p. Advisor: Rubens Nascimento Melo.
Abstract: It is increasingly recognized that e-Learning is crucial to the success of organizations. In an era where the intellectual capital is considered to be the most valuable asset of a company, surprisingly, not too much attention is given to the risks and threatens faced by e-learning endeavours. The critical role that e-learning is playing in the organizations calls for a specific focus on governing it. To this end, we are launching the term e-Learning Governance. e-Learning Governance can be defined as the responsibilities and practices carried out with a view to providing strategic direction to an institution's e-learning initiatives, ensuring that established objectives are achieved and risks managed properly, as well as that resources allocated are used responsibly. We need to go beyond methodologies for developing e-learning modules and extend the governance principles to all stages of e-learning. We propose, therefore, a Reference Model, independent of organizational structures, pedagogical frameworks and technical platforms. Our Reference Model conceptual framework encompasses an e-learning information architecture, processes and sub-processes governance rules and metrics. Furthermore, we also specify a system to support e-learning governance activities based on the proposed reference model.
Luis Gustavo FERRÃO. Uma infra-estrutura para matchmaking baseado em ontologias. [Title in English: An infrastructure for ontology-based matchmaking] M.Sc. Dissertation. Port. Presentation: 20/12/2004 p. Advisors: Carlos José Pereira de Lucena and Marco Antonio Casanova.
Abstract: Matchmaking should be understood,
in a general way, as a search process for matchings between demand and supply
requests within an application domain. This work defines a matchmaking software
infrastructure whose domain instances are described in terms of an ontology. The
proposed infrastructure has two major components: the framework Matching Module,
which defines a flexible and extensible platform for dealing with matchmaking
process, independently of the domain, and the OntoAPI, an API providing access
services to semantically annotated data, that use RDF, RDFS or OWL as
Luís Henrique Raja Gabaglia MITCHELL. Gestão de pessoas por competências no ambiente AulaNet. [Title in English: Competency-based people management in the AulaNet environment] M.Sc. Diss. Port. Presentation: 17/03/04 227 p. Advisor: Hugo Fuks.
Abstract: Collaboration, key for the success in the connected globalized world, demands knowledge workers to communicate, coordinate and cooperate in dynamic, multidisciplinary and geographically dispersed groups. E-learning rises as an important answer to the pressing need of non-stop learning. And the resulting continuous evolution of personal competencies calls for the use of competency management practices to aid activities such as expert location, group formation, career services and strategic company-wide planning. Uniting the collaboration, e-learning and competency management fields, the present work encloses the research on the estension of a collaborative learning environment (the AulaNet) with competency management tools. The theory guiding this research clarifies many of the concepts of the area, introduces the three dimensions of a competency and compares knowledge management with competency-based people management while lists the questions competency management can address. Then, details of the competency model developed for the AulaNet Environment are explained, as well as how the actors playing their roles in the environment can benefit from its new features. The document finishes by presenting the conclusion draw from an experiment using the competency model, carried out in 4 editions of disciplines at undergraduate courses at PUC-Rio.
Luiz Antônio de Moraes PEREIRA. TEAM: uma arquitetura para gerência de e-workflows. [Title in English: TEAM: An architecture for e-workflow management] Ph.D. Thesis. Port. Presentation: 14/07/04 184 p. Advisor: Rubens Nascimento Melo.
Abstract: In distributed collaborative applications, the use of centralized repositoires for storing shared data and programs compromises some important characteristics of this type of applications, such as fault tolerance, scalability and local autonomy. Applications like Kazaa, Gnutella and Edutella exemplify the use of peer-to-peer computing, which is being considered an interesting alternative for the solution of the problems mentioned above, without imposing typical restrictions of centralized or even distributed systems such as mediators and HDBMSs. In this work we present the TEAM (Teamwork-support Environment Architectural Model) architecture for managing workflows in the Web. Besides describing the components and connectors of the architecture, which is based on P2P computing, we address the modelling of processes and management of data, metadata and execution control information. We also discuss the strategy adopted for queries dissemination and messages sent to peers in environments based on the architecture. We illustrate the application of TEAM in a case study in e-learning.
Marcelo Fagundes FELIX. Análise formal de modelos de software orientada por abstrações arquiteturais. [Title in English: Formal analysis of software models oriented by architectural abstractions] Ph.D. Thesis. Port. Presentation: 06/04/04 169 p. Advisor: Edward Hermann Haeusler.
Abstract: There is a trend nowadays towards bigger and more complex systems concerning their parts and interconnectivity. In such scenario, modeling structure, overall organization and interaction have become a main concern, as well as fulfillment of mission critical requirements. The scope of our work encompasses Software Engineering related subjects such as Software Architecture, Modeling Techniques and more formal disciplines like Model Checking, Modal Logics and Process Algebra. Although inspired by such techniques, there is, indeed a methodological orientation in our work, traversing the boundaries of Software Engineering with Formal Methods, through which we seek to investigate and establish a systematic way for the effective utilization of formal methods in the first steps of software development. Still, more specificaly, we show how it is possible, starting from models based on architectural abstractions, to systematically produce a formal model upon which we can execute certain forms of behavior analysis. Our proposal includes a basic notational system to express architectural model along with their formal semantics and a prototype built to support specification and formal analysis tasks oriented by architectural abstractions. With this, we intend to stress some essential aspects of a development methodology which aims to integrate tools and formal techniques to software modeling.
Marcelo Ladeira REIS. Um algoritmo de geração de colunas e cortes para o problema de roteamento de veículos. [Title in English: An algorithm with column and cut generation for the Capacitated Vehicle Routing problem] M.Sc. Diss. Port. Presentation: 14/12/2004 85 p. Advisors: Marcus Vinicius Soledade Poggi de Aragão and Eduardo Uchoa Barboza.
Abstract: The Capacitated Vehicle Routing
problem (CVRP) has been one of the most studied problems in the field of
Combinatorial Optimization. A straight forward generalization of the popular
Travelling Salesperson problem, the CVRP has drawn attention of the most
prominent researchers since the early 60’s. One of the most important algorithms
appeared in the early 80’s when a suitable Lagrangean relaxation algorithm has
demonstrated to be far better than the contemporary ones. This algorithm
suggested the use of column generation algorithms that succeeded to become the
best ones in the late 80’s and early 90’s. Finally, in the mid 90’s, cutting
plane methods presented results that convinced the community that this should be
the approach for solving the hardest CVRP problems. This dissertation presents
an overview of those early algorithms and proposes a formulation that allows
uniting the best contributions of them. The resulting algorithm, labeled as a
branch-and-cut-and-price algorithm, deals with exponentially many variables and
constraints that define a relaxed solution space that is the intersection of the
relaxed solution spaces considered in the previous algorithms. The dissertation
also describes a specially devised dynamic programming algorithm to solve the
column generation subproblem and discusses robust branching strategies that
altogether allowed to build an algorithm that perfoms well on several different
classes of instances. The computational experience has shown that the approach
here proposed leads to lower bounds superior than the previous ones. Moreover,
it allowed to consistently solve instances with up to 135 vertices, including 18
that were solved for the first time.
Marconi de Arruda PEREIRA. Uma implementação do serviço WMS sobre a biblioteca TERRALIB. [Title in English: An Implementation of the WMS (Web Map Server) service over the Terralib Library] M.Sc. Diss. Port. Presentation: 09/07/04 108 p. Advisors: Marco Antonio Casanova and Renato Fontoura de Gusmão Cerqueira.
Abstract: This work describes an implementation of the services defined by the Web Map Server (WMS) standard, published by the Open GIS Consortium, over the TerraLib library. In particular, the results of this work allow any client that implements the WMS standard to visualize data stored in a TerraLib database. This work can be consider as a first step towards making the TerraLib Library compliant with the OpenGIS standard, thereby facilitating interoperability, using a relatively simple and well-defined protocol, with a variety of existing GIS software.
Marcos Antônio Vaz SALLES. Criação autônoma de índices em bancos de dados. [Title in English: Autonomous index creation in databases] M.Sc. Diss. Port. Presentation: 15/07/04 113 p. Advisor: Sergio Lifschitz.
Abstract: The choice and materialization of indexes are activities commonly done by database administrators to speed up database application processing. Due to the complexity of the index selection task and to the pressure for productivity increase put on tuning professionals, many works on the literature and on commercial systems seek for tools that can help the DBA choose the best indexes for a given workload. We classify these works as local self-tuning, once they are interested in a specific tuning problem, in opposition to global self-tunning work, which is targeted at obtaining acceptable performance for the system as a whole. This dissertation proposes two architectures that allow the complete automation of the index tuning task. Human intervention independence is achieved through the use of software agents. The combination of agents and DBMS makes systems more autonomous and self-tuning. We have implemented one of the proposed architectures in the open source DBMS PostgreSQL and obtained experimental results with a transactional workload that show the feasibility of our approach.
Maria Lúcia Arraes SEIXAS. Um método de avaliação para interfaces baseadas em mapas. [Title in English: A map-based interface evaluation method] Ph.D. Thesis. Port. Presentation: 09/07/04 113 p. Advisor: Clarisse Sieckenius de Souza.
Abstract: The integration of digital maps and geographical information into Geographical Information Systems (GIS) produces solutions for several groups of users. There is an increasing number of non experts that use GIS on the Web or in desktop applications to locate addresses, plan routes and trips, find places, and so on. Less complex applications designed for general use critically need evaluation, because their commercial success depends heavily on the quality of human-computer interaction. In spite of such critical need, it is very hard to find research about how to evaluate these kinds of simpler applications. We propose a semiotic inspection method (whose acronym in Portuguese is ISIM) that analyzes the effect of representations in map-based interfaces to communicate geographic information. ISIM combines analytic and empirical techniques to carry out evaluations. Analytic techniques are used to define contexts of use and users' profiles, as well as to interpret empirical observations. ISIM also uses an empirical technique of tests and interviews with users. ISIM, whose scope encompasses only GIS map-based interaction, can identify a class of basic problems of interaction and, as is the case with many semiotic methods, hint at design solutions for them.
Mauren Paola RUTHNER. Aplicação da transformada S na decomposição espectral de dados sísmicos. [Title in English: Application of S transform in seismic data spectral decomposition] M.Sc. Diss. Port. Presentation: 02/04/04 84 p. Advisors: Marcelo Gattass and Adelson Santos de Oliveira.
Abstract: One of the main steps in oil exploration is the definition of a geological model that can justify the existence of a hydrocarbon accumulation. Tools that can improve the precision of this geological model are a constant goal of the oil industry research. In this context, Partyka et al. have recently present a new technique that uses spectral seismic data decomposition in order to improve the model's accuracy in terms of the thickness definition of geological layers. In the present research, this technique is studied and tested, and a use for the S transform is proposed to locate the frequency components in the time domain. The S transform was recently developed by Stockwell et al. The test performed with synthetic data indicate that the technique developed by Partyka et al. provide a better qualitative response, because when the models in the test are disturbed, qualitative analyses are compromised. The S transform showed good results in locating the frequency components in the time domain, but it smoothes the amplitude spectrum. At the end of this work, an example of the use of this technique with real three-dimensional data is presented.
Melissa LEMOS. Workflow para Bioinformática. [Title in English: Workflow for Bioinformatics] Ph.D. Thesis. Port. Presentation: 13/09/04 197 p. Advisors: Marco Antonio Casanova and Antonio Basilio de Miranda.
Abstract: Genome projects usually start with a sequencing phase, where experimental data, usually DNA sequences, is generated, without any biological interpretation. DNA sequences have codes which are responsible for the production of protein and RNA sequences, while protein sequences participate in all biological phenomena, such as cell replication, energy production, immunological defense, muscular contraction, neurological activity and reproduction. DNA, RNA and protein sequences are called biosequences in this thesis. The fundamental challenge researchers face lies exactly in analyzing these sequences to derive information that is biologically relevant. During the analysis phase, researchers use a variety of analysis programs and access large data source holding Molecular Biology data. The growing number of Bioinformatics data sources and analysis programs indeed enormously facilitated the analysis phase. However, it creates a demand for systems that facilitate using such computational resources. Given this scenario, this thesis addresses the use of workflows to compose Bioinformatics analysis programs that access data sources, thereby facilitating the analysis phase. An ontology modeling the analysis program and data sources commonly used in Bioinformatics is first described. This ontology is derived from a carefull study, also summarized in the thesis, of the computational resources researchers in Bioinformatics presently use. A framework for biosequence analysis management systems is next described. The system is divided into two major components. The first component is a Bioinformatics workflow management system that helps researchers define, validate, optimize and run workflows combining Bioinformatics analysis programs. The second component is a Bioinformatics data management system that helps researchers manage large volumes of Bioinformatics data. The framework includes an ontology manager that stores Bioinformatics ontologies, such as that previously described. Lastly, instantiations for the Bioinformatics workflow management system framework are described. The instantiations cover three types of working environments commomly found and suggestively, called personal environment, laboratory environment and community environment. For each of these instantiations, aspects related to workflow optimization and execution are carefully discussed.
Pedro Mário Cruz e SILVA. Visualização volumétrica de horizontes em dados sismicos 3D. [Title in English: Volume visualization of horizons in 3-D seismic data] Ph.D. Thesis. Port. Presentation: 09/07/04 108 p. Advisors: Marcelo Gattass and Paulo Cezar Carvalho.
Abstract: This work presents aspects of volume visualization of seismic horizons in 3-D seismic data. We consider both the direct and indirect approaches of volume visualization. In the direct approach we investigate the problem of selecting horizons using transfer functions. We present the 2-D opacity technique, which seeks to increase the ability to select horizons for visualization. We compare the use of instantaneous phase, adjusted phase and unwrapped phase as the second dimension, while seismic amplitude is the first dimension. Also in the direct approach, we show that the seismic amplitude gradient is not a good approximation for the normal vectors in seismic horizons. We suggest the gradient of instantaneous phase as a solution to this problem. In the indirect volume visualization approach we introduce a new optimization model to overcome the seismic horizon tracking problem. We present a heuristic method based on a greedy strategy to find solutions that are good approximations of the horizon of interest, even for complex geological structures.
Renato Figueiró MAIA. Um framework para adaptação dinâmica de sistemas baseados em componentes distribuidos. [Title in English: A framework for dynamic adaptation of distributed component-based systems] M.Sc. Diss. Port. Presentation: 30/03/04 104 p. Advisor: Renato Fontoura de Gusmão Cerqueira.
Abstract: Dynamic adaptation of distributed applications has become an essential feature in development of computer systems, mainly justified by nowadays technology, which enables complex tasks to be performed by computers in application domains less suited for service interruption. This dissertation proposes the LuaOrb Adaptation Framework, which uses features of the programming language Lua to dynamically adapt systems based on the CORBA Component Model (CCM). This framework uses abstractions like roles and protocols to adapt systems by creating new interactions between systems components, as well as provide features for dynamic reconfigurations of CCM components. Due to limitations of CCM, an adaptation of this model to Lua concepts is proposed, resulting in the definition of dynamic containers, which enable development of dynamically adaptable components by changes on component structure and implementation. Dynamic containers allows adaptations to be done on different levels, namely on the level of a single component instance or implementation, as well as on all instances of a given component.
Reubem Alexandre D'Almeida GIRARDI. Framework para coordenação e mediação de Web services modelados como learning objects para ambientes de aprendizado na Web. [Title in English: Framework for coordination and mediation of Web Services modeled as Learning Objects for web-based learning environments] M.Sc. Diss. Port. Presentation: 27/08/04 111 p. Advisor: Carlos José Pereira de Lucena.
Abstract: The increasing interest in Web-based learning environments estimulates researches and evidences the importance of developing technologies and standards that allow environments, instructors and participants to create, find, consume, reuse, and to share instructional contents, known as learning objects. Metadata standards, learning objects and architectures to support these technologies in Learning Management Systems (LMS) are the key for the success of e-learning. In this context, the learning object concept has essential importance and concentrates the majority of the researches accomplished in this field. At the same time, observing that the learning in the web happens through the aid of tools and learning services which are part of LMS, leads to the reflection about the current modeling and understanding of these services. This work defends the modification of the learning objects concept, extending the current one by incorporating services to its extent, being these modeled as Web Service. Finally, a framework is presented in order to facilitate the adaptating of the Learning Management Systems to the new concept of learning objects, as well as a case study in the AulaNet Environment.
Roberto de Holanda CHRISTOPH. Engenharia de software para software livre. [Title in English: Software engineering for open source software] M.Sc. Diss. Port. Presentation: 23/03/04 111 p. Advisor: Julio Cesar Sampaio do Prado Leite.
Abstract: Open sources software has become quite popular nowadays, not only because of some well known applications such as Linux and Apache, but also due to the unique way in which this kind of software is developed, which has drawn a large number of followers around the world. However, in many open source projects, the informal way the development process takes place often results in disregard for the documentation. And low quality documentation is a barrier for new members to join the community. This thesis collaborates to a better understanding of open source software development, mainly in relation to issues in software evolution. It presents a proposal used in the evolution of the Open Source Project known as C&L to document the system code in terms of the application, using the concept of scenarios. By experiencing with a prototype, this work shows how the proposed standard can produce documentation more easily understandable by new members.
Rodrigo Silva GUARINO. Estudo experimental de algoritmos para otimização de consultas conjuntivas com predicados caros. [Title in English: Experimental study of conjunctive queries optimization with expensive predicates] M.Sc. Diss. Port. Presentation: 22/03/04 76 p. Advisor: Eduardo Sany Laber.
Abstract: Traditional database query optimization technique have as its main heuristic the organization of predicates in two main types: selection predicates and join predicates. Join predicates are considered much more expensive than selection predicates. In addition, it's also considered that there's no big difference among the costs of different selection predicates, what makes the optimizer executes them first in any order, reducing the number of tuples necessary to execute join predicates. This assumption, that is well applied in traditional database applications, becomes invalid in respect of recent database application, that executes complex functions over complex data in selection predicates. In this cases, selection predicates are considered more expensive than join predicates and their costs cannot be considered equivalent anymore. This makes the main heuristic of push down selections invalid for these kind of new selection predicates which calls for new optimization techniques. These type of cue named expensive predicates. This work has two main objectives: Present a software that makes possible the development, test and integrate analysis of different algorithms for evaluating expensive predicates and analyse the performance of four algorithm's implementations that are based on Cherry Picking strategy, which aims at exploring the data dependency between input values to expensive predicates. The experiments considered conjunctive(AND) queries, and the general idea is to try evalute the attributes in a order that minimizes cost of the tuples.
Rogério Miguel COELHO. Integração de ferramentas gráficas e declarativas na autoria de arquiteturas modeladas através de grafos compostos. [Title in English: Integration of graphic and declarative tools on the software architectures authoring modeled by composite graphs] M.Sc. Diss. Port. Presentation: 20/08/04 109 p. Advisors: Luiz Fernando Gomes Soares and Rogério Ferreira Rodrigues.
Abstract: This work presents a set of tools to help the implementations of applications for authoring system architectures based on composite graphs. The tools are divided in four graph views: structural, temporal, spatial, and declarative. The views are synchronized in order to offer an integrated authoring environment. Moreover, the views include filtering mechanisms to simplify the specification of more complex architectures. The tools were specialized to hypermedia authoring, but they can be use in other domains, such as software architecture specifications, formal specification tools, workflow projects, etc.
Romano José Magacho da SILVA. Integração de um dispositivo óptico de rastreamento a uma ferramenta de realidade virtual. [Title in English: Integrating an optical tracking device with a virtual reality toolkit] M.Sc. Diss. Port. Presentation: 31/03/04 76 p. Advisors: Marcelo Gattass and Alberto Barbosa Raposo.
Abstract: Virtual reality systems require tracking devices that do not harm the application immersive sensation. With the spread of digital cameras, the optical tracking of users' movement has been firmed as a new area of research. This work presents the integration of an optical tracking device with a virtual reality application development library. The proposed optical device is composed of a sphere coated with retroreflexive material, which is tracked by four cameras with infrared sensors. The study contains the implementation of the tracking device and its integration with ViRAL (Virtual Reality Abstraction Layer) tool.
Sabrina Silva de MOURA. Desenvolvimento de interfaces governadas por ontologias para aplicações na Web semântica. [Title in English: Interface development for hypermedia applications in the semantic Web] M.Sc. Diss. Port. Presentation: 08/09/04 150 p. Advisor: Daniel Schwabe.
Abstract: The current emergence of the Semantic Web has increased the volume of research initiatives related to the development of hypermedia applications in this environment. The common goal is to give semantic meaning to the content of the Web. This means that it is now possible that the data contained in the Web to be defined and related in such a way that it can be used by machines not only for automation, integration and reuse of data among applications, but also to allow richer interaction with human beings. This work applies the concepts of the Semantic Web to the development of interfaces for hypermedia applications, in the context of the Semantic Hypermedia Design Method (SHDM). For this, two ontologies are proposed, one representing concrete interface elements (concrete widgets ontology) and another representing abstract interface element (abstract widgets ontology). These abstract elements are used to describe the abstract interfaces and are mapped to concrete interface elements, specified as instances of the concrete widgets ontology. An implementation architectures is proposed, based on JSP and Tag Libraries, allowing the generation of the concrete page based on a defined abstract interface.
Sérgio da Costa CORTES. Um modelo de transações para integração de SGBD a um ambiente de computação móvel. [Title in English: A transaction model for DBMS integration to a mobile computation environment] Ph.D. Thesis. Port. Presentation: 15/07/04 215 p. Advisor: Sérgio Lifschitz.
Abstract: Portable computarized devices have become widely used in many different application domains and are, together with telecommunication networks, the underlying technology for mobile computing. In this environment Database Management Systems (DBMS) may provide reliability, security and availability, besides data integrity and efficiency persistent data access. These DBMS might be located either in conventional (fixed) networks, with the conventional data server role, or might serve global and local data for mobile computers and related technology. There are many transaction models for mobile database management. However, the particular characteristics of this mobile environment, such as frequent disconnections, weak and intermittent connectivity of wireless networks and clients movement, are not always well addressed. The goal of this thesis is to propose a computational model that enables the integration of a DBMS to a mobile environment. Indeed, we present a new multi-level database transactional model in order to handle mobile requirements and ACID transaction properties, where a DBMS is present. Our model is defined using the ACTA formalism based in first-order logic. The implementation of proposed transaction model becomes feasible through the use of object-oriented frameworks and software agents, with gave support to deal with the particularities of the mobile computing environment. Finally, we give a comparison between the most relevant transaction models for the mobile computing environment and our proposed model, emphasizing the treatment given to the ACID transactions properties.
Sérgio Estevão Machado Lisboa PINHEIRO. Um sistema de cache preditivo para o processamento em tempo-real de grandes volumes de dados gráficos. [Title in English: ] Ph.D. Thesis. Port. Presentation: 12/02/04 202 p. Advisors: Luiz Carlos Pacheco R. Velho and Waldemar Celes Filho.
Abstract: Nowadays, many areas of computer graphics need to process a huge amount of data. In order to visualize the data in real-time, it is necessary to solve two different problems. The first problem is the limited time available to perform rendering. The second one arises from the restricted capacity of storage high-speed memories, like RAM and texture memories. In order to solve the first problem, this work has used multi-resolution techniques. The multi-resolution representation allows the application to work with a constant amount of data during the rendering process. The second problem has been solved by a predictive management memory system based on the virtual memory model. This work proposes an architecture that allows any storage device to be incorporated in the system. Devices are organized sequentially. The heart of the system consist in allocating an area of memory for each device and managing this space optimally. The predictive system aims to load in advance. The data that will probably be used by the application in the near future. This work proposes a specific adaptive prediction algorithm for the visualization problem. This algorithm exploits the information about the camera parameter variations as well as the data transfer rate, in order to decide what should be loaded. The camera parameters are used to determine which data will possibly be used by the application. The transfer rate is used to decide which resolution level of the data should be loaded to the high-speed devices, in advance. The predictive memory management system has been tested for real-time visualization of satellite images and virtual panoramas.
Thiago Ferreira de NORONHA. Heurísticas para roteamento e atribuição mínima de comprimentos de onda por coloração de partições. [Title in English: Heuristics for routing and wavelength assignment by partition coloring] M.Sc. Diss. Port. Presentation: 10/03/2004 52 p. Advisor: Celso da Cruz Carneiro Ribeiro.
Abstract: In optical networks, the information is transmitted along the optical fibers as optical signas. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmition of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converteded to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing this connections so as that two lightpaths sharing a common link use a different wavelength. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach invloving the computation of alternative routes for the lightpaths, followed by the solution of a Partition Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint subsets, PCP consists in selecting and coloring only one vertex in each subset so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computaional experiments are reported comparing the new heuristics and those which already appeared in the literature.
Viviane Torres da SILVA. Uma linguagem de modelagem para sistemas multi-agentes baseada em um framework conceitual para agentes e objetos. [Title in English: From a conceptual framework for agents and objects to a multi-agent system modeling language] Ph.D. Thesis. Port. Presentation: 31/03/04 252 p. Advisor: Carlos José Pereira de Lucena.
Abstract: As a powerful and new paradigm for designing and implementing software systems, multi-agent systems require methodologies, modeling languages, development platforms and programming languages that explore their benefits and their peculiar characteristics. However, different methodologies, languages and platforms for multi-agent systems propose very distinct and varied sets of abstraction. In this context, there is a need for creating a conceptual framework that defines the frequently used multi-agent system abstractions, their relationships and their behavior. As it is the case with any new software engineering paradigm, the successful and widespread deployment of multi-agent systems require modeling languages,among other agent-based software technologies, that explore the use of agent-related abstractions and promote the traceability from the design models to code. This thesis contemplates the definition of a multi-agent system conceptual framework called TAO and of a multi-agent system modeling language called MAS-ML. Our goals are to describe the structural and dynamic aspects of the abstractions commonly used in multi-agent systems by defining a conceptual framework, to propose a modeling language that describes structural and dynamic diagrams to model such aspects and to present the traceability from the structural models into code.