RCAAP Repository

A caracterização de comportamento de usuários de Internet de banda larga possibilita o entendimento e a identificação das diferentes classes desses usuários, definidas por seus respectivos padrões de requisições de serviços. Tal caracterização cria condições para os ISPs (Internet Service Providers) de banda larga aprimorarem o gerenciamento da sua infra-estrutura tecnológica e o planejamento da prestação do serviço de acesso à Internet. Contudo, diferentes classes de usuários com padrões de requisição de serviços distintos requerem uma diferenciação de preço. O principal esquema de precificação praticado pelos provedores de acesso à Internet de banda larga é o esquema de tarifa plana (flat rate pricing scheme). Este esquema permite a criação de classes de assinatura atreladas ao valor máximo de transmissão que pode ser alcançado pelo usuário em sua conexão à Internet. Entretanto, a prática da tarifa plana pode não ser justa sob o ponto de vista dos usuários, pois, aqueles que utilizam poucos recursos em uma determinada classe de assinatura precisam subsidiar o uso de usuários da mesma classe que utilizam a maior parte da banda disponível. Além disso, esse esquema pode não ser vantajoso para o ISP de banda larga, uma vez que observa-se ociosidade de recursos em alguns momentos do dia e sobrecarga de trabalho em outros períodos. Um esquema de precificação justo sob o ponto de vista dos usuários deveria prever a diferenciação de preço para cada grupo de usuários com comportamento similar, permitindo que cada usuário escolha o nível de serviço mais condizente com a sua necessidade. E para ser vantajoso para o ISP, tal esquema deveria possibilitar também a otimização do uso dos recursos do provedor ao longo do dia. Este trabalho propõe um esquema de precificação de tráfego de banda larga baseado no comportamento dos usuários ao longo do dia (BPS -- Broadband Pricing Scheme), que é justo sob o ponto de vista dos usuários e vantajoso para o provedor de acesso. A criação desse esquema se justifica a partir da análise dos resultados da aplicação de uma metodologia de caracterização de comportamento de usuários de Internet de banda larga em um conjunto de dados reais de um ISP. A validação e a respectiva comparação do esquema proposto com outros esquemas de precificação descritos na literatura são realizadas por simulação com dados reais, coletados na infra-estrutura de um provedor de acesso de banda larga.Partindo da análise dos resultados da caracterização de comportamento de usuários de Internet de banda larga com dados reais, os resultados deste trabalho mostram que o BPS promove o uso justo da Internet por parte dos usuários do ISP e, conseqüentemente, otimiza os recursos do provedor re-distribuindo a carga de trabalho ao longo do dia. A simulação do esquema de precificação proposto, e de outros presentes na literatura, mostrou que o BPS é o esquema mais justo para os usuários, principalmente, porque a função utilidade utilizada para calcular os benefícios dos usuários é maior ou igual a zero na maioria das horas do dia. Além disso, os resultados da simulação também mostram que a economia de banda com o uso do BPS acontece significativamente, em média, em 60% do tempo, o melhor resultado entre os esquemas simulados. O uso de um esquema de precificação justo pode trazer benefícios tanto para o ISP quanto para os seus usuários.

O Problema do Caixeiro Viajante (PCV) e o Problema de Roteamento de Veículos (PRV), apesar da enorme gama de aplicações e do grande número de algoritmos desenvolvidos para resolvê-los, não possuem uma estrutura de custo que permita diferenciar produtos e/ou clientes mais importantes. Eles também não se preocupam com o tempo de espera dos consumidores que recebem as mercadorias e não asseguram um dado nível de qualidade de serviço para esses consumidores. Tanto o PCV quanto o PRV se preocupam apenas com o custo egoísta do operador logístico, que deseja retornar ao ponto de partida o mais cedo possível. Nesta tese são apresentados e resolvidos, de forma exata, quatro problemas, em que o custo da carga é relevante para o cálculo do custo total. Esse custo da carga está relacionado com a quantidade e com a qualidade dos produtos transportados, podendo também priorizar clientes mais importantes e/ou produtos perecíveis.Os problemas estudados neste trabalho são: Problema de Mínima Latência (PML); Problema de Um Veículo de Entrega (PUVE); Problema do Caixeiro Viajante Multiproduto (PCVM); e, Problema do Caixeiro Viajante Multiproduto Congestionado (PCVMC). Esses problemas têm como objetivo principal aliar os interesses, muitas vezes conflitantes, dos operadores logísticos que tendem a minimizar o seu próprio custo operacional, mas também precisam maximizar a satisfação dos seus clientes. Para todos os quatro problemas são apresentadas novas formulações matemáticas. Para o PML e para o PUVE, problemas existentes na literatura, são apresentados resultados exatos e resultados heurísticos melhores que os presentes na literatura. Para o PCVM são apresentados três versões de um algoritmo Cut-and-Branch baseado no método de Decomposição de Benders. Esse método se mostrou mais eficiente, em termos de tempo computacional, que o resolvedor CPLEX. Além disso, foi desenvolvido um algoritmo Lagrangeano que conseguiu resolver instâncias para as quais o CPLEX não consegue. Para o PCVMC, o problema mais geral, que engloba todos os anteriores e que usa uma função de custo não-linear, também foi desenvolvido um algoritmo baseado no Método de Particionamento de Benders que conseguiu resultados exatos de maneira eficiente.

