Sistema de multiprocessamento para simulação de N-corpos em FPGA

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Framework de controlo de acessos para Triple-stores com interface Sail API

Grande parte dos triples-stores são open source e desenvolvidos em Java, disponibilizando interfaces standards e privadas de acesso. A grande maioria destes sistemas não dispõe de mecanismos de controlo de acessos nativos, o que dificulta ou impossibilita a sua adopção em ambientes em que a segurança dos factos é importante (e.g. ambiente empresarial). Complementarmente observa-se que o modelo de controlo de acesso a triplos e em particular a triplos descritos por ontologias não está standardizado nem sequer estabilizado, havendo diversos modelos de descrição e algoritmos de avaliação de permissões de acesso. O trabalho desenvolvido nesta tese/dissertação propõe um modelo e interface de controlo de acesso que permite e facilite a sua adopção por diferentes triple-stores já existentes e a integração dos triples-stores com outros sistemas já existentes na organização. Complementarmente, a plataforma de controlo de acesso não impõe qualquer modelo ou algoritmo de avaliação de permissões, mas pelo contrário permite a adopção de modelos e algoritmos distintos em função das necessidades ou desejos. Finalmente demonstra-se a aplicabilidade e validade do modelo e interface propostos, através da sua implementação e adopção ao triple-store SwiftOWLIM já existente, que não dispõe de mecanismo de controlo de acessos nativo.

Extracção de regras de associação com itens raros e frequentes

Ao longo dos últimos anos, as regras de associação têm assumido um papel relevante na extracção de informação e de conhecimento em base de dados e vêm com isso auxiliar o processo de tomada de decisão. A maioria dos trabalhos de investigação desenvolvidos sobre regras de associação têm por base o modelo de suporte e confiança. Este modelo permite obter regras de associação que envolvem particularmente conjuntos de itens frequentes. Contudo, nos últimos anos, tem-se explorado conjuntos de itens que surgem com menor frequência, designados de regras de associação raras ou infrequentes. Muitas das regras com base nestes itens têm particular interesse para o utilizador. Actualmente a investigação sobre regras de associação procuram incidir na geração do maior número possível de regras com interesse aglomerando itens raros e frequentes. Assim, este estudo foca, inicialmente, uma pesquisa sobre os principais algoritmos de data mining que abordam as regras de associação. A finalidade deste trabalho é examinar as técnicas e algoritmos de extracção de regras de associação já existentes, verificar as principais vantagens e desvantagens dos algoritmos na extracção de regras de associação e, por fim, desenvolver um algoritmo cujo objectivo é gerar regras de associação que envolvem itens raros e frequentes.

Adaptive learning in agents behaviour: a framework for electricity markets simulation

Electricity markets are complex environments with very particular characteristics. A critical issue regarding these specific characteristics concerns the constant changes they are subject to. This is a result of the electricity markets’ restructuring, which was performed so that the competitiveness could be increased, but it also had exponential implications in the increase of the complexity and unpredictability in those markets scope. The constant growth in markets unpredictability resulted in an amplified need for market intervenient entities in foreseeing market behaviour. The need for understanding the market mechanisms and how the involved players’ interaction affects the outcomes of the markets, contributed to the growth of usage of simulation tools. Multi-agent based software is particularly well fitted to analyze dynamic and adaptive systems with complex interactions among its constituents, such as electricity markets. This dissertation presents ALBidS – Adaptive Learning strategic Bidding System, a multiagent system created to provide decision support to market negotiating players. This system is integrated with the MASCEM electricity market simulator, so that its advantage in supporting a market player can be tested using cases based on real markets’ data. ALBidS considers several different methodologies based on very distinct approaches, to provide alternative suggestions of which are the best actions for the supported player to perform. The approach chosen as the players’ actual action is selected by the employment of reinforcement learning algorithms, which for each different situation, simulation circumstances and context, decides which proposed action is the one with higher possibility of achieving the most success. Some of the considered approaches are supported by a mechanism that creates profiles of competitor players. These profiles are built accordingly to their observed past actions and reactions when faced with specific situations, such as success and failure. The system’s context awareness and simulation circumstances analysis, both in terms of results performance and execution time adaptation, are complementary mechanisms, which endow ALBidS with further adaptation and learning capabilities.

ECG denoising based on adaptive signal processing technique

