Avaliação da compressão de dados e da qualidade de imagem em modelos de animação gráfica para web : uma nova abordagem baseada em complexidade de Kolmogorov

Este trabalho versa sobre a avaliação da compressão de dados e da qualidade de imagens e animações usando-se complexidade de Kolmogorov, simulação de máquinas e distância de informação. Complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade baseada na máquina de Turing. No trabalho é proposto um método para avaliar a compressão de dados de modelos de animação gráfica usando-se simulação de máquinas. Também definimos formalmente compressão de dados com perdas e propomos a aplicação da distância de informação como uma métrica de qualidade de imagem. O desenvolvimento de uma metodologia para avaliar a compressão de dados de modelos de animação gráfica para web é útil, a medida que as páginas na web estão sendo cada vez mais enriquecidas com animações, som e vídeo, e a economia de banda de canal tornase importante, pois os arquivos envolvidos são geralmente grandes. Boa parte do apelo e das vantagens da web em aplicações como, por exemplo, educação à distância ou publicidade, reside exatamente na existência de elementos multimídia, que apoiam a idéia que está sendo apresentada na página. Como estudo de caso, o método de comparação e avaliação de modelos de animação gráfica foi aplicado na comparação de dois modelos: GIF (Graphics Interchange Format) e AGA (Animação Gráfica baseada em Autômatos finitos), provando formalmente que AGA é melhor que GIF (“melhor” significa que AGA comprime mais as animações que GIF). Foi desenvolvida também uma definição formal de compressão de dados com perdas com o objetivo de estender a metodologia de avalição apresentada Distância de informação é proposta como uma nova métrica de qualidade de imagem, e tem como grande vantagem ser uma medida universal, ou seja, capaz de incorporar toda e qualquer medida computável concebível. A métrica proposta foi testada em uma série de experimentos e comparada com a distância euclidiana (medida tradicionalmente usada nestes casos). Os resultados dos testes são uma evidência prática que a distância proposta é efetiva neste novo contexto de aplicação, e que apresenta, em alguns casos, resultados superiores ao da distância euclidiana. Isto também é uma evidência que a distância de informação é uma métrica mais fina que a distância euclidiana. Também mostramos que há casos em que podemos aplicar a distância de informação, mas não podemos aplicar a distância euclidiana. A métrica proposta foi aplicada também na avaliação de animações gráficas baseadas em frames, onde apresentou resultados melhores que os obtidos com imagens puras. Este tipo de avaliação de animações é inédita na literatura, segundo revisão bibliográfica feita. Finalmente, neste trabalho é apresentado um refinamento à medida proposta que apresentou resultados melhores que a aplicação simples e direta da distância de informação.

Uma Proposta de distribuição do servidor de arquivos em clusters

A evolução da Computação Baseada em Clusters, impulsionada pelo avanço tecnológico e pelo custo relativamente baixo do hardware de PCs, tem levado ao surgimento de máquinas paralelas de porte cada vez maior, chegando à ordem das centenas e mesmo milhares de nós de processamento. Um dos principais problemas na implantação de clusters desse porte é o gerenciamento de E/S, pois soluções centralizadas de armazenamento de arquivos, como o NFS, rapidamente se tornam o gargalo dessa parte do sistema. Ao longo dos últimos anos, diversas soluções para esse problema têm sido propostas, tanto pela utilização de tecnologias especializadas de armazenamento e comunicação, como RAID e fibra ótica, como pela distribuição das funcionalidades do servidor de arquivos entre várias máquinas, objetivando a paralelização de suas operações. Seguindo essa última linha, o projeto NFSP (NFS Parallèle) é uma proposta de sistema de arquivos distribuído que estende o NFS padrão de forma a aumentar o desempenho das operações de leitura de dados pela distribuição do serviço em vários nós do cluster. Com essa abordagem, o NFSP objetiva aliar desempenho e escalabilidade aos benefícios do NFS, como a estabilidade de sua implementação e familiaridade de usuários e administradores com sua semântica de uso e seus procedimentos de configuração e gerenciamento. A proposta aqui apresentada, chamada de dNFSP, é uma extensão ao NFSP com o objetivo principal de proporcionar melhor desempenho a aplicações que explorem tanto a leitura como a escrita de dados, uma vez que essa última característica não é contemplada pelo modelo original A base para o funcionamento do sistema é um modelo de gerenciamento distribuído de meta-dados, que permite melhor escalabilidade e reduz o custo computacional sobre o meta-servidor original do NFSP, e também um mecanismo relaxado de manutenção de coerência baseado em LRC (Lazy Release Consistency), o qual permite a distribuição do serviço sem acarretar em operações onerosas de sincronização de dados. Um protótipo do modelo dNFSP foi implementado e avaliado com uma série de testes, benchmarks e aplicações. Os resultados obtidos comprovam que o modelo pode ser aplicado como sistema de arquivos para um cluster, efetivamente proporcionando melhor desempenho às aplicações e ao mesmo tempo mantendo um elevado nível de compatibilidade com as ferramentas e procedimentos habituais de administração de um cluster, em especial o uso de clientes NFS padrões disponíveis em praticamente todos os sistemas operacionais da atualidade.

