Monografias em Ciência da Computação

2009

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: 27/DECEMBER/2009

INDEX

[MCC01/09]
KARLSSON, B.F.F.; FURTADO, A.L. PMA – a Plot-Manipulation Algebra. 34 p. Eng. E-mail: furtado@inf.puc-rio.br

Abstract: Plot composition is examined here at a logic design level, an intermediate stage that comes next to the conceptual level wherein the intended narrative genre is specified. An abstract data structure is proposed to represent plots, together with an algebra for manipulating the data structure. Our purpose is to adapt for narratives the strategy applied to databases by Codd's relational model. The basic operators of our Plot-Manipulation Algebra (PMA) were introduced in view of the four fundamental relations between events that we identified in a previous work. A logic programming prototype was implemented, in order to run examples using the algebra.
 

[MCC02/09]
SOARES, L.F.G.; MORENO, M.; MORENO, M. GINGA-NCL - transmissão de aplicações e comandos de edição ao vivo em sistemas de TV digital.  26 p. Port. E-mail: lfgs@inf.puc-rio.br

Abstract: DTV applications, with their related media objects, and live editing commands, with their associated parameters, are transmitted embedded in data structures supported by asynchronous transport services that must be defined by each particular DTV system. This report proposes several transport alternatives supported by Ginga-NCL middleware, stressing their data structures that allow not only mapping the authoring syntax to the transfer syntax without the author's intervention and knowledge, but also improving the transmission and processing performance of DTV applications. Although focusing on the Ginga-NCL middleware for terrestrial TV and IPTV systems, the proposed alternatives can be extended to other middlewares.  

[MCC03/09]
SOARES, L.F.G. Nested Context Language 3.0 – Part 12: Support to multiple exhibition devices. 26 p. Port. E-mail: lfgs@inf.puc-rio.br

Abstract: This technical report describes the support offered by NCL 3.0 to multiple exhibition devices. NCL (Nested Context Language) is an XML application language based on the NCM (Nested Context Model) conceptual model for hypermedia document specification, with temporal and spatial synchronization among its media objects.


[MCC04/09]
FAUSTINO, G.M.; GATTASS, M.; LUCENA, C.J.P. Automatic embryonic stem cells detection and counting in fluorescence microscopy images. 22 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In this paper, we propose an automatic embryonic stem cell detection and counting method in fluorescence microscopy images. We handle with pluripotent stem cells cultured in vitro. Our approach uses the luminance information to generate a graph-based image representation. Then, a graph mining process is used to detect the cells. The proposed method was extensively tested on a database of 92 images and the results were validated by specialists. We obtained an average precision, recall and F-measure of 93:97%, 92:04% and 92:87%, respectively.


[MCC05/09]
ÁVILA, B.; LABER, E.S. Merge source coding revisited. 11 p. Eng. E-mail: laber@inf.puc-rio.br

Abstract: We show that any comparison-based merging algorithm can be naturally mapped into a source coder via a conversion function introduced here. By applying this function over some well known merging algorithms, namely Binary Merging and Recursive Merging, we realize that they are closely related to a runlength-based coder with Rice coding and to the Binary Interpolative Coder, respectively. Furthermore, by applying the conversion function over the Probabilistic Merging algorithm we obtain a new runlengthbased coder that uses a variant of the Rice code, namely Randomized Rice Code. This new code uses a random source of bits with the aim of reducing its average redundancy with high probability.


[MCC06/09]
ALVIM, L.G.M.; MILIDIÚ, R.L. Aprendizado de máquina para Intraday Traders do mercado acionário. 25 p. Port. E-mail: milidiu@inf.puc-rio.br

Abstract: In this paper we investigate current strategies for Automated Intraday Traders of the Market and the state of the art of Machine Learning techniques. Based on this studies, we propose a new Intraday Trader which buys when prices are beginning to rise and sells when they start to fall, based on VWAP information of market stock prices. The trader strategy uses two market advisors: an interday detector of buy/sell candidate days and an intraday detector of buy/sell instants of candidate days. For the interday detector we use a SVM predictor to classify wether the next day VWAP will rise or fall. For the intraday detector, we use a committee of SVR and PLS to forecast daily VWAP, aiming at buying/selling below/above the VWAP, respectively. For testing the new trader, we use the LearnTrade Framework that supports: financial time series predictors, simulation resources for automated traders and a dataset of Bovespa. Promissing results were obtained with maximum profit of 75% for stocks with positive mean returns and 3.7% for stocks with negative mean returns.


