Uma Avaliação de abordagens alternativas para armazenar RDF em banco de dados relacional

O Resource Description Framework (RDF) é uma infra-estrutura, que possibilita a codificação, troca e reuso de metadata estruturado. Metadata é dados sobre dados. O termo refere a qualquer dado usado para ajudar a identificação, descrição e localização de recursos eletrônicos na rede. O RDF permite adicionar declarações, sinônimos e palavras que não estão presentes nos recursos, mas que são pertinentes a eles. Uma declaração RDF pode ser desenhada usando diagramas de arcos e nodos, onde os nodos representam os recursos e os arcos representam as propriedades nomeadas. O modelo básico consiste em recursos, propriedades e objetos. Todas as coisas sendo descritas pelas declarações RDF são chamadas de recursos. Um recurso pode ser uma página da Web inteira ou um elemento específico HTML ou XML dentro de um documento fonte. Uma propriedade é um aspecto específico, característica, atributo, ou relação usada para descrever um recurso. O objeto pode ser um outro recurso ou um literal. Estas três partes, juntas, formam uma declaração RDF. O resultado do parser para recursos com metadata RDF, é um conjunto de declarações referentes aquele recurso. A declaração destas propriedades e a semântica correspondente delas estão definidas no contexto do RDF como um RDF schema. Um esquema não só define as propriedades do recurso (por exemplo, título, autor, assunto, tamanho, cor, etc.), mas também pode definir os tipos de recursos sendo descritos (livros, páginas Web, pessoas, companhias, etc.). O RDF schema, provê um sistema básico de tipos necessários para descrever tais elementos e definir as classes de recursos. Assim, os recursos constituindo este sistema de tipos se tornam parte do modelo RDF de qualquer descrição que os usa. A geração de modelos RDF pode ser conseguida através de algoritmos implementados com linguagens de programação tradicionais e podem ser embutidos em páginas HTML, documentos XML e até mesmo em imagens. Com relação a modelos em imagens, servidores Web específicos são usados para simular dois recursos sobre o mesmo URI, servindo ora a imagem ora a descrição RDF. Uma alternativa para armazenar e manipular grande quantidade de declarações RDF é usar a tecnologia de banco de dados relacional. Abordagens para armazenar declarações RDF em banco de dados relacional foram propostas, mas todas elas mantêm modelos diversos de diferentes fontes. Critérios de avaliação como tempo de carga, proliferação de tabelas, espaço, dados mantidos e custo de instruções SQL foram definidos. Duas abordagens apresentaram resultados satisfatórios. Com uma nova abordagem proposta por este trabalho se obteve melhores resultados principalmente no aspecto de consultas. A nova proposta provê mecanismos para que o usuário faça seu próprio modelo relacional e crie suas consultas. O conhecimento necessário pelo usuário se limita em parte aos modelos mantidos e ao esquema RDF.

Reconhecimento de caracteres alfanuméricos de placas em imagens de veículos

