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, Pontifcia 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



MARQUES, M.P.; LANZELOTTE, R.S.G. Banco de dados e hipermídia: construindo um meta-modelo para o projeto Portinari. 105 p. Port.

Abstract: Data bases constitutes a natural repository for storing information dealt with by hypermedia  applications. Many works have investigated how to design the database model to support an hypermedia application. Another viewpoint consists in starting from an existing database and designing hypermedia front-ends to it. In this paper, we propose an approach to design hypermedia applications using the data stored in an existing database. The approach is based on a meta-model, that integrates the two environments through their respective models, thus enabling the hypermodel evolve with the database. We apply the the proposed approach to the PORTINARI Project, concerning the most famous Brazilian painter. The approach is generic and can be used to build hypermedia interfaces to any existing database.

POTENGY, A.B.; LUCENA, C.J.; COWAN, D.D. A programming approach for parallel rendering applications. 30 p. Eng. E-mail:

Abstract: Solutions to many problems in scientific computing can be expressed as parallel computations that can be implemented on multi-processor systems or networks of powerful workstations. Design and implementation of these parallel programs usually is a complex effort which requires cooperation among the participating tasks in order to ensure correct operation and consistency. This paper introduces the the ADV/ROI design approach that combines Abstract Data Views (ADVs) and Remote Object Invocation (ROI) and applies this approach to the implementation of parallel programs using the principles of object-oriented design. The ADV/ROI approach is applied in two steps. First, a "working" sequential version of a program is implemented and then this program is converted to parallel version using a well-defined procedure involving multiple inheritance. We also demonstrate that consistency of the views of the computation are maintained as the program evolves from its sequential to parallel version. The ADV/ROI aproach is then demonstrated by showing the design and implementation of a parallel volumetric ray tracer.

PORTO, S.C.S.; RIBEIRO, C.C. A tabu-search approach to task scheduling on heterogeneous processors under precedence constraints. 26 p. Eng. E-mail:

Abstract: Parallel programs may be represented as a set of interrelated sequential tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an appropriate allocation of processors to the task of the application. Given a parallel application defined by a task precedence graph, the goal of task scheduling (or processor assignment) is thus the minimization of the makespan of the application. In a heterogeneous multiprocessor system, task scheduling consists in determining which tasks will be assigned to each processor, as well as the execution order of the task assigned to each processor. In this work, we apply the tabu search metaheuristic to the solution of the task scheduling problem on a heterogeneous multiprocessor environment under precedence constraints. The topology of the Mean Value Analysis solution package for product form queueing networks is used as a framework for performance evaluation. We show that tabu search obtains much better results, i.e. shorter completion times, improving from 20 to 30% the makespan obtained by most appropriate algorithm previously published in the literature.

HAEBERER, A.M.; BAUM, G.A.; SCHMIDT, G. Dealing with non-constructive specifications involving quantifiers. 37 p. Eng. E-mail:

Abstract: The work presented here has its focus on the formal construction of programs out of non-constructive specifications involving quantifiers. This is accomplished by means of an extended abstract algebra of relations whose expressive power is shown to encompass that of first-order logic. Our extension is the first finitary one that solves the classic issue of lack of expressiveness of abstract relational algebras first stated by Tarski and later formally treated by Maddux, Nemeti, etc. First we compare our extension with classic approaches to expressiveness and our axiomatization with modern approaches to products. Then, we introduce some non-fundamental operations. One of them, the relational
implication, is shown to have heavy heuristic significance both in the statement of Galois connections for expressing relational counterparts for universally quantified sentences and for dealing with them. In the last sections we present two smooth program derivations based on the theoretical framework introduced previously.

DURAN, J.E.; BAUM, G.A. Construccion formal de programas a partir de especificaciones en un calculo de relaciones binarias extendido. 94 p. Spa. E-mail:

Abstract: We study the formal program construction from specifications in a calculus that extends Tarski's calculus of binary relations. This paper relies on a threefold base, i.e., the language of Structured Relational Algebras, some properties of these algebras and the Calculus of Binary Relations of Tarski. Some new constructions for specifying problems and program derivations are defined. By extending Tarski's calculus with an aditional set of axioms, here presented, we obtain an abstract representable algebra. After doing a number of derivations,we find new properties valid within the Structured Algebras. The most relevant of them are choosed and proved using the axioms. Finally, we undertake the problem of proving properties for relations. The proof of invariants is analized and a proof strategy is given.

