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


LABER, E.S.; PORTO, F.A.M.; VALDURIEZ, P.; GUARINO, R. Cherry picking: a data-dependency driven strategy for the distributed evaluation of expensive predicates. 24 p. Eng. E-mail:

Abstract: In this paper, we address the problem of optimizing distributed queries involving expensive predicates. We propose a novel approach, called Cherry Picking (CP), based on the modeling of data dependencies between the expensive predicates' input values as weighted bipartite graph. We propose three CP algorithms that select the vertexes in this graph to be evaluated by the expensive predicates that minimize the query execution cost: a Greedy algorithm, a Minimum Balanced Cover(MBC) algorithm and a variant called MBC* which runs in polynomial time. In order to analyze the optimality of these algorithms, we propose a new quality metric. We prove that MBC has quality 2 and that no other deterministic algorithm can yield quality smaller than 2, thus proving its optimality. We implemented these three algorithms as well as existing pipeline and hybrid strategies. Our experiments suggest that CP approach allows a considerable gain in performance compared to the Pipelined approach and that the CP Greedy algorithm, due to its simplicity and nice performance, is a very good candidate to be considered for implementation in query execution engines that deal with expensive predicates.

MILIDIÚ, R.L.; PESSOA, A.A.; LABER, E.S. Complexity of makespan minimization for pipeline transportation of petroleum products. 13 p. Eng. E-mail:

Abstract: PTP is a new model for the problem of transporting petroleum products through pipelines with no due dates. This model uses a directed graph G, where arcs represent pipes and nodes represent locations, and a set L of transportation orders. Since pipelines must always be full, we define a subset F c L of further orders that do not need to reach the corresponding destination nodes, being used only to move the pipeline contents. The problem of finding a feasible solution to PTP is known to be NP-hard, even if G is acyclic. The Synchronous PTP(SPTP) is a special case of PTP where all orders in F are initially stored at nodes. In this paper, we analyze the complexity of finding a minimum makespan solution to SPTP. This problem is called the SPTMP. We prove that, for any fixed e>0, there is no n1-e- approximate algorithm for SPTMP unless P = NP, where n is the input size. This result also holds if the graph G is both planar and acyclic.

CARASSO, F.; STAA, A.v. Utilizando JNI para adicionar implementação nativa C ou C++ a programas JAVA. 32 p. Port. E-mail:

Abstract: The JAVA programming language has been widely adopted for its portability and user friendliness. However it is quite inefficient when dealing with compute bound operations. There are a couple of ways to get around this drawback, one of them deals with the utilization of native code. This report presents a detailed explanation of how to add native code to JAVA programs by using the Java Native Interface, or JNI. Most of the JNI specifications are examined in this report and examples were created and tested to illustrate them.

PAULA, M.G.; SILVEIRA, M.S.; BARBOSA, S.D.J. Sistema de explicação para o processo de matrícula da pós-graduação do Departamento de Informática da PUC-Rio. 28 p. Port. E-mail:

Abstract: In this work we propose an explanation system to the registration process in the Informatics Department at PUC-Rio. The main idea is to provide the students with information about registration in graduate courses, considering each student's academic and administrative status and potential doubts, in order to personalize the given answer(s). This approach may be considered an evolution on FAQ systems because the student may ask further questions about the given answers, according to his/her needs, contextually unfolding the knowledge required to make adequate decisions.

SILVA, V.T.; LUCENA, C.J.P. Multi-level role modeling in multi-agent systems. 14 p. Eng. E-mail:

Abstract: This paper proposes a method to help discover the agents that will be part of a multi-agent system based on the definition of the system. This method is based upon the decomposition and the system goals together with the decomposition and specialization of the system into entities. The goals are associated with the entities, which play roles by trying to achieve the goals and enter into relationships with other entities. To help and validate the refinement process, the method describes rules that ensure how the goals, entities, roles and relationships defined in a certain stage of refinement will appear in the subsequent stages of the process.

MILIDIÚ, R.L.; LUCENA, C.J.P.; SARDINHA, J.A.R.P.; RIBEIRO, P.C. An object-oriented framework for building software agents. 10 p. Eng. E-mail:

Abstract: Agent technology is a new approach of Distributed Artificial Intelligence to implement autonomous entities driven by beliefs, goals, capabilities and plans, and other agency properties such as adaptation, interaction, and mobility. Software agents are the focus of considerable research in the artificial intelligence community, but not much has been done in the field of software engineering. In this paper, we present an object-oriented framework for building software agents in a distributed environment. The design of the framework also allows an easy mapping of the models developed in the analysis and design phase of the Gaia Methodology to object-oriented code. We belive that object-oriented framework technology can reduce not only the development time but also the complexity of implementing multi-agent systems. We present an instantiated application that uses this framework to illustrate an implementation.

LUCENA, C.J.P.; FUKS, H. Tecnologias de Informação Aplicadas a Educação (TIAE): manual do aprendiz. 13 p. Port. E-mail:

Abstract: This paper presents the methodology used in the Information Technology Applied to Education course, a course delivered through the Internet. The course is about the application of information technology to education. The course is being delivered using the AulaNet environment, a groupware for the creation, participation and maintenance of Web-based courses.

GARCIA, A.F.; CASANOVA, M.A. A fault-tolerance in distributed tuplespaces. 20 p. Eng. E-mail:

Abstract: The tuplespace data model is widely recognized for serving as a foundation for data exchange and/or event coordination in distributed systems. In fact, in the last couple of years, the tuplespace paradigm experienced a renaissance due to its suitability for developing distributed Internet applications. However, this model is originally based on a centralized scheme, being exposed to classical failures of centralized systems, such as single-point failures and bottleneck situations, all of which conflicts with some of the stringent requirements of distributed systems: fault-tolerance and scalability. So, there is a need for providing the tuplespace data model with fault-tolerance and scalability using replication techniques, i.e., distributing replicas of tuplespaces over different tuplespace servers. Enterprise TSpaces (ETS) is a further development of the stand-alone version of TSpaces that provides TSpaces with fault-tolerance in loosely coupled systems. The level of fault-tolerance of a ETS tuplespace can dynamically and independently be adjusted by modifying the number of replicas. In this context, the goals of this work are: (i) presenting the tuplespace data model, (ii) identifying the problems in replicating tuplespaces, (iii) surveying the techniques for dealing with such replication problems, and (iv) presenting the model ETS for fault-tolerance distributed tuplespaces.

SILVA, A.C.; CARVALHO, P.C.P.; GATTASS, M. Visualization of density variation in lung nodules. 13 p. Eng. E-mail:

Abstract: We proposed a method for visualize lung nodule, in order to emphasize their internal structures. This provides an additional tool for diagnosis, which is traditionally based on the analysis of shape, growth and location. The method is divided into three stages: the first stage is semi-automatic segmentation, using the region-growing algorithm; the second stage, based on the previous segmentation, identifies the internal structures of the nodule using moment theory to determine several thresholds; finally, in the third stage, to help visualizing these structures, a pseudocolor is associated to each threshold determined in the previous stage. The tool developed is under test, undergoing clinical evaluation, and its initial results are promising.

CÔRTES, S.C.; PORCARO, R.M.; LIFSCHITZ, S. Mineração de dados - funcionalidades, técnicas e abordagens. 35 p. Port. E-mail:

Abstract: The subject of the study is Data Mining, with emphasis on its functionalities (results), techniques and application strategies. We underline the importance of data mining as part of a larger research process called Knowledge Discovery in Database (KDD), for which is presented the methodology for preparation and exploration of data, interpretation of results and assimilation of mined knowledge. Data mining is presented in the context of business intelligence; its forms of presentation and the difficulties in implementation in corporations and some applications suitable for the use of data mining as well as their fields of research are discussed.

CÔRTES, S.C.; LIFSCHITZ, S. Sistemas de gerência de banco de dados baseados em agentes para um ambiente de computação móvel. 30 p. Port. E-mail:

Abstract: Agent-based databases enable the development of Database Management Systems (DBMSs) that may be configured and extended to give support to new data storage and retrieval requirements. For database management systems to be used in a mobile computing environment, the properties of reusability, autonomy, interaction and mobility can be obtained by the use of a software agent. This paper presents a proposal for a layered architecture in a mobile computing environment. The focus of the architecture is on the use of software agents in the server layer of the database, using a framework for the construction of the management system that will include the functionalities necessary for the mobile computing environment. A detailed discussion of DBMS architecture is also presented.

GONI, J.L.; FERNANDES, M.C.P.; LUCENA, C.J.P. e-Learning e a Web semântica. 18 p. Port. E-mail:

Abstract: The objective of this work is to propose a tool based in agents, denominated Web Semantic Search (WebSS), using the structure of the semantic Web, where through ontologies generated by the Protege-200 tool, it will be possible to recover learning contents in AulaNet servers, according to the granularity proposed by the ContentNet framework. It is presented an Analisys Model of the MESSAGE Methodology (methodology for engineering systems of software sgent), wich is an agent-oriented Software Engineering methodology, that extends the current techniques of object-oriented software development to simplify and to formalize the process of developing a multi-agent system.

GONI, J.L.; MILIDIÚ, R.L. Agentes de software para auxiliar ao professor na busca de conteúdos educacionais no padrão IMS. 19 p. Port. E-mail:

Abstract: With the growth of the amount of data available on the Internet, the use of software agent for information search and treatment is an option. In Web-Based Education the patterns defined by IMS for interoperability of education contents are a reality. Starting from the experiences and uses demonstrated by the literature, types of agent and their application in the search and treatment of data in the Web are presented. This work also presents a multi-agent system that favour the interoperability of contents in distance education, helping the teacher in the search in IMS-compliant servers.

GONI, J.L.; FUKS, H. Comparação de ambientes de ensino na Web baseados em plataforma IMS a partir dos papéis dos atores envolvidos. 24 p. Port. E-mail:

Abstract: A way to verify the several techniques now used in Distance Education on the Web consists in the analysis of each role a user plays in the participation on a management environment. To evaluate the practical viability of those environments, through a comparative analysis, we appoint the appropriate use of the Internet technology. It was also considered the pedagogic, technological and organizational aspects. The comparisons were made with environments that follow the IMS specifications. Based on these comparisons, some suggestions for the evolution of the AulaNet environment are shown considering each users' roles.

AYRES, F.V.M.; PORTO, F.A.M.; BARBOSA, A.C.P.; MELO, R.N. Um framework para construção de máquina de execução de consultas. 15 p. Port. E-mail:

Abstract: The integrated access to web published information allows for offering new services not initially foreseen by the individual web publishers. This type application requires the distributed execution of queries over the web. Although very promising, this strategy suffers from serious performance problems due to the unpredictability of the access time to the data sources.This work identifies and analysis query execution characteristics that should be supported by a flexible execution engine. We propose and implement a software framework that provides for the instantiation of different query execution engines. In particular, the framework instantiates an adaptive query execution engine that supports Web integration applications. This framework is also integrated to the CoDIMS environment (Configurable Data Integration Middleware System).

RENTERIA, C.J.; HAEUSLER, E.H.; VELOSO, P.A.S. NUL: dedução natural para lógica de ultrafiltros. 28 p. Port. E-mail:

Abstract: Ultrafilter logic is an extension of first order logic that uses a new quantifier to express a meaning of "almost all", that is, to express sentences like: "Almost all elements of our universe have the property P". Such a logic had previously been presented only in an axiomatic version. We give here a natural deduction version, wich is correct, complete and normalizable.

FUKS,H.; RAPOSO, A.B.; GEROSA, M.A.; LUCENA, C.J.P. O modelo de colaboração 3C e a engenharia de groupware. 16 p. Port. E-mail:

Abstract: This paper introduces an engineering approach based on the 3C model (Communication, Coordination and Cooperation) to the design and implementation of collaborative systems. Initially, the 3C model is studied by means of a detailed analysis of each one of its three elements. Then, a case study presents the application of the theoretical model to the development of a learningware environment and to the methodology of a web-based course. The main goal of the paper is to show the human aspects of the 3C model as a means to model collaborative activities and as an attempt for the formulation of Groupware Engineering.

