Technical Reports Published in 1996

  • IC-96-20 pdf bib
    Contracting and moving agents in distributed applications based on a service-oriented architecture.
    Bruno R. Schulze and Edmundo R. M. Madeira.
    December 1996. In English, 11 pages.

    Abstract: This paper presents a service-oriented platform for development and execution of distributed applications based on contracting stationary and migrating services. Services are seen as active objects build on top of a middleware using CORBA and added features. Customized services add to the middleware the ability to handle transparently application start-up and distribution according to load-balancing and inverse caching application demand. Services can be considered of any kind ranging from scientific specialized processing to data archiving juke-boxes. An application on system management in scientific experimental environment is driving the work on some aspects of the architecture and the management.

  • IC-96-19 pdf bib
    Uma abordagem de programação inteira para o problema da triangulação de custo mínimo.
    Aminadab P. Nunes and Cid C. de Souza.
    December 1996. In Portuguese, 24 pages.

    Resumo: Dado um conjunto finito de pontos no plano, uma triangulação planar é definida como um conjunto maximal de segmentos de reta conectando estes pontos, tal que dois destes segmentos não se interceptam, exceto nos extremos. Chamamos de triangulação de custo mínimo a triangulação planar cuja soma total dos comprimentos de seus segmentos de reta é mínimo dentre todas as triangulações planares do conjunto de pontos em questão.

    Não se conhece algoritmo polinomial que resolva o problema de determinar a triangulação de custo mínimo de um conjunto de pontos no caso geral, contudo, também não está provado tratar-se de um problema NP-difícil.

    Neste artigo estamos interessados na resolução exata deste problema. Nossa abordagem é baseada em técnicas de programação inteira, em particular avaliamos duas formulações distintas para o problema.

    A primeira formulação é baseada em uma equivalência entre o problema da triangulação de custo mínimo e uma versão restrita do problema do conjunto independente em um grafo. Além das desigualdades obtidas através da observação desta equivalência, mostramos como fortalecer a formulação através de certas propriedades geométricas do problema.

    Avaliamos ainda uma outra formulação baseada principalmente no trabalho apresentado por Loera et. al em The Polytope of All Triangulations of a Point Configuration, 12th European Workshop on Computational Geometry, 1996. Finalmente, reportamos nossos experimentos computacionais.

  • IC-96-18 pdf bib
    Integrating heuristics and spatial databases: A case study.
    Cid C. de Souza, Claudia M. B. Medeiros, and Ricardo S. Pereira.
    December 1996. In English, 16 pages.

    Abstract: This paper presents part of the ongoing efforts at IC-UNICAMP to apply heuristic algorithms to vectorial georeferenced data in order to help decision support in urban planning. The results reported are original in the sense that they combine recent research in both combinatorial algorithm development and geographic databases, using them in the solution of a practical problem. A first prototype, described in the paper, has already been developed and tested against real data on the city of Campinas, to support planning activities for the S ao Paulo State Post Office System, Brazil.

  • IC-96-17 pdf bib
    Workcase-centric workflow model.
    Jacques Wainer and Paulo Barthelmess.
    November 1996. In English, 5 pages.

    Abstract: We present a model of office work and workflow systems that we call workcase centric, based on the view that office work is a collaborative construction of a case artifact. This model allows for the uniform treatment of cases for which the organization has no predefined procedure, of exceptional cases where the standard procedure must be modified, and of standard cases.

  • IC-96-16 pdf bib
    A temporal extension to the parsimonious covering theory.
    Jacques Wainer and Alexandre M. Rezende.
    November 1996. In English, 19 pages.

    Abstract: This paper presents a temporal extension to the parsimonious covering theory (PCT), so instead of associating to each disorder a set of manifestation as it is done in PCT, one associates to each disorder a temporal graph that contains information about duration and elapsed time between the beginning of the manifestations. The definitions of solutions for temporal diagnostic problems is presented as well as algorithms that compute this solution. We also include some limited form of probabilistic information into the model in order to study how categorical rejection, the elimination of explanations that contain a disease for which a necessary manifestation is not present, interacts with temporal information. An application in a medical domain is presented and discussed.

  • IC-96-15 pdf bib
    Sinergia em desenho de grafos usando springs e pequenas heurísticas.
    Hugo A. D. do Nascimento, Cândido F. X. de Mendonça Neto, and Pedro S. de Souza.
    October 1996. In Portuguese, 12 pages.

    Resumo: Este trabalho mostra que fazendo-se uso de ``A-Teams'' (Times Assíncronos) podemos combinar algoritmos como Springs, Baricentro e heurísticas aleatórias, de uma maneira simples e flexível, de modo que cooperem sinergeticamente permitindo desenho de grafos com duas características estéticas, cujos problemas correspondentes são conflitantes e NP-difíceis.

  • IC-96-14 pdf bib
    Ensino de estruturas de dados e seus algoritmos através de implementação com animações.
    Pedro J. de Rezende and Islene C. Garcia.
    November 1996. In Portuguese, 9 pages.

    Resumo: Descrevemos as abordagens passiva e ativa utilizadas para ensino de algoritmos e estruturas de dados com recursos de animações gráficas. Introduzimos uma nova abordagem construtiva e descrevemos o ambiente Astral projetado para explorar seus benefícios. Nesta abordagem, além do estudante ter acesso a aplicativos exemplos providos de animações gráficas que ilustram o funcionamento de algoritmos, ele também realiza suas próprias animações durante o processo de implementação da estrutura e dos algoritmos de maneira simplificada mas com visualização gráfica notável e resultados sensivelmente positivos na aprendizagem. A experiência de uso deste ambiente tem mostrado grandes vantagens no ensino de disciplinas de graduação na área de computação.

  • IC-96-13 pdf bib
    Algoritmos de afinamento tridimensional: Exemplos de técnicas de otimização.
    Francisco N. Bezerra and Neucimar J. Leite.
    October 1996. In Portuguese, 14 pages.

    Abstract: Some algorithms have been proposed to the problem of thinning 3D binary images. These algorithms use homotopic removal of points to achieve an skeleton whose structure preserves the topology of the original image. This work deals with technics for the optimization of such algorithms. Briefly, we present two methods that avoid unnecessary topology checking of the image points, leading to less time consuming sequential thinning.

  • IC-96-12 pdf bib
    Modelling the output process of an ATM multiplexer with correlated priorities.
    Nelson L. S. Fonseca and John A. Silvester.
    August 1996. In English, 25 pages.

    Abstract: The traffic in the future Broadband Integrated Digital Networks is highly correlated and neglecting these correlations leads to a dramatic underestimation of performance. Being able to accurately estimate end-to-end performance is of paramount importance for traffic control. The purpose of this paper is to introduce a procedure for modeling the output process of a finite discrete time queue with selective discard mechanism loaded with a prioritized Discrete-time Batch Markovian Arrival Process (D-BMAP[H,L]) in which the priority level of a cell depends on the priority level of other cells in the flow. We show through numerical examples that his procedure is reasonably accurate. Moreover, we introduce a framework for the analysis of queueing networks with prioritized Markov Modulated flows.

  • IC-96-11 pdf bib
    Network design for the provision of distributed home theatre services.
    Nelson L. S. Fonseca, Cristiane M. R. Franco, and Frank Schaffa.
    August 1996. In English, 26 pages.

    Abstract: Video services is both a major business driver and a bandwidth consumer for the future broadband integrated network. Understanding different video services requirements is of paramount importance for network design. In this paper, we study Distributed Home Theatre, a video service which allows distributed users to debate a film. We investigate the interplay between bandwidth reduction and program replication techniques. We evaluate the impact of user distribution, network topology and number of users per session on this interplay. Moreover, we state a bandwidth minimization principle which can be used in admission control policies.

  • IC-96-10 pdf bib
    A CPU for educational applications designed with VHDL and FPGA.
    Nelson V. Augusto, Mário L. Côrtes, and Paulo C. Centoducatte.
    October 1996. In English, 12 pages.

    Abstract: This paper presents a CPU designed for educational applications to be used in the Computer Architecture Laboratories, at IC/UNICAMP. The CPU will be used as a basic plataform in order to introduce to the students novel design concepts such as VHDL, Logic Synthesis and FPGAs as well as a means to explore computer architecture characteristics and functionality. The paper also presents a few experiment possibilities, where the students incorporate new functions to the basic CPU using advanced techniques. The experiments complexity, the required design changes and their effects on the FPGA programming are also discussed.

  • IC-96-09 pdf bib
    Sequential and parallel experimental results with bipartite matching algorithms.
    João C. Setubal.
    September 1996. In English, 23 pages.

    Abstract: We present experimental results for four bipartite matching algorithms on 11 classes of graphs. The algorithms are depth-first search (DFS), breadth-first search (BFS), the push-relabel algorithm, and the algorithm by Alt, Blum, Mehlhorn, and Paul (ABMP). DFS was thought to be a good choice for bipartite matching but our results show that, depending on the input graph, it can have very poor performance. BFS on the other hand has generally very good performance. The results also show that the ABMP and push-relabel implementations are similar in performance, but ABMP was faster in most cases. We did not find a clear-cut advantage of ABMP over BFS or vice-versa, but both the ABMP and push-relabel implementations have generally smaller growth rates than BFS, and should thus be preferred if very large problems are to be solved. For small problems BFS is the best choice. We also present experimental results from a parallel implementation of the push-relabel algorithm, showing that it can be up to three times faster than its sequential implementation, on a shared-memory multiprocessor using up to 12 processors.

  • IC-96-08 pdf bib
    The effectiveness of multi-level policing mechanisms in ATM traffic control.
    John A. Silvester, Nelson L. S. Fonseca, G. S. Mayor, and Solange P. S. Sobral.
    August 1996. In English, 17 pages.

    Abstract: Statistical multiplexing was adopted in the ATM standard due to its potential for effective use of bandwidth. Coping with diverse Quality-of-Service requirements and with the variable-bit rate nature of multimedia applications makes traffic control a challenging task. In this paper, we show the advantages of adopting multi-level policing mechanism for ATM traffic control and compare different multi-level mechanisms based on the Leaky Bucket, on the Sliding Window and on the Jumping Window mechanism.

  • IC-96-07 pdf bib
    Conjunto fonte máximo em grafos de comparabilidade.
    Marcos F. Andrielli and Célia P. de Mello.
    July 1996. In Portuguese, 10 pages.

    Resumo: Um grafo de comparabilidade admite várias orientações transitivas. Cada uma delas determina um conjunto fonte para o grafo. Neste artigo propomos um algoritmo que encontra uma orientação transitiva que maximiza o conjunto fonte de um grafo de comparabilidade.

  • IC-96-06 pdf bib
    User interface issues in geographic information systems.
    Juliano L. de Oliveira and Claudia M. B. Medeiros.
    July 1996. In English, 48 pages.

    Abstract: Recently, much research effort has been employed in the area of Geographic Information Systems due to the vast potential for applications of this technology. Simultaneously, user interface subsystems of software products have received attention since the interface has marked influence in software acceptance. This paper presents an overview of research done in the intersection of these areas. The main approaches and the current problems of user interfaces for Geographical Information Systems are discussed and analyzed. This study concludes with open problems and new research directions for future work in this area.

  • IC-96-05 pdf bib
    Estudo comparativo de métodos para avaliação de interfaces homem-computador.
    Sílvio Chan and Heloisa V. da Rocha.
    September 1996. In Portuguese, 26 pages.

    Resumo: Neste relatório é apresentado um estudo comparativo de métodos de avaliação de interfaces homem-computador. O propósito deste estudo é verificar a aplicabilidade destes métodos, confrontando parâmetros tais como o perfil dos avaliadores, o envolvimento dos usuários e desenvolvedores, restrições de tempo e material, escopo de avaliação, passos e duração da avaliação, adaptação a tipos específicos de problemas de utilizabilidade, e outros. Com este estudo pretendemos fornecer uma visão comparativa e classificatória dos métodos de avaliação para auxiliar organizadores de avaliação na escolha de métodos e no planejamento de uma melhor abordagem de avaliação.

  • IC-96-04 pdf bib
    On the edge-colouring of split graphs.
    Celina M. H. de Figueiredo, João Meidanis, and Célia P. de Mello.
    June 1996. In English, 7 pages.

    Abstract: We consider the following question: can split graphs with odd maximum degree be edge-coloured with maximum degree colours? We show that any odd maximum degree split graph can be transformed into a special split graph. For this special split graph, we were able to solve the question, in case the graph has a quasi-universal vertex.

  • IC-96-03 pdf bib
    Cartas náuticas eletrônicas: Operações e estruturas de dados.
    Cleomar M. M. de Oliveira and Neucimar J. Leite.
    May 1996. In Portuguese, 25 pages.

    Resumo: Neste trabalho nós abordamos alguns problemas relativos ao desenvolvimento de um sistema de cartas náuticas eletrônico, através de uma abordagem de suas funções básicas e das estruturas de dados associadas. Com a utilização de cartas náuticas impressas como fonte primária de dados, apresentamos uma seqüência de operações a serem realizadas durante as fases de digitalização, pré-processamento e processamento das imagens. São analisados, ainda, esquemas de representação, considerando as características particulares dessas imagens e as operações a serem realizadas sobre as mesmas.

  • IC-96-02 pdf bib
    Automatic visualization of two-dimensional cellular complexes.
    Rober M. Rosi and Jorge Stolfi.
    May 1996. In English, 33 pages.

    Abstract: A two-dimensional cellular complex is a partition of a surface into a finite number of elements--faces (open disks), edges (open arcs), and vertices (points). The topology of a cellular complex consists of the abstract incidence and adjacency relations among its elements.

    Here we describe a program that, given only the topology of a cellular complex, computes a geometric realization of the same--that is, a specific partition of a specific surface in three-space--guided by various aesthetic and presentational criteria.

  • DCC-96-01 pdf bib
    Construção de interfaces homem-computador: Uma proposta revisada de disciplina de graduação.
    Fábio N. de Lucena and Hans K. E. Liesenberg.
    January 1996. In Portuguese, 13 pages.

    Resumo: A interface homem-computador é um dos componentes mais importantes de um sistema interativo. Grande parte das atuais propostas de grades curriculares de Cursos de Ciência da Computação não tratam adequadamente as várias questões pertinentes a este tópico. Este texto propõe a organização de uma disciplina de graduação desta natureza. A construção da interface de um sistema interativo é apresentada e exemplifica o tipo de trabalho prático que pode ser realizado pelos alunos.

  • Instituto de Computação :: Universidade Estadual de Campinas
    Caixa Postal 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas/SP - Brasil • Fone: [19] 3521-5838