RCAAP Repository

O grande sucesso da publicidade na Internet, observado atualmente, está diretamente relacionado ao investimento crescente em publicidade de busca que, por sua vez, tem sido essencial para o financiamento de conteúdos e serviços na Internet. De acordo com aForrester Research, os ganhos em publicidade de busca devem subir de 3,6 bilhões de dólares em 2004 para 11,6 bilhões em 2010. De fato, estes números podem ser maiores ainda. Para se ter uma idéia, o Yahoo anunciou um ganho de 875 milhões de dólares referente apenas ao segundo trimestre de 2005, enquanto o Google reportou um ganho de 1,384 bilhões para o mesmo período. Alémdisso, previsões sugerem que a influência da publicidade de busca irá aumentar nos próximos anos através da diversificação e introdução de novos serviços. A exploração de tais possibilidades implica em avanços tanto nas áreas comercial quanto tecnológica. Neste trabalho, nós discutimos o uso de técnicas de Recuperação de Informação para melhorar o desempenho de sistemas de atribuição de propagandas em publicidade de busca, com ênfase em publicidade baseada em conteúdo. Nós investigamos como as diferentes evidências já disponíveis para empresas (que operam sistemas de publicidade baseada em palavras-chave) afetam o casamento de propagandas com o conteúdo de páginas da Web. Como resultado deste estudo, nós propomos novas estratégias para atribuir propagandas a páginas da Web. Experimentos com uma coleção de propagandas real mostram que o uso adequado das evidências disponíveis possibilita um desempenho de alta qualidade no processo de atribuição de propagandas. Nós também investigamos a combinação de evidências conceituais e sintáticas. Para isto, nós primeiro estudamos métodos para melhorar a classificação de páginas da Web e observamos que estratégias de classificação baseadas em apontadores são melhores que as tradicionais, baseadas unicamente na análise de texto. Ao utilizarmos os melhores classificadores obtidos como fonte de informação conceitual, concluimos que a combinação de métodos baseados em casamento sintático com os baseados em casamento conceitual apresenta melhor desempenho que aqueles baseados unicamente em casamento sintático.

Uma rede de telecomunicação ótica está configurada de forma a responder a uma dada demanda com um certo objetivo. No entanto, com o passar do tempo e com o desenvolvimento da infraestrutura, a demanda da rede muda. É neste contexto que se encontra o problema da reconfiguração, que tenta propor mudanças na atual configuração de rede de forma a adaptá-la à novas demandas. Considerando a quantidade de dados transportada, não é viável interromper a utilização da rede para reconfigurá-la, mesmo que por alguns instantes. Vários parâmetros devem ser considerados para determinar o que seria uma boa solução, e varias métricas podem ser usadas para medir a qualidade de uma solução. Em um primeiro momento, estudamos o problema da reconfiguração como sendo um problema de otimização mono-objetivo. Nós propomos um modelo matemático que atende as condições do problema. No entanto, obter a solução ótima para oproblema via modelo pode ser muito custoso em termos de tempo de computação. Propomos então uma heurística gulosa e uma heurística usando o simulated annealing. As soluções obtidas apresentam características diferentes dependente da métrica otimizada. O algoritmo guloso é rápido e acha soluções aceitáveis. O algoritmo do simulated annealing obtém soluções comparaveis às soluções ótimas.Em um segundo momento estudamos os aspectos multiobjetivo do problema da reconfiguração. Eles consistem em considerar simultaneamente as diferentes métricas e procurar, não uma única solução, mas sim, um conjunto de soluções representando diferentes compromissos interessantes e em geral em conflito. Depois propomos um algoritmo que usa nosso modelo matemático e uma adaptaçãodo algoritmo evolutivo. Os métodos propostos acham diferentes compromissos interessantes. Ao flexibilizar uma métrica permite geralmente melhorar de forma significativa as soluções obtidas com outras métricas.

Dentre os fatores de avaliação da qualidade de um software, destaca-se a manutenibilidade, a medida da facilidade de realizar sua manutenção. A manutenção de software é responsável pela maior parte do custo total de um sistema. Desta forma, faz-se importante a obtenção de recursos que contribuam para a criação de software cuja manutenção seja mais fácil. Dentre outros aspectos, a obtenção de software com esta característica é proporcionada principalmente pelo projeto de software que vise estrutura flexível e estável, na qual o grau de interdependência entre as partes constituintes do software, seus módulos, seja o menor possível. Quanto maior o grau de conectividade de um software, mais rígida a sua estrutura, menor a manutenibilidade e maior o custo do sistema. A orientação por objetos é um paradigma de construção de software caracterizado por potencializar a obtenção de software de alta qualidade, favorecendo aspectos como modularidade, manutenibilidade e reusabilidade.Este trabalho tem como tese que a conectividade é o fator preponderante na avaliação da qualidade estrutural de um software e, conseqüentemente, deve ser tida como fator de grande importância na manutenção e no custo de um sistema. O objetivo principal desta dissertação é a proposta de um modelo de avaliação de conectividade em software orientado por objetos, bem como a construção de uma ferramenta de coleta de métricas que viabiliza a aplicação do modelo proposto para softwares implementados na linguagem Java.

