RCAAP Repository

A representação e execução de processos de negócio têm gerado importantes desafios na área de Ciência da Computação. Um desses desafios é a escolha do melhor arcabouço formal para a especificação dos controles de fluxo padrões. Algumas linguagens defendem o uso de redes de Petri ou álgebras de processos como base formal. O uso de redes de Petri para especificar workflows clássicos é uma abordagem bastante conhecida. Entretanto, pesquisas recentes vêm difundindo o uso de novas extensões da álgebra de processos como uma alternativa para a especificação formal de workflows. A principal contribuição deste trabalho é a definição da Navigation Plan Definition Language (NPDL). A NPDL foi implementada como uma extensão da linguagem SQL. Ela é uma alternativa para a representação de workflows que utiliza a álgebra de processos como arcabouço formal. A NPDL promove uma separação explícita entre o ambiente de especificação e o ambiente de execução de um workflow. Esta separação propicia o reaproveitamento de passos de negócio e o uso das propriedades da álgebra de processos não só na modelagem, mas também no controle da execução dos processos. Após a especificação de um workflow por meio da NPDL, a execução dos passos que o definem é controlada pela ferramenta NavigationPlanTool. Essa ferramenta é a segunda contribuição deste trabalho de pesquisa.

O modelo de atores tem sido visto como uma abordagem alternativa à programação concorrente convencional, baseada em travas e variáveis de condição. Atores são agentes computacionais que se comunicam por troca de mensagens e que possuem uma caixa de correio e um comportamento. As mensagens destinadas a um ator são armazenadas na caixa de correio do ator e processadas de maneira assíncrona. Sistemas de middleware orientados a mensagens trabalham com troca assíncrona de mensagens e formam uma base que simplifica o desenvolvimento de aplicações distribuídas. Tais sistemas permitem interoperabilidade com baixo acoplamento e provêm suporte para tratamento robusto de erros em caso de falhas. Message brokers são frequentemente apresentados como uma tecnologia que pode mudar a maneira com que sistemas distribuídos são construídos. A especificação AMQP é uma proposta recente de padronização de um protocolo para message brokers. Neste trabalho exploramos a potencial sinergia entre um message broker e uma implementação do modelo de atores. Criamos uma versão modificada da implementação do modelo de atores do projeto Akka que utiliza um message broker AMQP como mecanismo de transporte de mensagens para atores remotos.

Em Biomedicina, a detecção e a quanticação de anormalidades presentes num sinal são desejáveis. Uma estratégia de codicação baseada em extração de características, tais como picos ou frequências, pode não capturar todas as irregularidades. Assim, uma representação baseada em funções de base denidas com conhecimento a priori do sinal pode ser mais precisa para aplicações biomédicas. A escolha das funções base depende da natureza siológica do sinal e de suas peculiaridades. Sinais de eletrocardiograma (ECG) e eletroencefalograma (EEG) exibem características bem denidas. ECG, por exemplo, é um sinal elétrico composto de uma forma de onda especíca (P, QRS e T). Se as características de um sinal a ser sintetizado são bem compreendidas, é possível derivar uma assinatura para o sinal. Uma codicação apropriada permite a extração de parâmetros relevantes para sua análise, tais como anormalidades num ciclo cardíaco representadas por uma alteração no sinal de ECG, ou então uma excitação das ondas cerebrais representada por uma modicação no sinal de EEG. O objetivo deste projeto é introduzir uma nova técnica de codicação de sinais, que representa um sinal pela soma de funções sigmoides para aproximar iterativamente o sinal medido, com foco em aplicações biomédicas. Funções sigmoides tendem a reproduzir bem as grandes variações presentes em sinais biomédicos, daí a escolha de usá-las na codicação deste tipo de sinal. Serão explorados o nível de compressão dos dados, bem como a taxa de convergência. A técnica desenvolvida será comparada com técnicas convencionais de codicação e sua robustez será avaliada. Uma estratégia de codicação ótima pode trazer benefícios não só para a compressão, mas também na criação de assinaturas de sinais representando tanto condições siológicas normais como patológicas.