Dispositivos para aquisição e processamento de imagens podem ser encontrados em sistemas complexos de monitoração de segurança ou simples aparelhos celulares. Em certas aplicações, o tempo necessário para processar uma imagem não é tão importante quanto a qualidade das imagens processadas (por exemplo, em imagens médicas), mas em alguns casos a qualidade da imagem pode ser sacrificada em favor do tempo. Essa tese se foca nesse último caso, e propõe duas metodologias eficientes para o realce de contraste de imagens. Os métodos propostos são baseados em equalização de histograma (EH), e focam em imagens em tons de cinza e em imagens coloridas. Os métodos baseados em EH atualmente utilizados para processar imagens em tons de cinza tendem a mudar o brilho médio da imagem para o tom médio do intervalo de tons de cinza. Essa mudança não é desejavél em aplicações que visam melhorar o contraste em produtos eletrônicos utilizados pelo consumidor, onde preservar o brilho da imagem original é necessário para evitar o aparecimento de artefatos não exitentes na imagem de saída.Para corrigir esse problema, métodos de bi-equalização de histogramas para preservação do brilho e contraste de imagens foram propostos.Embora esses métodos preservem o brilho da imagem original na imagem processada com um realce significante do contraste, eles podem produzir imagens que não parecem naturais.Esse novo problema foi resolvido por uma nova técnica chamada de Multi-Equalização de histogramas, que decompõe a imagem original em várias sub-imagens, e aplica o método de EH clássico em cada uma delas. Essa metodologia realiza um realce de contraste menos intenso, de forma que a imagem processada parece mais 'natural'. Essa tese propõe duas novas funções de discrepância para decomposição de imagens, originando dois novos métodos de Multi-EH. Além disso, uma função de custo é utilizada para determinar em quantas sub-imagens a imagem original será dividida. Através da comparação objetiva e quantitative usando uma medida de constrate, os experimentos mostraram que os métodos propostos são melhores que outros EH estudados, uma vez que eles preservam o brilho e produzem imagens com uma aparência mais natural. Em relação aos métodos para realce de contraste em imagens coloridas, essa tese propõe um método genérico e eficiente de EH baseado no espaço de cores RGB que preserva o tom (a matiz), e implementa duas instâncias desse método genérico. A primeira instância utiliza os histogramas 1D R-red, G-green e B-blue para estimar um histograma 3D RGB, que é então equalizado. A segunda instância, por sua vez, utiliza os histogramas 2D RG, RB, e GB. A EH é executada utilizando transformadas de deslocamento que preservam a tonalidade da cor, evitando o aparecimento de cores não reais. Os métodos propostos tem complexidade linear no espaço e no tempo em relação ao tamanho da imagem, e não usam nenhuma conversão de um espaço de cores para outro. As imagens produzidas foram avaliadas objetivamente, comparando os métodos propostos com outros estudados. A avaliação objetiva foi feita utilizando medidas de contraste e de qualidade da cor da imagem, onde a qualidade foi definida como uma função ponderada dos índices de naturalidade e cromicidade. Um conjunto de 300 imagens extraídas da base de dados da Universidade de Berkeley foram analisadas. Os experimentos mostraram que o valor do contraste das imagens produzidas pelos métodos propostos é, em médias, 50% maior que o valor do contraste na imagem original, e ao mesmo tempo a qualidade das imagens produzidas é próxima a qualidade da imagem original.

Redes de Sensores Sem Fio (RSSF) são redes basicamente guiadas por eventos. Um evento pode ser definido como sendo composto por um critério causal e um critério espaço-temporal. No primeiro caso, o tipo do evento é identificado, enquanto que no segundo, a localização no tempo e no espaço em que o evento ocorreu é especificada. Um nó sensor é capaz de identificar o primeiro critério (tipo do evento) facilmente usando os seus diversos sensores. O critério espaço-temporal, entretanto, só pode ser identificado quando os nós sensores de uma RSSF possuem relógios sincronizados e são capazes de determinar suas posições físicas. Informações de tempo e espaço são necessárias também para uma série de algoritmos e protocolos em RSSFs como, por exemplo, em fusão de dados, rastreamento de objetos, contrução de mapas de energia, controle de densidade, etc. Logo, sincronização e localização em RSSFs são problemas importantes que precisam ser estudados e analisados.Nesta tese, propõe-se que sincronização e localização em RSSFs são, na verdade, duas partes do mesmo problema: localizar os nós da rede no tempo-espaço. Nestas redes, nem informações de espaço sem tempo nem de tempo sem espaço podem ser consideradas informações completas. Além disso, as semelhanças entre os problemas de localização e sincronização sugerem que eles podem e devem ser estudados e analisados como um único problema: localização no tempo e no espaço. Sob este ponto de vista, tempo pode ser visto como uma dimensão do espaço, i.e., precisa-se resolver um problema de localização em 4-dimensões. Como resultado, ao se resolver ambos os problemas ao mesmo tempo, a utilização dos recursos da rede pode ser minimizada e ambos os problemas podem apresentar melhores resultados se comparado com os casos em que eles são resolvidos separadamente.Três soluções diferentes para o problema de localização no tempo e no espaço são então propostas tendo-se em vista diferentes cenários em RSSFs. Tais soluções são os algoritmos Synapse, Lightness e Mobilis. Os algoritmos propostos não apenas aproveitam os recursos adicionais de hardware necessários para a localização dos nós para melhorar os resultados da sincronização como também aproveitam o custo maior de comunicação necessários para a sincronização de forma a melhorar a localização dos nós. Diversos experimentos são mostrados para avaliar a performance dos algoritmos propostos. Os resultados obtidos mostram que as soluções propostas são capazes de serem implementadas em RSSFs e também confirmam as vantagens em se resolver tanto a localização quanto a sincronização em um mesmo algoritmo.