CARVALHO, S.E.R. The object and event oriented language TOOL. 18 p. Eng. E-mail:

Abstract: TOOL is a programming system designed to simplify the task of building application programs running on graphical user interface plataforms. The current version runs above Microsoft Windows, version 3.1. This report describes the programming language component of the system. This is an object and event oriented language, designed to be easily understood by conventional language programmers. In this language both synchronous and the asynchronous behavior of objects are declared in classes.

CARVALHO, S.E.R. On the reuse of applications as components. 17 p. Eng. E-mail:

Abstract: Object orientation seems to provide a welcoming framework for software reuse. This software is typically in the form of individual classes, and the reuse is typically obtained through composition and inheritance. In this paper we address the reuse of stand-alone applications, without modifications, as components in other applications. We do this in the TOOL programming system, taking advantage of its handling of asynchronous messages at the class level.

CARVALHO, S.E.R. Sobre o comportamento de objetos. 14 p. Port. E-mail:

Abstract: The procedural behavior, the only one usually available in object oriented languages, is necessary in the construction of programs. However, other well-known behavioral semantics in the conventional programming world have no counterparts in object orientation. In this paper we propose the inclusion, in classes, of operations to handle asynchronous messages, exceptions, and the production of sequences of values for loop control objects, offering examples of their uses.

JAUMARD, B.; CARNEIRO, C.C. Implication graph and quadratic 0-1 optimization. 17 p. Eng. E-mail:

Abstract: A new approach for optimization of a quadratic function in 0-1 variables, based on the solution of a sequence of nested set covering problems, is presented. Each constraint of the set covering problems is associated with a circuit in the implication graph derived from the span of the quadratic function.

CARNEIRO, L.M.F.; COWAN, D.D.; LUCENA, C.J.P. The semantics of nesting object-oriented design. 20 p. Eng. E-mail:

Abstract: It has been observed that design of complex objects such as software requires both decomposition by form (atomic objects) and decomposition by function (nesting) in order to reduce the design to a set of manageable components. However, the object-oriented design paradigm mostly supports decomposition by form. This paper uses a simple example to motivate the need for nesting (decomposition by function) and illustrates how nesting might be incorporated into a design language. We then demonstrate how the introduction of nesting into software specification and design significantly increases reusability. ADV charts, a new visual formalism, and VDM are used to provide a semantics for nesting.

GUEDES, L.C.; STAA, A.v. Um processo de re-engenharia econômico e eficaz. 17 p. Port. E-mail:

Abstract: In this paper we propose a re-engineering process. Using this process, a source program is reestructured in order to reduce maintenance costs and, simultaneously, increase its quality. Several computer aided activities are performed during this process. Roughly speaking, this process uses syntax directed reverse engineering to transport the original source code to a CASE repository. It is a basic requirement that the CASE tool be capable of generating (linearize) source code from the content of the repository. Once disponible in the repository, the CASE tool is used to re-engineer the program. The process may be adapted to several different source languages, by simply defining the grammar and lexical analysers of these languages.

DUARTE, C.H.C.; HAEUSLER, E.H. Técnicas formais e informais: um estudo sobre integração usando "statecharts". 17 p. Port. E-mail:

Abstract: Large effort has been done to find techniques which turn software development tractable. Statechart is a visual formalism that has been widely used, intending to eliminate the problems in this activity. This paper propose a different approach to solve part of these problems, by integrating this formal technique to other informal one. Either, formal rationale about the integration is presented, showing that an integration method can be established, adopting the same semantic model to assign meaning to the specification languages used.

LEITE, J.C.S.P. Eliciting requirements using a natural language based approach: the case of the meeting scheduler problem. 15 p. Eng. E-mail:

Abstract: Requirements elicitation is a process in which the software engineer works toward understanding and discovering what is expected from a planned software system. Although it is common belief that it is a hard task, several researchers are attacking the problem using different frameworks. One of these frameworks is based on the use of natural language. One strong reason for natural language based framework is to avoid the introduction of artificial languages at the beggining of the software development process. We believe that, although using this framework, it is possible to achieve more precision. Our group has been investigating one approach, called the Language Extended Lexicon (LEL), that fits in such framework. We have used the LEL mainly for eliciting application vocabulary directly from actors in an application universe of discourse. In this study we report in a variation of our approach. We show how the LEL can help the elicitation of requirements when one is departing from a written document. The approach is supported by a hypertext system specially designed for the LEL.

