Monografias em Ciência da Computação



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

This file contains a list of the technical reports of the Departmento de Informática, Pontífícia Universidade Católica do Janeiro - PUC-Rio, Brazil, which are published in our series Monografias em Ciência da Computação (ISSN 0103-9741), edited by Prof. Carlos Lucena. Please note that the reports not available for download are available in their print format and can be obtained via the e-mail below.

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

Last update: 18/DECEMBER/2003


LERNER, A.; LIFSCHITZ, S.; ARAGÃO, M.V.S.P. An online approach for parallel join algorithms analysis. 13 p. Port. E-mail:

Abstract: In this work, we propose a methodology for parallel join algorithms evaluation based on competitive analysis. Such algorithms may be seen as online ones, as load balancing decisions are often made without precise knowledge of important input parameters. We identify three different instances of online problems in the join operation and propose a metric for quality of solution assessment valid for them. The metric is independent of algorithm, parallel architecture and load balancing technique and is the corner of the proposed method. Moreover, we suggest, as part of the competitive analysis work, a taxonomy for adversaries used on worst and average case analysis.

CASSINO, C.; IERUSALIMSCHY, R.; RODRIGUEZ, N.L.R. LuaJava - a scripting tool for Java. 8 p. Eng. E-mail:

Abstract: Scripting languages are becoming more and more important as a tool for software development, as they provide great flexibility for rapid prototyping and for configuring componentware applications. In this paper we present LuaJava, a scripting tool for Java. LuaJava adopts Lua, an dynamically typed interpreted language, as its script language. Great emphasis is given to the transparency of the integration between the two languages, so that objects from one language can be used inside the other like native objects. The final result of this integration is a tool that allows the construction of configurable Java applications, using off-the-shelf components, in a high abstraction level.

PAIVA, A.C.; SEIXAS, R.B., GATTASS, M. Introdução a visualização volumétrica. 145 p. Port. E-mail:

Abstract: A volumetric data set is a collection of data in which each data has an associated location in the three-dimensional space. In this work we discuss the techniques that handle these data sets to generate arbitraries views of the volume. We show the main applications that use these techniques, classify the algorithms, and discuss some implementation issues.

PAIVA, A.C.; GOMES, J. Visualização volumétrica em multiresolução. 84 p. Port. E-mail:

Abstract: A volumetric data set is a collection of data in which each data has an associated location in the three-dimensional space. In this work we review the wavelets theory and discuss tha application of this technique to the visualization of volumetric data. We show the main algorithms, and discuss some implementation issues.

SCHMIDT, A.E.; GATTASS, M.; CARVALHO, P.C.P. Combined 3D visualization of volume data and polygonal surfaces using a Shear-Warp algorithm. 25 p. Eng. E-mail:

Abstract: The present paper presents a study on integration between Shear-Warp and Z-Buffer algorithms, and extends the Shear-Warp algorithm to handle scenes composed of both volume and polygonal data. As volume data usually has a different resolution from that of the final image, in which Z-Buffer renders the polygonal data, several variants for this integration are analysed. Results are shown to support some conclusions on the trade-off quality-versus-time that can be expected.

RIVERA ESCRIBA, L.A.; CARVALHO, P.C.P.; VELHO, L. Modelagem e manipulação de objetos de geometria complexa. 38 p. Port. E-mail:

Abstract: In this paper, we focus the modeling and manipulation of surfaces of complex objects of arbitrary form, with the objetive of simulating the deformation of its surfaces. The object is modeled using cubic B-splines having a large number of control points. For the local deformation of the surface it is used a direct manipulation technique applied at a point that is determined by an adequate binary search, which also gives the segment of surface containing the point. In order to produce a realistic deformation of the surface, we explore the multiresolution representation of the object, applying the local deformation through the multiresolution surfaces level.

BRAGRANCA, R.C.M.; HAEUSLER, H.E; PEREIRA, L.C. A new cut-free sequent calculus for S5. 23 p. Eng. E-mail:

Abstract: The definition of a cut-free sequent calculus for S5 is a well-known problem. Traditional cut-elimination strategies do not seem to work for S5 and the main reason for this fact is that sequent calculus systems do not seem to be closed under "permutative" reductions. On the other hand, this problem is already solved for at least one Natural Deduction formalization of S5, where strong structural restrictions on the form of the branches of derivations guarantee a normalization result. The aim of the present work is to define a new sequent calculus, (SC5) for S5 where these strong global structural restrictions are simulated.

