Monografias em Ciência da Computação

2010

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, Pontifí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: 24/NOVEMBER/2010

INDEX

[MCC01/10]
DIAS JUNIOR, E.P.F.; RODRIGUES, P.G.; ENDLER, M. Middlewares e protocolos para redes sociais pervasivas. 17 p. Eng. E-mail: endler@inf.puc-rio.br

Abstract: Pervasive Social Networks (PSN) represent an evolution of the current Web 2.0 social networking services (e.g., Orkut, Facebook, Twitter) since they make possible the integration with Pervasive Computing concepts. As a result of this union of tech-nologies arises the possibility of taking advantage of the information based on the user physical context to enrich the forms of interaction and the sorts of information current-ly shared in social networks. This paper presents definitions of some terms related to Pervasive Social Networks, considers some of the offered services and also presents seven middleware implementations where these concepts are applied. The analyzed services have been classified based on several criteria such as: supported network ser-vices, deployment architecture, sensible information handling (security), underlying social network and discovery of potential new social links.


[MCC02/10]
BRANCO, A.; RODRIGUEZ, N. L. Macroprogramação em rede de sensores sem fio. 30 p. Port. E-mail: noemi@inf.puc-rio.br

Abstract: The area of Wireless Sensors Networks (WSN) has experienced in the last years an increase in applications due to the technological evolution and cost reduction of sensor devices. These new applications tend to use larger and more complex networks. The development of these new applications needs tools that facilitate the programming work. These tools must allow new programming abstractions for group and network as opposed to programming at the level of individual sensor nodes. Such models are being called macroprogramming models. This work evaluates different programming models for wireless sensors network. Although we focus on platforms with limited resources like Berkeley-Style Motes, we also evaluate some other models that do not fit into that description. The evaluation criteria range from the programming complexity to the application types that benefit from each model.


[MCC03/10]
SILVA, A.L.; NUNES, I.O.; LUCENA, C.J.P. Estudo sobre modelos de representação de preferências de usuário. 15 p. p. Port. E-mail: lucena@inf.puc-rio.br
Abstract: In this paper we present a survey about user preferences representation models. We have investigated ten research works that present several ways of representing user preferences. Besides introducing and describing these works, we show how the models that they adopt are related to each other, as well as discuss relevant issues about these works. We conclude that representation models were elaborated focusing on being manipulated by algorithms for reasoning about preferences. As a consequence, these models limit the way that user preferences can be expressed, and therefore there is a need of preferences elicitation algorithms for capturing and transforming user preferences into a model used by software systems. However, if higher level models were adopted, users would be able to express their own preferences.


[MCC04/10]
LUCENA, C.J.P.; FREIRE, F.; SILVA, V.T.; NETO, B.F.S; ABREU NETTO, M.T.; CIRILO, E.J.R.; NUNES, I.O.; CARVALHO, D.B.F.  Gerenciamento autonômico de redes: participação do LES no Projeto Horizon. 15 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: The Laboratory of Software Engineering (LES) intends to use the research developed in the context of multi-agent systems to enable the Horizon project to incorporate intelligence and autonomy into network management systems. It will be performed through the development of an infrastructure based on self-organizing agents regulated by norms and situated into the different network devices which will be endowed with rationality, reactivity, pro-activity and sociability.


[MCC05/10]
FLACH, B.C.; ARAGÃO, M.V.S.P.  On a class of stochastic programs with endogenous uncertainty: theory, algorithm and application. 61 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: In this work we study a class of stochastic programming problems with endogenous uncertainty – i.e., those in which the probability distribution of the random parameters is decision-dependent – which is formulated as a MINLP. Although discussed in the context of the humanitarian logistics problem, the proposed methodology and obtained results are also valid for a more general class of problems which comprehends a variety of applications. In particular, we propose (i) a convexification technique for polynomials of binary variables, (ii) an efficient cut-generation algorithm and (iii) the incorporation of importance sampling concepts into the stochastic programming framework so as to allow the solution of large instances of the problem.


[MCC06/10]
CASANOVA, M.A.; LAUSCHNER, T.; PAES LEME, L.A.P.; BREITMAN, K.K.; FURTADO, A.L.; VIDAL, V.M.P.   Revising the constraints of the mediated schema. 56 p. Eng. E-mail: casanova@inf.puc-rio.br