SANCHEZ, M.L.D.; MAFFEO, B. Ferramentas e técnicas para a modelagem da essência de sistemas de tempo-real para controle e monitoramento de processos. 25 p. Port. E-mail:

Abstract: This work presents a structure for the conceptual modelling of the real-time features in process controling systems. It uses tools and techniques of the Structured Methods area and illustrates the modelling of the essence of a system for controlling and monitoring, including exception handling (faults in the external environment), a litography by electron beam process.

GARCIA, A.C.B. Aquisição e recuperação de intensionalidade através de documentos ativos. 12 p. Port. E-mail:

Abstract: A new approach to design documentation is presented for increasing the quality of documents without increasing the designers overhead in creating it. The central idea is to create an initial design model able to generate and explain standard design decisions. Instead of recording their decisions, designers adjust the initial design model. The result is no longer a static record of the design, but an active document containing a design model able to generate explanations for a design. We have implemented a software prototype for the active documents approach in the domain of preliminary design of Heating, Ventilation and Air Conditioning Systems (HVAC). The prototype test results indicate that the approach is feasible. The results also indicate that active documents can be used beyound
documentation as a tool for studying design process.

SOARES, L.F.G.; CASANOVA, M.A.; RODRIGUEZ, N.L.R. An open hypermedia system with nested composte nodes and version control [Title in Portuguese: Um modelo conceitual hipermídia com nós de composição e controle de versões] 20 p. Eng. E-mail:

Abstract: This paper describes a model for hypermedia documents which includes facilities for structured organization of nodes and for version control. This model is currently being used as a basis in the implementation of a development tool for local and distributed hypermedia applications. The layered architecture of this tool grants the user access to distinct levels of abstaction; it also allows the system to maintain compatibility with the MHEG proposal for hypermedia object interchange.

MARTINS, I.H. Uma proposta para tratamento de exceções em uma linguagem orientada a objeto. 29 p. Port. E-mail:

Abstract: This article discusses a proposal and specification for Exception Handling (EH) in object oriented languages. The idea is to adapt conventional mechanisms of EH to the basic principles of object orientation. The proposal has two main goals. One of them is to respect the philosophy of classes and methods so that the EH resource can be easily absorbed by the user. Another goal is to provide flexibility in what refers to the scope of the handler (generic or specific), to the level of coupling between handler and code (instructions or methods), and to the moment of definition of the handler (in modeling time of the object or in programming time).

CARVALHO, S.E.R. Asynchronous behavior in the TOOL programming system. 32 p. Eng. E-mail:

Abstract: It is expected that a large portion of software systems to be constructed in this decade will involve object orientation, message passing and graphical user interfaces. In this paper we present an object and event driven programming system, TOOL, which takes full advantage of object orientation, by considering the handling of asynchronous messages as part of object bahavior. In this way low-level and error prone concerns with message queues and centralized handling routines are eliminated. Moreover, we can achieve full decoupling between interface and implementation in a GUI application, and reuse stand-alone applications as components in other applications.

LEITE, J.C.S.P. Working results in re-engineering. 16 p. Eng. E-mail:

Abstract: We view software re-engineering as a new approach to software maintenance. Instead of performing maintenance at the source code of systems, we work on high level abstractions. From these abstractions we proceed in a forward manner reusing the available implementations, when it is the case. As such, we view re-engineering as centered on design recovery. We have been working on methods for re-engineering and applying them to real cases. Our studies are centered on the idea of using JSD as a way of casting the recovered design. We worked with two small systems and a complex one. Our objective here is to highlight our approach, report on what has been done and point out what was learned.

GARCIA, A.C.B.; STEFIK, M.J.; HOWARD,H.C. Supporting design collaboration through active documents. 19 p. Eng. E-mail:

Abstract: Design is a cooperative activity that requires the participants to negotiate over design specification. Negotiation requires understanding of the decisions made by each participant. Static design documents unsuccessfully play the role of communicating rationale among design participants. In this paper, we present a new approach to documentation - active design documents (ADD). Active documents allow designers to communicate their design intent to other design participants, supporting negotiation on design requirements and cooperation during design. We describe the approach and present an implemented architecture for building active documents. We tested the architecture for the realistic domain of preliminary design of Heating, Ventilation and Air Conditioning Systems.

