Repositório RCAAP

Provedores de serviços de nuvem disponibilizam uma interface através da qual seus clientes podem solicitar, usar e liberar estes recursos. Muitos serviços implantados em nuvens incluem um componente para gerenciamento automatizado de recursos, encarregado de requisitar e librar recursos sem intervenção humana, à medida que a demanda varia. A técnica padrão para o gerenciamento de recursos se baseia em regras sobre utilização de recursos. Quando ocorre um aumento significativo na carga em um curto espaço de tempo, o sistema pode levar vários ciclos de monitoramento e ação até alcançar uma configuração adequada. Neste período, o sistema permanece sobrecarregado. Nesta pesquisa, investigamos como compreender adequadamente os efeitos da variação na disponibilidade de recursos sobre a capacidade de um sistema e como aplicar este conhecimento para melhorar sua elasticidade. Propomos uma estratégia que abrange avaliação da escalabilidade do sistema, visando sua modelagem, e a aplicação deste modelo nas estimativas de necessidade por recursos com base na carga de trabalho. Introduzimos um arcabouço para automatizar a avaliação de escalabilidade de sistemas distribuídos e efetuamos uma validação experimental da estratégia proposta. Comparamos a alocação de recursos e o desempenho obtido usando nossa estratégia e estratégia baseada em regras, fazendo a reprodução de carga real e usando cargas sintéticas. De forma geral, nossa proposta foi capaz de prover melhor desempenho, ao ponto que o uso de recursos cresceu, e consequentemente o custo de utilização. No entanto, a melhora de desempenho foi mais significativa que o aumento dos custos.

Métodos do tipo Lagrangiano Aumentado são muito utilizados para minimização de funções sujeitas a restrições gerais. Nestes métodos, podemos separar o conjunto de restrições em dois grupos: restrições fáceis e restrições difíceis. Dizemos que uma restrição é fácil se existe um algoritmo disponível e eficiente para resolver problemas restritos a este tipo de restrição. Caso contrário, dizemos que a restrição é difícil. Métodos do tipo Lagrangiano aumentado resolvem, a cada iteração, problemas sujeitos às restrições fáceis, penalizando as restrições difíceis. Problemas de minimização com restrições lineares aparecem com freqüência, muitas vezes como resultados da aproximação de problemas com restrições gerais. Este tipo de problema surge também como subproblema de métodos do tipo Lagrangiano aumentado. Assim, uma implementação eficiente para resolver problemas com restrições lineares é relevante para a implementação eficiente de métodos para resolução de problemas de programação não-linear. Neste trabalho, começamos considerando fáceis as restrições de caixa. Introduzimos BETRA-ESPARSO, uma versão de BETRA para problemas de grande porte. BETRA é um método de restrições ativas que utiliza regiões de confiança para minimização em cada face e gradiente espectral projetado para sair das faces. Utilizamos BETRA (denso ou esparso) na resolução dos subproblemas que surgem a cada iteração de ALGENCAN (um método de lagrangiano aumentado). Para decidir qual algoritmo utilizar para resolver cada subproblema, desenvolvemos regras que escolhem um método para resolver o subproblema de acordo com suas características. Em seguida, introduzimos dois algoritmos de restrições ativas desenvolvidos para resolver problemas com restrições lineares (BETRALIN e GENLIN). Estes algoritmos utilizam, a cada iteração, o método do Gradiente Espectral Projetado Parcial quando decidem mudar o conjunto de restrições ativas. O método do gradiente Espectral Projetado Parcial foi desenvolvido especialmente para este propósito. Neste método, as projeções são computadas apenas em um subconjunto das restrições, com o intuito de torná-las mais eficientes. Por fim, tendo introduzido um método para minimização com restrições lineares, consideramos como fáceis as restrições lineares. Incorporamos BETRALIN e GENLIN ao arcabouço de Lagrangianos aumentados e verificamos experimentalmente a eficiência e eficácia destes métodos que trabalham explicitamente com restrições lineares e penalizam as demais.