O objetivo desse trabalho é apresentar duas contribuições importantes para o problema de Verificação de Equivalência Combinacional (CEC, do Inglês, Combinational Equivalence Checking). A primeira contribuição importante é uma técnica de pré-processamento que deriva informações redundantes dos dois circuitos sob CEC de modo a reduzir o tempo utilizado pelo Resolvedor de Satisfabilidade (SAT) para aprova de equivalência entre ambos circuitos. Através dessa técnica, implementada em uma ferramenta denominada Vimplic, é possível superar em desempenho as principais ferramentas do estado da arte de CEC baseado em SAT. É importante ressaltar que a técnica depré-processamento proposta é formalizada de modo a garantir a exatidão das implicações derivadas e assegurar que a mesma não produz falsos negativos e nem falsos positivos em relação à equivalência dos circuitos sob CEC. Além de detalhes de implementação da Vimplic, o presente trabalho também apresenta uma revisão bibliográfica completa das técnicas de CEC e, principalmente, das técnicas de pré-processamento para SAT. Finalmente, através da aplicação da ferramenta Vimplic, é possível estabelecer relaçõesimportantes entre o presente trabalho e os trabalhos na área de Satisfabilidade através do estudo de redundância em fórmulas em CNF.A segunda contribuição importante proposta é uma ferramenta para geração de circuitos, a BenCGen, que tem como principal objetivo a produção de circuitos para benchmarks. Essa ferramenta é capaz de gerar 24 tipos de circuitos diferentes com tamanhos parametrizados.Variando-se do menor para o maior tamanho de cada circuito, mais de 1.000.000 circuitos podem ser gerados. Tal ferramenta vem suprir uma grande demanda de novos benchmarks para CEC e para outras áreas de Verificação Formal. É importante ressaltar que a maior parte dos circuitos gerados pela ferramenta foram provados corretos. Além disso, uma revisão bibliográfica dos principais benchmarks para a área de Verificação Formal é mostrada no presente trabalho, na qual são destacados os seus principais benefícios e limitações.Finalmente, um comparativo entre os resolvedores de Satisfabilidade mais eficientes na resolução de instância de problemas de CEC é apresentado. O comparativo foi feito por meio de um benchmark produzido pela ferramenta BenCGen e através do mesmo foi possívelindicar o resolvedor de SAT mais adequado para os problemas de CEC estudados.

A Internet é hoje uma das principais mídias de veiculação de anúncios, dentre outros motivos, devido a possibilidade de exposição global de produtos e serviços e aos baixos custos envolvidosnessa exposição. Com isso cada vez mais recursos são destinados a publicidade na rede. Oprincipal tipo de anúncio na Internet é a publicidade de busca, na qual um dado anuncianteobtém uma posição de destaque na lista de propagandas mediante um valor pago. Segundoprevisões do eMarketer, o crescimento dos ganhos com publicidade de busca será da ordemde 148%, saltando de US$ 16.9Bi em 2006 para US$ 42Bi em 2011. O tipo mais popular depublicidade de busca é conhecido como keyword-targeted advertising (propaganda direcionadabaseada em palavra-chave), no qual as propagandas exibidas para o usuário são escolhidasa partir dos termos de sua consulta. O sucesso da propaganda baseada em palavra-chavemotivou o surgimento de outro tipo de anúncio conhecido como content-targeted advertising(propaganda direcionada baseada em conteúdo). Neste caso, a lista de propagandas édeterminada a partir do texto da página na qual as propagandas serão exibidas.Neste trabalho propomos e testamos um novo arcabouço baseado em programação genéticapara o problema de propaganda direcionada baseada em conteúdo. Diferentemente detrabalhos anteriores nosso método permite combinar as evidências estatísticas disponíveis paramelhorar a sugestão de propagandas para páginas da Web. Assim, nosso trabalho propõe umanova técnica de sugestão de propagandas levando em consideração uma grande quantidade deevidências disponíveis o que leva a resultados superiores ao estado-da-arte na área.Para validar o arcabouço proposto utilizamos uma coleção real de páginas e uma coleçãoreal de propagandas. Os resultados experimentais mostram que o arcabouço baseado emprogramação genética superou em mais de 60% o melhor método da literatura em termosde precisão média. Além disso, programação genética mostrou-se bastante ecaz em evitar asugestão de propagandas não-relevantes em páginas da Web. Esse fato é muito importantedado o impacto negativo da sugestão de propagandas não-relevantes para os usuários. Porm, realizamos uma análise das árvores que representam os indivíduos gerados utilizandoprogramação genética, concluindo que existe grande variabilidade entre os melhores indivíduosem termos da estrutura das árvores. Além disso, vimos que apenas uma pequena parcela dasevidências disponíveis foi utilizada pelos melhores indivíduos encontrados.

