RCAAP Repository

Sistemas computacionais são constituídos por componentes de hardware e software que podem eventualmente falhar. Por esse motivo, o mecanismo de transação sempre foi imprescindível para a construção de sistemas robustos. O suporte transacional para a tecnologia Web services foi definido em agosto de 2005, num conjunto de três especificações denominadas WS-Coordination, WS-AtomicTransaction e WS-BusinessActivity. Juntas, essas especificações definem um alicerce sobre o qual aplicações robustas baseadas em Web services podem ser construídas. Nesta dissertação realizamos um estudo sobre transações atômicas em ambientes Web services. Em particular, estendemos o gerenciador de transações presente no servidor de aplicações JBoss, de modo que ele passasse a comportar transações distribuídas envolvendo Web services. Além disso, avaliamos o desempenho desse gerenciador de transações quando ele emprega cada um dos seguintes mecanismos de chamada remota: Web services/SOAP, CORBA/IIOP e JBoss Remoting. Finalmente, realizamos experimentos de escalabilidade e interoperabilidade.

O surgimento e a popularização de arquiteturas de software que fornecem suporte à programação distribuída orientada a objetos, como CORBA, .NET e Java EE, gerou uma demanda por infra-estruturas de segurança eficientes, capazes de proteger os recursos dos sistemas de ataques maliciosos. Essa proteção começa pela identificação dos usuários que interagem com os sistemas, processo conhecido como autenticação. Entretanto, a autenticação por si só não é suficiente para garantir a segurança dos recursos, uma vez que a autenticação não determina quais ações os usuários estão autorizados a executar depois de autenticados. Em outras palavras, um mecanismo de autorização, que faz valer as políticas de controle de acesso aos recursos definidas pelos administradores de sistemas, se faz necessário. Neste trabalho estudamos mecanismos de controle de acesso baseado em papéis e a aplicabilidade dos certificados de atributos X.509 como estrutura de armazenamento desses papéis em um ambiente Java EE. Em particular, estendemos a infra-estrutura de segurança do servidor de aplicações JBoss, de modo que ela passasse a comportar os certificados de atributos X.509. Além disso, analisamos as vantagens e desvantagens do uso de tais certificados e avaliamos o desempenho da extensão desenvolvida em relação a outras alternativas que são oferecidas pelo JBoss para o armazenamento de papéis dos usuários.

Esta tese propõe uma metodologia baseada em métodos de kernel, teoria fuzzy e probabilidade para tratar conjuntos de dados cujas observações são conjuntos de pontos. As medidas de probabilidade e os conjuntos fuzzy são usados para modelar essas observações. Posteriormente, graças a kernels definidos sobre medidas de probabilidade, ou em conjuntos fuzzy, é feito o mapeamento implícito dessas medidas de probabilidade, ou desses conjuntos fuzzy, para espaços de Hilbert com kernel reproduzível, onde a análise pode ser feita com algum método kernel. Usando essa metodologia, é possível fazer frente a uma ampla gamma de problemas de aprendizado para esses conjuntos de dados. Em particular, a tese apresenta o projeto de modelos de descrição de dados para observações modeladas com medidas de probabilidade. Isso é conseguido graças ao mergulho das medidas de probabilidade nos espaços de Hilbert, e a construção de esferas envolventes mínimas nesses espaços de Hilbert. A tese apresenta como esses modelos podem ser usados como classificadores de uma classe, aplicados na tarefa de detecção de anomalias grupais. No caso que as observações sejam modeladas por conjuntos fuzzy, a tese propõe mapear esses conjuntos fuzzy para os espaços de Hilbert com kernel reproduzível. Isso pode ser feito graças à projeção de novos kernels definidos sobre conjuntos fuzzy. A tese apresenta como esses novos kernels podem ser usados em diversos problemas como classificação, regressão e na definição de distâncias entre conjuntos fuzzy. Em particular, a tese apresenta a aplicação desses kernels em problemas de classificação supervisionada em dados intervalares e teste kernel de duas amostras para dados contendo atributos imprecisos.