Estudos de prognóstico clínico consistem na predição do curso de uma doença em pacientes e são utilizados por profissionais da saúde com o intuito de aumentar as chances ou a qualidade de sua recuperação. Sob a perspectiva computacional, a criação de um modelo prognóstico clínico é um problema de classificação, cujo objetivo é identificar a qual classe (dentro de um conjunto de classes predefinidas) uma nova amostra pertence. Este projeto visa a criar modelos prognósticos de lesões traumáticas do plexo braquial, um conjunto de nervos que inervam os membros superiores, utilizando dados de pacientes adultos com esse tipo de lesão. Os dados são provenientes do Instituto de Neurologia Deolindo Couto (INDC) da Universidade Federal do Rio de Janeiro (UFRJ) e contêm dezenas de atributos clínicos coletados por meio de questionários eletrônicos. Com esses modelos prognósticos, deseja-se identificar de maneira automática os possíveis preditores do curso desse tipo de lesão. Árvores de decisão são classificadores frequentemente utilizados para criação de modelos prognósticos, por se tratarem de um modelo transparente, cujo resultado pode ser examinado e interpretado clinicamente. As Florestas Aleatórias, uma técnica que utiliza um conjunto de árvores de decisão para determinar o resultado final da classificação, podem aumentar significativamente a acurácia e a generalização dos modelos gerados, entretanto ainda são pouco utilizadas na criação de modelos prognósticos. Neste projeto, exploramos a utilização de florestas aleatórias nesse contexto, bem como a aplicação de métodos de interpretação de seus modelos gerados, uma vez que a transparência do modelo é um aspecto particularmente importante em domínios clínicos. A estimativa de generalização dos modelos resultantes foi feita por meio de métodos que viabilizam sua utilização sobre um número reduzido de instâncias, uma vez que os dados relativos ao prognóstico são provenientes de 44 pacientes do INDC. Além disso, adaptamos a técnica de florestas aleatórias para incluir a possível existência de valores faltantes, que é uma característica presente nos dados utilizados neste projeto. Foram criados quatro modelos prognósticos - um para cada objetivo de recuperação, sendo eles a ausência de dor e forças satisfatórias avaliadas sobre abdução do ombro, flexão do cotovelo e rotação externa no ombro. As acurácias dos modelos foram estimadas entre 77% e 88%, utilizando o método de validação cruzada leave-one-out. Esses modelos evoluirão com a inclusão de novos dados, provenientes da contínua chegada de novos pacientes em tratamento no INDC, e serão utilizados como parte de um sistema de apoio à decisão clínica, de forma a possibilitar a predição de recuperação de um paciente considerando suas características clínicas.

While there is a wide variety of both open source and proprietary source code static analyzers available in the market, each of them usually performs better in a small set of problems, making it hard to choose one single tool to rely on when examining a program. Combining the analysis of different tools may reduce the number of false negatives, but yields a corresponding increase in the number of false positives (which is already high for many tools). An interesting solution, then, is to filter these results to identify the issues least likely to be false positives. This work presents kiskadee, a system to support the usage of static analysis during software development by providing carefully ranked static analysis reports. First, it runs multiple static analyzers on the source code. Then, using a classification model, the potential bugs detected by the static analyzers are ranked based on their importance, with critical flaws ranked first, and potential false positives ranked last. To train kiskadee\'s classification model, we post-analyze the reports generated by three tools on synthetic test cases provided by the US National Institute of Standards and Technology. To make our technique as general as possible, we limit our data to the reports themselves, excluding other information such as change histories or code metrics. The features extracted from these reports are used to train a set of decision trees using AdaBoost to create a stronger classifier, achieving 0.8 classification accuracy (the combined false positive rate from the used tools was 0.61). Finally, we use this classifier to rank static analyzer alarms based on the probability of a given alarm being an actual bug. Our experimental results show that, on average, when inspecting warnings ranked by kiskadee, one hits 5.2 times less false positives before each bug than when using a randomly sorted warning list.