Esta dissertação apresenta um arcabouço orientado por aspectos para a implementação automatizada de persistência. A implementação de persistência em bancos de dados relacionais pode ser dividida nos seguintes sub-interesses: controle de conexões, controle de transações, controle de sincronização de objetos e recuperação de dados. O arcabouço proposto inclui uma ferramenta capaz de gerar aspectos para implementar cada um desses sub-interesses.

O trabalho aqui apresentado foi iniciado para atender a uma solicitação da SEPLAG-MG (Secretaria de Estado de Planejamento e Gestão) de um estudo para orientar a contratação de produtos e serviços de software por órgãos do Estado de Minas Gerais. Desse modo, o objetivo almejado foi o desenvolvimento de um processo para dar suporte aos órgãos públicos na aquisição de produtos ou serviços de software. O processo abrange o apoio à geração dos itens do Edital de licitação e a orientação no controle e monitoração da contratação e na manutenção do produto adquirido.Como parte da metodologia para desenvolvimento do processo, foi necessário inicialmente determinar como o Estado adquire seus produtos e serviços de software atualmente. Isso foi realizado por meio de entrevistas com os gestores de TI dos órgãos do Estado que mais adquirem. Foi obtido um levantamento das melhores práticas executadas nos órgãos avaliados, analisadas à luz da literatura especializada, e dos principais problemas enfrentados pelos órgãos em um procedimento de aquisição de software.Além disso, como uma alternativa para os critérios de seleção de fornecedores utilizados atualmente, foi realizado um mapeamento da maturidade dos processos de desenvolvimento de software das empresas fornecedoras de software do Estado. Na obtenção desse mapa, foi utilizado um questionário baseado no CMMI nível 2 para o levantamento, a partir de uma amostra representativa, dentre o universo de empresas. Como resultado, há uma comparação entre o desempenho geral e por área de processo para as empresas no modelo de maturidade escolhido (CMMI nível 2), assim como uma comparação por porte e por área de atuação.Finalmente, outro resultado importante aqui relatado, foi o desenvolvimento de um processo de Aquisição de produtos e serviços de TI (PrATIco), que propõe um procedimento para a aquisição de software no ambiente da Administração Pública.

Verificação por Equivalência é um dos componentes chave da metodologia de verificação formal atual para sistemas digitais. Ela é técnica de Verificação Formal mais utilizada atualmente pela indústria para verificação de igualdade entre duas descrições de um circuito. Diversas abordagens baseadas BDDs e SAT obtiveram um considerável sucesso nesta área. No entanto a crescente distânciaentre a capacidade dos resolvedores atuais e a complexidade das instâncias a serem verificadas motivam a exploração de novas alternativas, em busca de soluções melhores. Esta dissertação apresenta um núcleo inteligente para processamento distribuído de resolvedores SAT em Verificação por Equivalência. Especificamente, o núcleo proposto explora o processamento paralelo de resolvedores SAT e propõe uma nova técnica para a identificação de similaridades estruturais entre os circuitos a serem verificados. Ao final, são apresentados resultados que comprovam a eficiência da metodologia proposta.