A crescente demanda por informação de qualidade, para análise e tomada de decisão, favorece o crescimento de ferramentas e métodos de automação do processo de extração e tratamento de dados da Web. O advento da Web trouxe consigo uma infindável quantidade de documentos e dados que se encontram difusos na Web. A centralização desses dados é de suma importância, pois reduz esforços na obtenção de dados de grandes repositórios, permitindo que esses esforços sejam dispendidos na análise e tomada de decisão, ou seja, retirar informação dos dados. Em muitos casos o interesse reside em uma forma efetiva de buscar informação ao invés de navegar por páginas da Web procurando dados de interesse, que muitas vezes não estão estruturados da melhor forma.A motivação para este trabalho surgiu da necessidade de se criar um processo que permita a coleta de páginas contendo dados de interesse e efetue a extração desses dados a partir de uma representação relacional previamente criada pelo usuário. O banco de dados relacional gerado como resultado desse processo permite que dados contidos na Web possam ser analisados e manipulados de acordo com as necessidades de uma determinada aplicação. Neste contexto foi desenvolvida a Web2DB, uma ferramenta que, a partir da modelagem de um sítio eletrônico da Web, permite o planejamento e execução da coleta das páginas e posteriormente a extração dos dados, armazenando-os em um banco de dados relacional. O usuário configura os tipos de página a serem coletados, os dados de interesse para a extração e a forma de carregamento dos dados no banco de dados. A ferramenta permite ainda a geração de visões para que os dados extraídos das páginas possam ser visualizados de forma mais aderente às necessidades dos usuários da ferramenta.É utilizada uma estratégia de extração dos dados baseada em exemplos. O foco na participação do usuário, nas fases de mapeamento do processo como um todo, visa agregar valor com o conhecimento do negócio envolvido. O restante das atividades é feita de forma automática. Trata-se de uma nova abordagem prática para o problema de extração de dados da Web, quando o objetivo é a análise de uma grande massa de dados difusa em vários sítios eletrônicos na Web. A ferramenta permite a construção de representações relacionais de grandes sítios da Web e, por ser genérica, pode ser aplicada a qualquer sítio eletrônico que contemple os requsitos da ferramenta.

Os recentes avanços tecnológicos possibilitaram um grande crescimento da utilização de dispositivos móveis nos últimos anos. Conseqüentemente, a demanda por aplicações seguras nesse ambiente também cresceu. Segurança em redes tradicionais (cabeadas) já é um tema de reconhecida complexidade. O ambiente móvel, entretanto, introduz ainda mais complicações, como o meio de comunicação aberto que facilita a interceptação dos dados transmitidos, e as restrições dos dispositivos móveis, que geralmente possuem menos recursos computacionais, o que impede a utilização de algoritmos mais sofisticados de segurança.Este trabalho propõe uma adaptação para os métodos de segurança em ambientes móveis, na qual os métodos de segurança são escolhidos dinamicamente de acordo com o valor semântico associado aos dados transmitidos. O objetivo é realizar transmissões utilizando métodos de segurança consistentes com o valor do dado transmitido. Dessa forma, é possível utilizar menos recursos computacionais nas transmissões que não necessitam de segurança, a fim de utilizá-los nas transmissões que realmente precisam de segurança. A solução proposta isola completamente a camada de aplicação dos detalhes de implementação dos algoritmos de segurança. Ela só precisa informar os requisitos de segurança e qualidade de serviço associados a cada transmissão, ficando a cargo da camada de segurança a responsabilidade de escolher e aplicar o método de segurança mais adequado a cada transmissão. Os resultados experimentais mostraram que é possível obter ganhos significativos de performance, principalmente quando parte dos dados é transmitida sem utilizar nenhum método de segurança. Os experimentos também mostraram que a camada de segurança é capaz de se adaptar bem aos requisitos estabelecidos para cada transmissão.