[MCC07/09]
VARASCHIM, J.D. Implantando o SCRUM em um ambiente de desenvolvimento de produtos para Internet. 18 p. Port. E-mail: bib-di@inf.puc-rio.br

Abstract: Internet companies need to implement products rapidly and efficiently, respecting time-to-market. In addition, as the popularity of agile development, companies are discovering that simply breaking down projects into small iterations is not enough. Agile methods require changes in management, architecture, testing as well as project management. Given the large adjustments required, enterprises are looking for some guidance.


[MCC08/09]
JENA, J.D.; ARAGÃO, M.V.S.P.; SILVA, D.S.P. Competitive deterministic heuristics for permutation flow shop scheduling. 20 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: In the last 50 years, the Permutation Flow Shop Scheduling Problem with makespan minimization (PFSP) has been a central and well-studied problem in Scheduling and Operations Research communities, known by its intractability, from theoretical and practical aspects. This work introduces polynomial time deterministic heuristics for the PFSP based on pruning techniques of the implicit enumeration tree following new extensions of the classical NEH heuristic. Experimental results attest that the proposed methods currently stand among the most eectives for the PFSP.


[MCC09/09]
GATTI, M.A.C.; LUCENA, C.J.P. A multi-environment multi-agent simulation framework for self-organizing systems. 13 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This paper introduces a multi-environment simulation framework for building self-organizing multi-agent systems. From an engineering point of view, the multienvironments approach brings the necessary modularity and separation of concerns to build self-organizing multi-agent systems that address hierarchy, interoperability and multi-aspects problems and domains. Our framework provides higher abstractions and components to support the development of self-organizing systems with multiple environments, which can be situated or not. Furthermore, the framework provides a coordination component and self-organizing design patterns to be instantiated and flexibility to evolve the framework with more complex patterns. To date, the literature does not present any architectural self-organizing pattern reuse at implementation level.


[MCC10/09]
VALERIANO, A.A.; MOTTA JR, P.R.; GATTI, M.A.C.; LUCENA, C.J.P. Requisitos funcionais para um middleware paralelo e distribuído de sistemas multi-agentes auto-organizáveis. 6 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: With the technological advance, some research areas turn itself more dependants to advanced computer system. Laboratory simulations become more expensive and take too long to be performed and computer simulations provide a more affordable way to make scientific experiences. Either way, the actual computers are still not so advanced to provide an efficient mechanism for those experiences to be executed in a satisfactory time. On this paper, it is described part of a framework’s architecture with the goal to provide an infra-structure to run agent-based simulations on a parallel and/or distributed environment, with total transparency to the system developer.


[MCC11/09]
GATTI, M.A.C.; SANGIORGI, U.B.; LUCENA, C.J.P. Towards a model driven approach for engineering self-organizing multi-agent systems. 10 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This paper introduces a tool for modeling self-¬organizing multi¬-agent systems based on a design approach that contains models that allow the design of more than message passing but the emergence of highly decentralized and dynamic distributed systems. It is crucial for self-organizing systems to model an environment where agents can interact indirectly through intentional events, for example by leaving objects in an environment for other agents to see. It is more scalable and convenient for the application developer. Our tool allows the visual construction and validation of the proposed models, representing the first step for code generation.


[MCC12/09]
SOARES, L.F.G. Nested Context Language 3.0 - Part 11: Declarative objects in NCL: nesting objects with NCL code in NCL documents. 21 p. Eng. E-mail: lfgs@inf.puc-rio.br

Abstract: This technical report describes how declarative objects, including objects with NCL code, may be related with other objects in an NCL application, and how declarative object players shall behave. NCL (Nested Context Language)is an XML application language based on the NCM (Nested Context Model) conceptual model for hypermedia document specification, with temporal and spatial synchronization among its media objects.


[MCC13/09]
SOARES, L.F.G.; MORENO, M.F.; SOARES NETO, C.S.; MORENO, M.F.; COSTA, R.R.; BATISTA, C.E.F.; LIMA, B. S.; ARAÚJO, E.C.; NOGUEIRA, E.; SANT'ANNA, F.; LIMA, G.F.; SOUSA JR., J.G.; SAVIGNON, R.; AZEVEDO, R.A.; VEIGA, A.; NAGATO, F. Next Context Language 3.0 - Part 13: Ginga-NCL implementors guide v1.0. 66 p. Port. E-mail: lfgs@inf.puc-rio.br

