Monografias em Ciência da Computação
2001
ABSTRACTS
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
bib-di@inf.puc-rio.br
Last update: 18/DECEMBER/2003
[MCC01/01]
CASANOVA, M.A.; LEMOS, M. Optimized buffer management for sequence comparison in molecular biology databases. 21 p. Eng.
E-mail: casanova@inf.puc-rio.br
Abstract: Comparing sequences - nucleotide, aminoacid - is one of the
basic operations every Molecular Biology database must support. There
are two well known sequence comparison algorithms, FAST and BLAST, the
latter being more popular (and many variations thereof). We propose in
this paper a buffer management strategy to optimize the simultaneous
execution of a set P of BLAST processes. The essence of the strategy
is to partition P into subsets P1,...,Pn and to allocate a separate
set Bi of buffers to each partition Pi. All sequences in the database
will then be cycled through the buffers in Bi so that all BLAST
processes in Pi will perform their sequence comparison synchronously. We first
show that finding the partition that minimizes overall
process delay is NP-complete. We then describe a heuristics that is
computationally feasible and yet obtains a near optimal solution.
[MCC02/01]
VELOSO, P.A.S. On some meanings of 'generally' and 'rarely'. 11 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine some meanings of 'generally' and 'rarely'. The
primary motivation is a precise approach to assertions and arguments
involving such vague notions, which occur often both in ordinary
language and in some branches of science. We focus mainly on the
intended meanings of such assertions by analysing some basic
intuitions and their underlying presuppositions. This leads to
distinguishing various versions according to their behaviour.
[MCC03/01]
VELOSO, P.A.S. On some postulates for 'generally' and 'rarely'.
16 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine some postulates for 'generally' and 'rarely'.
The primary motivation is a precise approach to assertions and
arguments involving such vague notions, which accur often both in
ordinary language and in some branches of science. Analysis of some
basic intuitions and their underlying presuppositions leads to
various distinguishing versions according to their behaviour. We
then propose some postulates aiming at characterising the families
of subsets corresponding to these notions.
[MCC04/01]
VELOSO, P.A.S. On some logics for qualitative reasoning about
'generally'. 20 p. Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: We examine logical systems, with generalised quantifiers,
for expressing vague notions, such as 'generally', and reasoning about
them. The primary motivation is a precise approach to assertions and
arguments involving such vague notions, which occur often both in
ordinary language and in some branches of science. Basic intuitions
about 'generally' are rendered precise by means of appropriate
families of subsets. This gives monotonic and conservative extensions
of classical first-order logic, sharing with it various properties.
Our logics, though related to default logics, are quite different,
belonging to a family of closely connected systems with generalised
quantifiers for qualitative reasoning about vague notions.
[MCC05/01]
RENTERIA, R.P.; MILIDIÚ, R.L. APLS: a fast approximate algorithm for
partial least-squares. 15 p. Eng. E-mail: milidiu@inf.puc-rio.br
Abstract: APLS, an approximate algorithm for solving the Partial
Least-Squares problem is presented. When dealing with more than one
dependent variable in the standard PLS modeling, one must compute
eigenvectors of the mixed independent and dependent variables matrix,
thus introducing a time overhead in the algorithm. APLS provides an
aproximate method for this calculation with competitive modeling error
and improved running time. In our experiments, APLS shows a 40% faster
running time when compared to the standard PLS algorithm.
[MCC06/01]
ABELEM, A.J.G.; STANTON, M.A.; RODRIGUEZ, N. QoS fim a fim através da combinação entre
serviços integrados e serviços diferenciados. 17 p.
Port. E-mail: noemi@inf.puc-rio.br
Abstract: Several alternatives for offering end-to-end QoS in IP
internetworks have been proposed over the last few years. Recently,
researchers of the IETF ("Internet Engineering Task Force") have
proposed a model which combines the integrated services/RSVP (intserv)
and differentiated services (diffserv) architectures. In this scheme,
the border routers between one region and another play fundamental
role, as they are responsible for mapping QoS functionality between
the different regions. In this article, an agent for NS simulator
(Network Simulator) is presented, which was developed to perform tasks
in support of this mapping, which include the choice of a suitable
Per-Hop Behavior (PHB), appropriate policing at the border of the
diffserv region, and admission control in accordance with the resources
available in the diffserv regions.
[MCC07/01]
ROSSETI, I.; ARAGÃO, M.P.; RIBEIRO, C.C.; UCHOA, E.; WERNECK, R.F.
New Benchmark instances for the Steiner problem in graphs. 6 p.
Eng. E-mail: poggi@inf.puc-rio.br
Abstract: In this work, 50 Steiner problems in graph's instances are
proposed. They are based on otimization problems as set covering and
code covering. These instances are interesting because, in most of them,
a good gap between linear relaxation and primal solution was obtained.
[MCC08/01]
MEDINA, M.T.; RIBEIRO, C.C.; SOARES, L.F.G. Automatic scheduling
of hypermedia documents with elastic times. 17 p. Eng. E-mail:
lfgs@inf.puc-rio.br
Abstract: The problem of automatic scheduling hypermedia documents
consists of finding the optimal starting times and durations of
objects to be presented, so as to ensure spatial and temporal
consistency of the presentation while respecting limits on shrinking
and stretching the ideal duration of each object. The combinatorial
nature of the minimization of the number of objects whose duration
is modified makes it most difficult objective to be tackled by optimization algorithms. We formulated this scheduling problem as a
mixed integer programming problem and we report some preliminary
investigations and computational results. We propose an original
approach to the minimization of the number of objects which are
shrinked or stretched. A simple primal heuristic based on variable fixations along the solution of a sequence of linear relaxations of
the mixed integer programming formulation is described. Computational
experiments on realistic size problems are reported. The effectiveness
of the heuristic in finding good approximate solutions within very
small processing times makes of it a quite promising approach to be
integrated within existing document formatters to perform compile time
scheduling or even run time adjustments. We also discuss results
obtained by Lagrangean relaxation and propose a dual heuristic using
the dual multipliers and modified costs, which consistently improves
the solutions found by the primal heuristic.
[MCC09/01]
SILVA, O.R.; GARCIA, A.F.; LUCENA, C.J.P. Achieving system-level
and agent-level dependability in multi-agent systems. 15 p. Eng.
E-mail: lucena@inf.puc-rio.br
Abstract: Development of multi-agent object-oriented systems is
complicated by two main factors: the increasing complexity associated
with their system-level and agent-level properties and the need to
provide their dependability. This paper explores the recent advances
of separation-of-concerns techniques to deal with the increasing
complexity in developing dependable multi-agent object-oriented
software. We propose a software architecture which: (i) uses aspect-oriented design and programming to handle separately each agency
property and facilitate the provision of fault tolerance at the
agent-level, and (ii) adopts a reflective associative blackboard
architecture in oreder to manipulate separately each property and
fault tolerance activities at the system-level. We also demonstrate
our multi-agent approach through the Portalware system, a web-based
environment for the development of e-commerce portals.
[MCC10/01]
GEROSA, M.A.; FUKS, H.; LUCENA, C.J.P. Uso da categorização e estruturação de mensagens para dinamizar a
discussão e reduzir a
sobrecarga de informação em cursos via Internet. 17 p. Port.
E-mail: lucena@inf.puc-rio.br
Abstract: This paper shows how the use of categorization and
structuring of messages in asynchronous textual communication tools
could be useful in courses delivered via Internet in order to organize
the argumentation and guide the participants to reflect about their
messages. Although the use of categorization causes an increase in
the total number of messages, there is a reduction at the information
overload. The use of message categorization in a distance course through the
AulaNet environment elaborates on how to define and improve the set of
categories.
[MCC11/01]
FUKS, H.; GEROSA, M.A.; LUCENA, C.J.P. The development and application
of distance learning courses on the Internet. 14 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: This paper presents the methodology, results and difficulties
encountered in the development and delivery of a course through the
Internet. The course, which is about the application of information
technology to education, is being delivered using the AulaNet environment, which is groupware for the creation, participation and
maintenance of Web-based courses. A model for group work is provided.
This paper also shows how this kind of environment can be used to
provide support, and to facilitate and manage cooperative learning.
[MCC12/01]
GEROSA, M.A.; FUKS, H.; LUCENA, C.J.P. Desenvolvimento e aplicação
de cursos totalmente a distância na Internet - um estudo de caso.
17 p. Port. E-mail: lucena@inf.puc-rio.br
Abstract: This paper presents the methodology, the results and the
difficulties found in the development and delivery of a course 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. This paper also shows how this kind
of environment can be used to give support, facilitate and manage
cooperative learning.
[MCC13/01]
SILVEIRA, M.S.; BARBOSA, S.D.J. Revelando as affordances do designer
via sistemas de help e interjeições de comunicabilidade. 41 p. Eng.
E-mail: simone@inf.puc-rio.br
Abstract: Traditional online help is often function-oriented,
unrelated to users' tasks and not situated at users' current context
of interaction. This is due mainly to the help development strategy,
and to the lack of a help model that takes into account typical users'
task flows. In addition to a help model, we also need adequate access structures to the various components of the help system, each providing
a different perspective on help content. This paper proposes the
integration of a help model with communicability concepts, both based
on Semiotic Engineering. Our goal is to provide users with better
access and content, which are designed to clarify users' specific
doubts, as expressed by users themselves, during interaction.
[MCC14/01]
GARCIA, A.F.; SILVA, V.T.; LUCENA, C.J.P.; MILIDIÚ, R.L. An
aspect-oriented design approach for multi-agent systems. 19 p. Eng.
E-mail: lucena@inf.puc-rio.br
Abstract: Objects and agents have many similarities, but agents are
also driven by beliefs, goals, capabilities, plans, and a number of
agency properties such as autonomy, adaptation, interaction, learning
and mobility. Moreover, cooperating software agents must incorporate
different collaborative capabilities in order to work together in heterogeneous contexts. In practice, a complex application is composed
of objects and multiple types of agents, each of them having distinct
agency properties and capabilities. An additional difficulty is that
these capabilities and a properties typically overlap and interact
with each other, and a disciplined scheme to composition is required.
This paper dicusses software enginnering approaches for multi-agent
systems, and presents a new approach for building multi-agent
object-oriented software from early stage of design. This approach (i)
describes structured integration of agents into the object model, (ii)
incorporates flexible facilities to build different types of software
agents, (iii) encourages the separate handling of each property and
capability of an agent, (iv) provides explicit support for disciplined
and transparent composition of agency properties and capabilities in
complex software agents, and (v) allows the production of agent-based
software so that it is easy to understand, maintain and reuse.
The proposed approach explores the benefits of aspect-based design
and programming for the incorporation of agents in object-oriented
systems. We also demonstrate our multi-agent approach through
the Portalware system, a web-based environment for the development
of e-commerce portals.
[MCC15/01]
MILIDIÚ, R.L.; PESSOA, A.A.; LABER, E.S. On-line pipeline
transportation of petroleum products with no due dates. 24 p.
Eng. E-mail: laber@inf.puc-rio.br
Abstract: In this paper, we introduce a new model for pipeline
transportation petroleum products without due dates. We use a
directed multigraph G where arcs represent pipes and nodes represent
locations. Moreover, we define an order as a requirement to transport
an amount of a given product. Orders are grouped into packages that
are received on-line. For this model, we give a necessary and
sufficient condition for the existence of a feasible pumping sequence
for the next order package. Furthermore, we propose the Batch-to-Pipe
Assignment (BPA) algorithm for the case we where all ordered volumes
are unitary. This algorithm tests the feasibility condition and, if is
satisfied, gives a feasible solution for the next order package in
O (r3) time, where r is the number of orders. If the multigraph G is
acyclic, then BPA leads to an optimal solution for the on-line problem.
In addition, we prove that no algorithm is (1.25 - 0.625/n)-competitive
against an adaptive adversary, and no randomized algorithm is
(1.125 - 0.3125/n)-competitive against an oblivious adversary when
n is the number of nodes in G. Finally, we show that our results
can be extended to non-unitary orders.
[MCC16/01]
CORTES, S.C.; LUCENA, C.J.P. Um framework de regras ativas para
sistemas de gerência de banco de dados distribuído. 25 p. Port.
E-mail: lucena@inf.puc-rio.br
Abstract: Active database management systems make possible the
development of advanced database applications, giving support to
a semantics that reflects the application behavior through the
definition of rules, which specify actions that are automatically
triggered by the occurrence of certain events. The use of active
rules in a distributed environment allows obtaining more
expressiveness, although with a considerable increase of the system
complexity. This work proposes a framework for constructing active
distributed database management systems that applies the reuse
technique (framework) in order to benefit by the specifications which
must exist in all systems of this kind, at the same time that allows
being configured/extended to specific operational environments, with
different rule semantics.
[MCC17/01]
SILVEIRA, M.S.; de SOUZA, C.S. Análise comparativa de sistemas de help online como fonte para
avaliação heurística destes sistemas. 42 p.
Port. E-mail: clarisse@inf.puc-rio.br
Abstract: How can we know precisely who will be accessing a designed
computer application, and when? If we don't know this, and thus can't
design an application targeted at a specific user group, how can we
better help different users to use it in a variety of situations? In
order to support users, an application needs to provide them with a
help system that not only helps them to do their tasks, but also to
understand why the application behaves the way it does. In this work,
we have made a comparative analysis of a few office applications'
online help systems. Based on this analysis, we propose guidelines
that may be used in heuristic help evaluation, in order to better
support designers in the creation of more efficient help systems.
[MCC18/01]
GUELL, N.; SCHWABE, D.; BARBOSA, S.D.J. Método de avaliação de usabilidade na Web baseado em modelo e
padrões de comportamento.
20 p. Port. E-mail: simone@inf.puc-rio.br
Abstract: This document proposes a usability evaluation method for Web
applications. The proposed method helps designers to diagnose and
solve design problems. Our approach is to recognize, during user's
interaction with the system, behaviors that are conduct patterns for
typical design problems. Initially, behavioral patterns were
described, classified and mapped onto classes of design problems.
Then, the design problem indicated by each behavioral pattern is
diagnosed using the OOHDM methodology. Finally, some design solutions
are proposed based on Guidelines and Design Patterns.
[MCC19/01]
RODRIGUES, R.F.; BACHELET, B.; MAHEY, P.; SOARES, L.F.G. Elastic
time computation for hypermedia documents. 17 p. Eng. E-mail:
lfgs@inf.puc-rio.br
Abstract: This paper presents a new elastic time algorithm for
adjusting hypermedia document presentation in order to avoid
temporal inconsistencies. The algorithm explores the flexibility
offered by some hypermedia models in the definition of media object
duration and uses this flexibility for choosing the objects to be
stretched or shrunk in such a way that the best possible quality of
presentation is obtained. Our proposal is based on the "out-of-killer"
method for minimum-cost flow problems and it seems to offer more
flexibility to model real-time applications in comparison with other
previous proposals based on the simplex method.
[MCC20/01]
SEIBEL, L.F.B.; LIFSCHITZ, S. A genome databases framework. 20 p.
Eng. E-mail: sergio@info.puc-rio.br
Abstract: There exists many molecular biology databases, also known as
Genome Databases, that need to be integrated together with all related
applications and other data sources. This work proposes the use of an object-oriented framework for genome data access and manipulations.
The framework approach may be an interesting solution in this context
due to the flexibility, reusability and extensibility requirements of
this application domain. We will present and discuss the framework in
details using class and sequence diagrams that explore both the
structural and dynamic parts of the architecture.
[MCC21/01]
MATHIAS FILHO, I.; LUCENA, C.J.P. Uma proposta para a incorporação
do modelo de features à linguagem UML. 17 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstratc: Feature modeling is one of the most successful techniques in
use to promote the reuse of software artifacts as of the initial stages
of development. The purpose of this paper is to present a proposal for
the incorporation of feature modeling into the UML language, wich has
become a standard for the modeling of object-oriented software. The
precise and careful specification of this proposal, wich uses formal
and informal techniques such as graphic notation, natural language and
formal language, will permit the building of tools that provide support
to the development of feature models for families of applications, and
the instantiation of members of these families based on these models.
Moreover, the use of the XMI standard in the representation of the
feature models will facilitate their integration with the many CASE
tools already existing on the market.
[MCC22/01]
OLIVEIRA, T.C.; MATHIAS FILHO, I.; LUCENA, C.J.P. A framework based
approach for workflow software development. 8 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: The purpose of Workflow Software is to provide users with
an environment in wich they can manipulate and control all the data
and tasks involved in achieving a predefined goal (main task). Some
features as user-interface, persistency, online guidance and multi-user
support, are all-important and should be present in the final software,
to obtain a high level of usability. It is also important that the
design of the software should take place in an environment that helps
the designer to deal with the large amount of definitions obtained
during the domain analysis phase and gap between these definitions
and the object oriented design model. This paper describes the main features of a tool to support a method that aids the designer to
develop workflow software.
[MCC23/01]
MATHIAS FILHO, I.; OLIVEIRA, T.C.; LUCENA, C.J.P. Domain oriented
framework construction. 16 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: Object-oriented Application Framework is a powerful reuse
technique that allows the sharing off requirements, design and code
among a set of applications systems instantiated from an original
framework. Nevertheless, little attention has been given to the role
of an explicit Domain Analysis phase in the framework construction
process. This paper describes an approach where the requirements
capture for an entire application family takes a central role in
the framework development, thus facilitating verification processes
and providing reliable documentation that will assist the
instantiation step.
[MCC24/01]
OLIVEIRA, T.C.; MATHIAS FILHO, I.; LUCENA, C.J.P. Using XML and
frameworks to develop information systems. 11 p. Eng. E-mail:
lucena@inf.puc-rio.br
Abstract: To accomplish the software development time and cost
constraints this develpoment should take place in an environment
that helps the designer to deal with the large amount of concepts
obtained during the domain analysis phase and the semantic gap
between those concepts and the object oriented desing model, due
to their different levels of abstraction. This paper discribes the
main features of an environment designed to support the development
of IS software based on framework reuse and XML specifications.
[MCC25/01]
MUCHALUAT-SAADE, D.C.; COLCHER, S.; SOARES, L.F.G. Relações de sincronização
espaço-temporal hipermídia também merecem status de
primeira classe. 18 p. Port. E-mail: lfgs@inf.puc-rio.br
Abstract: This paper introduces the concept of hypermidia connector,
presenting how spatio-temporal relations may be defined as a
specialization of architecture description languages (ADL) connectors.
Some features found in ADLs were brought to hypermidia authoring
languages, giving first-class status to synchronization relations
expressed by links. Among the profits, we can highlight the
possibility of reusing a spatio-temporal relation specification in different links with the same behavior and the possibility of defining
composite spatio-temporal relations expressed by links, which is an
original feature in hypermidia authoring languages.
[MCC26/01]
SILVEIRA, M.S.; DIAS, M.C.; QUENTAL, V.S.D Estudos preliminares para composição de
conteúdo de help através de interjeições de
comunicabilidade. 46 p. Port. E-mail: bib-di@inf.puc-rio.br
Abstract: Accessing help systems by What's this? expressions is easily
found in commercial WIMP applications. An improvement to this kind of
access is to use communicability utterances, such as Where is?, What
now?, and Why should I do this?, for instance. But how can the designer
answer these questions? What kind of answer is needed for each one?
This work describes studies to help the designer build this kind of
answer when he is developing the applications' help systems.
[MCC27/01]
CASTILHO, R.T.L.; GARCIA, A.H. Theses and dissertations presented to
the Departamento de Informática of PUC-Rio from 1969 to 2000. 206 p.
Eng. E-mail: bib-di@inf.puc-rio.br
Abstract: Catalogue encompassing more than 30 years of dissertations
and theses from the PUC-Rio Information Technology Department, the
first post-graduate Computer Science program in Latin America. It
evidences the continued stability of the program in the state-of-the-art of the discipline, is invested of relevant historical value,
being a significant example of the evolution of scientific and
technological research into the field of Computing in Brazil and is also a record of the many researchers that have populated and continue
to do so the academic Computing community in Brazil.
[MCC28/01]
COSTA, R.L.C.; LIFSCHITZ, S. Uma proposta de arquitetura de SGBD
baseado em agentes para auto-sintonia de índices. 30 p. Port.
E-mail: lifschitz@inf.puc-rio.br
Abstract: We present an architecture based on software agents for
DBMSs' self-tuning. In particular, we are interested in the features
of indexes' self-tuning. Thus, an engine is considered that makes
possible the automatic selection, creation and exclusion of indexes.
A case study is described and reveals adequacy to the agent based
architecture specified.
[MCC29/01]
CHAVEZ, C.F.G.; GARCIA, A.F.; LUCENA, C.J.P. From AOP to MDSOC:
an experience report. 19 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: In this report, we present some insights gathered through
the implementation of the Portalware system using the IBM Hyper/J
tool, having as a point an aspect-oriented design model and an
aspect-oriented implementation (using the Xerox Parc's AspectJ tool).
We present a preliminary mapping between the elements of the two
approaches and discuss some alternatives for deriving an hyperslice-based solution from the Portalware aspect-oriented model. We describe
the selected set of tranformations we have applied, some potential
problems and solutions related to the transformation process, and
finally, we present resulting Hyper/J solution. One of the motivations
behind this development exercise is a pratical assessment of each
approach's similarities and differences, strengths and weaknesses to
help in the validation of a generic aspect-based design model that
can be mapped to the implementation models supplied by AspectJ and
Hyper/J.
[MCC30/01]
SILVA, V.T.; LUCENA, C.J.P. Um modelo orientado a objetos para
sistemas multi-agentes. 14 p. Port. E-mail: lucena@inf.puc-rio.br
Abstract: In this work, we propose a mapping from agents, and its
fundamental properties and mental states, into objects. The proposed
objective of the mapping is generate a object-oriented model for
multi-agent systems to facilitate the maintainability and reusability
of the elements involved in the model. To assure these objectives,
a separation of concerns technique namely design patterns was applied
to the model. Design patterns provides separation of concerns because
they decouple the concerns of interest in classes or in groups of
inter-related classes. On the mapping the intra-agents aspects
(agent's properties and agent's mental states) have been modeled as
well as inter-agents aspects (communication between agents and the
environment). The modeling of these aspects and the focus on the
utilization of the mental states to model agents makes this approach
more appropriate to model cognitive agents (that execute plans based
on their goals and beliefs) than reactive agents.
[MCC31/01]
PINHEIRO, S.; VELHO, L.; GATTASS, M. A virtual memory system for
real-time visualization of multi-resolution 2D objects. 8 p. Eng.
E-mail: gattass@inf.puc-rio.br
Abstract: We describe a predictive memory management system that
allows the visualization of 2D graphic objects in real time. This
system is based on a virtual memory model. We show how the page
loading system predicts and fetches data before it is accessed by
the application and how the page replacement system decides which
data should be removed from memory. We demonstrate the effectiveness
of the system for real-time visualization of large panoramas.
[MCC32/01]
MILIDIÚ,R.L.; PESSOA, A.A. Complexidade de problemas de
planejamento de distribuição em oleodutos. 13 p. Port. E-mail:
milidiu@inf.puc-rio.br
Abstract: Petroleum derivates are typically transported through
pipelines in Brazil, and also in other countries. Pipeline networks
can be represented by a graph where nodes represent locations and
arcs represent oil pipeline segments. A natural approach to solve
the distribution problem - PDO - that arises in oil pipeline
networks is to develop efficient algorithms for simplified versions
of this problem. In this paper, we consider two simplified versions
of PDO:PDOS-2, a decision problem with only two distinct products,
and PDOP-3, a decision with only three distinct products and a planar
graph. We point out that both PDOS-2 and PDOP-3 include several
additional simplifying assumptions. Nevertheless, we prove that both
problems are NP-hard. We also consider two optimization problems
respectively based on PDOS-2 and PDOP-3. In both cases, an optimal
solution minimizes the makespan of the pumping operations. For both
problems, we prove that there is no(2 - e)-approximate algorithm, for
any e>0, unless P=NP.
[MCC33/01]
CORTES, M.; FONTOURA, M.; LUCENA, C. Using refactoring and
unification rules to assist framework evolution. 9 p. Eng.
E-mail: lucena@inf.puc-rio.br
Abstract: Although object-oriented software development has
experienced the benefits of using frameworks, a thorough understanding
of how to change them to meet evolving requirement needs is still
object of research. Therefore framework development is very expensive,
not only because of the intrinsic difficulty related to capturing the
domain theory, but also because of the lack of appropriate methods and
techniques to support the evolution and redesign of the framework
architecture. This paper proposes the use of refactoring and
unification rules to assist framework evolution. The approach is
illustrated through the JUnit testing framework.
[MCC34/01]
MOURA, A.L.; URURAHY, C.; CERQUEIRA, R.; RODRIGUEZ, N. Dynamic
support for nonfunctional requirements in distributed applications.
17 p. Eng. E-mail: noemi@inf.puc-rio.br
Abstract: This work presents an environment that allows distributed
applications to adapt dynamically to nonfunctional properties of
their components. This environment, based on the programming language
Lua and on CORBA, allows applications to select dynamically the
components that best suit their requirements, to verify whether the
system is satisfying these requirements, and react, when appropriate,
to variations in the nonfunctional properties of the services in use.
The paper also describes an example application based on the proposed environment.
[MCC35/01]
CORTES, S.C.; LUCENA, C.J.P. Um framework para construção de sistemas
de banco de dados móvel com regras ativas. 17 p. Port. E-mail:
lucena@inf.puc-rio.br
Abstract: This study presents an overview of the DBS-M-AR framework,
with emphasis on its components and hot spots. This is an
object-oriented framework for the construction of Mobile Database
Management Systems with Active Rules. A detailed discussion of its
instantiation is also included.
[MCC36/01]
MONTENEGRO, A.A.; RIBEIRO, C.C; ARAGÃO, M.V.S.P. Um algoritmo
randomizado para o problema de determinação do corte s-t mínimo
em grafos direcionados. 42 p. Port. E-mail: celso@inf.puc-rio.br
Abstract: The minimum cut problem in a direct graph consists basically
in finding a partitioning of the set of vertices of the graph in two
subsets, in such a way that the number (or the sum of the weights) of
the edges that the number (or the sum of the wheights) of the edges
that connect the partitions is minimized. An important variation of
this problem is the s-t minimum cut problem, in which we impose the
restriction that each candidadte cut separate two special vertices s
and t of the input set. As far as we are know, no eficient and simple
randomized algorithm has been proposed to solve this problem. In this
work we investigate the applicability of randomization techniques to
the s-t minimum, proposing an algorithm and analising its complexity.
[MCC37/01]
MONTENEGRO, A.A.; CARVALHO, P.C.P. Algoritmos de fluxo máximo para o
problema de correspondência em visão estéreo. 55 p. Port. E-mail:
bib-di@inf.puc-rio.br
Abstract: The epipolar constraint is one of the most important
properties used to solve the stereo correspondence problem. This
constraint makes possible the solution of the problem for each pair
of epipolar lines separetly. The main drawback with this approach is
that it does not exploit the coeherence that exists among the epipolar
lines, yielding some artifacts in the final solution. In this work we
investigate some recently proposed methods based on network flow
algorithms that are capable of taking into consideration the coherence
among epipolar lines.
[MCC38/01]
MONTENEGRO, A.A.; GATTASS, M. Determinação de superfícies de
profundidade através de visão estéreo. 48 p. Port. E-mail: mgattass@inf.puc-rio.br
Abstract: In this work we present the basic theoretical and
computational aspects of stereo vision. Our main focus is in the
geometry involved in the process as well as in the way the problem
can be modelled. Some traditional methods, as the correlation based
and the minimum path based methods, are presented in detail as
exemples of how the problem can be solved computationally.
[MCC39/01]
CRUZ, S.O.; LUCENA, C.J.P.; RANGEL, J.L.M. Identificando objetos através de pronomes. 26 p. Port. E-mail: lucena@inf.puc-rio.br
Abstract: The need to know the object identification to request it's
sevices is a restriction in the construction of object oriented
system. To reduce this restriction we have proposed a form of generic
reference to an object named pronoum. Pronoum allows the programmer
to specify how to send a message without knowing the destination
object by name. With pronouns, the visibility of an object increases
without breaking the rule of encapsulation. With this feature
decoupled server classes may be constructed and used in different
contexts. Some pronouns are defined in this work. Their usefulness in
the development of object oriented systems is illustrated through
examples. An implementation approach based on open languages is
suggested.
[MCC40/01]
GARCIA, A.F.; CHAVEZ, C., SILVA, V.T.; LUCENA, C.J.P. Developing
multi-agent software: an aspect-based approach and a pattern-based
approach. 16 p. Eng. E-mail: lucena@inf.puc-rio.br
Abstract: This paper proposes and compares two software engineering
approaches for multi-agent systems.The first proposal explores the
benefits of aspect-based design and programming and the second one is based on design
patterns. Both approaches have the following goals:
(i) describe structured integration of agents into the object model,
(ii) incorporate flexible facilities to build different types of
software agents, (iii) encourage the separate handling of each
property and capability of an agent, (iv) provide explicit support for
disciplined and transparent composition of agency properties and
capabilities in complex software agents, and (v) allow the production
of agent-based software so that it is easy to understand, maintain and
reuse. We also demonstrate our proposals through the Portalware system,
a web-based environment for the development of e-commerce portals.
[MCC41/01]
CUNHA, L.M.; GARCIA, A.F.; ASSIS, R.L.; FUKS, H.; LUCENA, C.J.P. O
"acompanhamento da participação" e avaliação no ambiente AulaNet. 8p.
Port. E-mail: lucena@inf.puc-rio.br
Abstract: Student evaluation in Web-based courses has to be part of
the process of learning, i.e., it should not be dealt as an isolated
issue. In this context, this paper presents evaluation concepts and
their application in the AulaNet environment, presenting a mechanism
for assessing the participation of the students. The mechanism goal
is to provide information about the student evolution while performing
learning activities. This information can be visualized by means of
the follow-up report.
[MCC42/01]
MOURA, M.A.M.; ENDLER, M. An infrastructure for management of fault
tolerant CORBA applications. 21 p. Eng. E-mail: endler@inf.puc-rio.br
Abstract: In the last years CORBA has become a de facto standard for
the development of object-oriented distributed applications. In spite
of some important features such as support for interoperability and
heterogeneity, only very recently CORBA specification, with the
adoption of the Fault Tolerant CORBA standard (FT-CORBA),
addressed issues concerning object replication and reliable
communication between objects, which are key components to provide
fault tolerance for distributed object systems. Since mid-90's
several research projects have proposed and explored some approaches
to incorporate fault tolerance mechanisms in CORBA but most of the
systems developed offer a rather basic support for managing groups of
object replicas. Our work builds upon one of these systems, called OGS. We created an extended OGS (called OGS+) and on the top of it we
developed Juggler, a distributed services that provides means for
flexible and automatic management of CORBA replicated objects through
the deployment of a set of high-level interfaces based on the ones
standardized by FT-CORBA.