SILVA, A.R. Pequi: uma implementação de PKIX para comunicações seguras. 73 p. Port. E-mail:

Abstract: Although the need for public key infrastructure has not been recognised for the widespread use of secure communication, the lack of easily available implementations has severely limited the use of public key cryptography to a small number of specific applications, with specialised solutions. Pequi is such an implementation designed to address a number of realistic wide-scale applications of this technology. The PKI implemented by Pequi is based on the integration of publicly available implementations of different components, to provide a network of certification authorities (CAs), which use LDAP for maintaining a distributed repository of certificates. Such implementation also performs automatic certificate path processing.

CAFEZEIRO, I.L.; HAEUSLER, E.H. Programming language syntax: expressing sharing. 30 p. Port. E-mail:

Abstract: This text presents an operator to syntactically express sharing. The operator will be defined very abstractly, not considering a particular application, and will deal with collection of entities instead of single entries.

de SOUZA, C.S. Semiotic engineering principles for evaluating end-user programming environments. Eng. E-mail:

Abstract: End user programming (EUP) environments are difficult to evaluate empirically. Most users don't engage in programming, and those who do are often discouraged by the complexity of programming tasks. Often the difficulties arise from the programming languages in which users are expected to express themselves. But there are other difficulties associated to designing extensions and adjustments to artifacts that have been originally designed by others. This paper characterizes EUP as a semiotic design process, and presents two principles that can be used to illustrate the distinctions between the various kinds of techniques and approaches proposed in this field. They introduce a preliminary theoretical model of EUP and thus facilitate the definition and interpretation of empirical evaluation studies. They also describe some specific semiotic qualifications that more usable and applicable EUP languages could be expected to have.

de SOUZA, C.S.; PRATES, R.O.; BARBOSA, S.D.J. A method for evaluating software communicability. Eng. E-mail:

Abstract: Computer tools are rational artifacts determined by the cultural background of designers and users. Communicating design assumptions, choices, and goals is a complex task, subject to constant misunderstandings that lead to a wide spectrum of breakdowns in human-computer interaction. This paper presents a method to help HCI practitioners evaluate the communicability of interactive systems, not only in terms of the effectiveness of their direct messages to users but also of the afforded conversational paths that should allow breakdowns to be circumvented. The whole proposal is tied to a semiotic background within which systems are like "discourse deputies" of their designers.

UCHOA, E.; ARAGÃO, M.V.S.P. Vertex-disjoint packing of two Steiner trees: polyhedra and branch-and-cut implementation issues. 23 p. Eng. E-mail:

Abstract: Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing of polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes.

FIORINI, S.T.; LEITE, J.C.S.P.; LUCENA, C.J.P. Describing process patterns. Eng. E-mail:

Abstract: This article proposes a new way of describing patterns in the software process domain. We propose an overall organization (community, family and individual) for process patterns. Most of the proposed patterns' descriptions rely heavily on natural language. We have analysed some of these proposals and presented an alternative based on a structured natural language description. Our strategy leads to a better presentation of the patterns as well as a reduction of ambiguity. Our proposal is integrated with an existing process environment. We differentiate among process pattern, standard process and solution process, pointing out that these notions are different and several times are taken for granted.

CASTILHO, R.T.L., comp., org. Catálogo de teses e dissertações do Departamento de Informática da PUC-Rio 1992-1998. 33 p. Port. E-mail:

Abstract: Lists the 160 master dissertations and 54 doctoral thesis presented at the Departamento de Informatica of PUC-Rio from 1992 to 1998.

BATISTA, T.V.; RODRIGUEZ, N.L.R. Configuração de aplicações baseadas em CORBA. 23 p. Port. E-mail:

Abstract: Recently much effort has been devoted to realize the ideal of building applications using plug-and-play software components. The development of this kind of applications separates components programming from the description of the application structure (configuration programming). For interoperability, standarization infra-strucutures offer support for heterogeneous components to work together. In this class, the CORBA standard is playing an important role. Configuration of CORBA applications is not in line with proposals in the configuration paradigm because the component interface does not describe the required services. Also, there is need for dynamic access to new components. This work describes how an interpreted language can deal with these issues, acting as a glue language between components and supporting dynamic reconfiguration of CORBA based applications.

LIMA, F.; TANAKA, A.; MELO, R.N. Integração de regras ativas e dedutivas no paradigma de orientação a objetos. 20 p. Port. E-mail:

Abstract: The use of rules in Database Systems increases language expressiveness and consequently, increases the processing power of Databases. The main objective of this work is to investigate different possibilities of integrating active and deductive rules in databases. Another approach is also presented where the Object Oriented (OO) paradigm is used initially as data model and language and later is enriched with active and deductive rules. Therefore, this work does not intend to evaluate an isolated aspect of using active rules and deductive rules, or even the utilization of OO paradigm in databases, but mainly to explore the combinations of these approaches and the possible advantages.

CUNHA, C.K.V.; QUENTAL, V.; SOUZA, C.S.; SCHWABE, D. End user programming model for workflow Web based systems. 18 p. Eng. E-mail:

Abstract: This paper presents the current stage of development of an End User Programming (EUP) model for Workflow Web Based Systems. The model is described and applied to a real system extension scenario. It is possible to see how the usage of this model allows the task of application maintenance to be shared among professional programmers and empowered end users. Our future step will be to relate this work to other EUP proposals and to describe the semiotic aspects that guide the development of this model.

LIMA, F.; CASANOVA, M.A.; MELO, R.N. Revisitando técnicas de banco de dados no contexto da Web. 12 p. Port. E-mail: 

Abstract: Database integration has been a research topic for over a decade. Although there are several proposals in the literature, the subject reemerges due to its frequent necessity. Companies have systems (legacy or not) that need to be integrated, and users often need to query disperse data sources. These examples are two common uses of database integration, still up to date. Many of the techniques already researched are still valid, however, nowadays it is necessary to consider a new environment that is becoming widespread in companies and users' realities, the World-Wide-Web (WWW). In this context, it is necessary to reevaluate the existing techniques. This work is a partial contribution to this challenge, while revisiting database techniques in the Web context.

LIMA, F.; MELO, R.N. Consultas em sistemas gerenciadores de bases de dados heterogêneos. 12 p. Port. E-mail:

Abstract: Query processing is a vital part of any Database Management System (DBMS). The presence of heterogeneity is systems that need to be integrated, insert new query processing issues that need to be addressed. Several research project were conducted in the filed of Heterogeneous Database Management System (HDBMS). More recently, due to the intense use of the Internet, the mediator architecture is being used as alternative, in this environment where the data sources can more unpredictable. This work presents several approaches, as well as their related architectures. Recent research projects using mediators is also described.

RIVERA ESCRIBA, L.A.; MENEZES, I.F.M.; CARVALHO, P.C.P. Modelagem e dinâmica de estruturas articuladas para propósitos de animação em computação gráfica. 29 p. Port. E-mail:

Abstract: Motion generation of articulated rigid bodies for computer graphics animation is a problem analyzed with the purpose of obtaning a real-time and computationally cheap animation. Its complexity lies in the control of holonomic restrictions due to the articulations. In the present work, we seek to emphasize the geometric representation of the articulated objects using hierarchical graphs, the dynamic formulation of its movements based on the Euler and Newton principles, and its recursive resolution, which allows a linear solution involving 3x3 matrices.

BERGMANN, U.; SANT'ANNA, M.; LEITE, J.C.S.P. Transformation circuit visual designer: an interface for component-based development. 31 p. Eng. E-mail:

Abstract: Transformation Circuit [1] (TC) is a new idea in the field of transformation systems. The metaphor with electrical circuit is a way of bringing the concept of components to the construction and use of software transformations and was the result of the integration between the areas of software architecture and transformation systems. The main advantage of a component based approach to transformation systems is the possibility of dealing with large numbers of transformations as well as meliorating its user-friendliness. This article gives an overview of transformation circuits and focus its attention on the tool, TCVD - Transformation Circuit Visual Designer, a special software system built to provide a graphical user interface to the use and construction of transformation circuits.

BARBOSA, C.A.M.; FEIJO, B.; DREUX, M.; BENTO, J.; MELO, R.; SCHEER, S. Distributed data model for collaborative CAD environments based on design history. 16 p. Eng. E-mail:

Abstract: This paper presents a distributed dynamic data model that aligned with the concepts of design as problem solving and design history. It is proposed a model for distributed CAD data that allows teams to work cooperatively, being able to access and change information in distributed engineering database systems, at run time. The virtual prototype is distributed over different networks with different platforms, operating systems, design teams and non-CAD users. The artifact specification is defined in a dynamic process, and a tree is used to provide user interaction to establish the object model for the sought artifact. The description regarding each object is stored as tuples in tables of conventional and heterogeneous databases. These objects are organized in such a way to allow the description of the design evolutionary aspects. Besides, the artifact properties can be associated with certain subject of interest or operational flow within the organization. Several associated activities within the design productive process (organization hierarchy, planning, process workflow, artifact specification, etc.) are integrated in the architecture of the proposed CAD environment.