Esta pesquisa aborda o projeto de efeitos de áudio baseados em decomposições que levam um sinal proveniente de um instrumento musical para a representação AM/FM. A decomposição AM/FM produz um par de sinais também no domínio do tempo, que representam o envelope (porção AM) e a frequência instantânea (porção FM) do sinal analisado. Estes dois sinais atuam em conjunto e podem recriar o sinal original caso utilizados para modular um oscilador senoidal em amplitude e em frequência. Por outro lado, a manipulação individual das porções AM e FM oferece novas possibilidades para processamento de sinais e implementação de efeitos musicais. Neste trabalho discutimos aspectos sobre diferentes técnicas para a decomposição, baseadas na Transformada de Hilbert em conjunto com o Sinal Analítico ou no Operador de Energia de Teager-Kaiser em conjunto com o Algoritmo de Separação de Energia. Apresentamos novos efeitos de áudio baseados em filtragem simples (passa-baixa, passa-banda, passa-alta), processamento dinâmico (distorção, compressor, expander) e manipulações das porções AM e FM inspiradas em efeitos clássicos (tremolo, flanger, octaver, chorus), entre outros efeitos. Implementações para operação em tempo-real são apresentadas e discutidas. Também foi realizada uma avaliação experimental da aplicação dos efeitos propostos, baseada na análise do comportamento de descritores de áudio relacionados com amplitude (variação dinâmica) e frequência (variação espectral) de sinais.

Seleção de características é um tópico muito importante em aplicações de reconhecimento de padrões, especialmente em bioinformática, cujos problemas são geralmente tratados sobre um conjunto de dados envolvendo muitas variáveis e poucas observações. Este trabalho analisa aspectos de seleção de características no problema de identificação de redes de regulação gênica a partir de sinais de expressão gênica. Particularmente, propusemos um modelo de redes gênicas probabilísticas (PGN) que devolve uma rede construída a partir da aplicação recorrente de algoritmos de seleção de características orientados por uma função critério baseada em entropia condicional. Tal critério embute a estimação do erro por penalização de amostras raramente observadas. Resultados desse modelo aplicado a dados sintéticos e a conjuntos de dados de microarray de Plasmodium falciparum, um agente causador da malária, demonstram a validade dessa técnica, tendo sido capaz não apenas de reproduzir conhecimentos já produzidos anteriormente, como também de produzir novos resultados. Outro aspecto investigado nesta tese é o fenômeno da predição intrinsecamente multivariada (IMP), ou seja, o fato de um conjunto de características ser um ótimo caracterizador dos objetos em questão, mas qualquer de seus subconjuntos propriamente contidos não conseguirem representá-los de forma satisfatória. Neste trabalho, as condições para o surgimento desse fenômeno foram obtidas de forma analítica para conjuntos de 2 e 3 características em relação a uma variável alvo. No contexto de redes de regulação gênica, foram obtidas evidências de que genes alvo de conjuntos IMP possuem um enorme potencial para exercerem funções vitais em sistemas biológicos. O fenômeno conhecido como canalização é particularmente importante nesse contexto. Em dados de microarray de melanoma, constatamos que o gene DUSP1, conhecido por exercer função canalizadora, foi aquele que obteve o maior número de conjuntos de genes IMP, sendo que todos eles possuem lógicas de predição canalizadoras. Além disso, simulações computacionais para construção de redes com 3 ou mais genes mostram que o tamanho do território de um gene alvo pode ter um impacto positivo em seu teor de IMP com relação a seus preditores. Esta pode ser uma evidência que confirma a hipótese de que genes alvo de conjuntos IMP possuem a tendência de controlar diversas vias metabólicas cruciais para a manutenção das funções vitais de um organismo.

A crescente capacidade do poder computacional e a proliferação de dispositivos ao nosso redor vem permitindo o desenvolvimento de novas e sofisticadas interfaces para interação humano-computador que reagem à presença e ao estado de seus usuários. Como o olhar tem a capacidade de transmitir muitas informações sobre o usuário, rastreadores de olhar, dispositivos que estimam a direção para onde uma pessoa olha, tem papel importante no desenvolvimento de tais interfaces. Entre suas aplicações temos o auxílio a pessoas com dificuldades motoras, que podem utilizar um rastreador de olhar como substituto ao mouse, aplicações de diagnóstico, que estudam evidências do comportamento humano, ou ainda o desenvolvimento de interfaces que utilizem a informação sobre o olhar como um canal a mais de comunicação com o usuário para perceber suas intenções. Muitas técnicas para atingir tal objetivo foram desenvolvidas mas as tradicionais ainda oferecem certas dificuldades de uso para seus usuários como a intolerância a movimentos de cabeça e a necessidade de calibração por sessão de uso. Neste trabalho fizemos um levantamento de uma série de técnicas de rastreamento de olhar, indo das mais tradicionais até algumas mais recentes que visam melhorar a facilidade de uso destes sistemas. Uma das técnicas mais promissoras utiliza múltiplas fontes de luz fixadas nos cantos do monitor do computador. Através da análise da posição dos reflexos gerados por essas fontes de luz sobre a córnea, juntamente com a informação da posição da pupila, presentes em imagens capturadas do olho, é possível estimar o ponto observado no monitor. Devido às suas vantagens ela foi escolhida para estudo mais detalhado e implementação. Extensos testes utilizando simulações foram realizados para avaliar seu desempenho. Foi também desenvolvida uma extensão dessa técnica, utilizando um modelo mais preciso do olho, visando melhorar sua precisão. Ao final apresentamos nossa implementação, baseada nessa extensão da técnica original, que é tolerante a movimentação da face e mostramos os resultados obtidos em testes realizados com um grupo de usuários.

Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais.