Sistemas de visão artificial são cada vez mais usados para auxiliar seres humanos a realizar diferentes tarefas. Estes sistemas são capazes de reconhecer padrões em imagens complexas. Técnicas de visão computacional têm encontrado crescente aplicação em estudos e sistemas de controle e monitoração de tráfego de automóveis. Uma das áreas de pesquisa que tem sido objeto de estudo por diferentes grupos é a leitura automática de placas de matrículas como forma de detectar transgressores, encontrar carros roubados ou efetuar estudos de origem/destino [BAR99]. Com o constante crescimento do volume de tráfego de automóvel e a limitada capacidade dos sensores convencionais, especialistas da área recorrem a técnicas de identificação automática de veículos para obter dados relativos ao escoamento de tráfego. A identificação automática de veículos tem tido essencialmente duas abordagens distintas: a utilização de transponders e a utilização de técnicas de visão computacional [INI85] . Estas são essencialmente úteis em casos em que não é viável obrigar os motoristas a instalar transponders em seus automóveis. No entanto, essas técnicas são mais sensíveis às condições atmosféricas e de iluminação tais como nevoeiros, chuva intensa, luz noturna, reflexos em superfícies, etc. Este trabalho apresenta um estudo de diversas técnicas de processamento de imagem objetivando o aperfeiçoamento de um sistema de identificação automática de placas de veículos. Este aperfeiçoamento está relacionado com a diminuição do tempo de execução necessário à localização e reconhecimento dos caracteres contidos nas placas dos veículos bem como a melhorar a taxa de sucesso no seu reconhecimento. A primeira versão do sistema de identificação da placas de veículos descrito em [SOU2000], desenvolvido no CPG-EE da UFRGS, denominado SIAV 1.0, localiza e extrai 91,3% das placas corretamente mas apresenta uma taxa de reconhecimento das placas de 37,3%, assim como um tempo de processamento não satisfatório. Neste trabalho, cujo sistema desenvolvido é denominado SIAV 2.0, a imagem é previamente processada através da aplicação de técnicas de realce da imagem. O principal objetivo das técnicas de realce é processar a imagem de modo que o resultado seja mais apropriado para uma aplicação específica do que a imagem original [GON93]. O sistema busca melhorar a qualidade da imagem eliminando ou suavizando sombras e reflexos presentes na cena em virtude da iluminação não controlada. Visando um menor tempo de execução durante o tratamento e análise da imagem um estudo estatístico baseado na distribuição gaussiana foi realizado de maneira a restringir a área de análise a ser processada. O SIAV possui duas redes neurais como ferramentas de reconhecimento de caracteres. A partir da análise dos diferentes modelos de redes neurais empregados na atualidade, foi desenvolvida uma nova arquitetura de rede a ser utilizada pelo SIAV 2.0 que oferece uma taxa de reconhecimento superior a rede neural usada no SIAV 1.0. Visando um melhor tempo de execução, a implementação em hardware dedicado para este modelo é abordado. Os testes foram realizados com três bancos de imagens obtidas por câmeras diferentes, inclusive por dispositivo "pardal" comercial. Estes testes foram realizados para verificar a efetividade dos algoritmos aperfeiçoados.

Estudo e solução da equação de transporte de nêutrons bidimensionais pelo método LTSn para elevadas ordens de quadraturas angulares : LTSn2D - Diag e LTSn2D - DiagExp

O principal objetivo dessa tese consiste em determinar uma solução numéricada equação bidimensional do transporte de nêutrons para elevadas ordens de quadratura angular. Diagonalizando a matriz de transporte LTSN bidimensional , construímos dois algoritmos que se diferenciam pela forma de representar os termos de fuga transversal, que surgem nas equações LTSN integradas transversalmente. Esses termos no método LTSN2D − Diag são expressos como combinação linear dos autovetores multiplicados por exponenciais dos respectivos autovalores. No método LTSN2D − DiagExp os termos de fuga transversal são representados por uma função exponencial com constante de decaimento heuristicamente identificada com parâmetros materiais característicos do meio. A análise epectral desenvolvida permite realizar a diagonalização. Um estudo sobre o condicionamento é feito e também associamos um número de condicionamento ao termo de fuga transversal. Definimos os erros no fluxo aproximado e na fórmula da quadratura, e estabelecemos uma relação entre eles. A convergência ocorre com condições de fronteira e quadratura angular adequadas. Apresentamos os resultados numéricos gerados pelos novos métodos LTSN2D − Diag e LTSN2D − DiagExp para elevadas ordens de quadratura angular para um problema ilustrativo e comparamos com resultados disponíveis na literatura.

Protocolo de recuperação por retorno, coordenado, não determinístico