Human skin is made of a stack of different layers, each of which reflects a portion of impinging light, after absorbing a certain amount of it by the pigments which lie in the layer. The main pigments responsible for skin color origins are melanin and hemoglobin. Skin segmentation plays an important role in a wide range of image processing and computer vision applications. In short, there are three major approaches for skin segmentation: rule-based, machine learning and hybrid. They differ in terms of accuracy and computational efficiency. Generally, machine learning and hybrid approaches outperform the rule-based methods but require a large and representative training dataset and, sometimes, costly classification time as well, which can be a deal breaker for real-time applications. In this work, we propose an improvement, in three distinct versions, of a novel method for rule-based skin segmentation that works in the YCbCr color space. Our motivation is based on the hypotheses that: (1) the original rule can be complemented and, (2) human skin pixels do not appear isolated, i.e. neighborhood operations are taken into consideration. The method is a combination of some correlation rules based on these hypotheses. Such rules evaluate the combinations of chrominance Cb, Cr values to identify the skin pixels depending on the shape and size of dynamically generated skin color clusters. The method is very efficient in terms of computational effort as well as robust in very complex images.

Segmentação de objetos em imagens é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. O conhecimento de alto nível e específico do usuário é frequentemente requerido no processo de segmentação, devido à presença de fundos heterogêneos, objetos com bordas fracamente definidas, inomogeneidade de campo, ruído, artefatos, efeitos de volume parcial e seus efeitos conjuntos. Propriedades globais do objeto de interesse, tais como conexidade, restrições de forma e polaridade de borda, são conhecimentos prévios de alto nível úteis para a sua segmentação, permitindo a customização da segmentação para um objeto alvo. Nesse trabalho, apresentamos um novo método chamado Transformada Imagem-Floresta Orientada Conexa (COIFT, Connected Oriented Image Foresting Transform), que fornece soluções ótimas globais de acordo com uma medida de corte em grafo, incorporando a restrição de conexidade na Transformada Imagem-Floresta Orientada (OIFT, Oriented Image Foresting Transform), com o fim de garantir a geração de objetos conexos, bem como permitir o controle simultâneo da polaridade de borda. Enquanto o emprego de restrições de conexidade em outros arcabouços, tais como no algoritmo de corte-mínimo/fluxo-máximo (min-cut/max-flow), leva a um problema NP-difícil, a COIFT conserva o baixo custo computacional da OIFT. Experimentos mostram que a COIFT pode melhorar consideravelmente a segmentação de objetos com partes finas e alongadas, para o mesmo número de sementes em segmentação baseada em marcadores.

A presente pesquisa explora areas de Processamento de Linguagem Natural (PLN), tais como, analisadores, gramaticas e ontologias no desenvolvimento de um modelo para o mapeamento de consulta em lingua portuguesa controlada para consultas SPARQL. O SPARQL e uma linguagem de consulta capaz de recuperar e manipular dados armazenados em RDF, que e a base para a construcao de Ontologias. Este projeto pretende investigar utilizacao das tecnicas supracitadas na mitigacao do problema de consulta a Ontologias utilizando linguagem natural controlada. A principal motivacao para o desenvolvimento deste trabalho e pesquisar tecnicas e modelos que possam proporcionar uma melhor interacao do homem com o computador. Facilidade na interacao homem-computador e convergida em produtividade, eficiencia, comodidade dentre outros beneficios implicitos. Nos nos concentramos em medir a eficiencia do modelo proposto e procurar uma boa combinacao entre todas as tecnicas em questao.

Em ambientes virtualizados, como nuvens computacionais, a capacidade efetiva de transmissão de dados via rede tende a ser inferior à de ambientes não virtualizados quando aplicações que fazem uso intensivo da rede são executadas. Uma das principais causas para essa diferença na capacidade de transmissão é a arquitetura da virtualização de rede, que adiciona passos para o sistema operacional transmitir e receber um pacote. Esses passos adicionais acarretam em maior utilização de memória e de processamento. Em ambientes virtualizados com o sistema operacional GNU/Linux, a New Application Programming Interface (NAPI) é utilizada para reduzir os impactos negativos da virtualização por meio de agregação de interrupções. Nesta dissertação de mestrado, são estudados mecanismos que modificam a configuração da NAPI. Experimentos mostram que esses mecanismos afetam o desempenho de máquinas virtuais e tem consequências diretas nas aplicações que fazem uso intensivo de rede e que são executadas em ambientes com os softwares de virtualização Xen, VMware e VirtualBox.