An Electrocardiogram (ECG) monitoring system deals with several challenges related with noise sources. The main goal of this text was the study of Adaptive Signal Processing Algorithms for ECG noise reduction when applied to real signals. This document presents an adaptive ltering technique based on Least Mean Square (LMS) algorithm to remove the artefacts caused by electromyography (EMG) and power line noise into ECG signal. For this experiments it was used real noise signals, mainly to observe the di erence between real noise and simulated noise sources. It was obtained very good results due to the ability of noise removing that can be reached with this technique. A recolha de sinais electrocardiogr a cos (ECG) sofre de diversos problemas relacionados com ru dos. O objectivo deste trabalho foi o estudo de algoritmos adaptativos para processamento digital de sinal, para redu c~ao de ru do em sinais ECG reais. Este texto apresenta uma t ecnica de redu c~ao de ru do baseada no algoritmo Least Mean Square (LMS) para remo c~ao de ru dos causados quer pela actividade muscular (EMG) quer por ru dos causados pela rede de energia el ectrica. Para as experiencias foram utilizados ru dos reais, principalmente para aferir a diferen ca de performance do algoritmo entre os sinais reais e os simulados. Foram conseguidos bons resultados, essencialmente devido as excelentes caracter sticas que esta t ecnica tem para remover ru dos.

Desenvolvimento de um pedómetro para telemóvel

Esta tese descreve o desenvolvimento do hardware e do software de um sistema com a capacidade de reconhecer o número de passos que uma pessoa efectua durante uma actividade física. O sistema consiste num acelerómetro controlado por um microcontrolador, que comunica com um dispositivo móvel através de Bluetooth. De modo a realizar o sistema foi necessário analisar uma vasta bibliografia, para conhecer o estado da arte desta tecnologia, entender o princípio de funcionamento do protocolo Bluetooth e os conceitos biomecânicos por detrás da marcha humana. A proposta deste trabalho apresentava como elemento diferenciador do estado da arte o uso de um acelerómetro em conjunto com sensores de pressão. Com a conjugação destes sensores pretendia-se aumentar a precisão de um equipamento que normalmente não é reconhecido por essa característica. Contudo, a indisponibilidade dos sensores de pressão levou a que o sistema só fosse constituído pelo acelerómetro. Embora, o sistema foi projectado considerando que os sensores de pressão serão incluídos num futuro desenvolvimento. Neste trabalho foram desenvolvidos dois algoritmos para detectar os passos que uma pessoa executa, com pé onde é colocado o sensor, quando caminha ou corre. Num dos testes realizados o algoritmo da “aceleração composta” detectou 84% dos passos, enquanto o algoritmo da “aceleração simples”detectou 99%. A plataforma para a interface gráfica pretendia-se que fosse um telemóvel, contudo não foi possível obter um telemóvel que suporta-se o perfil SPP (Serial Port Profile), necessário para a comunicação com o módulo Bluetooth usado. A solução passou por usar como plataforma um computador portátil com Bluetooth, para o qual foi desenvolvido a aplicação “Pedómetro ISEP” em Visual Basic. O “Pedómetro ISEP” apresenta várias funcionalidades, entre elas destaca-se o cálculo da distância percorrida, da velocidade, e das calorias consumidas, bem como, o registo desses valores em tabelas e da possibilidade de desenhar os gráficos representativos do progresso do utilizador.

Detecção e seguimento de objectos em imagens termográficas: análise experimental de modelos de descrição

A instalação de sistemas de videovigilância, no interior ou exterior, em locais como aeroportos, centros comerciais, escritórios, edifícios estatais, bases militares ou casas privadas tem o intuito de auxiliar na tarefa de monitorização do local contra eventuais intrusos. Com estes sistemas é possível realizar a detecção e o seguimento das pessoas que se encontram no ambiente local, tornando a monitorização mais eficiente. Neste contexto, as imagens típicas (imagem natural e imagem infravermelha) são utilizadas para extrair informação dos objectos detectados e que irão ser seguidos. Contudo, as imagens convencionais são afectadas por condições ambientais adversas como o nível de luminosidade existente no local (luzes muito fortes ou escuridão total), a presença de chuva, de nevoeiro ou de fumo que dificultam a tarefa de monitorização das pessoas. Deste modo, tornou‐se necessário realizar estudos e apresentar soluções que aumentem a eficácia dos sistemas de videovigilância quando sujeitos a condições ambientais adversas, ou seja, em ambientes não controlados, sendo uma das soluções a utilização de imagens termográficas nos sistemas de videovigilância. Neste documento são apresentadas algumas das características das câmaras e imagens termográficas, assim como uma caracterização de cenários de vigilância. Em seguida, são apresentados resultados provenientes de um algoritmo que permite realizar a segmentação de pessoas utilizando imagens termográficas. O maior foco desta dissertação foi na análise dos modelos de descrição (Histograma de Cor, HOG, SIFT, SURF) para determinar o desempenho dos modelos em três casos: distinguir entre uma pessoa e um carro; distinguir entre duas pessoas distintas e determinar que é a mesma pessoa ao longo de uma sequência. De uma forma sucinta pretendeu‐se, com este estudo, contribuir para uma melhoria dos algoritmos de detecção e seguimento de objectos em sequências de vídeo de imagens termográficas. No final, através de uma análise dos resultados provenientes dos modelos de descrição, serão retiradas conclusões que servirão de indicação sobre qual o modelo que melhor permite discriminar entre objectos nas imagens termográficas.