Modelo de adaptação de ensino utilizando agentes pedagógicos

A Inteligência Artificial é uma área da computação onde se está constantemente desenvolvendo pesquisas em software educacionais, principalmente os Sistemas Tutores Inteligentes (STI). Esses sistemas têm a capacidade de se adaptarem às particularidades de cada aluno, proporcionando assim, ambientes que facilitam a aprendizagem do usuário. Recentemente foi incorporada a tecnologia de agentes na modelagem do STI e nos ambientes educacionais na Internet. Estes agentes são denominados pedagógicos quando estão ligados a um ambiente onde existe uma sociedade de agentes que compõem um sistema de ensino-aprendizagem. Este texto apresenta um modelo de adaptação para ambientes genéricos de ensino, composto por agentes pedagógicos. A proposta é baseada em estudos relacionados com sistemas hipermídia adaptativos, sistemas tutores inteligentes, sistemas multiagentes e agentes pedagógicos. Inicialmente, o texto descreve o modelo. Logo após, é apresentada a implementação dos agentes os quais tem como tarefa prover a adaptação do ensino, sendo responsáveis em fornecer o caminho mais efetivo para a aprendizagem do aluno. Os agentes do modelo são denominados Agente Tutor, Agente Perfil e Agente de Comunicação. A realização da adaptação da instrução às características individuais do aprendiz implica o sistema conhecer: os padrões cognitivos de aprendizagem do aluno, traduzidos como estilos de aprendizagem e as suas implicações pedagógicas; e a modelagem das características do aprendiz: nível de conhecimento, metas, experiência e preferências do aprendiz. Finalmente, o texto descreve um estudo de caso, onde o modelo proposto foi integrado num ambiente de aprendizagem, e validado numa disciplina virtual a fim de avaliação de seus objetivos.

Análise da complexidade computacional de problemas de estatística descritiva com entradas intervalares