O uso da recuperação de processos para obter sistemas computacionais tolerantes a falhas não é um assunto novo. Entretanto, a discussão de algoritmos para a recuperação em sistemas distribuídos, notadamente aqueles que se enquadram na categoria assíncrona, ainda encontra pontos em aberto. Este é o contexto do presente trabalho. Este trabalho apresenta um novo algoritmo de recuperação por retorno, em sistemas distribuídos. O algoritmo proposto é do tipo coordenado, e seus mecanismos componentes determinam que seja classificado como um algoritmo baseado em índices (index-based coordinated). Desta forma, a tolerância a falhas é obtida através do estabelecimento de linhas de recuperação, o que possibilita um retorno consideravelmente rápido, em caso de falha. Seu desenvolvimento foi feito com o objetivo de minimizar o impacto ao desempenho do sistema, tanto quando este estiver operando livre de falhas como quando ocorrerem as falhas. Além disso, os mecanismos componentes do algoritmo foram escolhidos visando facilitar a futura tarefa de implementação. A satisfação dos objetivos decorre principalmente de uma importante característica assegurada pelos mecanismos propostos no algoritmo: o não bloqueio da aplicação, enquanto é estabelecida uma nova linha de recuperação. Esta característica, associada ao rápido retorno, oferece uma solução promissora, em termos de eficiência, para a recuperação, um vez que o impacto no desempenho tende a ser reduzido, quando o sistema encontra-se operando em ambas condições: livre de erros ou sob falha. Diferentemente da maioria dos algoritmos coordenados encontrados na literatura, o algoritmo proposto neste trabalho trata as mensagens perdidas. A partir da análise das características das aplicações, bem como dos canais de comunicação, quando estes interagem com o algoritmo de recuperação, concluiu-se que os procedimentos usados para recuperação de processos devem prever o tratamento desta categoria de mensagens. Assim, o algoritmo proposto foi incrementado com um mecanismo para tratamento das mensagens que têm o potencial de tornarem-se perdidas, em caso de retorno, ou seja, evita a existência de mensagens perdidas. Uma das decisões tomadas durante o desenvolvimento do algoritmo foi a de permitir um processamento não determinístico. Na realidade, esta escolha visou o aumento do espectro das falhas que poderiam ser tratadas pela recuperação. Tradicionalmente, a recuperação por retorno é empregada para tolerar falhas temporárias. Entretanto, a diversidade de ambiente, freqüente nos SDs, também pode ser usada para tolerar algumas falhas permanentes. Para verificar a correção do algoritmo, decidiu-se empregar um formalismo existente. Assim, a lógica temporal de Lamport (TLA) foi usada na especificação dos mecanismos do algoritmo bem como em sua demonstração de correção. O tratamento referente às mensagens perdidas, atrav´es do uso de mensagens de resposta, associado com o uso de uma lógica temporal, levou à necessidade de rever os critérios de consistência. Esta revisão gerou um conjunto de fórmulas de consistência ajustadas à existência de mensagens de diferentes classes: mensagens da aplicação e mensagens de resposta.

Operadores aritméticos de baixo consumo para arquiteturas de circuitos DSP

Este trabalho tem como foco a aplicação de técnicas de otimização de potência no alto nível de abstração para circuitos CMOS, e em particular no nível arquitetural e de transferência de registrados (Register Transfer Leve - RTL). Diferentes arquiteturas para projetos especificos de algorítmos de filtros FIR e transformada rápida de Fourier (FFT) são implementadas e comparadas. O objetivo é estabelecer uma metodologia de projeto para baixa potência neste nível de abstração. As técnicas de redução de potência abordadas tem por obetivo a redução da atividade de chaveamento através das técnicas de exploração arquitetural e codificação de dados. Um dos métodos de baixa potência que tem sido largamente utilizado é a codificação de dados para a redução da atividade de chaveamento em barramentos. Em nosso trabalho, é investigado o processo de codificação dos sinais para a obtenção de módulos aritméticos eficientes em termos de potência que operam diretamente com esses códigos. O objetivo não consiste somente na redução da atividade de chavemanto nos barramentos de dados mas também a minimização da complexidade da lógica combinacional dos módulos. Nos algorítmos de filtros FIR e FFT, a representação dos números em complemento de 2 é a forma mais utilizada para codificação de operandos com sinal. Neste trabalho, apresenta-se uma nova arquitetura para operações com sinal que mantém a mesma regularidade um multiplicador array convencional. Essa arquitetura pode operar com números na base 2m, o que permite a redução do número de linhas de produtos parciais, tendo-se desta forma, ganhos significativos em desempenho e redução de potência. A estratégia proposta apresenta resultados significativamente melhores em relação ao estado da arte. A flexibilidade da arquitetura proposta permite a construção de multiplicadores com diferentes valores de m. Dada a natureza dos algoritmos de filtro FIR e FFT, que envolvem o produto de dados por apropriados coeficientes, procura-se explorar o ordenamento ótimo destes coeficientes nos sentido de minimizar o consumo de potência das arquiteturas implementadas.

Desenvolvimento de arquitetura para sistemas de reconhecimento automático de voz baseados em modelos ocultos de Markov