A lógica é a ciência das inferências corretas, e um sistema lógico formal é uma ferramenta para demonstrar proposições em uma certa lógica de maneira correta. Há muitos sistemas lógicos formais, e muitas maneiras de formalizá-los, por exemplo, usando dedução natural ou cálculo de seqüentes. O cálculo das estruturas (CoS) é um novo formalismo proposto por Alessio Guglielmi em 2004 que generaliza o cálculo de seqüentes no sentido de que regras de inferência podem ser aplicadas em qualquer profundidade dentro de uma fórmula, em vez de apenas no conectivo principal. Com esta característica, demonstrações em CoS são menores do que em qualquer outro formalismo que suporte provas analíticas. Apesar de ser interessante ter esta nova liberdade e expressividade do cálculo das estruturas, sob o ponto de vista de construção de demonstrações mais liberdade significa um espaço de busca maior. E isto deve ser restringido quando se procura pela automação completa de sistemas dedutivos. Algun s esforços foram realizados para reduzir este não determinismo, mas se tratam de abordagens basicamente operacionais, e nenhum resultado teórico sólido a respeito do comportamento computacional do CoS foi obtido até agora. O foco principal desta dissertação é discutir caminhos para propor uma estratégia de demonstração para CoS adequada à implementação. Esta estratégia deve ser teórica, e não puramente operacional. Nós introduzimos o conceito de número de incoerência de subestruturas dentro de uma estrutura e usamos este conceito para atingir nosso resultado principal: um algoritmo que, de acordo com a nossa conjectura, corresponde a uma estratégia de demonstração para toda estrutura demonstrável no subsistema FBV (a lógica linear multiplicativa \MLL\ estendida pela regra mix) contendo apenas pares de átomos distintos dois a dois. Nosso algoritmo foi implementado e acreditamos que nossa estratégia seja um bom ponto de partida para explorar os aspectos computacionais do CoS e m sistemas mais gerais, como o próprio sistema BV.

Desde a popularização de documentos digitais, a classificação automática de textos é considerada um importante tópico de pesquisa. Apesar dos esforços na área, ainda há espaço para aperfeiçoar o desempenho de classificadores. A maior parte da pesquisa em classificação automática de texto foca em desenvolver algoritmos de classificação. Porém, não há muitos esforços concentrados em aperfeiçoar a representação das bases de dados usadas para treinar classificadores automáticos de texto. Este tipo de esforço, por sua vez, é o foco deste trabalho.Nós propomos uma estratégia de tratamento de dados, baseada em extração de características, que precede a tarefa de classificação, a fim de introduzir em documentos características discriminativas de cada classe capazes de melhorar a eficácia da classificação.Nossa estratégia é baseada em co-ocorrência de termos visando à geração de termos compostos discriminativos, chamados de c-termos, que podem ser incorporados aos documentos para facilitar a tarefa de classificação. A idéia é que, quando usados em conjuntos com os termos isolados, a ambigüidade e ruído inerente aos termos que compõem os c-termos é reduzida, portanto tornando-os mais úteis para separar classes em partições mais homogêneas.Contudo, o custo computacional da extração de características pode tornar o método inviável. Neste trabalho, elaboramos um conjunto de mecanismos que torna a estratégia computacionalmente viável ao mesmo tempo em que aperfeiçoamos a eficácia dos classificadores.Nós testamos essa abordagem com diversos algoritmos de classificação e coleções de texto que são referência na literatura. Resultados experimentais demonstram ganhos em quase todos os cenários testados, desde os algoritmos mais simples, como k-Nearest Neighbors (kNN) (46% de ganho em micro-média F1 sobre a coleção 20 Newsgroups 18828) até o algoritmo mais complexo, estado da arte, Support Vector Machine (SVM) (10,7% de ganho em macro-média F1 na coleção OHSUMED).

Mineração de padrões freqüentes é um dos temas mais explorados da mineração de dados, assumindo um papel essencial em inúmeras tarefas que possuem, como objetivo, encontrar padrões de determinado interesse numa base. Entretanto, grande parte das soluções propostas nesta linha de pesquisa ainda possui problemas não solucionados, sendo muitos deles relacionados com a explosão do número de padrões freqüentes encontrados na base de dados. Isto acontece pelo fato dos padrões freqüentes obedecerem à propriedade da antimonotonia, que diz que, se um padrão é freqüente, todos os seus sub-padrões também o serão. Como conseqüência, o conjunto-solução, por compreender uma grande quantidade de elementos relacionados, acaba por apresentar informações redundantes, provenientes de padrões de baixa significância, que não adicionam, ao resultado, informações úteis o suficiente para justificar a sua importância.Esta dissertação apresenta uma nova metodologia para obtenção de padrões de interesse numa base de dados que explora o conceito de ortogonalidade - definida como a medida do quanto os elementos de um conjunto contribuem com informações não redundantes para a solução de um problema - e a sua aplicação ao problema da classificação associativa, como forma de aumentar a eficácia de um classificador, diminuindo a redundância e a ambigüidade das regras.