A evolução das tecnologias de sequenciamento de DNA tem permitido a elucidação da sequência genômica de um número cada vez maior de organismos. Contudo, a obtenção da sequência nucleotídica do genoma é apenas a primeira etapa no estudo dos organismos. O processo de anotação consiste na identicação as diferentes regiões de interesse no genoma e suas funcionalidades. Várias ferramentas computacionais foram desenvolvidas para auxiliar o processo de anotação, porém nenhuma delas permite ao usuário selecionar sequências, processá-las de forma a encontrar evidências a respeito das regiões genômicas, como predição gênica e de domínios protéicos, analisá-las gracamente e adicionar informações a respeito de suas regiões em um mesmo ambiente. Assim, o objetivo desse projeto foi o desenvolvimento de uma plataforma gráca para a anotação genômica que permite ao usuário realizar as tarefas necessárias para o processo de anotação em uma única ferramenta integrada a um banco de dados. A idéia é proporcionar ao usuário liberdade para trabalhar com o seu conjunto de dados, possibilitando a seleção de sequências para análise, construção dos pipelines processamento das mesmas e análise dos resultados encontrados a partir de visualizador que permite ao usuário adicionar in- formações às regiões e fazer a curadoria das sequências. A ferramenta resultante é facilmente extensível, permitindo o acoplamento modular de novas funcionalidades de anotação e sua estrutura permite ao usuário trabalhar tanto com projetos de sequências expressas como anotação de genomas.

In terms of standard probabilistic reasoning, in order to perform inference from a knowledge base, it is normally necessary to guarantee the consistency of such base. When we come across an inconsistent set of probabilistic assessments, it interests us to know where the inconsistency is, how severe it is, and how to correct it. Inconsistency measures have recently been put forward as a tool to address these issues in the Artificial Intelligence community. This work investigates the problem of measuring inconsistency in probabilistic knowledge bases. Basic rationality postulates have driven the formulation of inconsistency measures within classical propositional logic. In the probabilistic case, the quantitative character of probabilities yielded an extra desirable property: that inconsistency measures should be continuous. To attend this requirement, inconsistency in probabilistic knowledge bases have been measured via distance minimisation. In this thesis, we prove that the continuity postulate is incompatible with basic desirable properties inherited from classical logic. Since minimal inconsistent sets are the basis for some desiderata, we look for more suitable ways of localising the inconsistency in probabilistic logic, while we analyse the underlying consolidation processes. The AGM theory of belief revision is extended to encompass consolidation via probabilities adjustment. The new forms of characterising the inconsistency we propose are employed to weaken some postulates, restoring the compatibility of the whole set of desirable properties. Investigations in Bayesian statistics and formal epistemology have been interested in measuring an agent\'s degree of incoherence. In these fields, probabilities are usually construed as an agent\'s degrees of belief, determining her gambling behaviour. Incoherent agents hold inconsistent degrees of beliefs, which expose them to disadvantageous bet transactions - also known as Dutch books. Statisticians and philosophers suggest measuring an agent\'s incoherence through the guaranteed loss she is vulnerable to. We prove that these incoherence measures via Dutch book are equivalent to inconsistency measures via distance minimisation from the AI community.

A crise mundial de 2008 impulsionou o avanço das políticas de governança do sistema financeiro global. Parte dessas políticas envolve a reformulação de processos de gerenciamento de informações, e neste cenário de reestruturação tecnológica, várias iniciativas se propõem a solucionar alguns dos problemas já conhecidos. Para viabilizar a adoção de um sistema financeiro global integrado e robusto, grandes empresas de tecnologia e instituições financeiras somam esforços para atender melhor às necessidades do setor. A arquitetura da World Wide Web é uma constante nessas iniciativas, e parte delas buscam os benefícios previstos pelas tecnologias semânticas, tais como sua alta capacidade de integração de dados heterogêneos e utilização de algoritmos de inferência para a dedução de informações. O objetivo deste estudo é utilizar ontologias e tecnologias semânticas, tais como OWL, na gestão de riscos do sistema financeiro, particularmente para verificar a sua aplicabilidade nas políticas de gestão de riscos específicas do sistema financeiro brasileiro, estabelecidas pelas normas publicadas pelo Banco Central (BACEN).

Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\".