Este trabalho foi realizado dentro da área de reconhecimento automático de voz (RAV). Atualmente, a maioria dos sistemas de RAV é baseada nos modelos ocultos de Markov (HMMs) [GOM 99] [GOM 99b], quer utilizando-os exclusivamente, quer utilizando-os em conjunto com outras técnicas e constituindo sistemas híbridos. A abordagem estatística dos HMMs tem mostrado ser uma das mais poderosas ferramentas disponíveis para a modelagem acústica e temporal do sinal de voz. A melhora da taxa de reconhecimento exige algoritmos mais complexos [RAV 96]. O aumento do tamanho do vocabulário ou do número de locutores exige um processamento computacional adicional. Certas aplicações, como a verificação de locutor ou o reconhecimento de diálogo podem exigir processamento em tempo real [DOD 85] [MAM 96]. Outras aplicações tais como brinquedos ou máquinas portáveis ainda podem agregar o requisito de portabilidade, e de baixo consumo, além de um sistema fisicamente compacto. Tais necessidades exigem uma solução em hardware. O presente trabalho propõe a implementação de um sistema de RAV utilizando hardware baseado em FPGAs (Field Programmable Gate Arrays) e otimizando os algoritmos que se utilizam no RAV. Foi feito um estudo dos sistemas de RAV e das técnicas que a maioria dos sistemas utiliza em cada etapa que os conforma. Deu-se especial ênfase aos Modelos Ocultos de Markov, seus algoritmos de cálculo de probabilidades, de treinamento e de decodificação de estados, e sua aplicação nos sistemas de RAV. Foi realizado um estudo comparativo dos sistemas em hardware, produzidos por outros centros de pesquisa, identificando algumas das suas características mais relevantes. Foi implementado um modelo de software, descrito neste trabalho, utilizado para validar os algoritmos de RAV e auxiliar na especificação em hardware. Um conjunto de funções digitais implementadas em FPGA, necessárias para o desenvolvimento de sistemas de RAV é descrito. Foram realizadas algumas modificações nos algoritmos de RAV para facilitar a implementação digital dos mesmos. A conexão, entre as funções digitais projetadas, para a implementação de um sistema de reconhecimento de palavras isoladas é aqui apresentado. A implementação em FPGA da etapa de pré-processamento, que inclui a pré-ênfase, janelamento e extração de características, e a implementação da etapa de reconhecimento são apresentadas finalmente neste trabalho.

ORPIS: um modelo de consistência de conteúdo replicado em servidores Web distribuídos

O surgimento de novas aplicações que utilizam o protocolo HTTP nas suas transações e a crescente popularidade da World Wide Web (WWW) provocaram pesquisas pelo aumento do desempenho de servidores Web. Para tal, uma das alternativas propostas neste trabalho é utilizar um conjunto de servidores Web distribuídos que espalham a carga de requisições entre vários computadores, atuando como um só associado a uma estratégia de replicação de conteúdo. Um dos problemas centrais a ser resolvido em servidores Web distribuídos é como manter a consistência das réplicas de conteúdo entre os equipamentos envolvidos. Esta dissertação apresenta conceitos fundamentais envolvendo o tema replicação de conteúdo em servidores Web distribuídos. São mostrados detalhes sobre arquitetura de servidores Web distribuídos, manutenção da consistência em ambientes de servidores Web distribuídos, uso de replicação e formas de replicação. Além disso, são citados alguns trabalhos correlatos ao propósito de manter réplicas consistentes em ambientes de servidores Web distribuídos. Este trabalho tem por objetivo propor um modelo de manutenção da consistência de conteúdo em servidores Web distribuídos com características de transparência e autonomia. O modelo, denominado One Replication Protocol for Internet Servers (ORPIS), adota uma estratégia de propagação otimista porque não existe sincronismo no envio das atualizações para as réplicas. Este trabalho apresenta os principais componentes tecnológicos empregados na Web, além dos problemas causados pela escalabilidade e distribuição inerentes a esse ambiente. São descritas as principais técnicas de aumento de desempenho de servidores Web que atualmente vêm sendo utilizadas. O modelo ORPIS é descrito, sendo apresentados seus pressupostos, elencados seus componentes e detalhados os seus algoritmos de funcionamento. Este trabalho dá uma visão geral sobre a implementação e os testes realizados em alguns módulos do protótipo do modelo, caracterizando o ambiente de desenvolvimento do protótipo e detalhes da implementação. São enumerados os atributos e métodos das classes do protótipo e definidas as estruturas de dados utilizadas. Além disso, apresentam-se os resultados obtidos da avaliação funcional dos módulos implementados no protótipo. Um ponto a ser salientado é a compatibilidade do modelo ORPIS aos servidores Web existentes, sem a necessidade de modificação em suas configurações. O modelo ORPIS é baseado na filosofia de código aberto. Durante o desenvolvimento do protótipo, o uso de software de código aberto proporcionou um rápido acesso às ferramentas necessárias (sistema operacional, linguagens e gerenciador de banco de dados), com possibilidade de alteração nos códigos fonte como uma alternativa de customização.