Esta tese de doutorado aborda os tópicos de modelagem e de reconhecimento de objetos estruturados, ou sistemas estruturados de objetos, em imagens. Um objeto ou sistema estruturado é aquele que pode ser descrito através de elementos primitivos que o compõem e pelas relações existentes entre esses elementos. Por exemplo, uma aeronave pode ser descrita pelos seguintes elementos primitivos: asas direita e esquerda, fuselagem e cockpit. O aspecto relacional de um objeto estruturado direciona sua representação computacional e seu reconhecimento em imagens ao paradigma estrutural de reconhecimento de padrões. Contudo, a variabilidade das características dos seus elementos primitivos é melhor representada através do paradigma estatístico de reconhecimento de padrões. Devido à complementaridade dos paradigmas, a conjunção dessas abordagens é um tema de pesquisa de interesse atual. Para conjugar esses dois aspectos, esta tese propôs uma metodologia que combina o conhecimento a priori das relações que caracterizam um objeto estruturado com dados estatísticos coletados de amostras desse objeto, num modelo híbrido denominado grafo estatístico-relacional (GER). Segundo essa representação, foi estudada uma abordagem probabilística para reconhecer um objeto estruturado em imagens. Nesse cenário, o GER modelo é considerado uma variável aleatória, enquanto uma rotulação de uma imagem de entrada é interpretada como uma potencial observação do modelo. A tarefa de reconhecimento foi então formulada como um problema de otimização, que busca maximizar a probabilidade da observação de acordo com o modelo. O método foi aplicado à modelagem de órgãos abdominais em imagens de ressonância magnética não-contrastadas. Esses órgãos apresentam um arranjo espacial consistente em imagens distintas, além de propriedades de aparência e anatômicas variáveis, o que vem ao encontro da proposta da representação por GER e da abordagem probabilística para o reconhecimento dos órgãos em novas imagens.

A implantação de composições de serviços web de grande escala apresentam vários desafios, tais como falhas corriqueiras na infraestrutura, heterogeneidade tecnológica, distribuição do sistema por diferentes organizações e atualização frequente dos serviços em operação. Nesta dissertação, estudamos como uma implantação automatizada baseada em middleware pode auxiliar na superação de tais desafios. Para isso, desenvolvemos o CHOReOS Enactment Engine, um sistema de middleware que possibilita a implantação distribuída e automatizada de composições de serviços web em uma infraestrutura virtualizada, operando no modelo de computação em nuvem denominado Plataforma como um Serviço. O middleware desenvolvido é avaliado qualitativamente em comparação a abordagens de implantação ad-hoc e quantitativamente pela sua escalabilidade em relação ao tempo de implantação das composições de serviços.