HERTZ, A.; JAUMARD, B.; RIBEIRO, C.C.; FORMOSINHO FILHO, W.P. A multi-criteria tabu search approach to cell formation problems in group technology with multiple objectives. 23 p. Eng. E-mail:

Abstract: Group technology techniques are now widely used in many manufacturing systems. Several algorithms have been proposed for the optimal design of efficient manufacturing cells. The cell formation problem must take into account several objectives: the number of bottleneck operations, the number of bottleneck machines and/or parts, the intercell flow, the intracell workload balancing, the subcontracting costs, the machine duplication costs, and the workload of the busiest machine or cell, among others. In this paper, we propose a multi-criteria methodology for solving the cell formation problem with multiple objectives. This approach is based on the use of the tabu search heuristic for solving a sequence of single-objective, multi-constrained subproblems, in which each objective is taken and optimized in turn, following their order of relative importance. The subproblems are tackled by a strategic oscillation strategy. Computational results concerning an application to a bi-criteria problem are reported for instances with up to 100 machines and 1000 parts.

de SOUZA, C.S.S.; DIAS, M.C.P.; GARCIA, L.S.; BASILIO, M.P. Semântica lexical em linguagens pseudo-naturais de interface. 18 p. Port.E-mail:

Abstract: This paper proposes an alternative to represent and process lexical semantic information of utterances in pseudo-natural language, occurring in dialogues between users and knowledge-based systems. The proposal is presented within the framework of Project LINX, where the formulation of users utterance may be supported by menu selection, and system reasoning is supported by a Natural Deduction Theorem Prover acting upon a logic knowledge base. The theoretical approach to lexical semantics, applying to both interpretation and generation of pseudo-natural language utterances is that of Jackendoff's Conceptual Structures. It offers important computational advantages, which are discussed in terms of the distribution between linguistic processing and logic proof, of the specificity of the notion of semantics in the LINX environment, and the types of methods that can be derived for the construction of both the knowledge base and the interface vocabulary.

de SOUZA, C.S.; CUNHA, M.O. Animação de imagens fractais e representação de processos em linguagens visuais. 15 p. Port. E-mail:

Abstract: The expression Visual Languages has been used in a variety of senses. In this paper we explore the possibilities of visualy representing computer processes at the user interface level by means of animated fractal images. Although the selected images are not iconic (i.e. they do not directly evoke the meaning of processes they represent), important abstractions are shown to be systematically related to perceptual changes in form. We discuss the implications of such abstractions for Visual Languages, both in terms of human-computer interactive codes and of declarative representation languages supporting animation effects.

de SOUZA, C.S. General help systems for network resource discovery. 12 p. Eng. E-mail:

Abstract: Wide area computer networks offer users a large volume and variety of resources that can help them to solve many kinds of daily problems in their work environment. However, the existence, let alone the contribution, of such resources is generally ignored by networkers. This work discusses usability issues as perceived in the INTERNET, and presents a research project underway, relative to General Help Systems (GHSs) - an intended means to narrow the distance between users needs and network resources.

SILVA, M.T.M.P.; FUKS, H. Um esboçoo de cálculo de influência de diálogos na escolha entre propostas de ação. 40 p. Port. E-mail:

Abstract: This work outlines an influence calculus for argumentative dialogs for choosing a course of action in computer supported cooperative work. Each possible action is examined when one of the parts questions  it. This triggers an argumentative dialog. Commitments to the issued arguments and their backings together with their relative weights are established as the dialog unfolds. These weights should describe the influence that each locution has in the evaluation of the course of action. The aim of such representation is to help the parts to clarify their points of view and to support the evaluation of the
best course of action.

STAA, A.v. Critérios para a avaliação da coesão. 17 p. Port. E-mail:

Abstract: A set of quality control criteria is presented. These criteria evaluate the quality factor cohesion. The criteria may be used whenever representations having several levels of abstraction are built. The criteria may be used with respect to several representation languages, not just with respect to structured design. When working with elements at different levels of abstraction a solution of each abstract element must be provided. This solution is defined at a lower level of abstraction. Furthemore, this solution must also satisty several relations with respect to the abstract element it intends to solve. The solution must also satisfy several structural properties. The objective of the quality control criteria is to provide a means to objectively decide wether a given solution is good or not.