Um Algoritmo para indução de árvores e regras de decisão

A classificação é uma das tarefas da Mineração de Dados. Esta consiste na aplicação de algoritmos específicos para produzir uma enumeração particular de padrões. Já a classificação é o processo de gerar uma descrição, ou um modelo, para cada classe a partir de um conjunto de exemplos dados. Os métodos adequados e mais utilizados para induzir estes modelos, ou classificadores, são as árvores de decisão e as regras de classificação. As regras e árvores de decisão são populares, principalmente, por sua simplicidade, flexibilidade e interpretabilidade. Entretanto, como a maioria dos algoritmos de indução particionam recursivamente os dados, o processamento pode tornar-se demorado, e a árvore construída pode ser muito grande e complexa, propensa ao overfitting dos dados, que ocorre quando o modelo aprende detalhadamente ao invés de generalizar. Os conjuntos de dados reais para aplicação em Mineração de Dados são, atualmente, muito grandes, e envolvem vários milhares de registros, sendo necessária, também, uma forma de generalizar estes dados. Este trabalho apresenta um novo modelo de indução de classificadores, em que o principal diferencial do algoritmo proposto é a única passada pelo conjunto de treinamento durante o processo de indução, bem como a sua inspiração proveniente de um Sistema Multiagente. Foi desenvolvido um protótipo, o Midas, que foi validado e avaliado com dados de repositórios. O protótipo também foi aplicado em bases de dados reais, com o objetivo de generalizar as mesmas. Inicialmente, foi estudado e revisado o tema de Descoberta de Conhecimento em Bases de Dados, com ênfase nas técnicas e métodos de Mineração de Dados. Neste trabalho, também são apresentadas, com detalhes, as árvores e regras de decisão, com suas técnicas e algoritmos mais conhecidos. Finalizando, o algoritmo proposto e o protótipo desenvolvido são apresentados, bem como os resultados provenientes da validação e aplicação do mesmo.

Estimativa da precipitação através de técnicas de sensoriamento remoto : estudo de caso para o estado do Rio Grande do Sul

A quantificação da precipitação é dificultada pela extrema aleatoriedade do fenômeno na natureza. Os métodos convencionais para mensuração da precipitação atuam no sentido de espacializar a precipitação mensurada pontualmente em postos pluviométricos para toda a área de interesse e, desta forma, uma rede com elevado número de postos bem distribuídos em toda a área de interesse é necessária para um resultado satisfatório. No entanto, é notória a escassez de postos pluviométricos e a má distribuição espacial dos poucos existentes, não somente no Brasil, mas em vastas áreas do globo. Neste contexto, as estimativas da precipitação com técnicas de sensoriamento remoto e geoprocessamento pretendem potencializar a utilização dos postos pluviométricos existentes através de uma espacialização baseada em critérios físicos. Além disto, o sensoriamento remoto é a ferramenta mais capaz para gerar estimativas de precipitação nos oceanos e nas vastas áreas continentais desprovidas de qualquer tipo de informação pluviométrica. Neste trabalho investigou-se o emprego de técnicas de sensoriamento remoto e geoprocessamento para estimativas de precipitação no sul do Brasil. Três algoritmos computadorizados foram testados, sendo utilizadas as imagens dos canais 1, 3 e 4 (visível, vapor d’água e infravermelho) do satélite GOES 8 (Geostacionary Operational Environmental Satellite – 8) fornecidas pelo Centro de Previsão de Tempo e Estudos Climáticos do Instituto Nacional de Pesquisas Espaciais. A área de estudo compreendeu todo o estado do Rio Grande do Sul, onde se utilizaram os dados pluviométricos diários derivados de 142 postos no ano de 1998. Os algoritmos citados buscam identificar as nuvens precipitáveis para construir modelos estatísticos que correlacionem as precipitações diária e decendial observadas em solo com determinadas características físicas das nuvens acumuladas durante o mesmo período de tempo e na mesma posição geográfica de cada pluviômetro considerado. Os critérios de decisão que norteiam os algoritmos foram baseados na temperatura do topo das nuvens (através do infravermelho termal), reflectância no canal visível, características de vizinhança e no plano de temperatura x gradiente de temperatura Os resultados obtidos pelos modelos estatísticos são expressos na forma de mapas de precipitação por intervalo de tempo que podem ser comparados com mapas de precipitação obtidas por meios convencionais.