Sistemas de gerência de redes são essenciais principalmente quando partes de uma rede não estão operacionais. Em particular, aplicações de gerência de redes devem funcionar corretamente na presença de falhas na rede. O acesso aos dados de gerência de um elemento de rede falho ou inacessível pode ajudar a determinar o motivo de sua falha. Contudo, a maioria dos sistemas de monitoramento de redes apenas permite o acesso aos objetos de gerência de agentes livres de falhas. Este trabalho apresenta uma estratégia para a construção de sistemas de gerência de redes altamente disponíveis. A estratégia emprega replicação de dados, um modelo organizacional hierárquico e distribuído, e a uso da abordagem de agrupamento, que permite uma divisão lógica das redes, a fim de reduzir a sobrecarga de mensagens trocada entre os elementos da rede. A primeira contribuição da tese é a definição de uma arquitetura de agrupamento de agentes para a replicação de objetos de gerência. A arquitetura é estruturada em três camadas. A camada inferior corresponde aos tradicionais agentes nos elementos da rede, que mantêm os objetos de gerência nas suas MIB´s (Management Information Base) locais. A camada intermediária corresponde as entidades de gerência chamadas gerentes de cluster que têm a tarefa de monitorar os objetos de gerência dos agentes e replicar tais objetos em outros gerentes de cluster. A camada superior corresponde a entidade gerente que define cada cluster de agentes assim como a relação entre esses clusters. Um cluster de agentes oferece funcionalidade de objetos tolerante a falhas. Desta maneira, objetos de gerência replicados de um agente falho ou inalcançável que a pertença a um dado cluster podem ser acessados através de seu gerente de cluster ou através de um dos seus clusters pares.A segunda contribuição da tese é um framework de agrupamento de agentes SNMP para a comunidade Internet. Este framework SNMP descreve a conjunto de objetos de gerência que suporta a replicação dos objetos de gerência. A MIB chamada ReplicMIB especifica como definir os membros de cluster, os objetos replicados, e os clusters pares de um dado cluster. Um exemplo quanto ao uso do framework é mostrado junto com a descrição dos objetos da MIB. A terceira contribuição da tese é uma ferramenta de gerência de falhas baseada no framework no framework de agrupamento de agentes SNMP. A ferramenta estende as funcionalidades dos agentes SNMP a fim de replicar objetos de gerência, e também possibilita o acesso aos dados de gerência replicados em agentes SNMP livres de falhas. A ferramenta foi construída usando os softwares de domínio público NET-SNMP e Ensemble. Modificações na estrutura interna permitem que os agentes SNMP atuem como gerentes de cluster. Uma aplicação de comunicação de grupo chamada mcluster garante a infraestrutura para uma comunicação confiável entre os gerentes de cluster e assegura assim a consistência dos objetos de gerência replicados. Uma extensiva avaliação desta ferramenta foi realizada numa rede local. A avaliação consistiu de uma análise dos recursos consumidos, uma análise de desempenho, e um breve estudo da disponibilidade dos objetos de gerência em situações de falhas.

Essa dissertação apresenta o problema da construção de quadros de horários em instituições de ensino, conhecido como timetabling, por um ângulo diferente dos trabalhos descritos na literatura, que é aplicável ao cenário brasileiro. A elaboração de quadros de horários acadêmicos é uma atividade estrutural de umainstituição de ensino. No sistema de ensino superior brasileiro existem regras e normas que definem parâmetros de qualidade, os quais devem ser atendidos pelas instituições. Esse trabalho propõe uma metodologia para construção de quadros de horários acadêmicos, tal que os aspectos de custo operacional e atendimento aos requisitos legais sejam considerados. Os principais parâmetros utilizados são oriundos do SINAES (Sistema Nacional de Avaliação da Educação Superior), gerido pelo MEC (Ministério da Educação), por meio da Avaliação Institucional realizada pelo INEP (Instituto Nacional de Estudos e Pesquisas Educacionais Anísio Teixeira). Entre eles cabe destacar o regime de trabalho, a titulação, as publicações e produções do corpo docente. Então, com base nessas e outras informações, deseja-se realizar a alocação dos professores nas atividades institucionais de modo eficiente, a fim de se obter o nível de qualidade desejado e uma aplicação racional dos recursos docentes. Devido à abordagem da gestão de custos, o trabalho é direcionado às instituições de ensino superior privadas, pois vários critérios abordados não estão presentes no contexto público. Então, um processo para a construção de um quadro de horários é proposto, o qual inclui modelos de otimização para a alocação de professores às disciplinas ofertadas, tanto para instituições organizadas em um único campus como para instituições multicampi.

Este trabalho apresenta uma nova abordagem para o desenvolvimento de interfaces visuais humano-robô baseadas em visão computacional. O método proposto se baseia na utilização de uma linguagem composta por gestos simples, onde um gesto isolado não possui qualquer significado, mas uma palavra, composta por uma seqüência de gestos realizados na ordem correta, gera uma resposta. Dessa maneira, pode ser definida uma gramática e associada uma ação do robô a cada uma dessas palavras, permitindo ao operador humano comandar o robô de maneira intuitiva.Considerando apenas gestos simples, o sistema de visão computacional privilegia a robustez se baseando em técnicas qualitativas, menos precisas porém mais robustas. A saída do sistema de visão computacional é processada por um sistema a eventos discretos estocástico que detecta a execução de comandos. O reconhecimento é realizado de maneira contínua, sendo o início e o fim de cada gesto identificados implicitamente pelo modelo. Foram utilizados dois tipos de sistemas a eventos discretos: cadeias de Markov e Modelos Ocultos de Markov (MOMs, do inglês, Hidden Markov Models). Para ambos os tipos foi desenvolvida uma metodologia para a construção automática do modelo.Os testes realizados comprovam a eficácia do método mesmo em ambientes complexos e com o executor dos gestos se movendo. Foi comprovada a robustez do método e a baixa incidência de falsos positivos, principalmente para os MOMs. A utilização de MOMs no contexto proposto apresentou desempenho superior ao das cadeias de Markov. Também foi identificada a importância da escolha correta dos comandos da gramática, para evitar uma deterioração significativa da taxa de reconhecimento à medida que a quantidade de comandos aumenta.