SILVA, G.M.H.; HAEUSLER, E.H.; VELOSO, P.A.S. Constructive program synthesis in imperative language using intuitionist logic and natural deduction. 19 p. Eng. E-mail:

Abstract: We present a method to extract programs from constructive derivations, which is known as constructive synthesis or proof-as-program. This method comes from the Curry-Howard isomorphism and is based on the fact that a constructive proof for a theorem, which describes a problem, can be seen as a be description of the solution of a problem, i.e., algorithm. In contrast with other constructive program synthesizers, in our work, the program (in an imperative language) is generated from a proof in many-sorted intuitionist logic using, as deductive system, the Natural Deduction. In addition, we provided a proof that the program generated is a representation of the solution for the specified problem by the theorem, in any theory that describes the data types used.

GARCIA, A.F.; LUCENA, C.J.P.; OMICINI, A.; CASTRO, J.; ZAMBONELLI, F. Software Engineering for Large-scale Multi-agent Systems - SELMAS 2002: workshop report. 19 p. Eng. E-mail:

Abstract: This paper report on the First International Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS 2002) held in Orlando, Florida, USA, May 19, 2002, as part of the International Conference on Software Engineering (ICSE 2002). The main purpose behind this workshop is to share and pool the collective experience of people, both academics and practitioners, who are actively working on software engineering for large-scale multi-agent systems. The call for papers elicited about 20 submissions of wich 17 papers were accepted for publication in the workshop proceedings and 12 papers were accepted for presentation. A selected set of workshop papers and invited papers are going to appear in the book Software Engineering for Large-Scale Multi-Agent Systems (LNCS, Springer, 2002). The workshop consisted of an opening presentation, several paper presentations that were organized into three distinct sessions, and a panel. During the workshop we informally reviewed ongoing and previus work and debated a number of important issues. The SELMAS'02 Web page, including the papers and the electronic
version of this report, can be found at <>. We begin by presenting an overview of our goals and the workshop structure, and then focus on the worshop's technical program.

MACEDO, L.M.; FURTADO, A.L. PlotDBase-integração de narrativas e dados de aplicativos na forma de enredos para descoberta de conhecimento. 23 p. Port. E-mail:

Abstract: Data information affecting people and companies may be grouped as narratives of real situations and converted into plots, composed by characters or actors, objects or resources, events or conditions, sequence of actions, goal inference rules and constraints. Plots can be described in format of logical predicates in defined clauses, as used by Prolog. In this paper we propose the creation of PlotDBase, a relational database of plots, which contains the models and instances, composed by sets of terms and their relationship, based on criteria and properties defined by expert users. The data used to build plots are picked up from application databases and several narratives. The PlotDBase is useful to integrate specific application systems and non-standard narratives. We propose the development of a tool that has features for data entry, data preparing and data processing as: selection, comparison and grouping of parts of several plots, automation transferring data from databases to plots, search for standards in action sequences, argument values in functions and rules, file data preparation to be used by Prolog programs and KDD programs.

FELIX, M.F.; HAEUSLER, E.H.; SOARES, L.F.G. Validating hypermidia documents: a timed automata approach. 15 p. Eng. E-mail:

Abstract: This paper presents a formal approach to validating hypermedia documents, a case of real-time and reactive computing application, aiming to extend these ideas to the contex of architectural design. The main aspect of hypermedia validation concerns to the so-called temporal consistency analysis problem: a document is consistent if it is possible present it in a way that all the event synchronization constraints can be fulfilled. The validation technique consists in providing formal semantics to hypermedia documents via network of timed-automata, in a compositional way. Therefore, obtained a behavioral model of the document, we can pass to the model-checking phase. The consistency analysis consists on to formulate an adequate set of temporal logic formulas that will be checked against to the automata model. The specifications of the hypermedia documents that we are written using the modeling concepts of NCM (Nested Context Model), a conceptual model to hypermedia documents, and we choose UPPAAL as the model-checking tool to implement the our hypermedia validation model. This work as well constitutes a preliminary investigation, via a case study, about how we can integrate formal validation, using model-checking techniques, with software architecture design.