A necessidade de poder computacional é crescente nas mais diversas áreas de atuação humana, tanto na indústria como no ambiente acadêmico. A Computação em Grade permite a interligação de recursos computacionais dispersos de maneira a permitir sua utilização mais efetiva, provendo aos usuários acesso simplificado ao poder computacional de diversas máquinas. Entretanto, os primeiros projetos de Computação em Grade objetivavam a interligação de máquinas paralelas ou aglomerados de alto desempenho e alto custo, acessível apenas a poucas instituições. Em contraponto ao alto custo das máquinas paralelas, os computadores pessoais se difundiram de maneira extraordinária nos últimos quinze anos. A expansão da base instalada foi acompanhada de uma crescente evolução na capacidade de tais máquinas. Os aglomerados dedicados de computadores pessoais representam a primeira tentativa de utilização de tais recursos para computação paralela e, apesar de serem amplamente utilizados, ainda requerem um investimento significativo. Entretanto, as mesmas instituições que adquirem tais aglomerados dedicados normalmente possuem centenas ou até milhares de computadores pessoais, os quais têm sua capacidade utilizada apenas parcialmente, resultando em grande ociosidade dos recursos. Os sistemas de Computação em Grade Oportunistas fornecem a possibilidade de se utilizar a base instalada de computadores pessoais de maneira a realizar computação utilizando a parte dos recursos que, de outra forma, estariam ociosos. Diversos sistemas dessa categoria foram desenvolvidos e utilizados com êxito para realizar tarefas de computação em diversas áreas como astronomia, biologia e matemática. O InteGrade, sistema de Computação em Grade Oportunista aqui apresentado, pretende oferecer características inovadoras para sistemas oportunistas, como suporte a aplicações paralelas que demandam comunicação entre nós e a utilização de coleta e análise de padrões de uso das máquinas da Grade, de maneira a permitir que se realize previsões sobre a disponibilidade das máquinas, permitindo uma utilização mais eficiente das mesmas. Além disso, o InteGrade emprega amplamente o paradigma de Orientação a Objetos, tanto na definição da arquitetura do sistema quanto na sua implementação. O trabalho aqui apresentado consistiu no estudo de outros projetos de Computação em Grade, na definição de uma arquitetura inicial para o InteGrade, passando pela descrição de seus principais módulos assim como sua implementação. Além disso, também descrevemos o projeto e a implementação de uma biblioteca para programação paralela no InteGrade utilizando o modelo BSP.

A qualidade dos sistemas de software é uma preocupação de todo bom projeto e muito tem se estudado para melhorar tanto a qualidade do produto final quanto do processo de desenvolvimento. Teste de Software é uma área de estudo que tem crescido significativamente nos últimos tempos, em especial a automação de testes que está cada vez mais em evidência devido à agilidade e qualidade que pode trazer para o desenvolvimento de sistemas de software. Os testes automatizados podem ser eficazes e de baixo custo de implementação e manutenção e funcionam como um bom mecanismo para controlar a qualidade de sistemas. No entanto, pouco conhecimento sobre a área e erros comuns na escrita e manutenção dos testes podem trazer dificuldades adicionais aos projetos de software. Testes automatizados de baixa qualidade não contribuem efetivamente com o controle de qualidade dos sistemas e ainda demandam muito tempo do desenvolvimento. Para evitar esses problemas, esta dissertação apresenta de forma crítica e sistemática as principais práticas, padrões e técnicas para guiar o processo da criação, manutenção e gerenciamento dos casos de testes automatizados. Inicialmente, são feitas comparações entre a automação de testes e outras práticas de controle e garantia de qualidade. Em seguida, são apresentados os problemas e soluções mais comuns durante a automação de testes, tais como questões relacionadas a tipos específicos de algoritmos, sistemas com persistência de dados, testes de interfaces de usuário e técnicas de desenvolvimento de software com testes automatizados. Para finalizar, a dissertação traz uma reflexão sobre o gerenciamento e a abordagem da automação de testes para tornar o processo mais produtivo e eficaz.