A multiplicação de dois números segundo o algoritmo de Karatsuba

Em tempos que já lá vão, aprendemos um algoritmo para multiplicar números. Talvez o nosso professor não o designasse “algoritmo” para não nos assustar, mas, independentemente da formalidade do nome, aprendemos um conjunto bem definido de regras para executar a operação da multiplicação. Este artigo descreve este algoritmo e o algoritmo inventado pelo matemático russo Anatoly Alexeevitch Karatsuba (1937–2008).

Supporting intra-task parallelism in real-time multiprocessor systems

Os sistemas de tempo real modernos geram, cada vez mais, cargas computacionais pesadas e dinâmicas, começando-se a tornar pouco expectável que sejam implementados em sistemas uniprocessador. Na verdade, a mudança de sistemas com um único processador para sistemas multi- processador pode ser vista, tanto no domínio geral, como no de sistemas embebidos, como uma forma eficiente, em termos energéticos, de melhorar a performance das aplicações. Simultaneamente, a proliferação das plataformas multi-processador transformaram a programação paralela num tópico de elevado interesse, levando o paralelismo dinâmico a ganhar rapidamente popularidade como um modelo de programação. A ideia, por detrás deste modelo, é encorajar os programadores a exporem todas as oportunidades de paralelismo através da simples indicação de potenciais regiões paralelas dentro das aplicações. Todas estas anotações são encaradas pelo sistema unicamente como sugestões, podendo estas serem ignoradas e substituídas, por construtores sequenciais equivalentes, pela própria linguagem. Assim, o modo como a computação é na realidade subdividida, e mapeada nos vários processadores, é da responsabilidade do compilador e do sistema computacional subjacente. Ao retirar este fardo do programador, a complexidade da programação é consideravelmente reduzida, o que normalmente se traduz num aumento de produtividade. Todavia, se o mecanismo de escalonamento subjacente não for simples e rápido, de modo a manter o overhead geral em níveis reduzidos, os benefícios da geração de um paralelismo com uma granularidade tão fina serão meramente hipotéticos. Nesta perspetiva de escalonamento, os algoritmos que empregam uma política de workstealing são cada vez mais populares, com uma eficiência comprovada em termos de tempo, espaço e necessidades de comunicação. Contudo, estes algoritmos não contemplam restrições temporais, nem outra qualquer forma de atribuição de prioridades às tarefas, o que impossibilita que sejam diretamente aplicados a sistemas de tempo real. Além disso, são tradicionalmente implementados no runtime da linguagem, criando assim um sistema de escalonamento com dois níveis, onde a previsibilidade, essencial a um sistema de tempo real, não pode ser assegurada. Nesta tese, é descrita a forma como a abordagem de work-stealing pode ser resenhada para cumprir os requisitos de tempo real, mantendo, ao mesmo tempo, os seus princípios fundamentais que tão bons resultados têm demonstrado. Muito resumidamente, a única fila de gestão de processos convencional (deque) é substituída por uma fila de deques, ordenada de forma crescente por prioridade das tarefas. De seguida, aplicamos por cima o conhecido algoritmo de escalonamento dinâmico G-EDF, misturamos as regras de ambos, e assim nasce a nossa proposta: o algoritmo de escalonamento RTWS. Tirando partido da modularidade oferecida pelo escalonador do Linux, o RTWS é adicionado como uma nova classe de escalonamento, de forma a avaliar na prática se o algoritmo proposto é viável, ou seja, se garante a eficiência e escalonabilidade desejadas. Modificar o núcleo do Linux é uma tarefa complicada, devido à complexidade das suas funções internas e às fortes interdependências entre os vários subsistemas. Não obstante, um dos objetivos desta tese era ter a certeza que o RTWS é mais do que um conceito interessante. Assim, uma parte significativa deste documento é dedicada à discussão sobre a implementação do RTWS e à exposição de situações problemáticas, muitas delas não consideradas em teoria, como é o caso do desfasamento entre vários mecanismo de sincronização. Os resultados experimentais mostram que o RTWS, em comparação com outro trabalho prático de escalonamento dinâmico de tarefas com restrições temporais, reduz significativamente o overhead de escalonamento através de um controlo de migrações, e mudanças de contexto, eficiente e escalável (pelo menos até 8 CPUs), ao mesmo tempo que alcança um bom balanceamento dinâmico da carga do sistema, até mesmo de uma forma não custosa. Contudo, durante a avaliação realizada foi detetada uma falha na implementação do RTWS, pela forma como facilmente desiste de roubar trabalho, o que origina períodos de inatividade, no CPU em questão, quando a utilização geral do sistema é baixa. Embora o trabalho realizado se tenha focado em manter o custo de escalonamento baixo e em alcançar boa localidade dos dados, a escalonabilidade do sistema nunca foi negligenciada. Na verdade, o algoritmo de escalonamento proposto provou ser bastante robusto, não falhando qualquer meta temporal nas experiências realizadas. Portanto, podemos afirmar que alguma inversão de prioridades, causada pela sub-política de roubo BAS, não compromete os objetivos de escalonabilidade, e até ajuda a reduzir a contenção nas estruturas de dados. Mesmo assim, o RTWS também suporta uma sub-política de roubo determinística: PAS. A avaliação experimental, porém, não ajudou a ter uma noção clara do impacto de uma e de outra. No entanto, de uma maneira geral, podemos concluir que o RTWS é uma solução promissora para um escalonamento eficiente de tarefas paralelas com restrições temporais.