Abstract: This technical report provides operational guidelines for Ginga-NCL middleware implementations aiming at terrestrial and satellital DTV, and IPTV systems which follows norms ABNT 15606.2 and 15606.5, and ITU-T recommendation H.761.


[MCC14/09]
IVSON, P.; DUARTE, L.; CELES, W. GPU-accelerated uniform grid construction for ray tracing dynamic scenes. 17 p. Eng. E-mail: celes@inf.puc-rio.br

Abstract: We present a novel data-parallel algorithm for quickly rebuilding Uniform Grids on state of the art GPUs. The technique combines very fast scan and sorting procedures to classify scene primitives according to the spatial subdivision. Results demonstrate this routine is not only scalable with scene size, but achieves faster rebuild times than other state of the art implementations. In addition, we have developed a ray-tracing procedure that achieves interactive visualization rates, even when enabling shadows and reflection rays. Since the grid structure can be effciently rebuilt each rendering frame, we can maintain performance with fully animated scenes containing unstructured movements. Overall performance achieved greatly improves upon Uniform Grids on the CPU, while remaining competitive to more adaptive structures such as the BVH and kd-tree.


[MCC15/09]
VALENTE, L.; de SOUZA, C.S.; FEIJÓ, B. Turn off the graphics: designing non-visual interfaces for mobile phone games. 24 p. Eng. E-mail: bfeijo@inf.puc-rio.br

Abstract: Mobile phones are a widespread platform for ICT applications because they are highly pervasive in contemporary society. Hence, we can think of mobile gaming as a serious candidate to being a prominent form of entertainment in the near future. However, most games (for computers, console and mobile devices) make extensive use of the visual medium, which tends to exclude visually-impaired users from the play. While mobile gaming could potentially reach many visually-impaired users, who are very familiar with this technology, currently there seems to be only very few alternatives for this community. In an attempt to explore new interactive possibilities for such users, this work presents an initial study on non-visual interfaces for mobile phone games. It is based on Semiotic Engineering principles, emphasizing communication through aural, tactile and gestural signs, and deliberately excluding visual information. Results include a number of issues that can be incorporated to a wider research agenda about mobile gaming accessibility, both for the visually-impaired and sighted.


[MCC16/09]
GATTI, M.A.C.; LUCENA, C.J.P.; GARCIA, A.F. A pattern language for self organizing systems. 15 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Developers and maintainers of self-organizing software systems need design patterns to facilitate design reuse. To tackle this problem, we propose a catalogue of agent-oriented design patterns for structuring the pivotal mechanisms of a selforganizing system. The presented pattern language has a twofold purpose. First, it defines the common self-organizing behavior and the underlying environment structure. Second, all the patterns describe how the information flow should be designed in a complex self-organizing system. The pattern language also shows how the basic patterns can be composed to design more sophisticated self-organizing mechanisms. The automated guided vehicles application was chosen as a unified example of the pattern language usage, while a number of well-known pattern uses are also described.


[MCC17/09]
SANT'ANNA, F.; SOARES NETO, C.s.; BARBOSA, S.D.J.; SOARES, L.F.G.S. Nested Context Language 3.0 - Aplicações declarativas NCL com objetos NCLua imperativos embutidos. 30 p. Port. E-mail: lfgs@inf.puc-rio.br

Abstract: The Nested Context Language (NCL) allows the development of multimedia applications with spatio-temporal synchronization among media objects, such as videos, sounds and images. In order to extend NCL with a general purpose programming language, objects written with the Lua language, the so called NCLua objects, are also supported. For common media objects, it is the role of the media player to interpret the actions commanded by the NCL formatter, such as start and abortion of media presentations. However, for NCLua objects, this role is attributed to the object author, which can give any semantics to the commanded actions. An NCLua object communicates with the NCL document in which it is embedded through events, in accordance with the transitions in its state machine. This technical report describes how NCLua objects are developed

[MCC18/09]
SILVA, M.T.; LUCENA, C.J.P. Suporte a uma abordagem para uma LPS de SMA com configuração dinâmica. 21 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: Multi-Agent Systems Products Lines (MAS-PL) have been used in order to produce high congurable solutions. In this sense, one of the goals is to characterize an approach for high congurable systems. The presented work aims at provide an approach for dynamic conguration of MAS-PLs, allowing runtime product derivation. As a Case-Study, it has been reused NASA Projects for ANTs conguration. However, several possible congurations have been explored in order to present self-adaptation in parallel with MASPL dynamic capability.