A busca por explicações de fatos ou fenômenos é algo que sempre permeou o raciocínio humano. Desde a antiguidade, o ser humano costuma observar fatos e, de acordo com eles e o conhecimento presente, criar hipóteses que possam explicá-los. Um exemplo clássico é quando temos consulta médica e o médico, após verificar todos os sintomas, descobre qual é a doença e os meios de tratá-la. Essa construção de explicações, dado um conjunto de evidências que o indiquem, chamamos de \\textit{abdução}. A abdução tradicional para a lógica clássica estabelece que o dado meta não é derivado da base de conhecimento, ou seja, dada uma base de conhecimento $\\Gamma$ e um dado meta $A$ temos $\\Gamma ot \\vdash A$. Métodos clássicos de abdução buscam gerar um novo dado $H$ que, juntamente com uma base de conhecimento $\\Gamma$, possamos inferir $A$ ($\\Gamma \\cup H \\vdash A$). Alguns métodos tradicionais utilizam o tableaux (como em \\cite) para a geração da fórmula $H$. Aqui, além de lidarmos com a abdução baseada em corte, através do KE-tableaux, que não necessita assumir que o dado meta não seja derivado da base de conhecimento, lidaremos também com a lógica probabilística, redescoberta por Nilsson, em \\cite, onde temos a atribuição de probabilidades a fórmulas. Dizemos que uma instância em lógica probabilística é consistente se existe uma distribuição probabilística consistente sobre as valorações. Determinar essa distribuição probabilística é que o chamamos de problema PSAT. O objetivo de nosso trabalho é definir e estabelecer o que é uma abdução em Lógica Probabilística (abdução em PSAT) e, além disso, fornecer métodos de abdução para PSAT: dada uma instância PSAT $\\left\\langle \\Gamma, \\Psi ightangle$ na forma normal atômica \\cite e uma fórmula $A$ tal que existe uma distribuição probabi bylística $\\pi$ que satisfaz $\\left\\langle \\Gamma, \\Psi ightangle$ e $\\pi(A) = 0$, cada método é capaz de gerar uma fórmula $H$ tal que $\\left\\langle \\Gamma \\cup H , \\Psi ightangle \\!\\!|\\!\\!\\!\\approx A$ onde $\\pi(A) > 0$ para toda distribuição $\\pi$ que satisfaça $\\left\\langle \\Gamma \\cup H , \\Psi ightangle$. Iremos também demonstrar que alguns dos métodos apresentados são corretos e completos na geração de fórmulas $H$ que satisfaçam as condições de abdução.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs

A estimação da iluminação é essencial para aplicações de realidade mista que se propõem a integrar elementos virtuais a cenas reais de maneira harmoniosa e sem a perda do realismo. Um dos métodos mais utilizados para fazer essa estimação é conhecido como iluminação baseada em imagens (Image Based Lighting - IBL), método que utiliza light probes para capturar a intensidade da iluminação incidente em uma cena. Porém, IBL estima a iluminação incidente apenas para um determinado instante e posição. Nesta dissertação, será avaliado um modelo de iluminação que utiliza séries temporais de imagens de light probes, obtidas de maneira esparsa em relação ao tempo, para renderizar cenas em instantes arbitrários. Novas cenas contendo objetos virtuais poderão ser renderizadas utilizando imagens de light probes artificiais, geradas a partir das amostras da iluminação originais. Diferentes funções de interpolação e aproximação são avaliadas para modelar o comportamento luminoso. As imagens finais produzidas pela metodologia também são verificadas por voluntários, de modo a determinar o impacto na qualidade de renderização em aplicações de realidade mista. Além da metodologia, foi desenvolvida uma ferramenta de software em forma de plugin para facilitar o uso de IBL temporalmente variável, permitindo assim a renderização realística de objetos virtuais para instantes arbitrários

Um emparelhamento em um grafo é um conjunto de arestas duas a duas não adjacentes. Dado um grafo G com pesos em suas arestas, o problema do emparelhamento de peso é máximo é encontrar um emparelhamento cuja soma dos pesos de suas arestas é máxima. Neste trabalho estudamos diferentes soluções para esse problema. Estudamos algoritmos combinatórios que resolvem o problema no caso em que G é bipartido e no caso geral. O algoritmo de Edmonds é um algoritmo polinomial cuja complexidade de tempo é O(n^4), onde n é o número de vértices do grafo G. Discutimos nesse trabalho nossa implementação desse algoritmo. Num trabalho de 1985, Grötschel e Holland propuseram o uso de ferramentas de programação linear para resolver o mesmo problema. O método chamado de planos-de-corte baseia-se em um resultado de Padberg e Rao de que o problema da separação associado ao poliedro dos emparelhamentos pode ser resolvido em tempo polinomial. Neste trabalho fizemos implementações dos dois métodos e os utilizamos para resolver diversos tipos de instâncias do problema. Nossa conclusão é que o método poliédrico, apesar de utilizar ferramentas genéricas, é bastante eficiente na prática.