A Estatística é uma ferramenta indispensável em todos os campos científicos. A Estatística descritiva é usada para sintetizar dados. O principal problema desta área está relacionado aos valores de uma amostra, os quais geralmente possuem erros que ocorrem durante a obtenção dos dados. Um dos objetivos deste trabalho é apresentar uma forma de representação para os valores amostrais que considera os erros contidos nestes valores. Esta representação é realizada através de intervalos. A literatura mostra que foram realizadas pesquisas somente em problemas de calcular os valores intervalares das medidas de dispersão variância, covariância e coeficiente de correlação, que a utilização da computação intervalar na solução de problemas de medidas de dispersão intervalar sempre fornece solução com intervalos superestimados (intervalos com amplitude grande), e que ao procurar uma solução com intervalos de amplitude pequena (através da computação da imagem intervalar), o problema passa a pertencer a classe de problemas NP-Difícil. Com o objetivo principal de analisar a complexidade computacional dos problemas de computar os valores dos indicadores estatísticos descritivos com entradas intervalares, e realizar uma classificação quanto a classe de complexidade, a presente tese apresenta: i) definições intervalares de medidas de tendência central, medidas de dispersão e separatrizes; ii) investigação da complexidade de problemas das medidas de tendência central média, mediana e moda, das medidas de dispersão amplitude, variância, desvio padrão, coeficiente de variação, covariância, coeficiente de correlação e das separatrizes e iii) representação intervalar dos valores reais, de tal modo que garante a qualidade de aproximação nos intervalos solução calculado através da extensão intervalar Primeiramente, apresentamos uma abordagem intervalar para os indicadores estatísticos e propomos algoritmos para a solução dos problemas de computar os intervalos de medidas de tendência central intervalar, dispersão intervalar e separatrizes intervalares. Tais algoritmos utilizam a aritmética intervalar definida por Moore, a extensão intervalar e foram projetados para serem executados em ambientes intervalares como IntLab e Maple Intervalar. Por meio da análise da complexidade computacional verificamos que os problemas de medidas de tendência central, dispersão e separatrizes, com entradas intervalares, pertencem à classe de problemas P. Este trabalho apresenta, portanto, algoritmos de tempo polinomial que calculam os intervalos dos indicadores estatísticos com entradas intervalares, e que retornam como solução intervalos com qualidade de aproximação. Os resultados obtidos no desenvolvimento do trabalho tornaram viável a computação da Estatística Descritiva Intervalar.

Using an animated pedagogical agent to interact affectively with the student

This work proposes an animated pedagogical agent that has the role of providing emotional support to the student: motivating and encouraging him, making him believe in his self-ability, and promoting a positive mood in him, which fosters learning. This careful support of the agent, its affective tactics, is expressed through emotional behaviour and encouragement messages of the lifelike character. Due to human social tendency of anthropomorphising software, we believe that a software agent can accomplish this affective role. In order to choose the adequate affective tactics, the agent should also know the student’s emotions. The proposed agent recognises the student’s emotions: joy/distress, satisfaction/disappointment, anger/gratitude, and shame, from the student’s observable behaviour, i. e. his actions in the interface of the educational system. The inference of emotions is psychologically grounded on the cognitive theory of emotions. More specifically, we use the OCC model which is based on the cognitive approach of emotion and can be computationally implemented. Due to the dynamic nature of the student’s affective information, we adopted a BDI approach to implement the affective user model and the affective diagnosis. Besides, in our work we profit from the reasoning capacity of the BDI approach in order for the agent to deduce the student’s appraisal, which allows it to infer the student’s emotions. As a case study, the proposed agent is implemented as the Mediating Agent of MACES: an educational collaborative environment modelled as a multi-agent system and pedagogically based on the sociocultural theory of Vygotsky.

Estudo e desenvolvimento de um transdutor de posição linear magnética diferencial

Este trabalho tem como objetivo o estudo e o desenvolvimento de um transdutor magnético de posição, cujo princípio de funcionamento é baseado na relação entre a distribuição do fluxo magnético em sua estrutura, provido por uma fonte de fluxo magnético constante, c.c. ou c.a., e a posição linear da parte móvel do transdutor ao longo de sua direção de deslocamento ou excursão. O transdutor pode ter entreferros de medição para medir a indução magnética nas culatras laterais, com fluxo magnético de excitação constante, c.c. ou c.a., ou não ter entreferros de medição, caso em que apenas fluxo magnético de excitação c.a. é empregado. Em ambos os casos, com fluxo magnético de excitação c.a., bobinas exploradoras foram usadas para medir o fluxo magnético estabelecido nas culatras de acordo com a posição da parte móvel do transdutor. Para o primeiro caso foi desenvolvido um protótipo no qual o material das culatras é aço maciço. Para o segundo foram desenvolvidos dois protótipos, um com barra de aço maciça, e o outro com núcleo de lâminas de Fe-Si. Além de se desenvolver uma modelagem analítica para estudar o transdutor, empregou-se, como ferramenta auxiliar de simulação, uma modelagem eletromagnética por elementos finitos. Os resultados teóricos, simulados e experimentais são esclarecedores e demonstram que o transdutor confeccionado com lâminas de Fe-Si e excitação através de fluxo magnético c.a. apresenta uma saída linear. É demonstrado também que a metodologia proposta e utilizada na modelagem e na concepção do transdutor são adequadas e indicam o domínio da teoria e da tecnologia propostas. As configurações sugeridas são extensivamente analisadas por este trabalho No caso do transdutor com fluxo magnético c.a. proposto e resultante desse estudo, sua topologia pode ser considerada inovadora, não sofrendo um efeito de histerese no seu sinal de saída devido à histerese magnética de suas culatras ferromagnéticas como acontece no transdutor com fluxo magnético c.c.. Isso, entre outras razões, ensejou o depósito de sua patente. Adicionalmente, é robusto, de fácil confecção, com enrolamentos que não requerem uma montagem de precisão como em outros transdutores eletromagnéticos de posição, e de baixo custo.