SZWARCMAN, D.; FEIJÓ, B.; COSTA, M. A framework for networked emotional characters. 12 p. Eng. E-mail:

Abstract: This paper presents a framework for distributed emotional characters on a computer network and proposes innovative concepts for shared emotional state management. Firstly, behavior accuracy is defined in terms of three types of behavior (physical, procedural and emotional). Secondly, visual soundness - a concept inversely proportional to behavior accuracy - is associated with the autonomy of clones. Thirdly, the usual concept of dead reckoning is relaxed by exploring the idea of autonomy, which is the basis for networked emotional characters. The framework built on the top of Bamboo [7] can gracefully cope with reactive environments producing good levels of smooth animation, visual soundness, behavioral accurancy and collision avoidance.

PLASTINO, A.; RIBEIRO, C.C.; RODRIGUEZ, N. Uma ferramenta para desenvolvimento de aplicações SPMD com suporte para balanceamento de carga. 49 p. Port. E-mail:

Abstract: We present in this work the tool SAMBA for parallel applications development. SAMBA (Single Application, Multiple Load Balancing) supports the development of SPMD applications, offering several load balancing strategies. The tool facilitates the identification and selection of appropriate load balancing algorithms for applications under development. We describe SAMBA's functionality and architecture, as well as its programming model. We also describe the algorithms implemented in the load balancing library.

RIPPER, P.S.; FONTOURA, M.F.; MAIA NETO, A.; LUCENA, C.J.P. V-Market: a framework for agent mediated e-commerce systems based on virtual marketplaces. 13 p. Eng. E-mail:

Abstract: Software agent technology is still an emerging technology, and as such, agent based software design is stillin its infancy. Software agents have just started to be used in the e-commerce domain, and they are already starting to create a series of new possibilities to this arena. Agents can be used to automate as well as to enhance many stages of the traditional consumer-buying behavior process. This paper proposes a software engineering approach to the design of agent mediated e-commerce systems, through the definition of an object-oriented framework. The paper presents the underlying concepts and the architecture of the environment, showing how it allows developers to customize virtual marketplaces and define transaction categories on demand, incorporating many possible products and services that can be traded online.

FONTOURA, M.; HAEUSLER, E.H.; LUCENA, C.J.P. A systematic approach for framework development. 35 p. Eng. E-mail:

Abstract: This paper presents several object-oriented design techniques and discusses their ability to represent frameworks adequately. Based on the analysis of these techniques requirements for a design representation for frameworks are proposed. A design language based on extensions to UML is introduced to satisfy the requirements by representing frameworks variation points and their instantiation process as first-class citizens. These extensions are defined using the UML extensibility mechanisms: stereotypes, tagged values, and constraints. The use of the language to systematize framework implementation is discussed. An analysis of the design language is presented through two large case studies that show how it can be used to assist framework development and instantiations. The semantic of the new constructors is formally described to allow the verification of the development and instantiation activities. 

BARUQUE, C.B.; MELO, R.N. Estendendo um banco de dados relacional extensível para aplicações OLAP. 24 p. Port. E-mail:

Abstract: Nowadays, executives do not complain any longer about the lack of information. The new problem encountered by them lies on the fact that each department of an enterprise has a limited vision of it. Users are not allowed to have a holistic view of the enterprise since they can only access "their own data". A new technology is being used to integrate corporate data in such a way that users have access not only to their own data but also to other departments' data and external data as well which may influence their decisions. This is the Data Warehousing technology (DW) where all data of an enterprise is integrated in a corporate database, based on which OLAP (On-Line Analytical Processing) applications are run allowing for data analysis and business forecasting. The typical OLAP users are called Knowledge Workers. They use this technology to process Executive Information Systems (DSS). The data depicts the executive vision of the enterprise, in which data are analised from various perspectives. We propose the utilization of an extensible relational database, the POSTGRES, which allows the storage of this sort of data together with its manipulation, through the creation of specific functions.

BARUQUE, C.B.; LEITE, J.C. Auditoria em Data Warehouse. 28 p. Port. E-mail:

Abstract: Data warehousing is a high value asset, not only for its costs, but for the information that it holds. Since it is a corporate data repository from which strategic decisions are made, it is necessary to emphasize the need for safeguarding this important asset. Thus, in order to give an overview about the state of the art of DW auditing this article presents a well accepted process for the development of DW with associated control objectives; enumerates control issues with possible solutions in the light of common business requirements; presents possible security measures for DW (including the risks associated with the Internet) and suggests an audit program to ensure data quality, emphasizing that DW is a corporate asset whose risks should be kept to a minimum.