STAA, A.v. Projeto TOTEM: meta-ambiente de desenvolvimento de software definição do projeto. 36 p. Port. E-mail:

Abstract: TOTEM's main objective is to contribute to the enhancement of the current practice of software engineering. In order to achieve this goal, a software engineering meta-environment will be built. With this meta-environment specific computer aided software engineering environment instances can be generated. Each of these instances provides support to a selected set of development, maintenance and/or management activities. The collection of instances supports the cooperative work of development teams. Each instance may be adapted to the specific needs of the object system to be developed and to the needs of the people using the set of instances. In adition to instantiating production environments, the TOTEM meta-environment will also provide support to experimental research in Software Engineering. This document defines the requirements of the TOTEM meta-environment. It defines also the basic architecture of the meta-environment.

STAA, A.v. Uso de instrumentação para a construção de programas confiáveis. 11 p. Port. E-mail:

Abstract: In this paper we discuss the implementation of reliable programs using "almost" reliable components. The implementation method contributes alsoto the productivity increase when compared to traditional implementation based on testing and debugging. The implementation method is based on (i) the use of design and programming tools aiming at the construction of "almost" correct programs, (ii) the use of robust and auto-verifiable data structures, (iii) the inclusion of executable assertions into the programs, (iv) the use of co-routines to verify the structural correctness of the data structures during idle cycles.

FRIAS, M.; BAUM, G.; HAEBERER, A.M.; VELOSO, P.A.S. A representation theorem for fork-algebras. Eng. E-mail:

Abstract: Not available.

FEIJO, B.; LUCENA, C.J.P.; BENTO, J. A formal approach to design based on cognition. 17 p. Eng. E-mail:

Abstract: Most of the current general design methodologies do not capture the cognitive nature of design. The present paper proposes an approach based on an evolving theory of the design process inspired on a cognitive interpretation of design. This approach provides a pragmatic guideline for developing and evaluating design methodologies used in connection with CAD and CASE systems. Furthermore, it seems that several current design models are interpretations of the proposed theory.

de SOUZA, C.S. Testing predictions of semiotic engineering in HCI. 10 p. Eng. E-mail:

Abstract: This paper presents an overview of Semiotic Engineering and, with support of results achieved in a small-scale experiment, proposes a method for testing predictions derived from semiotically-motivated interface design principles. Semiotic Engineering is a theoretic approach we have proposed for the construction of user interface languages, within a perspective about HCI according to which systems are themselves complex messages sent from designers to users. The original semiotic theory from which our approach draws its fundamentals is Umberto Eco's Theory of Sign Production. The long-range goal of Semiotic Engineering is to contribute for a theory of design in HCI. Thus, the fundamental principles we have proposed must be experimentally tested as a means to evaluate the theory. Preliminary test methods and results reported here suggest methodological procedures for experimental studies in Semiotic Engineering.

VELOSO, P.A.S.; HAEBERER, A M. On fork algebras and program derivation. 35 p. Eng. E-mail:

Abstract: Fork algebras provide a useful basis for relational calculi for program derivation; they arise as extensions of relational algebras with a new operator, called fork, which anables the introduction, by definition, of projections. In this paper we examine some fundamental issues concerning fork algebras, presenting the proofs of expressiveness and representability and discuss and illustrate their importance for program derivation.

CARVALHO, S.E.R. Specifying object behavior. 16 p. Eng. E-mail:

Abstract: The procedural behavior, the only one usually available in object oriented languages, is necessary in the construction of programs. However, other well-known behavioral semantics in the conventional programming world have no counterparts in object orientation. In this paper we propose the inclusion, in classes, of operations to handle asynchronous messages, exceptions, and the production of sequences of values for loop control objects, offering examples of their uses.

CARVALHO, S.E.R. Coroutine semantics in the TOOL programming environment. 18 p. Eng. E-mail:

Abstract: In this paper we discuss two situations, in object oriented programming, where the semantics of coroutines is useful in the implementations of loop iterators and of dynamic data structures navigators. In both of these operations the receiving object is a loop control object. Iterators are applied to produce, outside of the loop's environment, the next value for the loop control object; navigators are applied to indicate, outside of the loop environment, the next element in a dynamic data structure.