Abstract: This paper addresses the problem of changing the constraints of a mediated schema to accommodate the set of constraints of a new export schema. The relevance of this problem lies in that the constraints of a mediated schema capture the common semantics of the data sources and, as such, they must be maintained and made available to the users of the mediation environment. The paper first argues that such problem can be solved by computing the greatest lower bound of two sets of constraints. Then, for an expressive family of conceptual schemas, it shows how to efficiently decide logical implication and how to compute the greatest lower bound of two sets of constraints.


[MCC07/10]
SERRANO, M.; LUCENA, C.J.P.  Dynamic database for intentional development of ubiquitous systems. 20 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper, we present our Dynamic Database Building Block centered on our Intentional Systematic Software Development for Ubiquitous Systems (ISSD for UbSystems). This specific building block is composed of a Dynamic Database Architecture and an agent-oriented Layer Structure. Our main goal is to store, search, recovery, and protect the stakeholders’ information considering different ubiquitous profiles, and special privacy policies through reusable standard solutions. Moreover, we use this building block to dynamically allow the insertion of new devices’ features, network specification, users’ preferences, and contract information. This dynamic mechanism is particularly important in ever-changing environments to improve the traditional database models, in which you must previously specify the entities and fields. Furthermore, we evaluated our support in an extensive dental case study, and also compared it with other related work.


[MCC08/10]
 SERRANO, M.; LUCENA, C.J.P.; MYLOPOULOS, J.; YU, E.  Experiences with model reuse: non-functional requirements catalogues for ubiquitous systems. 8 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Requirements engineering activities demand adequate conceptual modeling support to be effectively and efficiently performed, especially in complex domains such as ubiquitous computing. Ubiquitous systems are embedded in ever-changing environments, in which the device heterogeneity, user mobility, content server distribution, adaptability, context awareness and other issues are intrinsic. Unfortunately, there is a lack of conceptual and tool support that guides developers from requirements to code while respecting the non-functional requirements that arise from the special nature of ubiquitous systems. In this paper, we present a catalogue of nonfunctional requirements for ubiquitous systems and a method for using it to guide systematic system development. We report on experiences in the construction of this catalogue, drawing on state-of-the-art literature as well as our own experimental research. The catalogue is constructed using the NFR Framework. Operationalizations of the NFRs are illustrated through the use of multi-agent-systems, goal orientation and distributed intentionality.


[MCC09/10]
CASANOVA, M.A.; FURTADO, A.L.; MACEDO, J.A.F.; VIDAL, V.M.P.  Extralite schemas with role hierarchies.32 p. Eng. E-mail: casanova@inf.puc-rio.br

Abstract: This paper addresses the problems of testing strict satisfiability and deciding logical implication for extralite schemas with role hierarchies. Using the OWL jargon, extralite schemas support named classes, datatype and object properties, minCardinalities and maxCardinalities, InverseFunctionalProperties, class subset constraints, and class dis-jointness constraints. Extralite schemas with role hierarchies also support subset and dis-jointness constraints defined for datatype and object properties. Strict satisfiability impos-es the additional restriction that the constraints of a schema must not force classes or data-type or object properties to be always empty, and is therefore more adequate than the tra-ditional notion of satisfiability in the context of database design. The decision procedures outlined in the paper are based on the satisfiability algorithm for Boolean formulas in con-junctive normal form with at most two literals per clause, and explore the structure of a set of constraints, captured as a graph.


[MCC10/10]
 PICCININI, H.; LEMOS, M.; CASANOVA, M.A.; FURTADO, A.L.   W-Ray: a strategy to publish Deep Web geographic data. 32 p. Eng. E-mail: casanova@inf.puc-rio.br

Abstract: This work introduces an approach to address the problem of accessing geographic data from the Deep Web. The approach relies on describing the relevant data through well-structured sentences, and on publishing the sentences as Web pages, following the W3C and the Google recommendations. For conventional data, the sentences are generated with the help of database views. For vector data, the topological relationships between the objects represented are first generated, and then sentences are synthesized to describe the objects and their topological relationships. Lastly, for raster data, the geographic objects overlapping the bounding box of the data are first identified with the help of a gazetteer, and then sentences describing such objects are synthesized. The Web pages thus generated are easily indexed by traditional search engines, but they also facilitate the task of more sophisticated engines that support semantic search based on natural language features.


[MCC11/10]
FURTADO, A.L.; BARBOSA, S.D.J.; CASANOVA, M.A.; PICCININI, H.  First version of a prototype for publishing Deep Web data. 13 p. Eng. E-mail: furtado@inf.puc-rio.br