O desafio de encontrar corretamente genes eucarioticos codificadores de proteinas nas sequencias genomicas e um problema em aberto. Neste trabalho, implementamos uma plata- forma, com o objetivo de melhorar a forma com que preditores de genes sao implementados e avaliados. Tres novas ferramentas foram implementadas: ToPS (Toolkit of Probabilistic Models of Sequences) foi o primeiro arcabouco orientado a objetos que fornece ferramentas para implementacao, manipulacao, e combinacao de modelos probabilisticos para representar sequencias de simbolos; MYOP (Make Your Own Predictor) e um sistema que tem como objetivo facilitar a construcao de preditores de genes; e SGEval utiliza grafos de splicing para comparar diferente anotacoes com eventos de splicing alternativos. Utilizamos nossas ferramentas para o desenvolvimentos de preditores de genes em onze genomas distintos: A. thaliana, C. elegans, Z. mays, P. falciparum, D. melanogaster, D. rerio, M. musculus, R. norvegicus, O. sativa, G. max e H. sapiens. Com esse desenvolvimento, estabelecemos um protocolo para implementacao de novos preditores. Alem disso, utilizando a nossa plata- forma, desenvolvemos um fluxo de trabalho para predicao de genes no projeto do genoma da cana de acucar, que ja foi utilizado em 109 sequencias de BAC geradas pelo BIOEN (FAPESP Bioenergy Program).

O recente crescimento da utilização de Unidades de Processamento Gráfico (GPUs) em aplicações científicas, que são voltadas ao desempenho, gerou a necessidade de otimizar os programas que nelas rodam. Uma ferramenta adequada para essa tarefa é o modelo de desempenho que, por sua vez, se beneficia da existência de uma ferramenta de extração de informações de desempenho para GPUs. Este trabalho cobre a criação de um gerador de microbenchmark para instruções PTX que também obtém informações sobre as características do hardware da GPU. Os resultados obtidos com o microbenchmark foram validados através de um modelo simplificado que obteve erros entre 6,11% e 16,32% em cinco kernels de teste. Também foram levantados os fatores de imprecisão nos resultados do microbenchmark. Utilizamos a ferramenta para analisar o perfil de desempenho das instruções e identificar grupos de comportamentos semelhantes. Também testamos a dependência do desempenho do pipeline da GPU em função da sequência de instruções executada e verificamos a otimização do compilador para esse caso. Ao fim deste trabalho concluímos que a utilização de microbenchmarks com instruções PTX é factível e se mostrou eficaz para a construção de modelos e análise detalhada do comportamento das instruções.

The state of the art in machine learning of Boolean functions is to learn a hypothesis h, which is similar to a target hypothesis f, using a training sample of size N and a family of a priori models in a given hypothesis set H, such that h must belong to some model in this family. An important characteristic in learning is that h should also predict outcome values of f for previously unseen data, so the learning algorithm should minimize the generalization error which is the discrepancy measure between outcome values of f and h. The method proposed in this thesis learns family of models compatible with training samples of size N. Taking into account that generalizations are performed through equivalence classes in the Boolean function domain, the search space for finding the correct model is the projection of H in all possible partitions of the domain. This projection can be seen as a model lattice which is anti-isomorphic to the partition lattice and also has the property that for every chain in the lattice there exists a relation order given by the VC dimension of the models. Hence, we propose a model selector that uses the model lattice for selecting the best model with VC dimension compatible to a training sample of size N, which is closely related to the classical sample complexity theorem. Moreover, this model selector generalizes a set of learning methods in the literature (i.e, it unifies methods such as: the feature selection problem, multiresolution representation and decision tree representation) using models generated from a subset of partitions of the partition space. Furthermore, considering as measure associated to the models the estimated error of the learned hypothesis, the chains in the lattice present the so-called U-curve phenomenon. Therefore, we can use U-curve search algorithms in the model lattice to select the best models and, consequently, the corresponding VC dimension. However, this new generation of learning algorithms requires an increment of computational power. In order to face this problem, we introduce a stochastic U-curve algorithm to work on bigger lattices. Stochastic search algorithms do not guarantee finding optimal solutions, but maximize the mean quality of the solution for a given amount of computational power. The contribution of this thesis advances both the state of the art in machine learning theory and in practical problem solutions in learning.