Uma abordagem Bottom-UP para a integração semântica de esquemas XML

XML (eXtensibile Markup Language) é um padrão atual para representação e intercâmbio dos semi-estruturados na Web. Dados semi-estruturados são dados não convencionais cujas instâncias de uma mesma fonte de dados podem ter representações altamente heterogêneas. Em função isto, um esquema para estes dados tende a ser extenso para suportar todas as alternativas de representação que um dado pode assumir. Parte do grande volume de dados disponível hoje na Web é composto por fontes de dados heterogêneas XML sobre diversos domínios do conhecimento. Para realizar o acesso a estas fontes, aplicações na Web necessitam de um mecanismo de integração de dados. O objetivo principal deste mecanismo é disponibilizar um esquema de dados global representativo dos diversos esquemas XML das fontes de dados. Com base neste esquema global, consultas são formuladas, traduzidas para consultas sobre os esquemas XML, executadas nas fontes de dados e os resultados retornados à aplicação. Esta tese apresenta uma abordagem para a integração semântica de esquemas XML relativos a um domínio de aplicação chamada BInXS. BInXS adota um processo bottom-up de integração, no qual o esquema global é definido para um conjunto de esquemas XML representadas atrtavés de DTDs (Document Type Definitions). A vantagem do processo bottom-up é que todas as informações dos esquemas XML são consideradas no esquema global. Desta forma, toda a informação presente nas fontes de dados pode ser consultada. O processo de integração de BInXS é baseado em um conjunto de regras e algoritmos que realizam a cnversão de cada DTD para um esquema canônico conceitual e a posterior integração semântica propriamente dita destes esquemas canônicos. O processo é semi-automático pois considera uma eventual intervenção de um usuário especialista no domínio para validar ou confirmar alternativas de resultado produzidas automaticamente. Comparada com trabalhos relacionados, BInXS apresenta as seguintes contribuições: (i) uma representação canônica conceitual para esquemas XML que é o resultado de uma anállise detalhada do modelo XML; (ii) um étodo de unificação que lida com as particularidades da integração de dados semi-estruturados e; (iii) uma estratégia de mapeamento baseada em expressões de consulta XPath que possibilita uma tradução simples de consultas globais para consultas a serem executadas nas fontes de dados XML.

Uso do network simulator-NS para simulação de sistemas distribuídos em cenários com defeitos

O desenvolvimento de protocolos distribuídos é uma tarefa complexa. Em sistemas tolerantes a falhas, a elaboração de mecanismos para detectar e mascarar defeitos representam grande parte do esforço de desenvolvimento. A técnica de simulação pode auxiliar significativamente nessa tarefa. Entretanto, existe uma carência de ferramentas de simulação para investigação de protocolos distribuídos em cenários com defeitos, particularmente com suporte a experimentos em configurações “típicas” da Internet. O objetivo deste trabalho é investigar o uso do simulador de redes NS (Network Simulator) como ambiente para simulação de sistemas distribuídos, particularmente em cenários sujeitos à ocorrência de defeitos. O NS é um simulador de redes multi-protocolos, que tem código aberto e pode ser estendido. Embora seja uma ferramenta destinada ao estudo de redes de computadores, o ajuste adequado de parâmetros e exploração de características permitiu utilizá-lo para simular defeitos em um sistema distribuído. Para isso, desenvolveu-se dois modelos de sistemas distribuídos que podem ser implementados no NS, dependendo do protocolo de transporte utilizado: um baseado em TCP e o outro baseado em UDP. Também, foram estudadas formas de modelar defeitos através do simulador. Para a simulação de defeito de colapso em um nodo, foi proposta a implementação de um método na classe de cada aplicação na qual se deseja simular defeitos. Para ilustrar como os modelos de sistemas distribuídos e de defeitos propostos podem ser utilizados, foram implementados diversos algoritmos distribuídos em sistemas síncronos e assíncronos. Algoritmos de eleição e o protocolo Primário-Backup são exemplos dessas implementações. A partir desses algoritmos, principalmente do Primário-Backup, no qual a simulação de defeitos foi realizada, foi possível constatar que o NS pode ser uma ferramenta de grande auxílio no desenvolvimento de novas técnicas de Tolerância a Falhas. Portanto, o NS pode ser estendido possibilitando que, com a utilização dos modelos apresentados nesse trabalho, simule-se defeitos em um sistema distribuído.