AMARAL, F.N.; HAEUSLER, E.H.; ENDLER, M. A real-time specification language. 12 p. Eng. E-mail:

Abstract: A specification language for real-time software systems is presented, along with a model-theoretic semantics. Notions from Category Theory are used to specify how the components of a system should interact. The potential role of the proposed language in the search for interoperability of specification formalisms is briefly discussed.

MAMANI MACEDO, N.A.; LEITE, J.C.S.P.; MACEDO-SOARES, T.D.L.v.A. Building a strategic oriented corporate memory. 28 p. Eng. E-mail:

Abstract: This paper shows a porposal for building corporate memory based on a general architecture. It has three layers: sources, middleware and repositories. First, we create an enterprise model, named Basic Framework (BF), with a view to building a Strategic Corporate Memory (SCM). Second, we use ontology and multi agents system as a means to organize our proposal. The BF is the main component, where we store relevant information for the organization extracted from legacy systems, databases, Internet sites or human-beings. This conceptual enterprise model is based on management theory and uses constructs from, both positioning and resource-based views of strategic analysis, together with function analysis and total quality management. We also stress the evolutionary aspect of the SCM by relying on the configuration management concept of baseline.

SILVA, O.; GARCIA, A.; LUCENA, J.C.P. The reflective blackboard pattern. 21 p. Eng. E-mail:

Abstract: Software architectures of large multi-agent systems (MASs) are inherently complex and have to cope with an increasing number of system-wide properties and their corresponding control policies. So with the increasing size and complexity of these systems a more sophisticated software architectural approach becomes necessary. In this context, we propose the Reflective Blackboard architectural pattern, which is the result of the composition of two other well-knowm architectural patterns: the Blackboard pattern and the Reflection pattern. The proposed pattern provides, early in the architectural design stage, the context in which more detailed decisions related to systemic properties and associated policies can be made in late stages of MAS development. The pattern allows a better separation of concerns, supporting the separate handling of control strategies by means of the computational reflection technique. Moreover, these control activities are handled independently from the application data agents, providing a better architecture for real-life multi-agent systems. An electronic marketplace architecture, with the goal of interconnecting providers and consumers of goods and services to find one another and transact business, electronically, is assumed as a case study through the paper to clarify all the expressed concepts and to show the applicability of our proposal.

CARVALHO, G.R.; STAA, A.v. Estudo e análise do processo de desenvolvimento e de ferramentas associados a ebXML. 37 p. Port. E-mail:

Abstract: In the electronic commerce era there are lots of initiatives to promote the integration of processes and enterprises, processes and environments for integration of services, applications and enterprises appear as a promising area of study in software engineering. Among the business-oriented processes standards initiatives is ebXML. This paper purpose is to evaluate the ebXML proposal and some modeling tools that propose some functionality for the effective use of ebXML proposal as an e-business development process.

COELHO, T.A.S.; ENDLER, M. Ambientes de suporte à colaboração em redes móveis. 50 p. Port. E-mail:

Abstract: This work discusses some issues related to collaborative systems, and specifically, some questions ralated to Workflow Management Systems for mobile environments. The concept of awareness, the concurrency control method, and the problems deriving from mobility and disconnections are discussed. Besides a comparison among several Worflow Management Systems, such as Exotica, RainMan, CoAct and WorkToDo, this report contains a proposal of an architecture for a Workflow Management System for wireless mobile networks. In this proposal users are physically distributed and only establish connection with the workflow server when they need to send or to receive data. According to the proposed architecture, in addition to one central coordinator, there may be several secondary coordinators, which are able to delegate tasks to other users under their control. In this architecture, the concept of locking tasks is avoided and tasks may be replicated for the execution by many users, aiming to decrease the workflow execution time. The main contribution of the proposed architecture are the ability to replicate workflow tasks and the optimistic concurrency control policy, which provide means for avoiding that workflow users block each other due to pending executions of casually dependent tasks.