Neste trabalho são apresentados dois novos descritores de forma para tarefas de recuperação de imagens por conteúdo (CBIR) e análise de formas, que são construídos sobre uma extensão do conceito de tensor scale baseada na Transformada de Distância Euclidiana (EDT). Primeiro, o algoritmo de tensor scale é utilizado para extrair informações da forma sobre suas estruturas locais (espessura, orientação e anisotropia) representadas pela maior elipse contida em uma região homogênea centrada em cada pixel da imagem. Nos novos descritores, o limite do intervalo das orientações das elipses do modelo de tensor scale é estendido de 180º para 360º, de forma a melhor discriminar a descrição das estruturas locais. Então, com base em diferentes abordagens de amostragem, visando resumir informações mais relevantes, os novos descritores são construídos. No primeiro descritor proposto, Tensor Scale Sector (TSS), a distribuição das orientações relativas das estruturas locais em setores circulares é utilizada para compor um vetor de características de tamanho fixo, para uma caracterização de formas baseada em região. No segundo descritor, o Tensor Scale Band (TSB), foram considerados histogramas das orientações relativas extraídos de bandas concêntricas, formando também um vetor de características de tamanho fixo, com uma função de distância de tempo linear. Resultados experimentais com diferentes bases de formas (MPEG-7 e MNIST) são apresentados para ilustrar e validar os métodos. TSS demonstra resultados comparáveis aos métodos estado da arte, que geralmente dependem de algoritmos custosos de otimização de correspondências. Já o TSB, com sua função de distância em tempo linear, se demonstra como uma solução adequada para grandes coleções de formas.

Mobile music applications are becoming commonplace around the world, and mobile devices are used as digital instruments everywhere. Controlling, performing, or composing music in real time with these devices encourages collaboration and interaction, as telecommunication improvements allow many people to cooperate through local networks or the Internet. In this context, the aim of this thesis is to evaluate mobile technologies that might be suitable for mobile musicians and their audiences while performing or composing. Specifically, the main goal is to explore technologies for collaborative mobile music and to obtain quantitative and qualitative data regarding these technologies and their settings, so that composers might take full advantage of the available options for mobile applications. This evaluation focuses on message exchange using Multicast, Unicast, and Cloud Services, using academic networks as the main pathway. With these services, messages are organized as packet streams, characterized by different sizes and time intervals. Evaluation also includes the development of several applications that make use of these technologies running on Android devices and web browsers. These applications were used in actual performances, serving as both evaluation tools and experimental music instruments. The results were analyzed in terms of round trip time and data loss under very different configuration scenarios, demonstrating that although some obvious impediments are unavoidable (e.g. significant delays in international settings), it is possible to choose the specific technology and achieve interesting results under most music application scenarios. I argue that although in theory Multicast appears to be the best technology to use by far, it is the most difficult to implement due to the burden of configuring every step of the network pathway. On the other hand, Cloud Services are certainly slower than direct connections, but are the most compatible and easiest technology to set up, and are definitely suitable for many collaborative music experiences. To conclude, there is a discussion of how mobile music practitioners can take advantage of these results for composition and performance by considering specific technological advantages or drawbacks that are inherent to each technology and setting.

Nos sistemas operacionais atuais não há um escalonador adequado para tratar aplicações de tempo real soft. Estas tarefas se caracterizam pela co-existência com outras aplicações de tempo real ou convencionais. No âmbito das políticas de escalonamento existentes, adotou-se nesta dissertação o SMART (Scheduling Multimedia Applications Real-Time) como solução para o problema mencionado. Esta política foi analisada, projetada e implementada como escalonador do sistema operacional LINUX. O objetivo da implementação realizada foi analisar o desempenho deste escalonador, bem como o desempenho de uma aplicação multimídia neste sistema em uma situação de sobrecarga. A aplicação de tempo real construída em TK/TCL foi intitulada 'Controle de aproximação de aeronaves em aeroportos'. Os testes foram realizados com a aplicação executando sozinha, a aplicação com mais 41 processos (20 processos que consumiam memória, 20 processos que gastavam CPU e 1 processográfico), a aplicação com 10 processos (todos gráficos) e a aplicação com um processo de compilação do processador de texto emacs versão 20.2. Isto no sistema LINUX com o SMART e com seus escalonadores padrão, realizando-se uma análise comparativa dos resultados obtidos e dos custos de escalonamento. Esta dissertação também apresenta uma pequena resenha dos escalonadores de tempo real, os quais foram classificados sob alguns paradigmas que os caracterizam. Adicionalmente, exibe-se os esforços atuais na comunidade LINUX, comparando-se os sistemas estudados com o LINUX modificado pela inclusão do escalonador SMART