Em um mundo onde cada vez mais a informação se torna importante, contar com bases de dados confiáveis e consistentes é requisito essencial para tomada de decisão, análise de tendências, detecção de fraudes, mineração de dados, suporte a clientes, inteligência de negócio entre outros. Uma das formas de melhorar a qualidade dos dados é eliminar réplicas e consolidar a informação. Neste trabalho, apresentamos a ferramenta chamada FERAPARDA (FERramenta de Apoio ao PAReamento de DAdos). Ela permite combinar informação de várias bases de dados por meio do pareamento probabilístico de registros. O processo de pareamento se baseia na construção e comparação de pares registros, comparando nomes, endereços e outros atributos que geralmente não serviriam como identicadores individuais e na classificação probabilística do resultado. Não é raro encontrarmos bases com milhares senão milhões de registros, onde os dados podem apresentar problemas como ausência, inconsistência, erros de entrada ou mesmo duplicidade de informação. Tais problemas e a quantidade de registros obrigam a comparação de muitos pares (no pior caso, quadrático em relação ao tamanho da base), algo que torna o processo muito demorado para ser executado em um único computador. Geralmente, o processo de pareamento de registros é executado mais de uma vez com seus parâmetros sendo a justados a cada execução, uma vez que características da base de dados podem tornar difícil a decisão sobre o resultado. Um exemplo são bases de dados onde nomes de pessoas ocorrem com grande freqüência ou ainda situações onde é muito difícil diferenciar se dois registros dizem respeito à mesma pessoa, como é o caso de gêmeos. Existem muitas ferramentas que realizam o pareamento probabilístico de registros. No entanto, poucos trabalhos discutem a paralelização do processo, que se torna ainda mais necessária quando lidamos com bases de dados reais. Para diminuir o tempo de processamento, estudamos neste trabalho formas de paralelizar o algoritmo de pareamento de registro. Apresentamos e discutimos cada etapa do processo de pareamento e como ele foi paralelizado. Conseguimos com sucesso implementar uma solução capaz de escalar bem quando executada em um cluster de computadores. Neste trabalho também discutimos diferentes aspectos do paralelismo aplicados ao problema e também como a localidade de referência pode ser explorada a fim de maximizar o desempenho e escala da implementação, sem no entanto demandar uma grande quantidade de recursos, especialmente memória principal. Mostramos como o uso de cache de comunicação é fundamental para a escalabilidade e como uma das etapas - a blocagem - tem importância direta neste resultado. Esperamos que a ferramenta FERAPARDA possa ser usada em diferentes bases de dados, desde bases comerciais até bases da saúde e de programas sociais a fim de melhorar a qualidade da informação e melhorar a qualidade dos serviços que se baseiam em tal informação.

Atualmente, um dos grandes desafios da computação é o enorme volume de dados gerado pela facilidade de armazenamento e crescente uso de tecnologias em diversos contextos. A análise desses dados fornece apoio à tomada de decisões relacionadas a diversas áreas. Entretanto, pela grande quantidade de dados, essa análise tornou-se inviável de ser realizada sem o auxílio de técnicas computacionais. Nesse contexto, se apresenta a área de Mineração de Dados, que tem por objetivo a geração de conhecimento a partir de grandes volumes de dados. Ela abrange diversas técnicas, entre elas a de regras de associação, foco deste trabalho. Entretanto, um dos principais desafios para a ampla utilização desse tipo de sistema é a sua usabilidade, pois são vários os desafios de interação existentes. Esses sistemas normalmente são difíceis de usar, uma vez que requerem um conhecimento aprofundado de aspectos técnicos sobre o seu funcionamento. Neste trabalho, com o objetivo de ampliar o uso de ambientes de mineração de dados, apresentamos, implementamos e avaliamos um modelo de interface extensível que permite criar novas interfaces de mais alto nível e específicas para um contexto, abstraindo o conhecimento técnico. Nossa proposta consiste em um modelo que define os componentes de um módulo de extensão a ser acoplado em sistemas de segunda geração, sistemas que envolvem diversas aplicações e abrangem diversas técnicas. Para isso ser possível, considera-se dois perfis de usuários: os especialistas e os leigos. Os usuários especialistas devem dominar tanto o domínio da aplicação quanto o sistema de mineração de dados (que requer conhecimento técnico específico). O objetivo do especialista consiste em criar um nível de abstração que permita que usuários leigos, que não possuam os conceitos técnicos envolvidos, possam usar o sistema em contextos e problemas específicos. O modelo criado foi baseado na teoria da Engenharia semiótica, que considera que a interação consiste em um processo de comunicação entre o projetista e o usuário final. Nesse contexto, o modelo apresenta elementos em sua arquitetura que consideram esse aspecto e que permitem que os especialistas se tornem co-autores do sistema. Avaliações iniciais do modelo foram realizadas e uma implementação do mesmo foi desenvolvida, visando analisar sua viabilidade e utilidade. Os indicadores obtidos nas avaliações foram positivos, trazendo como grande benefício a possibilidade de ampliar a aplicação de técnicas mineração de dados, tanto em relação aos contextos de uso quanto ao público alvo.