LEITE, M.C.; LUCENA, C.J. Introducing object circuits. 18 p. Eng. E-mail:

Abstract: In this paper, we introduce the concept of object circuits, a programming technique which addresses traditional object-oriented programming through the electric circuit's metaphor. We motivate the discussion by studying the usefulness of object circuits on the specific domain of modeling & simulation, and conclude by generalizing its applicability to other research areas.

COELHO, T.A.S., CASANOVA, M.A. Linguagens para especificação de workflows. 43 p. Port. E-mail:

Abstract: This work presents a brief discussion about some languages for workflow specification found in the literature: the WIDE Project's language, that aims at executing distributed workflows; the BPEL4WS language, based on the concept of Web services; and the XRL language, for the management of eletronic commerce transactions. After analysing these languages, this work proposes an extension of the XRL language. The extension proposed meets the requirements of the emergency plan description for the InfoPAE Project, a partnership between TecGraf and Petrobras. The workflow specification language proposed is based on XML and assumes that a workflow can be composed of many other subworkflows, which can be executed in a distributed and, sometimes, independent manner.

BRANDÃO, A.A.F.; LUCENA, C.J.P. Uma introdução à engenharia de ontologias no contexto da Web semântica. 16 p. Port. E-mail:

Abstract: The semantic Web is an evolving research area which strongly depends on ontologies. When developing applications in the semantic Web, one needs to pay attention to the ontologies they will use. Some ontology description languages are not fitted to some kinds of applications and the interoperability is not a common feature in most of the tools to develop ontologies, which may prevent the importation of existing ontologies. Because of that, several research groups develop their own ones. In this work we survey several definitions of ontology for the semantic web, describe some ontology development methodologies and relate a case study about developing an ontology for a semantic Web-based application, which will generate academic reports using semantic Web content from a Web site.

SILVA, V.T.; GARCIA, A.F.; BRANÃO, A.A.F.; CHAVEZ, C.v.F.G.; LUCENA, C.J.P.; ALENCAR, P.S.C. Theoretical foundations for agents and objects in Software Engineering. 21 p. Eng. E-mail:

Abstract: Agent-based software engineering has been proposed in addition to object-oriented software engineering for mastering the complexity associated with the development of large-scale distributed systems. However, there is still a poor understanding of the interplay between the agent and object notions from a software engineering perspective. Moreover, the many facets of agent-based software engineering are rarely used in the various phases of the software development lifecycle because of the lack of a comprehensive framework to support consistent application of its core abstractions. In this context, this paper presents TAO, an evolving innovative conceptual framework based on the agent and object abstractions, which are the foundations for modeling large-scale software systems. The conceptual framework provides support for decomposing large-scale software systems as organizations of passive components, the objects, and autonomous components, the agents, with each of these elements playing roles to interact with each other and to coordinate their actions in order to fulfill system goals.

FURTADO, A.L.; CIARLINI, A.E.M. Cognitive and affective motivation in conceptual modelling. 30 p. Eng. E-mail:

Abstract: A proposal is presented towards the extension of conceptual models of information systems, in order to allow specification and simulation of the behaviour of agents with an adequate degree of realism. Our method is mainly based on rules to infer the goals of agents from situations holding at given states. In this paper, we argue that the rules should take into account both cognitive and affective characteristics, as can be conveyed, for the various agents, by their individual profiles and current internal states. Such characteristics should also influence the choice of strategies to handle goal interferences in multi-goal/multi-agent environments.

CUNHA, L.M.; LUCENA, C.J.P., eds. PRONEX MOBILE 2002 - frameworks e tecnologia de software: métodos, ferramentas e soluções de domínio específico. 61 p. Port. E-mail:

Abstract: The PRONEX 2002 workshop tooke place in the Computer Science Department at PUC-Rio in December, 17th. Masters students and PhD candidates presented the progress of their research projects. In this paper you will find some short articles about the work developed by the students in cooperation with their advisors and cooperating researchers. The volume includes work-in-progress and also abstracts of concluded theses.