O CoGrOO é um corretor gramatical de código aberto em uso por milhares de usuários de uma popular suíte de escritório de código aberto. Ele é capaz de identificar erros como: colocação pronominal, concordância nominal, concordância sujeito-verbo, uso da crase, concordância nominal e verbal e outros erros comuns de escrita em Português do Brasil. Para tal, o CoGrOO realiza uma análise híbrida: inicialmente o texto é anotado usando técnicas estatísticas de Processamento de Linguagens Naturais e, em seguida, um sistema baseado em regras é responsável por identificar os possíveis erros gramaticais. O objetivo deste trabalho é reduzir a quantidade de omissões e intervenções indevidas e, ao mesmo tempo, aumentar a quantidade de verdadeiros positivos sem, entretanto, adicionar novas regras de detecção de erros. A última avaliação científica do corretor gramatical foi realizada em 2006 e, desde então, não foram realizados estudos detalhados quanto ao seu desempenho, apesar de o código do sistema ter passado por substancial evolução. Este trabalho contribuirá com uma detalhada avaliação dos anotadores estatísticos e os resultados serão comparados com o estado da arte. Uma vez que os anotadores do CoGrOO estão disponíveis como software livre, melhorias nesses módulos gerarão boas alternativas a sistemas proprietários.

A indústria de software é muito dinâmica e novas ideias surgem a todo instante em todas as partes do mundo. Nem sempre é fácil fazer com que essas ideias sejam adotadas, pois, para isso, é preciso fazer as pessoas mudarem sua forma de pensar. Deve-se sempre considerar o fato de que o ser humano, diferente do computador, é inusitado e imprevisível. Apesar disso, podemos encontrar determinados padrões de comportamento, que não resolvem todas as questões, mas ajudam a lidar com situações e continuar caminhando para atingir um determinado objetivo. Trazemos nesta dissertação uma pequena introdução sobre o conceito de padrões e, em seguida, apresentamos 48 Padrões para Introduzir Novas Ideias, propostos por Linda Rising e Mary Lynn Manns. Esses Padrões têm o objetivo de ajudar na difícil tarefa de introduzir uma nova ideia dentro de alguma organização, pois se essa ideia pressupõe mudanças culturais, o trabalho é ainda mais complicado. Propomos também quatro novos padrões, que podem ser incorporados ao catálogo original. Num desses novos padrões, mostramos a importância de se usar atividades artísticas no dia-a-dia de pessoas que trabalham com desenvolvimento de software; mostramos também como a Arte pode nos ajudar a introduzir novas ideias. Pesquisamos algumas práticas como teatro, pintura, poesia, música e meditação. Pudemos encontrar elementos de ligação entre o lado puramente matemático e bem definido do ser humano e o seu lado abstrato, analógico e artístico. Desenvolver software deve ser encarado como uma atividade humana, acima da questão técnica e puramente lógica. Existem pessoas envolvidas no processo: as que usam e as que criam o software. Existe uma barreira que separa os programadores das pessoas que usam o software. Essa barreira pode ser quebrada se pessoas da Computação começarem a desenvolver, além das habilidades lógicas que já lhes são óbvias, habilidades artísticas e de relações humanas.

Este trabalho estuda o problema da Satisfazibilidade Probabilística (PSAT), revendo a sua solução via programação linear, além de propor novos algoritmos para resolvê-lo através da redução ao SAT. Construímos uma redução polinomial do PSAT para o SAT, chamada de Redução Canônica, codificando operações da aritmética racional em bits, como variáveis lógicas. Analisamos a complexidade computacional dessa redução e propomos uma Redução Canônica de Precisão Limitada para contornar tal complexidade. Apresentamos uma Redução de Turing do PSAT ao SAT, baseada no algoritmo Simplex e na Forma Normal Atômica que introduzimos. Sugerimos modificações em tal redução em busca de eficiência computacional. Por fim, implementamos essas reduções a m de investigar o perl de complexidade do PSAT, observamos o fenômeno de transição de fase e discutimos as condições para sua detecção.