Na tentativa de ampliar o espectro de busca e atenuar problemas de escalabilidade, redes Par-a-Par (P2P) têm sido apontadas como alternativa para novas gerações de máquinas de busca na Web. No entanto, a eficácia da busca por conteúdo em ambientes P2P pode ser gravemente limitada por características observadas em sistemas P2P reais, tais como a entrada e saída dinâmica de pares no sistema. Nosso estudo analisa o impacto desse aspecto na eficácia de máquinas de busca P2P. De forma a estimar os limites da eficácia, focamos nossa análise em modelos de rede P2P com níveis extremos de conhecimento dos pares sobre os documentos da rede. Nossos resultados revelam que o comportamento dinâmico dos pares pode afetar consideravelmente a eficácia da busca mesmo em cenários otimistas: em redes com altos níveis de conhecimento dos pares sobre os documentos da rede, uma fração significativa de consultas sofre um impacto na qualidade das respostas de pelo menos 26% ainda em cenários muito estáveis. Também confirmamos que o impacto desse aspecto em redes com baixos níveis de conhecimento dos pares pode ser ainda mais grave (75%). Também avaliamos a replicação de conteúdo como possível forma de atenuar os efeitos do comportamento dinâmico dos pares na eficácia de máquinas de busca P2P. Para tanto, analisamos o efeito de os usuários baixarem algumas páginas listadas na resposta à consulta e as adicionarem à sua coleção local. Observamos que essa estratégia pode melhorar significativamente a eficácia de máquinas de busca P2P. De fato, a qualidade das respostas em redes com níveis muito baixos de nhecimento dos pares sobre os documentos da rede pode melhorar significativamente mesmo em cenários pouco estáveis. Também discutimos os desafios existentes para adoção dessa solução. De fato, considerando a grande autonomia dos pares e a ausência dos benefícios da replicação comuns em sistemas P2P de compartilhamento de arquivos, o desenvolvimento das futuras máquinas de busca P2P pode depender amplamente de novos mecanismos de incentivo que considerem aspectos específicos desse tipo de aplicação.

Com o advento da Web 2.0, uma gama variada de aplicações têm incentivado maior interação entre usuários, acarretando a formação de redes de relacionamentos complexas. As características dessas redes de relacionamentos podem ser melhor entendidas de forma a identificar, por exemplo, como usuários fazem uso do sistema, permitindo assim futuras propostas de melhorias ou novas funcionalidades. Um exemplo destes tipos de aplicação são os sistemas de compartilhamento de fotos, cada vez mais populares graças à facilidade de criação e armazenamento de fotos e imagens digitais, reforçando a necessidade de uma maior investigação desses sistemas. Esta dissertação apresenta uma caracterização de dois tipos de redes de relacionamentos extraídas do Flickr, um sistema Web 2.0 muito popular direcionado ao armazenamento, organização, busca e compartilhamento de fotos. A primeira rede consiste de usuários do Flickr interligados por meio de relações de contato ou amizade entre eles, enquanto a segunda inclui usuários do Flickr interligados por meio de relações de testemunho. A caracterização das redes foi realizada em duas vertentes. A primeira vertente engloba a análise de características individuais dos usuários presentes em cada uma dessas redes, visando identificar e contrastar o padrão de uso do sistema visto em cada rede. Já a segunda vertente engloba a análise social de cada uma das redes e tem como objetivo entender as interações existentes entre os usuários em cada uma delas. Nossos resultados indicam que usuários que fazem uso da funcionalidade de testemunhos são, em geral, usuários mais ativos e com maior compromisso com a utilização do sistema. Além disso, um estudo de tráfego das fotos dos usuários presentes nas duas redes mostrou, entre outras coisas, que a popularidade das fotos dos usuários é fortemente correlacionada com o número de testemunhos recebidos pelos usuário e com o número de vezes que o usuário foi adicionado em listas de contatos. Finalmente, verificou-se que, enquanto a rede de contatos possui fortes características sociais, a rede de testemunhos é menos social e provavelmente reflete interações mais relacionadas ao interesse de um usuário pelo conteúdo de outros. Estes resultados se manifestaram estáveis em três coletas diferentes, realizadas em um intervalo de seis meses.

Redes em malha sem fio (wireless mesh networks) são redes dinamicamente auto-organizadas e auto-configuráveis cujos nós automaticamente estabelecem e mantêm a conectividade entre eles. As redes em malha sem fio possuem três tipos de nós: clientes, roteadores e gateways. Os roteadores e os gateways têm pouca ou nenhuma mobilidade. Os roteadores formam a espinha dorsal (backbone) das redes em malha sem fio. A comunicação em uma rede em malha sem fio é multi-salto (multi-hop), e as funcionalidades de gateway/bridge dos nós possibilitam a integração de diferentes redes, tais como, Internet, Wi-Fi, celular etc.O planejamento de redes em malha sem fio envolve muitas variáveis como topologia, mobilidade, tráfego, custo e capacidade. Neste trabalho é proposto um modelo matemático para o problema de planejamento de redes em malha sem fio. A solução do modelo consiste em determinar os caminhos de roteamento entre clientes e gateways que minimizam os custos de instalação dos roteadores utilizados e os custos dos enlaces que fazem parte das rotas. São realizados experimentos para validação do modelo utilizando o pacote de otimização comercial CPLEX. Os experimentos mostram que o problema de planejamento de redes em malha sem fio é um problema computacionalmente difícil. Neste trabalho também é desenvolvido um simulador para redes em malha sem fio sobre os arcabouços de simulação JiST e SWANS. O algoritmo de roteamento proposto encontra rotas que também minimizam os custos de instalação dos roteadores utilizados e os custos dos enlaces que fazem parte das rotas. As soluções apresentadas pelo simulador são comparadas com as soluções encontradas pelo CPLEX. O simulador é robusto e eficiente. Ele encontra boas soluções para os cenários de simulação, além de conseguir simular redes de tamanho razoável.