Este texto apresenta nosso projeto de implementação de um arcabouço de suporte a agentes móveis dentro de um ambiente de grade denominado InteGrade. Nosso arcabouço - MobiGrid - foi criado de forma a permitir que aplicações seqüenciais longas possam ser executadas em uma rede de estações de trabalho pessoais. Os agentes móveis são utilizados para encapsular essas aplicações com longo tempo de processamento. O encapsulamento de uma aplicação com longo tempo de processamento dentro de um agente móvel é o que denominamos como tarefa. Sendo assim, as tarefas podem migrar sempre que a máquina é requisitada por seu usuário local, já que são providas com capacidade de migração automática. Nosso arcabouço também fornece ao usuário um gerente que rastreia as tarefas por ele submetidas. Baseados no ambiente de execução de tarefas descrito, criamos um modelo matemático para efetuarmos simulações de como se comportariam muitas tarefas submetidas a uma grade com grande quantidade de estações de trabalho. Neste trabalho apresentamos também esse modelo, bem como os resultados das simulações nele baseadas.

Nesta tese apresentamos o projeto e a implementação do KEMS, um provador de teoremas multi-estratégia baseado no método de tablôs KE. Um provador de teoremas multi-estratégia é um provador de teoremas onde podemos variar as estratégias utilizadas sem modificar o núcleo da implementação. Além de multi-estratégia, o KEMS é capaz de provar teoremas em três sistemas lógicos: lógica clássica proposicional, mbC e mCi. Listamos abaixo algumas das contribuições deste trabalho: * um sistema KE para mbC que é analítico, correto e completo; * um sistema KE para mCi que é correto e completo; * um provador de teoremas multi-estratégia com as seguintes características: - aceita problemas em três sistemas lógicos: lógica clássica proposicional, mbC e mCi; - tem seis estratégias implementadas para lógica clássica proposicional, duas para mbC e duas para mCi; - tem treze ordenadores que são usados em conjunto com as estratégias; - implementa regras simplificadoras para lógica clássica proposicional; - possui uma interface gráfica que permite a visualização de provas; - é de código aberto e está disponível na Internet em http://kems.iv.fapesp.br; * benchmarks obtidos através da comparação das estratégias para lógica clássica proposicional resolvendo várias famílias de problemas; - sete famílias de problemas para avaliar provadores de teoremas paraconsistentes; * os primeiros benchmarks para as famílias de problemas para avaliar provadores de teoremas paraconsistentes.

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2).

Recentes avanços proporcionaram às grades computacionais um bom nível de maturidade. Esses sistemas têm sido implantados em ambientes de produção de qualidade na comunidade de pesquisa acadêmica e vêm despertando um grande interesse da indústria. Entretanto, desenvolver aplicações para essas infra-estruturas heterogêneas e distribuídas ainda é uma tarefa complexa e propensa a erros. As iniciativas de facilitar essa tarefa resultaram, na maioria dos casos, em ferramentas não integradas e baseadas em características específicas de cada grade computacional. O presente trabalho tem como objetivo minimizar a dificuldade de desenvolvimento de aplicações para a grade através da construção de um ambiente integrado e extensível de desenvolvimento (IDE) para computação em grade chamado InGriDE. O InGriDE fornece um conjunto único de ferramentas compatíveis com diferentes sistemas de middleware, desenvolvidas baseadas na interface de programação Grid Application Toolkit (GAT). O conjunto de funcionalidades do InGriDE foi desenvolvido com base na plataforma Eclipse que, além de fornecer um arcabouço para construção de IDEs, facilita a extensão do conjunto inicial de funcionalidades. Para validar a nossa solução, utilizamos em nosso estudo de caso o middleware InteGrade, desenvolvido no nosso grupo de pesquisa. Os resultados obtidos nesse trabalho mostraram a viabilidade de fornecer independência de middleware para IDEs através do uso de uma interface genérica de programação como o GAT. Além disso, os benefícios obtidos com o uso do Eclipse como arcabouço para construção de IDEs indicam que os recursos fornecidos por esse tipo de arcabouço atendem de forma eficiente as necessidades inerentes ao processo de desenvolvimento de aplicações para a grade.