BARBOSA, A.C.P.; MELO, R.N. Usando SGBDH para acessar e disponibilizar informações na WEB. 29 p. Port. E-mail:

Abstract: The Internet, particularly the Web, has permitted to democratise the information through more practical and efficient ways for its access and divulging. As a consequence, on the Internet there's a set of distributed and heterogeneous information (Web sites) which needs to be integrated for many applications. The HDBMS is being proposed as one of the solutions to the integration of heterogeneous and autonomous sources, without the necessity of changing them. This work presents a study about the usage of HDBMS to permit the access and the availability of information in the Web.

BARBOSA, A.C.P.; TANAKA, A.K. SGBDH como integrador de informações ambientais heterogêneas. 37 p. Port. E-mail:

Abstract: The environment preservation is becoming an increasing preocupation on all over the world. The pollution and the environment destruction have been causing natural problems and accidents in many poor and rich countries. For a better planning, looking for a sustainable development, many institutions, public or not, started to collect and store environmental data and develop Environmental Information Systems (FIS). So, nowadays there is a set of distributed and heterogeneous information which must be integrated to solve many applications. Heterogeneous Database Management Systems (HDBMS) have been proposed as one of the solutions to the integration of both autonomous and heterogeneous data sources without changing them. This work presents a study about the usage of HDBMS to permit the integration and the access to the environmental heterogeneous and distributed information.

SILVA, V.T.; LUCENA, C.J.P. ContentNet; um framework para interoperabilidade de conteúdos educacionais utilizando a plataforma EDUCAUSE - IMS. 13 p. Port. E-mail:

Abstract: The World Wide Web original organization assumed that its stored information was to be read by machines without concern to the possibility of machines interpreting this information. The growth of the amount of information available on the Web made it more complex to search, have access to and to obtain information on the Web. To cope with this problem the platform IMS has been proposed. A consortium formed by academic institutions, companies and government agencies is developing the platform. The goal of the platform is to promote the viability and growth of online activities in the area of education. One of the most important activities of the consortium in Internet based learning with the possibility of  interoperability among different environments for Web-based education. Based on the porposed platform and the need for content exchange among different AuleNet servers we have developed an object oriented framework to enable the description, localization and use of educational content available in servers which are compatible with the IMS platform.

UCHOA, E.; ARAGÃO, M.P.; RIBEIRO, C.C. Preprocessing Steiner problems from VLSI layout. 20 p. Eng. E-mail:

Abstract: VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely to reduce significantly such VLSI instances. We propose a new preprocessing procedure, combining earlier ideas from the literature in such a way that they are now effective over VLSI problems. Testing this procedure over the 116 instances available in the SteinLib, we obtained significant reductions within reasonable computational times. These reductions allowed a branch-and-cut to solve 28 out of 32 open instances in the SteinLib, some with more
than 20,000 edges.

BARUQUE, C.B.; FEIJÓ, B. Um estudo sobre a integração das áreas de mineração de dados e visualização de dados. 38 p. Port. E-mail:

Abstract: Data warehousing is a high value asset, not only for its costs, but for the information that it holds. Since it is a corporate data repository from which strategic decisions are made, it is necessary to emphasize the need for safeguarding this important asset. Thus, in order to give an overview about the state of the art of DW auditing this article presents a well accepted process for the development of DW with associated control objectives; enumerates control issues with possible solutions in light of common business requirements; presents possible security measures for DW (including the risks associated with the Internet) and suggests an audit program to ensure data quality, emphasizing that DW is a corporate asset whose risks should be kept to a minimum.

FONTOURA, M.; LUCENA, C.J.P.; ANDREATTA, A.; CARVALHO, S.E., RIBEIRO, C.C. Using UML-FW to enhance framework development: a case study in the local search heuristics domain. 13 p. Eng. E-mail:

Abstract: Currently, frameworks are most commonly represented through design diagrams written in standard object-oriented analysis and design methods (OOADMs). However, these design notations do not provide elements for identifying the frameworks variation points and how the instantiation should be performed. Therefore, users have to rely on extra documentation in order to create framework instances, which is not always available. This work proposes an extension to UML that explicitly represent all the information required for framework development and instantiation. The approach is illustrated through a large real-world framework for local search heuristics.