Um Estudo de técnicas de aceleração para algoritmos de análise de timing funcional baseados em geração automática de teste

Este trabalho tem como objetivo estudar e avaliar técnicas para a aceleração de algoritmos de análise de timing funcional (FTA - Functional Timing Analysis) baseados em geração automática de testes (ATPG – Automatic Test Generation). Para tanto, são abordados três algoritmos conhecidos : algoritmo-D, o PODEM e o FAN. Após a análise dos algoritmos e o estudo de algumas técnicas de aceleração, é proposto o algoritmo DETA (Delay Enumeration-Based Timing Analysis) que determina o atraso crítico de circuitos que contêm portas complexas. O DETA está definido como um algoritmo baseado em ATPG com sensibilização concorrente de caminhos. Na implementação do algoritmo, foi possível validar o modelo de computação de atrasos para circuitos que contêm portas complexas utilizando a abordagem de macro-expansão implícita. Além disso, alguns resultados parciais demonstram que, para alguns circuitos, o DETA apresenta uma pequena dependência do número de entradas quando comparado com a dependência no procedimento de simulação. Desta forma, é possível evitar uma pesquisa extensa antes de se encontrar o teste e assim, obter sucesso na aplicação de métodos para aceleração do algoritmo.

Sistema Aldeia : programação paralela e distribuída em Java sobre Infiniband e DECK

Esse trabalho de dissertação está incluído no contexto das pesquisas realizadas no Grupo de Processamento Paralelo e Distribuído da UFRGS. Ele aborda as áreas da computação de alto desempenho, interfaces simples de programação e de sistemas de interconexão de redes velozes. A máquina paralela formada por agregados (clusters) tem se destacado por apresentar os recursos computacionais necessários às aplicações intensivas que necessitam de alto desempenho. Referente a interfaces de programação, Java tem se mostrado uma boa opção para a escrita de aplicações paralelas por oferecer os sistemas de RMI e de soquetes que realizam comunicação entre dois computadores, além de todas as facilidades da orientação a objetos. Na área a respeito de interconexão de rede velozes está emergindo como uma tentativa de padronização a nova tecnologia Infiniband. Ela proporciona uma baixa latência de comunicação e uma alta vazão de dados, além de uma série de vantagens implementadas diretamente no hardware. É neste contexto que se desenvolve o presente trabalho de dissertação de mestrado. O seu tema principal é o sistema Aldeia que reimplementa a interface bastante conhecida de soquetes Java para realizar comunicação assíncrona em agregados formados por redes de sistema. Em especial, o seu foco é redes configuradas com equipamentos Infiniband. O Aldeia objetiva assim preencher a lacuna de desempenho do sistema padrão de soquetes Java, que além de usar TCP/IP possui um caráter síncrono. Além de Infiniband, o Aldeia também procura usufruir dos avanços já realizados na biblioteca DECK, desenvolvida no GPPD da UFRGS. Com a sua adoção, é possível realizar comunicação com uma interface Java sobre redes Myrinet, SCI, além de TCP/IP. Somada a essa vantagem, a utilização do DECK também proporciona a propriedade de geração de rastros para a depuração de programas paralelos escritos com o Aldeia. Uma das grandes vantagens do Aldeia está na sua capacidade de transmitir dados assincronamente. Usando essa técnica, cálculos da aplicação podem ser realizados concorrentemente com as operações pela rede. Por fim, os canais de dados do Aldeia substituem perfeitamente aqueles utilizados para a serialização de objetos. Nesse mesmo caminho, o Aldeia pode ser integrado à sistemas que utilizem a implementação de soquetes Java, agora para operar sobre redes de alta velocidade. Palavras-chave: Arquitetura Infiniband, agregado de computadores, linguagem de programação Java, alto desempenho, interface de programação.