O recente desenvolvimento das tecnologias de aquisição de dados fez com que cada vez tivessemos mais dados disponíveis para processamento, entretanto, o aumento do volume de dados disponível criou uma demanda de processamento que extrapola a capacidade de apenas um computador, dessa forma, aplicações científicas foram forçada a utilizar recursos distribuídos e compartilhados. Entretanto,a maioria das aplicações científicas existentes foram desenvolvidas seqüencialmente e não eram capazes de utilizar recursos distribuídos. Em resposta a essas necessidades foram introduzidos os sistemas de fluxo de trabalho científicos, os quais permitiram a utilização de aplicações sequênciais em ambientes distribuídos, possibilitando a exploração de grandes bases de dados. A introdução desses sistemas é baseada na observação de que aplicações científicas são construídas pela composição de múltiplos estágios de computação, como em pipelines tradicionais, que precisam ser executados em grandes coleções de dados. Dessa forma, os sistema de fluxo de trabalho permitiram que os estágios de computação da aplicação fossem mapeados em estágios de fluxos de trabalho, os quais são compartilhados entre usuários e executados em ambientes distribuídos.Neste trabalho, apresentamos um sistema de fluxo de trabalho único no sentido de que o mesmo foi especialmente desenvolvido para facilitar a execução dessas aplicações em ambientes distribuídos utilizando bancos de dados para armazenamento de dados científicos. Nosso sistema é otimizado para execução fluxos de trabalho intensivos em dados, pois nos preocupamos com as tarefas de gerenciamentode dados. Os resultados experimentais obtidos com este sistema mostram que podemos alcançar speedups próximos do linear para aplicações sofisticadas, criadas por múltiplos componentes.

Com a popularização das conexões de alta velocidade, cada vez mais usuários estão dispostos a utilizar aplicações baseadas em mídia contínua, motivando o desenvolvimento e implantação de diversas aplicações em uso comercial ou institucional. Mídia contínua é um tipo de aplicação de tempo real e que, por esse motivo, requer garantias de qualidade de serviço (QoS) por parte da infra-estrutura computacional. Existe uma série de abordagens para melhorar a QoS para mídia contínua em redes baseadas em "melhor esforço" como a Internet. Exemplos de abordagens são técnicas de replicação ou caching, entrega compartilhada e roteamento otimizado. Esta dissertação enfatiza a última abordagem e trata de mecanismos de roteamento que explorem a diversidade de caminhos e o compartilhamento de fluxos.A caracterização da diversidade de caminhos existente na Internet subsidia o primeiro grupo de trabalhos. No entanto, as tentativas de caracterização realizadas anteriormente foram limitadas a ISPs norte-americanos e europeus. Além disso, os protocolos para otimizar roteamento baseados em fluxos compartilhados somente haviam sido avaliados em topologias sintéticas e em poucas topologias reais. Dadas as limitações dos trabalhos realizados até o momento, esta dissertação analisa mais a fundo os ganhos potenciais da aplicação de técnicas alternativas para roteamento de mídia contínua na Internet.Para tanto, estendemos uma técnica de mapeamento de topologias em nível de roteadores e a usamos para coletar topologias reais da Internet, espalhadas pelo mundo. Caracterizamos essas topologias quanto à diversidade de caminhos, a fim de subsidiar trabalhos que se baseiam na premissa da existência de tal diversidade. Nossa caracterização revelou a existência de uma alta diversidade de caminhos em topologias mais dispersas (continentais), e uma diversidade baixa para topologias mais restritas (países pequenos). Por fim, realizamos uma análise extensiva de heurísticas propostas por Almeida para criação da árvore de distribuição para roteamento com fluxos compartilhados. Essa análise envolve o uso de topologias com diversos graus de dispersão e a variação de diversos parâmetros, tais como o número e a demanda dos sites clientes. Nossos resultados revelam que essas heurísticas são superiores na criação de árvores de distribuição para fluxos compartilhados, quando comparadas ao protocolo default para unicast e similares propostos como padrão também para compartilhamento de fluxos, apresentando ganhos de cerca de 35%, em termos banda média de rede consumida. Ganhos da ordem de 70% foram obtidos em situações nas quais a grande maioria dos sites faz o papel de réplica e de cliente ao mesmo tempo.