Adaptação dinâmica do timeout de detectores de defeitos através do uso de séries temporais

Uma aplicação distribuída freqüentemente tem que ser especificada e implementada para executar sobre uma rede de longa distância (wide-área network-WAN), tipicamente a Internet. Neste ambiente, tais aplicações são sujeitas a defeitos do tipo colapso(falha geral num dado nó), teporização (flutuações na latência de comunicação) e omissão (perdas de mensagens). Para evitar que este defeitos gerem comseqüências indesejáveis e irreparáveis na aplicação, explora-se técnicas para tolerá-los. A abstração de detectores de defeitos não confiáveis auxilia a especificação e trato de algoritmos distribuídos utilizados em sistemas tolerantes a falhas, pois permite uma modelagem baseada na noção de estado (suspeito ou não suspeito) dos componentes (objetos, processo ou processadores) da aplicação. Para garantir terminação, os algoritmos de detecção de defeitos costumam utilizar a noção de limites de tempo de espera (timeout). Adicionalmente, para minimizar seu erro (falasas suspeitas) e não comprometer seu desempenho (tempo para detecção de um defeito), alguns detectores de defeitos ajustam dinamicamente o timeout com base em previsões do atraso de comunicação. Esta tese explora o ajuste dinâmico do timeout realizado de acordo com métodos de previsão baseados na teoria de séries temporais. Tais métodos supõem uma amostragem periódica e fornececm estimativas relativamente confiáveis do comportamento futuro da variável aleatória. Neste trabalho é especificado uma interface para transformar uma amostragem aperiódica do atraso de ida e volta de uma mensagem (rtt) numa amostragem periódica, é analisado comportamento de séries reais do rtt e a precisão dee sete preditores distintos (três baseados em séries temporais e quatrro não), e é avaliado a influência destes preditores na qualidade de serviço de um detector de defeitos do estilopull. Uma arquitetura orientada a objetos que possibilita a escolha/troca de algoritmos de previsão e de margem de segurança é também proposta. Como resultado, esta tese mostra: (i) que embora a amostragem do rtt seja aperiódica, pode-se modelá-la como sendo uma série temporal (uma amostragem periódica) aplciando uma interface de transformação; (ii) que a série temporal rtt é não estacionária na maioria dos casos de teste, contradizendo a maioria das hipóteses comumente consideradas em detectores de defeitos; (iii) que dentre sete modelos de predição, o modelo ARIMA (autoregressive integrated moving-average model) é o que oferece a melhor precisão na predição de atrasos de comunicação, em termos do erro quadrático médio: (iv) que o impacto de preditores baseados em séries temporais na qualidade de serviço do detector de defeitos não significativo em relação a modelos bem mais simples, mas varia dependendo da margem de segurança adotada; e (v) que um serviço de detecção de defeitos pode possibilitar a fácil escolha de algoritmos de previsão e de margens de segurança, pois o preditor pode ser modelado como sendo um módulo dissociado do detector.

SAM: um sistema adaptativo para transmissão e recepção de sinais multimídia em redes de computadores