Dinodontosaurus (Synapsida, Dicynodontia) reconstituições morfológicas e aspectos biomecânicos

Dicinodontes possuem um mosaico de características, que incluem, por exemplo, extrema redução dentária, movimento propalinal da mandíbula, e o desenvolvimento de uma postura diferenciada em alguns gêneros. Nesses, enquanto os membros anteriores permanecem abduzidos, em uma postura primitiva, os posteriores se tornam totalmente aduzidos. Para discutir aspectos paleobiológicos, foram efetuadas análises morfofuncionais e biomecânicas em espécimes do gênero Dinodontosaurus Romer, 1943, um dicinodonte de porte médio do Mesotriássico do estado do Rio Grande do Sul, Brasil. É endossada a sinonímia da maioria das espécies do gênero com Dinodontosaurus turpior, excetuando-se Dinodontosaurus platygnathus, cujos materiais apresentam características conflitantes, e é tratado aqui como nomen dubium. É apresentada uma sucinta descrição osteológica para as formas juvenis do gênero, nos quais se observa a presença de seis vértebras sacrais, além de um mínimo de 17 caudais, adicionando informações que permitem novas reconstruções esqueletais. Enfoque é dado na miologia facial e dos membros, com base na comparação de modelos para diferentes taxa, seguindo a abordagem de suporte filogenético de animais viventes. Apenas músculos de presença inequívoca são reconstituídos, a menos quando há argumentos morfológicos convincentes. A partir de observações morfofuncionais, é eliminada a possibilidade de Dinodontosaurus utilizar suas presas com a mandíbula aberta, seja para alimentação ou defesa, e é reforçado seu caráter como ornamentação Na falta de análogos posturais modernos, comparações com preguiças terrícolas extintas levaram alguns autores a propostas de uma postura bípede para os dicinodontes, ao menos facultativa, para se erguerem nas patas traseiras e alcançarem níveis mais elevados de vegetação. Para testar essa hipótese, foram abordados vários aspectos biomecânicos envolvidos na postura bípede, em Dinodontosaurus. Seu centro de massa foi localizado a partir da suspensão de modelos em argila, estando posicionado em um ponto, no plano sagital, aproximadamente na metade da distância entre os estilopódios anteriores e posteriores, um pouco mais próximo dos primeiros; para os indivíduos juvenis, um modelo digital obtido através de scanner 3D a laser também corroborou esse posicionamento, o que sugere que a postura bípede não poderia ser facilmente mantida sem apoio, e um caminhar bípede seria totalmente impraticável. Foram estimados os momentos de resistência da coluna vertebral, a partir de medidas da largura e altura dos centros vertebrais em sua borda posterior, sendo que os resultados foram compatíveis com um animal de postura quadrúpede. Foram também calculados os índices de capacidade atlética para os ossos longos dos membros anteriores e posteriores; para isso, foram estimadas as massas, com os indivíduos juvenis atingindo entre 23 e 32kg, enquanto o adulto não ultrapassaria 300kg. As massas foram obtidas baseando-se em estimativas de volume a partir de silhuetas e de modelos tridimensionais em computação Os valores obtidos para os índices de capacidade atlética são muito superiores aos de outros animais descritos na literatura, embora sejam compatíveis com outros terápsidos não-mamalianos julgados quadrúpedes, e estão na mesma ordem de grandeza entre os ossos dos membros anteriores e posteriores, o que também alude à postura quadrúpede. Através de observações morfológicas gerais, localização do centro de massa, estimativa de momentos de resistência da coluna vertebral e cálculo de índices de capacidade atlética para os membros, conclui-se que, ao menos no que concerne a Dinodontosaurus, não há evidências que suportem as analogias morfofuncionais com as preguiças terrícolas, animais que apresentam diversas adaptações para o bipedalismo. Os resultados para os índices de capacidade atlética também lançam dúvidas sobre sua aplicabilidade generalizada em comparações paleobiológicas.