Mecanismos de busca na Web são caros para manter, caros para operar, e difíceis de projetar. Mecanismos modernos de busca contam com clusters de máquinas servidoras para processamento de consultas. Assim, o desempenho do processamento paralelo de consultas num cluster de servidores de índice é crucial para os mecanismos modernos de busca na Web. O objetivo desta tese é prover um arcabouço para o projeto e análise da infra-estrutura de mecanismos de busca na Web. Neste arcabouço (i) investigamos e analisamos a questão do desbalanceamento num cluster computacional composto por servidores de índice homogêneos e (ii) propomos um modelo de planejamento de capacidade para mecanismos de busca na Web.Num cluster de servidores de índice, o tempo de resposta depende basicamente do tempo de serviço do servidor mais lento para gerar uma resposta ordenada parcial. Abordagens anteriores investigam questões de desempenho neste contexto usando simulação, modelagem analítica, experimentação, ou uma combinação delas. Entretanto, estas abordagens simplesmente assumem tempos de serviço balanceados entre os servidores de índice homogêneos, um cenário que não observamos em nossa experimentação. Ao contrário, verificamos que mesmo com uma distribuição balanceada da coleção de documentos entre os servidores de índice, relações entre a freqüência de uma consulta na coleção e o tamanho de suas listas invertidas correspondentes levam a desbalanceamentos nos tempos de serviço de uma consulta nestes mesmos servidores, porque estas relações afetam o comportamento do cache do disco. Além disso, os tamanhos relativos da memória principal em cada servidor de índice (com referência ao uso do espaço em disco) e o número de servidores que participam do processamento paralelo de consultas também afetam o desbalanceamento nos tempos locais de serviço de uma consulta.A predição do desempenho de um mecanismo de busca na Web é usualmente feita empiricamente através de experimentação, requerendo uma configuração custosa. Assim, a modelagem tem um apelo natural neste contexto. Introduzimos um modelo de planejamento de capacidade para mecanismos de busca na Web que considera o desbalanceamento nos tempos de serviço de uma consulta entre os servidores de índice homogêneos. Nosso modelo, que é baseado numa rede de filas, é simples e razoavelmente preciso. Discutimos como ajustá-lo e como usá-lo para predizer, por exemplo, o impacto no tempo de resposta da consulta quando parâmetros tais como CPUs e discos são alterados. Isto permite ao gerente da máquina de busca determinar a priori se uma nova configuração do sistema irá manter o tempo de resposta sob determinadas restrições. Nossa abordagem é distinta e, acreditamos, útil para predizer o desempenho de mecanismos de busca reais.

Este trabalho trata o problema de estimar o alinhamento temporal entre 2 seqüências de vídeo não sincronizadas da mesma cena 3D, capturadas de pontos de vista distintos por uma câmera perspectiva e uma câmera para-catadióptrica. Apresentamos um método que é uma extensão de uma técnica já existente para alinhar temporalmente múltiplas seqüências de vídeo adquiridas por câmeras perspectivas.Resultados experimentais com seqüências reais mostram que nosso método pode alinhar os vídeos mesmo quando possuem grandes desalinhamentos. Finalmente, resultados experimentais com seqüências sintéticas mostram como nosso método se comporta na presença de erros no sistema.

Nas últimas décadas testemunhamos um crescimento contínuo do uso da tecnologia da informação em todas as áreas do conhecimento humano. Em paralelo, também se observa um aumento do grau de interatividade provida pelos sistemas computacionais como conseqüência tanto de uma melhor conectividade quantomelhores interfaces, incluindo recursos multimídia, como vídeo, áudio, ou realidade virtual. Assim, pode-se dizer que sistemas computacionaisinterativos, isto é, sistemas com os quais usuários interagem continuamente, requisitando e provendo informações, têm se tornado populares em nossa sociedade. Desde transações bancárias até telefones celulares, estamos quase sempre interagindo com sistemas e até mesmo com outros usuários através desses sistemas. Deve-se notar que os sistemas atuais possibilitam não somente as interações homem-computador, mas também uma variada gama de interaçõesusuário-usuário, que são mais ricas e complexas. Uma parte significativa das interações intermediadas por sistemas é síncrona,ou seja, o usuário submete informação ou uma requisição ao sistema e espera ela resposta, posteriormente solicita outra parte de informação e esse processo interativo continua. A Web, em particular o protocolo HTTP, é um exemplo de interação síncrona. De fato, padrões de interação similares existem desde o primeiro sistema computacional nos anos sessenta. Essas interações costumam ser complexas e intrigantes. É bastante difícil determinar exatamente os fatores que levam o usuário a comportar-se conforme observado. Primeiramente porque as informações que temos sobre os usuários sãoesparsas e variáveis, em termos de condições instantâneas que abarcam o comportamento observado e do seu histórico de ações. É notável observar que as interações não são isoladas, mas que as interações sucessivas constituem um ciclo de realimentação, onde o comportamento do usuário afeta o sistema e vice-versa. Existem fortes evidências de que boa parte do comportamento de um usuário seja reativo, ou seja, o usuário reage a condições instantâneas em tempo real. A hipótese principal desta dissertação é que o mundo real é reativo. Esse conceito significa que o comportamento do usuário varia de acordo com alguns fatores relacionados ao servidor e a aplicação que está sendo provida. A principal hipótese deste trabalho de tese é que sistemas computacionais interativos possuem um forte componente reativo. A tese desta dissertação é definir, caracterizar e modelar a reatividade em sistemas interativos, em particular em sistemas Internet. Entender a reatividade do usuário tem aplicabilidade em muitos cenários, desde avaliação de sistemas até melhoriasdos mesmos, como através de personalização. O maior desafio deste trabalho é identificar qual o limite da caracterização da reatividade. A principal motivação deste trabalho é entender como os usuários interagem com o sistema, possibilitando prover serviços com melhor desempenho e entender melhor as aplicações que envolvem negociação. As contribuições deste trabalho são a formalização do conceito de reatividade, a especificação de um modelo de reatividade multi-nível, a elaboração de metodologias de caracterização para modelar a reatividade do usuário e a validação do modelo e metodologia através de sua aplicação a cenários relevantes, como serviços Internet e e-business. Essas contribuições estão publicadas em alguns artigos internacionais. Vislumbramos como benefícios deste trabalho melhorias na caracterização de cargas de trabalho, novas técnicas de geração de carga de trabalho que considerem a reatividade, novas técnicas de controle de qualidade de serviço (QoS) e melhorias na modelagem e caracterização de serviços de e-business.