Esta Tese apresenta o SAM (Sistema Adaptativo para Multimídia), que consiste numa ferramenta de transmissão e recepção de sinais multimídia através de redes de computadores. A ferramenta pode ser utilizada para transmissões multimídia gravadas (vídeo sob demanda) ou ao vivo, como aulas a distância síncronas, shows e canais de TV. Seu maior benefício é aumentar o desempenho e a acessibilidade da transmissão, utilizando para isso um sinal codificado em camadas, onde cada camada é transmitida como um grupo multicast separado. O receptor, utilizando a ferramenta, adapta-se de acordo com a sua capacidade de rede e máquina no momento. Assim, por exemplo, um receptor com acesso via modem e outro via rede local podem assistir à transmissão na melhor qualidade possível para os mesmos. O principal foco da Tese é no algoritmo de controle de congestionamento do SAM, que foi denominado ALM (Adaptive Layered Multicast). O algoritmo ALM tem como objetivo inferir o nível de congestionamento existente na rede, determinando a quantidade de camadas que o receptor pode suportar, de forma que a quantidade de banda recebida gere um tráfego na rede que seja eqüitativo com outros tráfegos ALM concorrentes, ou outros tráfegos TCP concorrentes. Como se trata de transmissões multimídia, é desejável que a recepção do sinal seja estável, ou seja, sem muitas variações de qualidade, entretanto, o tráfego TCP concorrente é muito agressivo, dificultando a criação de um algoritmo estável. Dessa forma, desenvolveu-se dois algoritmos que formam o núcleo desta Tese: o ALMP (voltado para redes privativas), e o ALMTF (destinado a concorrer com tráfego TCP). Os elementos internos da rede, tais como os roteadores, não necessitam quaisquer modificações, e o protocolo funciona sobre a Internet atual. Para validar o método, se utilizou o software NS2 (Network Simulator), com modificações no código onde requerido. Além disso, efetuou-se uma implementação inicial para comparar os resultados das simulações com os da implementação real. Em http://www.inf.unisinos.br/~roesler/tese e também no CD anexo a esta Tese, cuja descrição encontra-se no Anexo B, podem ser encontrados todos os programas de apoio desenvolvidos para esta Tese, bem como a maior parte da bibliografia utilizada, o resultado das simulações, o código dos algoritmos no simulador e o código do algoritmo na implementação real.

Desenvolvimento de um plano agregado de produção para um sistema agroindustrial

Esta dissertação traz como tema principal o planejamento da produção, com enfoque no planejamento agregado da produção. Tal planejamento de longo prazo é o elo entre a alta administração da empresa e a manufatura. Através dele, as metas estratégicas da empresa são comunicadas por meio de uma linguagem comum ao corpo tático/operacional, visando coordenar os esforços e buscar comprometimento para o alcance das metas. O desenvolvimento de um plano agregado de produção é concretizado através do uso de algoritmos de pesquisa operacional, visando otimizar o sistema, considerando-se os fatores restritivos. O planejamento agregado da produção definirá o grau de utilização dos recursos de produção e servirá de base para elaboração dos planejamentos de produção mais detalhados, que definirão como melhor utilizar os recursos disponibilizados num horizonte de planejamento mais curto e sob menores incertezas de mercado. Esta dissertação traz como aplicação prática a modelagem de um plano agregado de produção para uma agroindústria de grande porte e diversas plantas produtoras, no segmento de produtos suínos.

Um estudo sobre curvas NURBS

O objetivo primordial desse trabalho está concentrado no estudo de Curvas NURBS (B-spline Racional N˜ao-Uniforme). A literatura em português sobre NURBS é escassa, pouco difundida e os textos e artigos existentes tendem a ser rigorosos, longos e teóricos. Assim, o presente estudo está direcionado para os conceitos matemáticos de NURBS, para o qual foi utilizado uma ferramenta chamada DesignMentor com a finalidade de testar os algoritmos desses conceitos. NURBS são funções paramétricas que podem representar qualquer tipo de curva. NURBS são usadas em computação gráfica na indústria de CAD/CAM e estão sendo consideradas um padrão para criar e representar objetos complexos (indústria automobilística, aviação e embarcação). As ferramentas de criação gráfica mais sofisticadas provêem uma interface para usar NURBS, que são flexíveis suficiente para projetar uma grande variedade de formas. Hoje é possível verificar o uso expandido de NURBS, modelando objetos para as artes visuais, arte e escultura; também estão sendo usados para modelar cenas para aplicações de realidade virtual. NURBS trabalha bem em modelagem 3D, permitindo facilidade para manipular e controlar vértices, controlar curvatura e suavidade de contornos. NURBS provêm uma base matemática, unificada para representar formas analíticas e livres além de manter exatidão e independência de resolução matemática.