O presente texto descreve a tese de doutorado intitulada Análise de Formas usando Wavelets em Grafos. O tema está relacionado à área de Visão Computacional, particularmente aos tópicos de Caracterização, Descrição e Classificação de Formas. Dentre os métodos da extensa literatura em Análise de Formas 2D, percebe-se uma presença menor daqueles baseados em grafos com topologia arbitrária e irregular. As contribuições desta tese procuram preencher esta lacuna. É proposta uma metodologia baseada no seguinte pipeline : (i) Amostragem da forma, (ii) Estruturação das amostras em grafos, (iii) Função-base definida nos vértices, (iv) Análise multiescala de grafos por meio da Transformada Wavelet Espectral em grafos, (v) Extração de Características da Transformada Wavelet e (vi) Discriminação. Para cada uma das etapas (i), (ii), (iii), (v) e (vi), são inúmeras as abordagens possíveis. Um dos desafios é encontrar uma combinação de abordagens, dentre as muitas alternativas, que resulte em um pipeline eficaz para nossos propósitos. Em particular, para a etapa (iii), dado um grafo que representa uma forma, o desafio é identificar uma característica associada às amostras que possa ser definida sobre os vértices do grafo. Esta característica deve capturar a influência subjacente da estrutura combinatória de toda a rede sobre cada vértice, em diversas escalas. A Transformada Wavelet Espectral sobre os Grafos revelará esta influência subjacente em cada vértice. São apresentados resultados obtidos de experimentos usando formas 2D de benchmarks conhecidos na literatura, bem como de experimentos de aplicações em astronomia para análise de formas de galáxias do Sloan Digital Sky Survey não-rotuladas e rotuladas pelo projeto Galaxy Zoo 2 , demonstrando o sucesso da técnica proposta, comparada a abordagens clássicas como Transformada de Fourier e Transformada Wavelet Contínua 2D.

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais.

O presente texto descreve métodos e apresenta resultados do projeto de pesquisa de mestrado intitulado \"Dois Problemas em Análise de Formas de Estruturas de Ramificação\". Ambos os problemas abordados estão relacionados às sub-áreas da Análise de Formas denominadas Caracterização e Descrição de Formas. O primeiro problema consiste na investigação de um conjunto de características propostas para distingüir, primeiramente, entre estruturas de ramificação de vasos sangüíneos em imagens de retina segmentadas manualmente e automaticamente. A seguir, as mesmas características são aplicadas para discernir entre estruturas de ramificação de vasos sangüíneos em imagens de retina com e sem retinopatia diabética proliferativa (Proliferative Diabetic Retinopathy - PDR). A PDR é uma das patologias associadas à diabetes, que pode culminar na cegueira do indivíduo. Diagnósticos são possíveis por meio de imagens de fundo de olho e, quando efetuados precocemente, viabilizam intervenções oportunas evitando a perda da visão. Neste trabalho, 27 imagens digitais de fundo de olho foram segmentadas por dois processos distintos, isto é, segmentação manual por um especialista e a segmentação automática, mediante a transformada contínua Wavelet - CWT e classificadores estatísticos. Visando à caracterização destas formas, um conjunto de 08 características foi proposto. Este conjunto foi formado por três grupos, a saber: descritores tradicionais geométricos (Área, Perímetro e Circularidade), descritores associados à transformada wavelet ( 2o momento estatístico da distribuição de módulos da CWT, Entropia de Orientação da distribuição de fases da CWT e Curvatura) e um descritor fractal (Dimensão de Correlação - Global e Mediana). Uma Análise Discriminante Linear LDA revelou que as características geométricas tradicionais não detectam o início da retinopatia diabética proliferativa. A maior capacidade discriminante individual foi exibida pela Curvatura, com Área sob a curva ROC de 0.76. Um subconjunto com 6 características apresentou grande capacidade discriminante com Área sob a curva ROC de 0.90. O segundo problema diz respeito à extração de contorno de estruturas de ramificação bidimensionais de neurônios tridimensionais. Este trabalho contribui originalmente com uma solução para este problema, propondo dois algoritmos desenvolvidos para Rastreamento de Ramos e Extração do Contorno Paramétrico de estruturas de ramificação, capazes de transpor regiões críticas formadas por cruzamentos ocasionados pela projeção de estruturas 3D no plano das imagens 2D. Grande parte dos métodos baseados em contorno para análise de formas de estruturas de ramificação de células neuronais não produz representações corretas destas formas, devido à presença de sobreposições entre processos neuronais, levando os algoritmos tradicionais de extração de contorno a ignorar as regiões mais internas destas estruturas, gerando representações incompletas. O sistema proposto neste trabalho foi desenvolvido objetivando a solução do problema de extração de contorno, mesmo na presença de múltiplas sobreposições. Inicialmente, a imagem de entrada é pré-processada, gerando um esqueleto 8-conexo com ramos de um pixel de largura, um conjunto de sementes de sub-árvores dendríticas e um conjunto de regiões críticas (bifurcações e cruzamentos). Para cada sub-árvore, o algoritmo de rastreamento rotula todos os pixels válidos de um ramo, até chegar em uma região crítica, onde o algoritmo decide a direção em que deve continuar o rastreamento. Nosso algoritmo mostrou-se robusto, mesmo quando aplicado a imagens com segmentos paralelos muito próximos. Resultados obtidos com imagens reais (neurônios) são apresentados.