[MCC19/09]
MARTINS, L.O.; SILVA, P.M.; GATTASS, M.An application of optical flow to time-lapse analysis in 2-D seismic images. 10 p. Port. E-mail: mgattass@inf.puc-rio.br

Abstract: Time-lapse (4-D) seismic reservoir monitoring is a relative new technology that is gaining recognition in oil and gas producing areas around the world. In this paper, we propose an application of Horn-Schunck’s optical flow estimation method in order to obtain the movement field between pairs of seismic images. Optical flow estimation can provide important information about velocity of each image pixel. This way, we show that is possible to catch important displacements between pairs of seismic images separated by a time interval. In this work, each seismic image was deformed through the application of a synthetic field. The results obtained show that this method is able to recover with reasonable precision tiny displacements commonly found in time-lapse seismic data.


[MCC20/09]
M0TTA JUNIOR, P.R.; RODRIGUEZ, N.L.R.; LUCENA, C.J.P. On object and component design approaches for parallel programming. 14 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: The evolution of the field of programming traditionally trades performance for more powerful abstractions that are able to simplify the programmer's work. It is possible to observe the effects of this evolution on the parallel programming area. Typically parallel programming focuses on high performance based on the procedural paradigm to achieve the highest possible throughput, but determining the point in which one should trade performance for more powerful abstractions remains an open problem. With the advent of new system level tools and libraries that deliver greater performance without programmer's intervention, the myth that the application programmer should optimize communication code starts to be challenged. As the growing demand for large scale parallel solutions becomes noticeable, problems like code complexity, design and modeling power, maintainability, faster development, greater reliability and reuse, are expected to take part on the decision of which approach to use. In this paper, we discuss the use of new paradigms that provide higher-level abstractions and may provide many benefits to parallel programming developers. We argue that the decision of whether or not one should choose to apply these techniques on an application project remains subjective and depends on many factors related to time to delivery, programmer experience, and complexity, among others.


[MCC21/09]
FURTADO, A.L. A decision-making process for digital storytelling. 19 p. Eng. E-mail: furtado@inf.puc-rio.br

Abstract: The method proposed here to determine, in a simplified but still plausible way, the behaviour of the characters participating in a story is based on rules that associate a given situation with a list of different goals. In view of the rules whose situation holds at the current state, each character engages in a decision-making process along three steps: goal selection, plan selection, and commitment. The selection criteria reflect individual preferences originating, respectively, from drives, attitudes and emotions. Four kinds of inter-character relations are considered, which may lead to goal and plan interferences. A prototype logic programming tool was developed to run experiments.

[MCC22/09]
MOURA, P.N.S.; ENDLER, M. Algoritmos de eleição para redes móveis ad hoc. 13 p. Port. E-mail: endler@inf.puc-rio.br

Abstract: This paper presents the leader election problem in mobile ad hoc and surveys several algorithms in the literature. Two of which were chosen so that an in-dept study and a comparison regarding not only the applicability, but also the computational complexity, were done.

[MCC23/09]
JACYNTHO, M.D.A. Processos para desenvolvimento de aplicações Web. 25 p. Port. E-mail: bib-di@inf.puc-rio.br

Abstract: Web application development presents significant differences from conventional application development. The spectrum varies from technical to organizational differences. Technical means the specific architectures and technologies employed and the impacts involved. Organizational is related to the strategic use of these applications aiming at improving the business. Among other issues, uncertainty, volatility and high competitiveness are innate characteristics which must be carefully addressed. Therefore, the nature of web engineering suggests the need of specialized software processes that cover, in a systematic way, the complete life cycle of hypermedia web applications, in contrast to adopting ad-hoc approaches to comply with the constraints imposed by this application domain. This essay presents an abridge discussion concerned with the impact of these differences on development process for web applications, analyzing some proposals, indentifying the requirements and challenges. This work intends to be an initial step towards the definition of a process suitable to web development, in dimensions such as requirements gathering, user interface, testing and navigation design.

[MCC25/09]
NUNES, I.O.; BARBOSA, S.D.J.; LUCENA, C.J.P. Modeling user preferences into agent architectures: a survey. 12 p. Port. E-mail: lucena@inf.puc-rio.br.

Abstract: Personal agents are becoming popular for automating tasks for users. Given that these agents represent individuals, there is the need to capture user preferences and customize agents according to the users' specific needs. Several approaches have been proposed in order to model user preferences and use them in algorithms that generate an output specific for each user. In this paper we present a survey of these approaches and concepts proposed to represent user preferences, mainly into agent architectures. We also discuss how these concepts are used in the agent reasoning process.