Abstract: To make data stored in relational databases accessible to search engines by applying the W-Ray method, introduced in a previous paper, a prototype called WRay1 was developed. Working on views designed according to the ER (Entity-Relationship) modelling principles, WRay1 endeavours to express the data items of more general interest under the form of template-driven natural language sentences. The sentences are registered on html pages, which are then posted on the Web.

 
[MCC12/10]
VALENTE, L.; FEIJÓ, B. H.  The audio flashlight, reloaded: a mobile multiplayer non-visual game. 11 p. Eng. E-mail: feijo@inf.puc-rio.br

Abstract: This work presents an outline for a mobile multiplayer non-visual game. This new game builds upon a former game named “The Audio Flashlight”. The main difference in the new version is the multiplayer functionality, where two players are able to cooperate to reach a common goal. As far as we are concerned, this represents the first non-visual multiplayer game for mobile devices. We are concerned to explore a number of issues on tactile feedback. For example: how it helps the player in identifying game elements; how its use relates to spatial localization; how players will negotiate in a collaborative setting, where the tasks are split among them and they depend on each other to advance in the game.


[MCC13/10]
ARAGÃO, M.V.S.P.; VIANA, H.; BARBOZA, E.U.  Team orienteering problem: formulations and branch-cut and price. 11 p. Eng. E-mail: feijo@inf.puc-rio.br

Abstract: The Team Orienteering Problem is a routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. A fixed number of identical vehicles, with a limited total duration for their routes, is given. The total profit gathered by all routes is to be maximized. We devise an extended formulation where edges are indexed by the time they are placed in the route. A new class of inequalities, min cut, and the triangle clique cuts of Pessoa et. al., 2007 are added. The resulting formulation is solved by column generation. Branching is done following the work of Boussier et al. 2007, to which the branch-cut-and-price algorithm here proposed is compared. A few new upper bounds were obtained. Overall the presented approach has shown to be very competitive.

 
[MCC14/10]
NUNES, I.O.  On the development of personalized user agents: a model driven approach. 17 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Many modern computer systems are providing assistance to several of our usual tasks, by incorporating features with a proactive and autonomous behavior. A generalized and ambitious idea underlying such systems is the personalized user agents, which are personal assistants acting on the users' behalf. Even though significant research effort has been invested on developing user agents, we are far from their massive adoption. Research work in the context of human-computer interaction have criticized agent-based methodologies that seem to produce systems not easily accepted by the user: one of the main reasons is the autonomy of the agents that can cause a loss of control by the user. Different users need different kinds of user agents. In addition, a large group of users is willing to adopt user agents only if they know exactly what the agent is going to do. Our research addresses this group of users. We aim at tackling two main problems: (i) how to empower end-users to instruct their personal agents; and (ii) how to build this family of applications, considering software architecture quality attributes. Our solution to these issues is to investigate a virtual separation of concerns. The main idea is to propose a virtual user model that is a high-level global view of user customizations, which is implemented by an underlying service-oriented multi-agent infrastructure. This user model might be able to drive runtime adaptations in the user agents, based on a modeldriven approach. Our approach most likely will comprise: (i) a reference architecture that provides a general structure for user-customizable applications; (ii) a user Domain-specific Model, and a corresponding end-user Domain-specific Language, to model user configurations and preferences; (iii) a model-driven mechanism that supports the runtime adaptation of user agents; and (iv) a framework based on the components of our approach, which provides an infrastructure to build applications of our target domain, i.e. personal assistance software systems.

 
[MCC15/10]
NUNES, I.O.; LUCENA, C.J.  BDI4JADE: a BDI layer on top of JADE. 15 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Several agent platforms that implement the belief-desire-intention (BDI) architecture have been proposed. Even though most of them are implemented based on existing general purpose programming languages, such as the the Java language, the rely on a Domain-specic Language (DSL) writen in specic le types (e.g. XML). As a consequence, this prevents the integration with existing libraries and frameworks, and developers from using advanced language features. Due to these limitations of these BDI agent platforms, we have implemented the BDI4JADE, which is presented in this paper. It is a BDI layer on top of JADE, an agent platform.

 
[MCC16/10]
 COSTA, A.D.; SILVA, V.T.; LUCENA, C.J.P. A multi-agent system framework to assure the reliability of self-adapted behaviors. 14 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: One of the most important issues in self-adaptive systems is to assure the reliability of self-adapted behaviors. However, few works provide solution to deal with such concern. The majority considers the execution of test cases to validate the selfadapted behavior. Based on this idea, the paper proposes a framework that helps on building self-adaptive and self-testable multi-agent system. This framework allows the creation of different self-adaptation processes (control-loops) composed of a set of activities (e.g. collect, analyze, plan, execute, etc). In order to help on testing and validating the adapted behavior, the framework provides two main activities (test and validate) and a set of elements that help on representing the self-test concept in different control-loops. The applicability of the framework is demonstrated by an industrial system, developed to a petroleum company, responsible for identifying routes that attend products derived from the petroleum (e.g. kerosene, gasoline, etc.) in different places in Brazil.

 