Análise e síntese de música através de sistemas computacionais

Este trabalho, realizado no âmbito da unidade curricular de Tese/Dissertação, procura mostrar de que forma a Computação Evolucionária se pode aplicar no mundo da Música. Este é, de resto, um tema sobejamente aliciante dentro da área da Inteligência Artificial. Começa-se por apresentar o mundo da Música com uma perspetiva cronológica da sua história, dando especial relevo ao estilo musical do Fado de Coimbra. Abordam-se também os conceitos fundamentais da teoria musical. Relativamente à Computação Evolucionária, expõem-se os elementos associados aos Algoritmos Evolucionários e apresentam-se os principais modelos, nomeadamente os Algoritmos Genéticos. Ainda no âmbito da Computação Evolucionária, foi elaborado um pequeno estudo do “estado da arte” da aplicação da Computação Evolucionária na Música. A implementação prática deste trabalho baseia-se numa aplicação – AG Fado – que compõe melodias de Fado de Coimbra, utilizando Algoritmos Genéticos. O trabalho foi dividido em duas partes principais: a primeira parte consiste na recolha de informações e posterior levantamento de dados estatísticos sobre o género musical escolhido, nomeadamente fados em tonalidade maior e fados em tonalidade menor; a segunda parte consiste no desenvolvimento da aplicação, com a conceção do respetivo algoritmo genético para composição de melodias. As melodias obtidas através da aplicação desenvolvida são bastante audíveis e boas melodicamente. No entanto, destaca-se o facto de a avaliação ser efetuada por seres humanos o que implica sensibilidades musicais distintas levando a resultados igualmente distintos.

Detecção de sectores cruzados e optimização de cobertura em redes LTE

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Estudo e proposta de algoritmo para a minimização do corte de eólica no contexto de uma análise custo-benefício multicritério

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Many-core approach to 2D-DCT calculation using an FPGA

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Sistema de visão para aterragem automática de UAV

Dissertação para obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Automação e Electrónica Industrial

Problemas de programação matemática com restrições lineares de equilíbrio

Neste trabalho é desenvolvido um algoritmo enumerativo paramétrico de optimização global para a resolução de Problemas de Programação Matemática com Restrições de Equilíbrio ou de Complementaridade (MPEC). A comparação com outras técnicas globais da literatura é efectuada para um leque variado de problemas, de modo a poder avaliar a eficiência do processo proposto. A utilização de algoritmos de MPEC para a resolução de alguns problemas de optimização global é o outro grande objectivo desta tese. Nesse sentido são introduzidas novas formula¸c˜oes de programas bilineares e lineares complementares como MPECs. São ainda analisadas e discutidas formulaçõess MPEC para o problema de programação linear inteira 0-1, para a determinação do Conjunto Independente Máximo de um Grafo (MIS) e para a estimação do Número de Condição de uma Matriz. Para o problema MIS é desenvolvido um algoritmo de ramificação e limitação, baseado na decomposição de uma função quadrática numa diferença de duas funçõess convexas (DC). Finalmente é introduzida uma técnica MPEC local para a estimação do número de condição com a norma l1 e é estabelecido para matrizes de Minkowski que o número de condição nessa norma pode ser estimado com apenas um sistema de equações lineares. Em todos os desenvolvimentos houve uma grande preocupação em testar as novas formulações e algoritmos com problemas conhecidos da literatura, de modo a aferir da qualidade e interesse dessas propostas.