Nesta tese, dois diferentes problemas de programação da produção são abordados, o Flexible JobShop Scheduling Problem com Flexibilidade de sequenciamento e o Flowshop Scheduling Problem com tempos de espera e permutação de sequência. Para ambos, inicialmente um algoritmo list scheduling (LS) que explora características do problema é desenvolvido e então estendido para um método do tipo Beam Search (BS) que utiliza o LS em seus principais elementos: (1) expansão dos níveis, (2) avaliação local dos candidatos e (3) avaliação global dos candidatos. Todos os métodos propostos são determinísticos e seus pseudocódigos são cuidadosamente descritos para garantir a replicabilidade dos resultados reportados. O desempenho dos métodos propostos são avaliados utilizando instâncias e outros métodos heurísticos da literatura. Os resultados computacionais obtidos mostram a eficiência das heurísticas propostas que superaram os métodos da literatura utilizando pouco tempo computacional.

Um Processo de Decisão Markoviano (MDP) pode ser usado para modelar problemas de decisão sequencial. No entanto, podem existir limitações na obtenção de probabilidades para modelagem da transição de estados ou falta de confiabilidade nas informações existentes sobre estas probabilidades. Um modelo menos restritivo e que pode resolver este problema é o Processo de Decisão Markoviano com Probabilidades Intervalares (BMDP), que permite a representação imprecisa das probabilidades de transição de estados e raciocínio sobre uma solução robusta. Para resolver BMDPs de horizonte infinito, existem os algoritmos síncronos de Iteração de Valor Intervalar e Iteração de Política Robusto, que são ineficientes quando o tamanho do espaço de estados é grande. Neste trabalho são propostos algoritmos assíncronos de Iteração de Política baseados no particionamento do espaço de estados em subconjuntos aleatórios (Robust Asynchronous Policy Iteration - RAPI) ou em componentes fortemente conexos (Robust Topological Policy Iteration - RTPI). Também são propostas formas de inicializar a função valor e a política dos algoritmos, de forma a melhorar a convergência destes. O desempenho dos algoritmos propostos é avaliado em comparação com o algoritmo de Iteração de Política Robusto para BMDPs para domínios de planejamento existentes e um novo domínio proposto. Os resultados dos experimentos realizados mostram que (i) quanto mais estruturado é o domínio, melhor é o desempenho do algoritmo RTPI; (ii) o uso de computação paralela no algoritmo RAPI possui um pequeno ganho computacional em relação à sua versão sequencial; e (iii) uma boa inicialização da função valor e política pode impactar positivamente o tempo de convergência dos algoritmos.

Knowledge representation in ontologies is based on Description Logics, which are decidable fragments of first-order logic. Since knowledge is not static, it is necessary to deal with the acquisition of new information, which may contradict the existing knowledge. Belief Revision aims to solve this problem, but the classical AGM framework assumes an ideal agent that is able to deal with logically closed sets of sentences, and some of its generalisations for belief bases (such as ontologies represented in Description Logics) may lead to loss of information due to the fact that no sentence can be added when a contraction operation is performed. In this work, we analyse kernel constructions for pseudo-contraction operations and their formal properties. Also, we show the close relationship between concepts and definitions of Belief Revision and Ontology Repair (such as pseudo-contractions and gentle repairs, respectively), and we propose a unified notation for their operations.