Dados um texto e um padrão, o problema de busca de padrões em textos consiste em determinar as posições do texto onde existe uma ocorrência do padrão. Quando o texto e padrão são cadeias de caracteres, a busca é dita unidimensional. Quando ambossão matrizes, a busca é dita ser bidimensional. Existem variações deste problema onde se permite a busca do padrão, de alguma maneira, modificado. A modificação que permitiremos ao nosso padrão é que ele possa estar escalado. Descrevemosalgoritmos seqüencias lineares para estes problemas, uni ou bidimensionais, com e sem escala, presentes na literatura. Para o caso bidimensional sem escala é apresentado, ainda, um algoritmo de tempo sublinear sob determinadas condições nasmatrizes de entrada. Para estes problemas propomos novos algoritmos paralelos, utilizando o modelo CGM (Coarse Grained Multicomputers), cujos tempos de computação local são lineares na entrada (local), consomem memória também linear e utilizamapenas uma rodada de comunicação em que são trocados, no máximo, uma quantidade também linear de dados. As condições do modelo são, assim, respeitadas. Do nosso conhecimento, não há na literatura outros algoritmos paralelos em modelos degranularidade grossa para o problema de busca unidimensional com escala e para os problemas de busca bidimensional com ou sem escala. Estes algoritmos propostos foram implementados em linguagem C, utilizando interface PVM e foram executados namáquina Parsytec PowerXplorer. Os resultados experimentais obtidos mostraram que as implementações tiveram ganhos significativos ao utilizar-se mais de um processador

Nesta dissertação apresentamos duas vertentes da pesquisa em aprendizagem computacional, uma formal e outra empírica, destacando o modelo de análise 'Provavelmente Aproximadamente Correto' (PAC) e o algoritmo REAL de indução de árvores de decisãosobre atributos de domínio real. A seguir, levantamos a curva de aprendizagem do algoritmo REAL sobre uma base de dados padrão para testes de algoritmos de aprendizagem desta natureza e comparamos esta curva com as previsões teóricas dadas pelomodelo PAC e pelo modelo de Convergência Uniforme. Fica evidente a grande lacuna entre estes resultados e então propomos algumas possibilidades de aprofundamento deste análise

O paradigma de orientação a objetos se consolidou ao longo da década de 90 e tem demonstrado grande potencial em facilitar o tratamento de questões de evolução e mudanças em sistemas. Entretando, diversos problemas ainda são encontrados namanutenção de sistemas construidos sob a ótica dos conceitos e abstrações presentes neste paradigma. Recentemente novos enfoques para projeto orientado a objetos têm sido propostos com o intuito de favorecer requisitos de manutenciobilidade ereutilização/evolução de sistemas orientados a objetos. Este trabalho descreve um estudo comparativo do impacto das técnicas de programação orientada a aspectos e programação adaptativa com relações de contexto no projeto de sistemas comrequisitos de adaptação estática e dinâmica. O estudo foi conduzido através da reengenharia do projeto dos sistemas: JAWS - um servidor Web adaptativo - e SPIN - um sistema operacional extensível. Nosso objetivo foi analisar e avaliar aaplicabilidade das técnicas no projeto de sistemas mais flexíveis a mudanças futuras. O estudo demonstra que a aplicação dos preceitos de programação orientada a aspectos e programação adaptativa com relações de contexto pode trazer diversosbenefícios para o projeto de sistemas adaptáveis, entre eles: separação de interesses e facilidades de reutilização, na evolução estática, na configuração dinâmica e no entendimento progressivo da estrutura e comportamento do sistema. O trabalhopropõe ainda uma categorização para os tipos de adaptações encontrados em sistemas de software