Identificação de nomes ativos em agentes-π baseada em tipos

Na última década muitos esforços têm sido feitos em verificação formal de propriedades de agentes do cálculo-π. Uma dessas propriedades é a equivalência observacional, que serve para determinar se um processo é equivalente a sua especificação. Contudo, a verificação de equivalência observacional não é um problema trivial. A maioria dos algoritmos destinados a verificação de equivalência são baseados na construção de sistemas de transições rotuladas (π-autômatos). O principal problema com essa abordagem é o grande número de estados envolvidos podendo chegar a um número infinito. Montanari e Pistore mostram que é possível gerar π-autômatos finitos para agentes-π e é possível reduzir a quantidade de estados desses π-autômatos, através da identificação dos nomes ativos. Um nome é semanticamente ativo em um agente se ele pode ser executado de forma observável por ele. Este é um trabalho de análise estática, que tem por objetivo coletar os possíveis nomes ativos contidos em expressões-π, utilizando para isso um sistema de tipos. A vantagem da utilização de sistemas de tipos em relação a outras formas de análise estática é que sistemas de tipos são sistemas lógicos, logo as técnicas de prova da lógica podem ser aproveitadas no estudo de propriedades de sistemas de tipos. Além disso sistemas de tipos são definidos através da estrutura sintática de expressões, facilitando assim as provas por indução estrutural. Assim a principal contribuição deste trabalho é a elaboração do Active-Base-π, um sistema de tipos para a coleta de nomes ativos de expressões-π.

Visualização interativa e manipulação de imagens 3D em tempo real usando métodos baseados na GPU

Este trabalho apresenta um conjunto de ferramentas que exploram as capacidades recentes das placas gráficas de computadores pessoais para prover a visualização e a interação com volumes de dados. O objetivo é oferecer ao usuário ferramentas que permitam a remoção interativa de partes não relevantes do volume. Assim, o usuário é capaz de selecionar um volume de interesse, o que pode tanto facilitar a compreensão da sua estrutura quanto a sua relação com os volumes circundantes. A técnica de visualização direta de volumes através do mapeamento de texturas é explorada para desenvolver estas ferramentas. O controle programável dos cálculos realizados pelo hardware gráfico para gerar a aparência de cada pixel na tela é usado para resolver a visibilidade de cada ponto do volume em tempo real. As ferramentas propostas permitem a modificação da visibilidade de cada ponto dentro do hardware gráfico, estendendo o benefício da visualização acelerada por hardware. Três ferramentas de interação são propostas: uma ferramenta de recorte planar que permite a seleção de um volume de interesse convexo; uma ferramenta do tipo “borracha”, para eliminar partes não relevantes da imagem; e uma ferramenta do tipo “escavadeira”, para remover camadas do volume Estas ferramentas exploram partes distintas do fluxo de visualização por texturas, onde é possível tomar a decisão sobre a visibilidade de cada ponto do volume. Cada ferramenta vem para resolver uma deficiência da ferramenta anterior. Com o recorte planar, o usuário aproxima grosseiramente o volume de interesse; com a borracha, ele refina o volume selecionado que, finalmente, é terminado com a escavadeira. Para aplicar as ferramentas propostas ao volume visualizado, são usadas técnicas de interação conhecidas, comuns nos sistemas de visualização 2D. Isto permite minimizar os esforços do usuário no treinamento do uso das ferramentas. Finalmente, são ilustradas as aplicações potenciais das ferramentas propostas para o estudo da anatomia do fígado humano. Nestas aplicações foi possível identificar algumas necessidades do usuário na visualização interativa de conjuntos de dados médicos. A partir destas observações, são propostas também novas ferramentas de interação, baseadas em modificações nas ferramentas propostas.