Auto-organização é um importante conceito para o desenvolvimento de sistemas de rede autônomos e de larga escala. Sua idéia principal é "a obtenção de um comportamento global a partir de interações locais entre os elementos do sistema", e isso leva a redes menos dependentes de controle centralizado, e que tendem a ser escaláveis, adaptáveis e, consequentemente, robustas. Em particular, uma área de pesquisa bastante ativa é a de Redes de Sensores sem Fio (Wireless Sensor Networks -- WSNs). WSNs possuem um grande potencial de serem empregadas em várias aplicações relevantes, e foram concebidas sob o paradigma da auto-organização devido a muitas características intrínsecas. Essas redes são formadas por uma grande quantidade de dispositivos sensores interconectados por um canal sem fio com a finalidade de realizar tarefas de sensoriamento de forma distribuída e cooperativa. Além da escala, que aumenta a complexidade de desenvolvimento e manutenção, essas redes tendem a ser muito dinâmicas, pois alterações topológicas podem ser freqüentes devido à destruição de elementos, ao esgotamento de energia, à inclusão de novos sensores, ou à intermitência de comunicação causada por interferências ou obstáculos. Ainda, muitas aplicações dessas redes requerem um funcionamento autônomo, pois podem ser aplicadas em locais remotos, inóspitos e de difícil acesso. Embora muitos trabalhos na literatura abordem aspectos de auto-organização em WSNs, às vezes de forma implícita, não é provida uma visão mais geral e prática que possa ser usada para novos projetos e desenvolvimentos. Além disso, o projeto de funções auto-organizáveis pode não ser trivial, pois não há métodos formais ou modelos para o mapeamento dos comportamentos globais desejados para regras de interações locais. Assim, esta tese avança em dois aspectos particulares da aplicação do conceito de auto-organização a essas redes. No primeiro, um guia de projeto (guideline) é desenvolvido para nortear a modelagem e desenvolvimento de novas funções auto-organizáveis nessas redes, e sua vantagem consiste em um melhor entendimento e a especificação de funções auto-organizáveis através de aspectos e mecanismos gerais. No segundo, um esquema de gerenciamento dessas redes é proposto de forma a consi- derar um aspecto prático da operação de WSNs de que diferentes requisitos ou objetivos globais podem ser requeridos por uma aplicação externa ou entidade de gerência. Assim, o esquema consiste em manter o funcionamento da rede de forma auto-organizável em um nível operacional, mas permitir a ação sobre as regras de interação locais por entidades centralizadas de mais alto nível que, por sua vez, têm a visão mais geral das necessidades externas e do desempenho da rede para o atendimento a esses diferentes objetivos. Com base nesses aspectos gerais propostos, este trabalho ainda apresenta duas contribuições individuais abordando funções específicas de WSNs. Na primeira, a objetividade necessária às WSNs é mostrada através do desenvolvimento de uma solução de roteamento. Em particular, duas propostas de roteamento pró-ativo e reativo auto-organizáveis são combinadas em uma solução adaptativa híbrida, chamada Multi, que estende a aplicação de auto-organização em uma abordagem prática. Na segunda, a necessidade de considerar diferentes funções auto-organizáveis em um projeto integrado é apresentada com em uma solução, chamada RDC, que considera as funções de roteamento e controle de densidade.