[MCC17/10]
CARVALHO, D.F.; NASSER, R.B.; de SOUZA, C.S. Um estudo sobre a utilização de programas com interface baseada em mapas. 28 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: Geographic information systems (GIS) on the Internet, with its interfaces based on maps, bring a novel perspective for the users on the use of these applications, as powerful tools for specific objectives. However, the interaction model based on direct manipulation of the maps can complicate or even prevent, that users use these systems effectively. In this work, the research is to identify problems in this interaction from the perspective of Semiotic Engineering, through methods known as The Semiotic Inspection Method and The Communicability Evaluation Method. Moreover, the scenario used in this study addresses complex tasks as planning trips, being necessary the combined use of different applications in order to accomplish what is proposed.

 
[MCC18/10]
CARVALHO, D.F.; HAEUSLER, E.H; de SOUZA, C.S.; LUCENA, C.J.P. Análise de riscos em projetos: uma abordagem por reflexão computacional baseada em lógica. 14 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: Risk management is a discipline of project management that aims to identify, analyze and handle project risks, to increase the probability of success. Even with so noble objectives in the project management field, this area has the lowest maturity level in companies. 75% of the project managers do not apply any kind of systematic risk management tactics and vaguely understand the concepts related to this discipline, not to mention the consequences. This work proposes a tool to help project managers to do risk analysis. This tool is a model based on logic used for computational re ection about risks in projects. The epistemology used to build this model, taking advantage of a logic-based model checker to verify its properties, is presented together with an example. Potential users for this methodology evaluate the proposed model with interview and experiment.

 
[MCC19/10]
CARVALHO, D.F.; MILIDIÚ, R.L.; LUCENA, C.J.P. Sistemas de recomendação: uma abordagem por filtro colaborativo baseado em modelos. 9 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: On the Internet, an increasing number of applications are using recommender; consequently, the system users are becoming increasingly reliant on their recommendations. The present work explores the use of machine learning algorithms to implement a recommendation system based on the collaborative Filtering technique. The experiment uses a classic machine-learning problem based on a dataset from the literature of collaborative filtering systems. Four models are used to represent the dataset are defined and solved by three machine-learning algorithms. The results show that the machine-learning algorithms produces better results from richer models, but requires more computational resources. The trade-off analysis shows evidences of the benefits for trying different techniques and configurations on the development of new recommendation systems.

 
[MCC20/10]
CARVALHO, D.F.; LUCENA, C.J.P. Social media savvy: exploiting Orkut data. 27 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This work presents a new method to savvy the social media from Orkut. The focus is the user interaction in the communities. The social is primarily available in the conversation present on the communication forum.  However, the community association has also a special meaning in the system, because users make use of the associations difined through badges defining their profiles. The method creates a model of community relationships to extract entriguing relationships of the social data. Special plots for data visualization help the social media expert to analyze  the data. Three case studies illustrate the application of the proposal method, and present considerations about it, as well.

 
[MCC21/10]
COSTA, A.D.; SILVA, V.T.; LUCENA, C.J.P. Uma nova linguagem de modelagem para testes de software. 20 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Nowadays, to document software tests is a big concern of projects that perform the creation and execution of tests at large-scale systems. One of the approaches used to perform such documentation is UML Testing Profile (UTP). This approach allows the modeling of several test concepts. However, from our experience in coordinating test teams in different large-scale systems, we identified important test concepts that are not modeled by UTP. Based on this idea, the document presents a new test modeling language. Such language will represent these identified concepts from the extension of the UTP. Besides, we intend to define new well-formed rules to this extension, beyond creating a transformer that will allow the generation of test cases from UTP diagrams. These tests will be executed from a framework that performs self-test in adaptive systems based on software agents.