No sistema brasileiro de saúde, cabe aos Centros de Saúde o papel de órgão provedor de assistência médica primária. Para que esse papel seja cumprido com responsabilidade e eficácia, se mostrou fundamental a condução de programas públicos de atenção primária que envolvam visitas domiciliares aos pacientes. O objetivo desses programas, tais como o Estratégia de Saúde da Família (ESF), também conhecido como Programa de Saúde da Família (PSF), é o de melhorar a qualidade do serviço de saúde prestado à população por meio da aproximação entre equipes de saúde e a comunidade, permitindo, dessa forma, uma migração do paradigma de tratamento de doenças para o de promoção da saúde. No entanto, apesar da importância desses programas para a organização e articulação do sistema de atenção primária, as atividades de atenção domiciliar são normalmente conduzidas com pouco ou nenhum suporte de Tecnologia da Informação (TI). Esta pesquisa de mestrado tem por objetivo mostrar a definição e o desenvolvimento de um sistema móvel que auxilie os profissionais de saúde na coleta de informações dos pacientes que usufruem dos serviços de saúde citados acima. O projeto recebeu o nome de Projeto Borboleta e durante o tempo desta pesquisa várias versões do software foram desenvolvidas. Essas versões geraram protótipos do sistema que foram submetidos a testes em campo e, a partir da avaliação realizada pelos profissionais de saúde, surgiram alterações diversas.

Este trabalho apresenta uma plataforma para coleta e análise de imagens urbanas, que integra Interfaces de Programação de Aplicativos \"Application Programming Interfaces\" (APIs) de sistemas de busca de imagens, Sistemas de Informações Geográficas (SIGs), mapas digitais e técnicas de visão computacional. Esta plataforma, INACITY, permite que usuários selecionem regiões de interesse e capturem elementos de relevância para a arquitetura urbana, como, por exemplo árvores e buracos em ruas. A implementação da plataforma foi feita de maneira a permitir que novos módulos possam ser facilmente incluídos ou substituídos possibilitando a introdução de outras APIs de mapas, SIGs e filtros de Visão Computacional. Foram realizados experimentos com as imagens obtidas através do \"Google Street View\" onde árvores são capturadas em áreas de bairros inteiros em questão de minutos, um ganho significativo quando comparado com o procedimento manual para levantamento deste tipo de dado. Além disso, também são apresentados resultados comparativos entre os métodos de visão computacional propostos para a detecção de árvores em imagens com outros métodos heurísticos, em um conjunto onde as árvores estão marcadas manualmente e assim as taxas de precisão e de redescoberta de cada algoritmo podem ser avaliadas e comparadas.

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação

Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos.

Schistosoma mansoni é o parasita causador da esquistossomose mansônica que, de acordo com o Ministério da Saúde do Brasil, afeta atualmente vários milhões de pessoas no país. Uma das formas de diagnóstico da esquistossomose é a detecção de ovos do parasita através da análise de lâminas microscópicas com material fecal. Esta tarefa é extremamente cansativa, principalmente nos casos de baixa endemicidade, pois a quantidade de ovos é muito pequena. Nesses casos, uma abordagem computacional para auxílio na detecção de ovos facilitaria o trabalho de diagnóstico. Os ovos têm formato ovalado, possuem uma membrana translúcida, apresentam uma espícula e sua cor é ligeiramente amarelada. Porém nem todas essas características são observadas em todos os ovos e algumas delas são visíveis apenas com uma ampliação adequada. Além disso, o aspecto visual do material fecal varia muito de indivíduo para indivíduo em termos de cor e presença de diversos artefatos (tais como partículas que não são desintegradas pelo sistema digestivo), tornando difícil a tarefa de detecção dos ovos. Neste trabalho investigamos, em particular, o problema de detecção das linhas que contornam a borda de vários dos ovos. Propomos um método composto por duas fases. A primeira fase consiste na detecção de estruturas do tipo linha usando operadores morfológicos. A detecção de linhas é dividida em três etapas principais: (i) realce de linhas, (ii) detecção de linhas, e (iii) refinamento do resultado para eliminar segmentos de linhas que não são de interesse. O resultado dessa fase é um conjunto de segmentos de linhas. A segunda fase consiste na detecção de subconjuntos de segmentos de linha dispostos em formato elíptico, usando um algoritmo baseado na transformada Hough. As elipses detectadas são fortes candidatas a contorno de ovos de S. mansoni. Resultados experimentais mostram que a abordagem proposta pode ser útil para compor um sistema de auxílio à detecção dos ovos.