Este trabalho oferece uma discussão geral sobre o tema de fusão de dados em redes de sensores sem fio (RSSFs) que permite: (i) a identificação de problemas em aberto e (ii) o entendimento dos requisitos e implicações do uso de fusão de dados em RSSFs.Esta discussão é feita através de um levantamento bibliográfico do estado-da-arte envolvendo fusão de dados em RSSFs. Analisando as arquiteturas, modelos e métodos de fusão de dados identificados neste levantamento bibliográfico, é proposto um arcabouço (framework), chamado Diffuse, que compreende as principais funções eatividades de um processo genérico de fusão de dados e uma API que implementa métodos de fusão freqüentemente utilizados em RSSFs. O Diffuse é, portanto, uma ferramenta que permite ao projetista refletir e avaliar quais tipos e quais métodos de fusão de dados podem ser utilizados em sua solução, e como especificamente estes métodos podem ser usados para compor uma tarefa ou uma aplicação de fusão de dados. Embora o Diffuse possa ser aplicado em diferentes contextos, como prova de conceito, este trabalho mostra como o Diffuse pode ser usado para projetar uma solução econômica (em termos de consumo de energia) que ofereça um serviço confiável (tolerante a falhas) de roteamento. Os resultados aqui apresentados mostram que a abordagem proposta é capaz de reduzir o custo de comunicação para prover tal serviço. Em alguns casos, o tráfego gerado por esta abordagem chega a ser 85% inferior ao tráfego gerado por soluções freqüentemente utilizadas em RSSFs. Além disso, este trabalho propõe uma estratégia de roteamento, baseada em atribuição de papéis, para garantir a execução de uma aplicação de fusão de dados. Neste caso, baseando-se na premissa de que fusão de dados é utilizada pela aplicação para detecção de eventos, é proposto um algoritmo de atribuição de papéis, chamado InFRA, que organiza a rede somente quando um evento é detectado. De maneira resumida, o InFRA é um algoritmo reativo de atribuição de papéis que procura pelas menores rotas (conectando os nós fontes aos sorvedouros) que maximizam aagregação de dados. Os resultados apresentados mostram que, em alguns casos, o InFRA utiliza apenas 70% da energia gasta por outros algoritmos de roteamento usualmente adotados em RSSFs.

Avanços em técnicas de compressão, diminuição no custo de armazenamento e transmissões em grande velocidade têm facilitado a forma como os vídeos são criados, armazenados e distribuídos. Comoconseqüência, os vídeos passaram a ser utilizados em várias aplicações. Devido ao aumento na quantidade de dados dos vídeos distribuídos e usados em aplicações atuais, estes se destacam comoum tipo de dado multimídia, introduzindo, porém, o requerimento de um gerenciamento mais eficiente destes dados. Tudo isto tem aberto o caminho para novas áreas de pesquisa, tais como a indexação erecuperação de vídeo baseadas no conteúdo semântico, visual e espaço-temporal.Esta tese apresenta um trabalho dirigido à criação de um suporte unificado para a indexação semi-automática de video e recuperação iterativa. Para criar uma indexação unificada, é selecionado umconjunto de quadros-chave que capturam e encapsulam o conteúdo do vídeo. Isso é conseguido através da segmentação do vídeo em tomadas constitutivas e selecionando um número ótimo de quadros dentre os limites da tomada. Primeiro, desenvolvemos um algoritmo para segmentação automática (detecção de cortes de cena). A fim de prescindir da definição de limiares e parâmetros, utilizamos um método de classificação supervisionado. Adotamos um classificador SVM devido à habilidade para utilizar espaços de características de alta dimensão (utilizando funções de kernels) preservando a grande capacidade de generalização. Igualmente, avaliamos profundamente diferentes combinações de características ekernels. Avaliamos o desempenho do nosso classificador utilizando diferentes funções kernel visando encontrar aquele que apresente melhor desempenho. Nossos experimentos, seguem estritamente o protocolo da Avaliação TRECVID. Apresentamos os resultados obtidos na tarefa de detecção de cortes de cenas da Avaliação TRECVID de 2006. Os resultados obtidos foram satisfatórios lidando com um grande conjunto de características graças a nosso classificador SVM baseado em kernels.O passo seguinte depois da segmentação é a extração de quadros-chave. Eles são selecionados a fim de minimizar a redundância de representação enquanto preservam o conteúdo da tomada, i.e., selecionando um número ótimo de quadros dentro dos limites da tomada. Nós propomos um sistema interativo de recuperaçao de vídeo: RETINVID baseano no sistema RETIN, uma máquina de busca e recuperação por conteúdo de imagens. O objetivo do aprendizado ativo quando utilizando em indexação é reduzir significativamente o número de quadros-chave anotados pelo usuário. Usamos o aprendizado ativo para ajudar no etiquetado semântico de bases de dados de vídeos. A abordagem de aprendizado propõe amostras de tomadas-chave do vídeo para serem anotadas e posteriormente atualizar a base de dados com as novas anotações. Logo, o sistema usa o aprendizado cumulativo adquirido para propagar as etiquetas ao resto da base de dados, este processo é executado toda vez que uma amostra de quadros-chave é apresentada ao usuário para ser anotada.As amostras de quadros-chave apresentadas são selecionadas baseadas na habilidade do sistema para incrementar o conhecimento obtido. Portanto, temos escolhido o aprendizado ativo devido à capacidade de recuperar categorias complexas, especificamente a traves do uso das funções kernel. A falta de dados para treinamento, categorias não-balanceadas e o tamanho do vetor de características podem ser superados através do aprendizado ativo. Avaliamos o desempenho do nosso sistema usando a base da dados utilizada na tarefa de alto-nível da Avaliação TRECVID de 2005.