Problemas em geometria computacional permitem a modelagem de situações do mundo físico no computador, de forma que esses problemas possam ser resolvidos eficientemente. Estudamos algoritmos e estruturas de dados para a solução de problemas de geometria computacional no âmbito cinético, ou seja, onde admitimos que os objetos geométricos (pontos, retas, polígonos, etc.) possuam movimento associado. Com isso, nos problemas cinéticos o valor dos atributos geométricos, que são propriedades geométricas de um conjunto, se altera com o passar do tempo. Nesta dissertação abordamos, no cenário cinético, o problema de se manter o máximo de um conjunto, o par de pontos mais próximo, o fecho convexo e o diagrama de Voronoi. Esses são exemplos de atributos geométricos. Para que possamos manter atributos geométricos sobre um conjunto de objetos em movimento de forma eficiente, apresentamos um modelo proposto por Basch, Guibas e Hershberger, que introduz as estruturas de dados cinéticos. Elas são compostas de uma prova da corretude de atributo sendo 'animada' através do tempo. Apesar do movimento contínuo de cada objeto, o atributo somente será alterado pela ocorrência de eventos em momentos discretos no tempo. O modelo também introduz medidas para a análise do desempenho de tais estruturas sob quatro diferentes pontos de vista. Uma estrutura de dados cinética, segundo o modelo, deve ser eficiente, local, compacta e ter resposta rápida. Apresentamos também uma estratégia de implementação para as estruturas de dados cinéticas e exemplificamos sua utilização no problema do máximo

Embora a programação concorrente tenha se popularizado, construir um programa concorrente correto é ainda uma tarefa muito difícil pois a falha exibida pelo programa pode ser dependente do escalonamento e apenas raramente se repetir. Nesta dissertação é descrita uma nova ferramenta, chamada Ladybug, capaz de detectar dinamicamente e existência de condições de disputa em programas Java. Ladybug rescreve classes Java já compiladas, inserindo invocações a métodos de monitoramento. O algoritmo utilizado pelos métodos de monitoramento (Ladyburg oferece dois), bem como sua implementação (privilegiando velocidade ou economia de melhoria), são escolhidos pelo usuário no momento da execução do programa escrito. Ladybug foi utilizadacom problemas cláasicos de concorrencia, programas de alunos de graduação da disciplina 'Programação Concorrente', um servidor e um cliente HTTP, e pareceu ser efetiva na descoberta de condições de disputa

Neste trabalho, estaremos tratando fundamentalmente de teorias formais. Desta forma, cada sistema baseado em conhecimento considerado será tratado por meio da teoria formal que implementa. Conseqüentemente, consideraremos um sistema completamente definido pela caracterização da linguagem na qual ele é codificado, seus axiomas e regras de inferências válidas para seu funcionamento. Sob esta ótica, torna-se possível caracterizar o processo de compartilhamento de conhecimento como a interação dos formalismos implementados pelos sistemas participantes. Entretanto é impostante que os resultados teóricos obtidos sejam também reproduzidos nas implementações de sistemas que codifiquem, em liguagens executáveis por computadores, os formalismos analisados e os métodos propostos. Torna-se, então, útil a elaboração de programas que ilustrem os resultados obtidos. Claramente, o trabalho aqui proposto não tem como objetivo principal a construção de um programa. A importânciado desenvolvimento e implementação de um sistema reside na possibilidade de se avaliar um modelo teórico pelo comportamento de um programa. Enfim, todos os programas propostos e desenvolvidos np decorrer desta pesquisa têm como objetivo dar suporte a uma teoria e não compor um sistema comercial