Dado um grafo G = (V,E), com custos nos vértices de V e nas arestas de E, o Problema da Árvore de Custo Mínimo com k Arestas (k-ACM) consiste em encontrar uma sub-árvore T em G com exatas k arestas, com o objetivo de que o custo de T seja mínimo. Este problema possui aplicacoções nas áreas de arrendamento de campos de petróleo, telecomunicações e roteamento, dentre outras.Neste trabalho, são propostas reformulações de Programação Inteira que se baseiam em uma transformação realizada sobre o grafo de entrada do problema. Após uma análise empírica do comportamento de algoritmos Branch-and-Bound que empregam as reformulações, foi proposta uma Relaxação Lagrangeana para uma delas. Esta Relaxação, que visa obter limites inferiores para o problema, foi integrada a uma heurística que se mostrou capaz de gerar limites superiores de qualidade para o mesmo.

Diversas técnicas para extrair e entender as informações contidas em imagens vêm sendo desenvolvidas através dos anos. Contudo, em geral, essas técnicas baseiam-se na premissa que os objetos e o observador estão imersos em um meio transparente como o ar, ou seja, um meio que não modifique a propagação luz. Não obstante, existem vários cenários em que o meio não é transparente, como os ambientes subaquáticos.Esta dissertação apresenta um estudo sistemático do problema de visualização de ambientes subaquáticos com iluminação natural e propõe uma metodologia para tratar esse problema. Adegradação na visibilidade de imagens subaquáticas é causada principalmente pelos efeitos de Atenuação e Dispersão da luz. Descrevemos as atuais soluções que vêm sendo propostas para reduzir esses efeitos e apresentamos uma metodologia com duas novas técnicas para estimação de parâmetros. Os problemas observados na visualização das imagens subaquáticas são causados basicamente pela interação da luz com a água. Dessa forma a metodologia que apresentamos melhora a visibilidade de cenas subaquáticas de forma automática, aliando um modelo físico que explique a propagação da luz na água a técnicas de Visão Computacional. A abordagem desenvolvida baseia-se no uso de um par de câmeras para adquirir imagens da cena, um sistema de visão estéreo denso para estimar sua estrutura tridimensional e duas técnicas para estimar parâmetros do modelo de propagação da luz em ambientes subaquáticos.Por meio de simulações e experimentos com cenas reais avaliamos as limitações e a qualidade na restauração de imagens subaquáticas utilizando a metodologia apresentada. Utilizando métricasqualitativas e quantitativas obtivemos resultados promissores para as técnicas de estimação de parâmetros propostas.

Este trabalho investiga o conjunto de respostas para consultas existencialmente quantificadas no contexto de um sistema de prova que representa as suas deduções na forma de árvores de prova. Em particular, nas situações em que o sistema gera uma resposta disjuntiva para a consulta do usuário, este trabalho propõe que uma resposta baseada em casos deveria ser fornecida ao invés. Inicialmente, é apresentada uma definição formal de respostas nesse contexto, a qual considera que mesmo árvores de prova geradas nos passos intermediários de uma dedução produzem respostas em potencial para a consulta. Particiona-se, ainda, o conjunto de respostas existentes segundo a definição dada em três classes de respostas: extensionais, intensionais e hipotéticas, e mostra-se que qualquer um desses tipos de respostas pode corresponder a uma resposta disjuntiva. Para as situações em que o sistema gera uma resposta disjuntiva da forma P(A1) V P(A2) V ... V P(Ak), é proposto um algoritmo que, a par tir da dedução da resposta na forma de árvore de prova, determina uma resposta baseada em casos para a mesma consulta. Uma resposta baseada em casos consiste em uma resposta definida em função de um número finito e exaustivo de casos no domínio do problema, sendo que cada caso implica em uma resposta não disjuntiva P(Ai) para a consulta.

Apresentamos uma arquitetura paralela para a renderização e ciente de múltiplos pontos de vista em um cluster de GPUs. Nossa abordagem utiliza um renderizador de light _eld para reconstruir os pontos de vista desejados a partir de um conjunto de imagens da cena. Para permitir a renderização de cenas dinâmicas, geramos as amostras novamente a cada quadro ao invés de gerar um bu_er de imagens. Ao mesmo tempo, nossa paralelização permite que cada ponto de vista utilize qualquer uma das amostras geradas, evitando trabalho redundante. A e_ciência da solução foi avaliada por meio de modelos matemáticos e validada por meio de medições de speedup e e_ciência. Concluímos que a solução proposta é escalável e pode suportar renderização a taxas interativas.