Problemas de seqüenciamento podem ser encontrados nas mais diversas áreas da ciência. Se considerarmos aplicações industriais, existe um grande número de problemas que podem ser modelados através de problemas de seqüenciamento, em especial aqueles relacionados a problemas de planejamento e programação da produção.O planejamento da produção de uma empresa é usualmente realizado considerando dois ou três níveis. Cada nível com diferentes objetivos, mas com uma forte correlação entre eles. Na escola clássica, num primeiro estágio a empresa trabalha com produtos agregados ou famílias de produtos, onde o foco do planejamento está na otimização dos recursos utilizados e na capacidade das plantas. Os problemas de seqüenciamento são encontrados no nível imediato do planejamento da produção.O objetivo desta tese é apresentar, discutir e resolver dois problemas de seqüenciamento, ambos os casos estão baseados num caso real de uma empresa Brasileira. O primeiro problema consiste num caso de máquinas paralelas considerando restrições realistas, como tempos de preparação de máquinas dependentes da seqüência e datas de entregas. Para resolver este problema, em forma exata, são propostos três modelos matemáticos e um algoritmo Branch and Bound. Um algoritmo baseado na técnica de relaxação Lagragiana é apresentado, seu principal objetivo é melhorar o limite inferior do problema e dessa forma melhorar o desempenho do algoritmo B\&B. O segundo problema considerado é o problema de flow shop permutacional. Nesse caso, são propostos e testados dois algoritmos híbridos.

Em menos de uma década, Programação Orientada por Aspectos (AOP) evoluiu de um conceito teórico para um conjunto de linguagens de programação e arcabouços de amplo uso no desenvolvimento de sistemas comerciais. A tecnologia que suporta ferramentas AOP é intrinsecamente intrusiva, pois altera o comportamento do código-base de aplicações. A costura de código realizada por compiladores da linguagem AspectJ deve introduzir comportamentos transversais definidos por adendos (advices) em programas Java sem causar impactos no seu desempenho. Neste trabalho caracterizam-se as técnicas de compilação e costura de código adotadas pelos compiladores da linguagem AspectJ ajc e abc, e identificam-se problemas existentes no código gerado durante a costura de adendos de contorno. Os problemas analisados são a repetição de implementações de adendos e hachuras (shadows) e repetição de variáveis de contexto. Apresentam-se otimizações que eliminam esses problemas para ambos os compiladores, bem como indicações de integração dessas soluções à etapa de costura de código de cada um. As otimizações propostas reduzem o tamanho, o tempo de execução e o consumo de memória de programas AspectJ que usam adendos de contorno.

Este trabalho apresenta uma análise comparativa de técnicas para a extração de regras de bancos de dados através da Análise Formal de Conceitos (AFC). As regras consideradas aqui são conjuntos de dependências entre atributos de bancos de dados. Especificamente, as dependências são: implicações, dependências funcionais, regras de associação e regras de classificação. Essas regras são originárias, principalmente, da teoria dos bancos de dados, na qual desempenham papel fundamental para auxiliar processos de tomada de decisão caso das implicações, regras de associação e classificação e na normalização de modelos lógicos caso das dependências funcionais. A AFC, por sua vez, possui uma estrutura matemática especialmente adequada para auxiliar na análise de dados. Essa análise é feita através de reticulados conceituais que representam dados de forma hierárquica. Sendo assim, o objetivo do trabalho é analisar e comparar métodos que utilizem a AFC para a descoberta de dependências entre atributos em bancos de dados. São analisados dez algoritmos representativos para extração dos quatro tipos de regras mencionados. Desses algoritmos, quatro são usados na identificação de dependências funcionais e implicações. São eles: Next Closure, Find Implications, Impec e Aprem-IR. Os seis algoritmos restantes são úteis na identificação de regras de associação e de classificação. Foram analisados quatro algoritmos para extrair regras de associação: AClose, Frequent Next Neighbours, Titanic e Galicia. Finalmente, foram analisados dois algoritmos para identificar regras de classificação: GRAND e Rulearner.Os algoritmos foram implementados e submetidos a bancos de dados reais e sintéticos.Os bancos de dados foram escolhidos e gerados segundo dois critérios: tamanho da base de dados (número de entradas) e densidade. Esses dois critérios tentam suprir a deficiência constatada na literatura no que diz respeito à escolha de bancos de dados para avaliação de algoritmos. Constatou-se que os algoritmos apresentam comportamentos característicos para diferentes bancos de dados. Neste trabalho, é sugerida a adequação de cada algoritmo aos bancos de dados com diferentes densidades e tamanhos.