Teses e Dissertações

Autor(res):Eduardo Vieira Queiroga

Resumo:

Inicialmente, este trabalho aborda o relaxed correlation clustering (RCC), que é um problema NP-difícil de particionamento de vértices que busca minimizar o desequilíbrio relaxado em grafos de sinais, tendo aplicações em análise de redes sociais.  Para resolvê-lo, são propostas duas novas formulações de programação linear inteira e uma meta-heurística baseada em busca local. Esta última usa estruturas de dados auxiliares para realizar, de forma eficiente, avaliações de movimentos durante o processo de busca. Experimentos computacionais em instâncias existentes e em novas instâncias geradas demonstram a superioridade das abordagens propostas quando comparadas com métodos da literatura. Enquanto as abordagens exatas obtiveram soluções ótimas para instâncias em aberto, a meta-heurística proposta foi capaz de encontrar soluções de alta qualidade em tempo razoável de CPU.

A segunda parte deste trabalho é sobre o problema de roteamento de veículos com coleta na volta (VRPB, do inglês vehicle routing problem with backhauls), que é uma variante clássica de roteamento de veículos que considera dois tipos de clientes: entrega e coleta.  No VRPB, uma rota precisa visitar clientes de entrega antes de clientes de coleta. Para resolver o VRPB de forma exata, são propostos dois algoritmos do tipo branch-cut-and-price (BCP). O primeiro deles segue o modelo tradicional com apenas um subproblema de princing, enquanto o segundo explora o particionamento dos clientes em entrega e coleta e define dois subproblemas.  Experimentos computacionais mostram que os algoritmos de BCP são capazes de obter soluções ótimas, muitas delas sendo inéditas, para todas as instâncias da literatura, que possuem até 200 clientes. Foi observado que a abordagem com dois subproblemas de pricing é mais eficiente que a tradicional.

Além disso, novas instâncias com até 1000 clientes foram geradas para as quais bons limitantes foram encontrados.  Também foram avaliadas três meta-heurísticas efetivas, onde duas delas exploram, em níveis diferentes, informações específicas do problema.

A última parte deste trabalho propõe um Partial OPtimization Metaheuristic Under Special Intensification Conditions (POPMUSIC) para o clássico problema de roteamento de veículos capacitado (CVRP). A abordagem proposta usa um algoritmo de BCP como uma heurística para resolver subproblemas com dimensões que geralmente variam entre 25 e 200 clientes. Experimentos foram realizados em instâncias tendo entre 302 e 1000 clientes. Partindo de soluções iniciais obtidas por algumas das melhores meta-heurísticas da literatura, o POPMUSIC foi capaz de obter consistentemente melhores soluções para execuções longas de até 32 horas. Ao começar da melhor solução disponível na CVRP library, o POPMUSIC foi capaz de encontrar novas melhores soluções para várias instâncias, incluindo algumas muito grandes. Em um experimento final, o POPMUSIC foi aplicado com sucesso para o VRP com frota heterogênea e o VRPB.

Palavras-chave: Correlação de Clusters Relaxado; Roteamento de Veículos com Coleta na Volta; Roteamento de Veículos Capacitado; POPMUSIC.

Autor(res):Luan Teylo Gouveia Lima

Resumo:

Os principais provedores de nuvens computacionais oferecem diversos tipos de máquinas virtuais (MVs) em distintos modelos de contratação, com diferentes garantias e graus de confiabilidade, dos quais os mais populares são o sob demanda (on-demand) e o spot. As MVs on-demand são alocadas por um custo fixo por unidade de tempo, e sua disponibilidade é garantida pelo provedor durante toda a execução da aplicação. Já as instâncias spot são oferecidas com um grande desconto monetário, quando comparadas com as on-demand. Contudo, tanto a disponibilidade quanto a confiabilidade variam de acordo com a demanda de recursos enfrentada pelo provedor. Ademais, as instâncias spot podem ser encerradas ou hibernadas a qualquer momento, caso o provedor necessite de seus recursos computacionais.

Em novembro de 2017, a Amazon Web Services (AWS) introduziu o recurso de hibernação em MVs spot. Agora, em vez de encerrar as MVs, o provedor pode hiberná-las temporariamente. Nesta tese, estamos interessados na execução  aplicações Bag-of-Tasks sujeitas a um deadline. Assim, propomos o Hibernation Aware Dynamic Scheduler (HADS), um framework modular e leve que pode ser facilmente atualizado para atender a novos requisitos. O HADS inclui uma série de funções integradas, como balanceamento de cargas (por meio de um procedimento de work-stealing), checkpoint nativo e procedimentos de migração e recuperação de tarefas. Ao contrário de outros frameworks que lidam com a rescisão/revogação de MVs spot, o HADS explora o recurso de hibernação dessas máquinas para minimizar os custos monetários de execução, gerenciando todo o ciclo de vida da aplicação.

Além dos modelos de contratação, os provedores de nuvem  introduziram recentemente o conceito de MVs  burstable. Essas MVs lidam com as variações da carga de trabalho das aplicações,  aumentando  a sua capacidade de processamento durante um período limitado de tempo. As MVs burstable são oferecidas no mercado on-demand com um grande desconto em comparação a MVs com poder de processamento equivalente. Assim, neste trabalho, também apresentamos o Burst-HADS, uma extensão do HADS que explora instâncias burstable para minimizar o tempo total de execução da aplicação. O Burst-HADS é um framework multi-objetivo que minimiza o custo monetário da execução e o tempo de execução das aplicações. Portanto, esta tese apresenta o HADS e Burst-HADS e todos os estudos realizados ao longo do seu desenvolvimento.

Palavras-chave: Computação em Nuvem;  Escalonamento; Máquinas spot; Checkpoint.

Autor(res):João Felipe Nicolaci Pimentel

Resumo:

O crescimento das cidades demandam regulamentações na utilização de espaços urbanos, em especial a definição de regras de zoneamento urbano, que são as regras de uso de cada pedaço de terra da cidade. Observar a evolução do uso do solo e das regras de zoneamento pode revelar ricas informações sobre o desenvolvimento urbano. Por esse motivo, cidades têm disponibilizado conjuntos de dados que descrevem a evolução histórica de atributos e geometria de seus terrenos. A natureza espaço-temporal desses dados, tornam as análises desafiadoras em especial pela complexidade da componente espacial. Neste trabalho, propomos o Urban Chronicles, um sistema de análise visual que permite a exploração interativa das mudanças nos padrões de uso do solo. Para demonstrar a capacidade analítica do sistema, utilizamos os dados de uso do solo da cidade de Nova Iorque – Primary Land Use Tax Lot Output (PLUTO), e realizamos análises que consideram diferentes escalas geográficas e de tempo. Urban Chronicles possibilita agregações em tempo de execução, assim como operações de filtragem dos terrenos, utilizando uma estrutura de dados baseada em árvore para indexar atributos e as formas dos terrenos que sofrem alterações ao longo tempo. A avaliação do sistema é realizada através de estudos de casos que analisam os impactos do furacão Sandy em bairros de Nova Iorque, assim como os efeitos de um plano de zoneamento proposto para uma região do Brooklyn.

Palavras-chave: Visualização; Análise de dados; Dados urbanos; Planejamento urbano.

Autor(res):Vinicius Corrêa Ferreira

Resumo:

A fim de explorar plenamente os benefícios das tecnologias sem fio na telemedicina, um novo tipo de rede sem fio emergiu: as redes corporais sem fio ou as Wireless Body Area Networks (WBANs). No entanto, desafios técnicos e sociais devem ser tratados para permitir sua adoção prática. Alguns desses desafios já são conhecidos de outros cenários, como os requisitos de operação para uma rede sem fio, a eficiência energética, os poucos recursos computacionais e a composição heterogênea da rede. Alguns fatores como o uso do corpo humano como meio de propagação, os efeitos da radiação no tecido humano e variações na movimentação do corpo fazem das redes corporais sem fio um novo paradigma de redes de comunicação sem fio. A eficiência na comunicação é essencial, principalmente em cenários de saúde. Para atingir os requisitos das aplicações em WBANs, enquanto preserva a eficiência energética e diretrizes de segurança física do usuário destas redes, este trabalho propõe um mecanismo de suporte ao agendamento de transmissões baseado na movimentação do corpo humano. Uma avaliação de cenários típicos de movimentos do corpo, como estar parado, caminhando, correndo, embasam o escalonamento e agendamento de transmissões para a comunicação dos nós da rede. Em cenários de mobilidade periódica, o mecanismo proposto obteve desempenho até 25% superior na taxa de entrega de pacotes se comparado ao CSMA/CA, mecanismo de acesso aleatório, e 20% superior ao TDMA, agendamento sem a ciência do movimento. O mecanismo também melhora a eficiência energética. Uma redução de 20% na energia gasta para transmitir um bit de aplicação foi observada quando comparado com CSMA/CA e uma redução de 17% quando comparado com TDMA. Em cenários com mudanças de posturas, o tempo de reação observado foi de até 7 segundos e a quantidade de nós na rede não interferiu no comportamento do mecanismo.

Palavras-chave:

Redes Corporais Sem Fio; WBANs; IEEE 802.15.6; Agendamento de Transmissões.

Autor(res):Thiago Malheiros Porcino

Resumo:

A realidade virtual (RV) e os head-mounted displays (HMD) estão constantemente ganhando popularidade em vários segmentos, tais como: educação, militar, entretenimento e saúde. Embora tais tecnologias possibilitem uma grande sensação de imersão, elas também podem desencadear sintomas de desconforto. Tal condição é chamada de cybersickness (CS) e é bastante popular em publicações recentes sobre realidade virtual. Propõe-se neste trabalho uma nova análise experimental usando aprendizado de máquina simbólico para classificar as causas potenciais de CS em jogos de RV. Primeiramente, as teorias de manifestações de desconforto geralmente atribuídas a ambientes de realidade virtual foram revisadas. Além disso, também foram revisadas as estratégias existentes com o objetivo de minimizar os problemas de CS. Foi discutido como a medição da CS pode ser realizada com base em dados subjetivos, biossinais (ou dados objetivos) e de perfil dos usuários. Em segundo lugar, uma nova abordagem foi proposta para prever as próximas manifestações da CS. O resultado foi uma solução capaz de sugerir se o usuário de RV está entrando em uma situação de CS, com 99.0% de acurácia no melhor caso. Foi adotado o classificador random forest após uma validação envolvendo 16 classificadores diferentes de aprendizado de máquina, listados no capítulo 5 deste trabalho. O conjunto de dados foi construído por meio de um questionário de perfil de CS e dois jogos de realidade virtual que também foram elaborados neste trabalho. Terceiro, são estimadas as causas da CS e são classificadas de acordo com seu impacto pelo algoritmo de aprendizado de máquina simbólico desenvolvido. Os experimentos foram realizados usando dois jogos de realidade virtual e 6 protocolos experimentais, juntamente com 37 amostras válidas de um total de 88 voluntários. Em resumo, os resultados mostram que a rotação e a aceleração desencadearam a CS com mais frequência em um jogo de voo em comparação a um jogo de corrida. Pode-se observar também que indivíduos menos experientes com RV são mais propensos a sentir o desconforto. Os resultados corroboram com a confirmação da hipótese de que a experiência prévia com RV desempenha um papel mais importante no jogo de corrida, pois este jogo oferece mais liberdade ao usuário em termos de controladores, mais alternativas de deslocamento e uma aceleração mais autocontrolada. Adicionalmente, diferentes causas que desencadeiam a CS surgem com base em exposições de RV de curto ou longo prazo. São sugeridas estratégias para mitigar a CS para esses dois cenários: experiências de exposição de curto e longo prazo.

Autor(res):Bruno Augusto Dorta Marques

Resumo:

Os recentes avanços em plataformas de realidade mista impulsionam o surgimento de novos paradigmas de interação. Em particular, Head-mounted Displays (HMDs) estão sendo desenvolvidos pela indústria para criar uma interface entre o mundo virtual e o mundo real, permitindo que os usuários interajam com elementos virtuais e reais presentes simultaneamente em uma única cena. Nessa composição de elementos reais e virtuais, discrepâncias perceptuais na iluminação de objetos podem ocorrer; essa diferença entre a iluminação do mundo virtual e a iluminação do mundo real é um problema referido como problema de incompatibilidade de iluminação. Neste trabalho propomos um framework de realidade mista para solucionar o problema de incompatibilidade de iluminação. O framework é baseado em estimar a iluminação de ambientes do mundo real e adaptar os elementos do mundo virtual de acordo com a iluminação estimada. Estimar a iluminação de uma cena real é uma tarefa difícil. Abordagens adotadas por trabalhos relacionados na literatura solucionam essa tarefa impondo fortes suposições sobre a cena, ou requerem o conhecimento prévio da cena, como por exemplo a geometria da cena, limitando a usabilidade dos métodos existentes para aplicações de realidade mista. Neste trabalho utilizamos uma abordagem baseada em deep learning para o desenvolvimento de três modelos para estimativa de iluminação. Os modelos são apropriados para o framework de realidade mista a não requerem conhecimento prévio da cena. O Point Light Source estimator e o Spherical Harmonics Light Probe estimator consideram que mãos humanas podem serem utilizadas como um light-probe da iluminação ambiente. Esta hipótese é explorada para inferir a iluminação ambiente utilizando fotografias em visualizações egocêntricas capturadas pela câmera localizada nos HMD’s de realidade mista. O Environment Light Probe estimator faz uso de imagens de ambientes reais a fim de criar um modelo robusto de estimativa de iluminação ambiente capaz de estimar a iluminação ambiente utilizando uma fotografia em baixa faixa dinâmica do ambiente. Os métodos de estimativa de iluminação ambiente foram validados através de testes sintéticos e aplicações de re-iluminação de cenas em realidade mista. Trabalhos futuros são propostos afim de proporcionar melhorias que podem aumentar a imersão do usuário em aplicações de realidade mista.

Palavras-chave: Realidade Mista, Estimativa de Iluminação, Aprendizado Profundo,

Redes Neurais Convolucionais

Autor(res):Julliano Trindade Pintas

Resumo:

Os métodos de Seleção de Atributos (SA) aliviam problemas principais no desenvolvimento de modelos de classificação de textos, pois são utilizados para reduzir a dimensionalidade dos dados, melhorar a acurácia do modelo e reduzir o custo computacional. Por este motivo, os métodos de SA têm recebido muita atenção da comunidade de inteligência artificial nos últimos anos. Realizamos uma Revisão Sistemática de Literatura (RSL) abrangente que avaliou 1376 artigos únicos de periódicos e conferências publicados nos últimos oito anos (2013-2020). Após a triagem de resumos e análise de elegibilidade de texto completo, mapeamos 175 estudos sobre SA especificamente para classificação de textos.

Nós identificamos que praticamente todos os métodos de SA mapeados possuem uma grande dependência do volume de dados rotulados de treinamento. No entanto, o conjunto de dados rotulados disponível pode ser limitado em muitas situações, o que pode degradar a eficácia desses métodos. Por esse motivo, investigamos o uso da inteligência coletiva no processo de SA com objetivo reduzir esta dependência. Nesta tese, propomos e avaliamos o método CrowdFS (Crowd-based Feature Selection) que se combina a avaliação de diferentes indivíduos para apoiar SA para classificação de textos.

Para avaliar a eficácia do método proposto, realizamos um primeiro experimento com uma equipe de especialistas de uma empresa multinacional de energia e um segundo experimento utilizando uma plataforma aberta de tarefas (Appen) com participantes não especialistas. Nossa avaliação de resultados demonstrou que o CrowdFS resultou em uma acurácia equivalente aos métodos existentes, porém com uma dependência menor de volume de dados rotulados. Além disso, quando combinamos o método CrowdFS com métodos existentes, identificamos uma melhora na acurácia da classificação em relação ao uso dos métodos SA existentes de maneira isolada. Além de avaliar a eficácia do método proposto, discutimos nesta tese questões relevantes que identificamos sobre utilização de inteligência coletiva no processo de SA, como modos de agregação de respostas, número necessário de participantes, perfil dos participantes e critérios de qualidade.

Palavras Chave

Seleção de Atributos; Inteligência Coletiva; Redução de dimensionalidade; Classificação de texto;

Autor(res):Daniel Vasconcelos Corrêa da Silva

Resumo:

A transmissão contínua de vídeo pela Internet, o streaming, está entre as maiores aplicações de rede da atualidade, tanto em número de usuários, quanto no volume de tráfego de dados. Em meio aos formatos de transmissão contínua de vídeo, o streaming ao vivo é certamente o que impõe mais desafios à infraestrutura de rede, como, por exemplo, não conseguir mensurar com precisão o volume de usuários durante a transmissão, ou mesmo as condições gerais da rede, além das eventuais e prováveis dificuldades da criação do conteúdo em si. O crescimento da transmissão contínua de vídeo ao vivo só foi possível graças: (i) à melhoria geral da infraestrutura da Internet, que promoveu a redução de preço e garantiu acesso a taxas de transmissão mais altas, inclusive para redes móveis, e (ii) ao avanço no desenvolvimento dos dispositivos de comunicação utilizados pelos usuários. Dentre estes equipamentos, disponíveis aos usuários da rede, destacam-se, pela popularidade, os dispositivos móveis, que já se apresentam, em muitos casos, como principal tipo de equipamento usado no acesso à Internet. Os celulares atuais, os smartphones, já acumulam muitas funções para além da telefonia à medida que se tornam cada vez mais poderosos computacionalmente. O mesmo se aplica aos tablets, tipo de dispositivo com características muito semelhantes aos celulares em termos de usabilidade e mobilidade. Entender o comportamento dos usuários móveis de vídeos ao vivo é imperativo para perceber e mapear problemas, para tornar possível pesquisar soluções atualizadas e realistas para este paradigma de transmissão de vídeo. Neste contexto, o objetivo deste trabalho é caracterizar e entender o comportamento dos usuários de dispositivos móveis em transmissões de vídeo ao vivo a partir de dados do servidor de um dos maiores provedores de conteúdo do Brasil. Espera-se estabelecer elementos de comparação e mensuração do engajamento dos usuários nas sessões, estabelecer a natureza e consequências dos problemas enfrentados pelos usuários e fornecer informações em formato que ajude pesquisadores e profissionais da área a verificar e mitigar problemas e planejar próximos passos desta importante aplicação da Internet.

Palavras-chave: Streaming, vídeo ao vivo, dispositivo móvel

Autor(res):Rodrigo Lamblet Mafort

Resumo:

Este trabalho aborda dois problemas de propagação em redes, onde a principal ideia é identificar um conjunto de vértices capaz de dominar ou contaminar/influenciar os demais ao longo de sucessivas iterações. Nos modelos de propagação, um vértice é dito contaminado quando o número de seus vizinhos já contaminados supera um valor previamente definido, conhecido como o requisito do vértice. Os problemas de propagação em redes têm várias aplicações práticas, como, por exemplo, modelar computacionalmente a disseminação de informações ou influência em redes sociais, ou a propagação de uma epidemia em uma sociedade. Um exemplo bastante atual de uma aplicação do problema é a busca pelo menor número de usuários da rede social que devem emitir inicialmente uma informação para que ela se dissemine por toda a rede. O primeiro problema considerado neste trabalho é o Problema da Dominação Vetorial, onde a dominação de todos os vértices deve ser realizada em uma única iteração. Isto é, o problema busca um conjunto mínimo de vértices tal que todo vértice ou está contido neste conjunto, ou é imediatamente contaminado pelos vértices do conjunto. Para este problema, o foco do trabalho é identificar os limiares da complexidade computacional. Entretanto, dado o vasto universo de famílias de grafos, o escopo do trabalho foi delimitado aos grafos cordais e suas subclasses. Este estudo produziu um algoritmo linear para os grafos \textit{split}-indiferença, entre outros resultados. O segundo problema abordado é o Problema da Seleção de Alvos, que pode ser visto como uma generalização do anterior, onde o contágio do grafo ocorre ao longo de várias iterações. Ou seja, um vértice contaminado em uma iteração colabora para que seus vizinhos também sejam contaminados nas iterações seguintes. Por ser um tema de grande interesse prático, o problema foi tratado através de algoritmos aproximativos. Um dos resultados obtidos neste trabalho é um algoritmo bioinspirado paralelizado, capaz de identificar soluções melhores do que as previamente conhecidas na literatura para grandes redes sociais.

Palavras-chave: Propagação em Redes; Problema da Dominação Vetorial; Problema da Seleção de Alvos; Complexidade Computacional; Algoritmos em Grafos.

Autor(res):Marques Moreira de Sousa

Resumo:

Problemas de otimização combinatória estão cada vez mais presentes na tomada de decisão dos mais variados setores da economia. No Brasil, devido a sua extensa malha rodoviária pela qual a maioria dos produtos e serviços essenciais à população são transportados, o uso de técnicas de otimização para geração de rotas e consequente minimização dos custos operacionais, apresenta-se como uma estratégia relevante. Definir rotas por meio da representação de problemas de otimização consiste em uma alternativa para redução de custos, mantendo empresas competitivas em um mercado cada vez mais sufocado pela alta carga tributária e outros encargos que incidem sobre toda a cadeia produtiva. Nesse sentido, o Problema do Caixeiro Viajante com Seleção de Hotéis consiste na definição de uma rota que minimiza a soma dos tempos necessários para viajar entre clientes, respeitando um limite de tempo de viagem diário e escolhendo, quando necessário, hotéis para descanso entre dias consecutivos de trabalho. Sua variante com múltiplos caixeiros, além de minimizar os tempos necessários para viajar entre clientes e realizar a escolha dos hotéis intermediários, precisa construir múltiplas rotas, uma para cada caixeiro, respeitando um limite máximo de viagens para cada rota. Nesta tese, propomos heurísticas e estratégias híbridas utilizando a metaheurística Iterated Local Search (ILS), técnicas de mineração de dados e de Programação Linear Inteira. Para diversas instâncias contidas na literatura obtivemos resultados equivalentes aos melhores já conhecidos, bem como novas melhores soluções para uma parcela considerável das 1811 instâncias conhecidas para os dois problemas.

Palavras-chave: Problema do Caixeiro Viajante; Seleção de Hotéis; Heurísticas; Mineração de Padrões Frequentes.

Autor(res):Igor da Penha Natal

Resumo:

Os smartphones se tornaram um dispositivo indispensável para as pessoas devido às suas crescentes funcionalidades e preços mais acessíveis para a população em geral. Seus sensores incorporados, incluindo o Global Position System – GPS, o acelerômetro e o giroscópio, abriram oportunidades para apoiar diversas tarefas na rotina das pessoas. Uma das tarefas que utilizam esses sensores é a de reconhecimento de atividade humana (Human Activity Recognition – HAR), tanto em ambientes internos quanto em ambientes externos. Neste trabalho é apresentado um modelo minimalista de HAR para ambientes fora de casa (MOut-HAR), a abordagem contempla desde a coleta de dados até a concepção de um reconhecedor de atividades. O minimalismo proposto está diretamente ligado ao número de sensores utilizados, no caso apenas o GPS, e ao número de atributos utilizados. Os dados de GPS foram enriquecidos com o conhecimento semântico gerando o atributo de Ponto de Interesse (Point of Interest – POI) e complementados com poucas informações do perfil do usuário. A coleta de dados foi guiada através de uma ontologia baseada no conhecimento prévio do estado da arte e através de um aplicativo para smartphones Android. Foram coletados dados de voluntários dos estados do Rio de Janeiro e Minas Gerais, gerando um dataset chamado HAR-Brazilian dividido em dois subconjuntos. O modelo desenvolvido tem como objetivo reconhecer 13 atividades distintas, incluindo 3 atividades de deslocamento e 10 estacionárias. O modelo foi avaliado através de acurácia, recall, precisão e F-Score, e apresentou resultados semelhantes ou melhores que o estado da arte. Os resultados demostram que uma combinação adequada de informações, mesmo que sejam simples, podem produzir uma solução eficiente para a tarefa de HAR em ambientes fora de casa.

Palavras-chave: reconhecimento de atividade humana, dados sensoriais enriquecidos, informações semânticas, perfil do usuário, aprendizado de máquina.

Autor(res):Alan Diêgo Aurélio Carneiro

Resumo:

Um knot em um grafo direcionado G é um subgrafo fortemente conexo Q de G com pelo menos dois vértices, tal que, nenhum vértice em V(Q) possui aresta direcionada a um vértice em V(G) \ V(Q. O Knot é uma estrutura importante já que caracteriza a existência de deadlocks em um modelo de computação distribuída clássico, chamado modelo Ou. A detecção de deadlocks está intimamente relacionada ao reconhecimento de grafos livres de knots da mesma maneira que a resolução de deadlock está intimamente relacionada ao problema de Eliminação de Knots por Deleção de Vértices (Knot-Free Vertex Deletion (KFVD)), que consiste em determinar se dado um grafo G e um inteiro k, G possui um subconjunto de vértices S ⊆ V(G) e |S| ≤ k tal que G[V \ S] não contém knot.

 Nesta tese, primeiramente foi realizada uma revisão da literatura sobre a complexidade computacional do problema de resolução de deadlock nos modelos clássicos de computação distribuída. Foram apresentados que: o problema de Eliminação de Knots por Deleção de Arcos pode ser resolvido em tempo O(n); KFVD é NP-difícil mesmo quando o grafo de entrada é fortemente conexo ou bipartido, planar e com grau máximo 4; KFVD pode ser resolvido em tempo O(m√n) quando o grafo de entrada é sub-cúbico. Além disso, é apresentada uma equivalência entre as versões do problema de Eliminação de Knots por Deleção de Arcos/Vértices para grafos com pesos e grafos sem pesos.  

Em seguida, é apresentada uma análise de complexidade parametrizada de granularidade fina para KFVD. Provamos que: KFVD é W[1]-difícil quando parametrizado pelo tamanho da solução k; pode ser solucionado em tempo 2^klogφn^O(1), mas assumindo a hipótese de tempo exponencial forte (Strong Exponential Time Hypothesis (SETH)) não pode ser solucionado em tempo (2-ε)^klogφn^O(1), onde φ é o tamanho da maior componente fortemente conexa de G; pode ser resolvido em tempo 2^ϕn^O(1), mas assumindo a hipótese de tempo exponencial (Exponential Time Hypothesis (ETH)) não pode ser resolvido em tempo 2^o(ϕ)n^O(1), onde ϕ é o número de vértices com grau de saída no máximo k; a menos que NP ⊆ coNP/poly, KFVD não admite núcleo polinomial mesmo quando φ=2 e parametrizado pelo tamanho da solução k.

  Finalmente, considera-se parâmetros de largura onde provamos que: KFVD quando parametrizado pelo tamanho da solução k é W[1]-difícil mesmo quando o tamanho do maior caminho direcionado p, juntamente com o Kenny-width do grafo são limitados por constantes; é solucionável em tempo FPT quando parametrizado por clique-width; pode ser resolvido em tempo 2^O(twlogtw)n, mas, assumindo ETH não pode ser resolvido em tempo 2^o(tw)n^O(1), onde tw é a treewidth do grafo subjacente. Além disso, dado que o tamanho do conjunto mínimo de vértices de retroalimentação (directed feedback vertex set) dfv é um limite superior para o tamanho de um certificado de solução para KFVD, investigamos parametrizações por dfv, onde mostramos que KFVD pode ser solucionado em tempo FPT quando parametrizado tanto por dfv+κ ou dfv+p, e adimite um algoritmo FPT quando parametrizado pela distância a um DAG tendo uma cobertura por caminhos limitada (outro parâmetro superior ao dfv).    

Palavras-chave:  Knot, FPT, W[1]-difícil, ETH, Treewidth, Parâmetros de largura.

Autor(res):Pablo Nascimento da Silva

Resumo:

O envelhecimento é um processo biológico complexo e pode ser caracterizado por um declínio contínuo das funções de um organismo que ocorre com o aumento da idade. O estudo de genes que regulam o envelhecimento pode levar à criação de novos medicamentos e tratamentos para aumentar a expectativa de vida de um organismo. Nesta tese, focaremos no estudo de novos métodos capazes de aumentar a capacidade preditiva de classificadores para identificar genes relacionados com o envelhecimento.

Neste trabalho, genes são descritos através de atributos da Gene Ontology (GO) e atributos que representam interações entre proteínas, chamados atributos PPI (Protein-Protein Interactions). Atributos da Gene Ontology são organizados hierarquicamente. Um espaço de atributos hierárquico é formado por atributos binários que possuem relações de generalização-especialização. Embora exista uma grande variedade de métodos para a seleção de atributos tradicional, métodos que consideram a estrutura hierárquica são pouco explorados. Portanto, são propostos dois métodos de seleção de atributos para explorar espaços de atributos hierárquicos: (i) um método lazy baseado na hipótese de que atributos positivos são mais relevantes e informativos para a classificação, chamado Select Relevant Positive Feature Values (RPV); e (ii) um método evolucionário chamado Genetic Algorithm for Hierarchical Feature Spaces (GA-HFS) que aplica dois novos operadores de mutação enviesada, especificamente desenvolvidos para tratar o problema dos atributos redundantes em espaços de atributos hierárquicos.

O uso the atributos PPI para classificação não é trivial, pois seus valores são incertos, i.e., tais valores são escores numéricos que representam a probabilidade de duas proteínas interagirem. Para solucionar este problema, este trabalho explora uma nova medida de distância chamada Probabilistic Jaccard para lidar com as características incertas dos atributos, e que pode ser utilizada com o algoritmo de classificação baseado nos vizinhos mais próximos. Adicionalmente, é proposto um novo método de seleção de atributos chamado Lazy Feature Selection Method for Uncertain Features (LFSUF), capaz de lidar com a incerteza dos atributos.

Mostramos empiricamente que explorar apropriadamente as características hierárquicas e incertas de atributos pode melhorar a capacidade preditiva de classificadores que identificam genes relacionados ao envelhecimento.

Palavras-chave: Classificação, Biologia do Envelhecimento, Seleção de Atributos, Espaços de Atributos Hierárquicos, Espaços de Atributos Incertos

Autor(res):Yona Lopes

Resumo:

Com as redes elétricas inteligentes, os dispositivos do sistema elétrico de potência se tornam multifuncionais e passam a se comunicar de forma bidirecional e em tempo real. Para atender a essa nova demanda, os sistemas de supervisão e controle precisam evoluir e incorporar novas funcionalidades, permitindo maior dinamismo e flexibilidade para acompanhar a escala das redes elétricas inteligentes. A inserção de fontes de energia renováveis traz novas possibilidades, e, também, muitos desafios. Nesse novo cenário, a rede de comunicação precisa ser ainda mais confiável, evitando que falhas de comunicação interfiram nos mecanismos de proteção e controle da rede elétrica. As propostas que exploram o novo paradigma das redes elétricas inteligentes dependem de sistemas de comunicação mais flexíveis e dinâmicos, com interação em tempo real, sendo este, um dos principais desafios da área.

            Nesta tese, os desafios relacionados às redes de comunicação para o sistema elétrico são identificados e discutidos. Com base neste levantamento, propõe-se um framework, intitulado ARES (Autonomic and Resilient Communication framEwork for Smart grids), para dar suporte de comunicação às novas aplicações de energia. O ARES objetiva permitir que a capacidade multifuncional dos dispositivos seja explorada e que as aplicações de energia possam contar com uma rede de comunicação mais dinâmica e que atenda às restrições temporais rígidas impostas pelo novos sistemas de proteção baseados na norma IEC 61850. O framework permite que os serviços de supervisão e controle configurem dinamicamente a rede, permitindo o desenvolvimento de uma nova geração de aplicação de energia que possam agir sobre a rede de comunicação em tempo real. A norma IEC 61850 foi estendida para permitir que novas implementações baseadas na prioridade do dispositivo físico para o sistema elétrico e nas suas possíveis funções, variáveis ou não ao longo do tempo, sejam realizadas. O ARES é baseado em SDN (Software Defined Network), e no modelo de informação da norma IEC 61850.

            A implementação do framework ARES mostrou sua viabilidade prática, de forma a entregar uma rede mais dinâmica e flexível, permitindo que um novo SCADA, intitulado SCADA-NG, possa ser construído com aplicação de energia mais inteligentes e mais capazes.  A resiliência de uma rede para teleproteção de subestações baseada no framework também foi avaliada, mostrando que a solução atende aos requisitos impostos pelo setor de energia elétrica para o estudo de caso apresentado.

Palavras chave: SDN, Autoconfiguração, Resiliência, SCADA-NG, ARES.

Autor(res):Eduardo Charles Vasconcellos

Resumo:

Segundo a organização mundial da saúde, problemas cardíacos são uma das principais causas de morte no mundo. Problemas como arritmias são causadas por comportamentos anômalos na dinâmica elétrica do tecido cardíaco e podem ser estudados por meio de simulações computacionais, usando modelos matemáticos que descrevem a eletrofisiologia do tecido. Nesta tese foram desenvolvidas duas estratégias paralelas usando GPUs e CUDA para acelerar tais simulações. Dois modelos da eletrofisiologia cardíaca foram implementados para criar os simuladores e testar as estratégias paralelas propostas aqui: um modelo de duas variáveis e outro de 41 variáveis. Uma das estratégias propostas, chamada towerDS, foi baseada na abordagem de janela deslizante, desenvolvida para paralelizar o método de diferenças centradas em GPU usando o CUDA. Nossa estratégia propõe uma estrutura de armazenamento de dados projetada para otimizar os acessos a memória global da GPU quando executando a janela deslizante. A segunda estratégia propõe uma estrutura de dados que pode ser ajustada à geometria da parte ventricular do coração, otimizando o uso de recursos da GPU e o acesso a memória global da mesma pelas threads. Também foi desenvolvida uma estratégia de comunicação para execução de simulações com a janela deslizante e sua estrutura otimizada em ambientes com múltiplas GPUs. Os resultados atingidos demonstram ser possível simular 1 segundo de atividade elétrica com apenas 4 segundos de simulação. Este resultado indica que em breve, com arquiteturas de GPUs um pouco melhores, poderemos atingir o tempo real. Esta simulação em 4 segundos foi com o modelo de duas variáveis e oito GPUs, para um domínio discreto cúbico com 256³ células. Com uma única GPU, a estratégia paralela com a estrutura towerDS aplicada ao modelo de duas variáveis, foi capaz de reduzir o tempo de processamento da simulação entre 6% e 40%, quando comparada a implementação com a janela deslizante clássica. A variação no ganho de tempo depende do tamanho do domínio e da GPU utilizada. Já para o modelo de 41 variáveis, a implementação paralela com a estrutura adaptativa chega a ser até 10x mais rápida que a implementação com a janela deslizante.

Palavras-chave: computação em GPUs; simulações numéricas paralelas; modelos da eletrofisiologia cardíaca; método de diferenças finitas em GPU; otimização do uso de memória em GPU.

Autor(res):Edhelmira Lima Medina

Resumo:

Existe um crescimento exponencial de informações clínicas que são geradas e armazenadas diariamente nos sistemas de informação de hospitais e centros de saúde. Estas informações muitas vezes estão distribuídas em banco de dados de diferentes provedores, fazendo com que os profissionais da saúde possuam conhecimento altamente incompleto do paciente. Nesse sentido, a presente tese aborda o tema da preservação de dados clínicos de um indivíduo durante seu ciclo de vida. De acordo à literatura identificamos que na área de saúde os documentos clínicos devem ser preservados historicamente, porém, essa preocupação é pouco explorada. Para isso, esta tese propõe um metamodelo, que em alto nível de abstração, permita representar a integração de processos clínicos (eventos temporais relacionados à saúde que geram documentos clínicos), a representação do prontuário eletrônico e sua preservação a longo prazo. A metodologia adotada nesta tese é baseada no Design Science Research (DSR) e consiste em cinco passos: identificação do problema, sugestão, desenvolvimento, validação e conclusão. A etapa de identificação do problema consiste em procurar fontes de conhecimento sobre a preservação digital no domínio da saúde e identificar suas carências. Na etapa de sugestão se propõe um metamodelo para facilitar a visualização de processos clínicos, prontuário eletrônico do paciente e preservação digital. Isto como resultado de uma revisão bibliográfica sistemática da literatura, visto que não se encontrou uma representação similar. Na etapa de desenvolvimento se formaliza o metamodelo que está baseado no meta-metamodelo Ecore e é construído no Eclipse Modeling Framework. A validação é realizada por meio da instanciação de modelos que descrevem cenários criados com base em questões de competência. Finalmente na conclusão se analisa os resultados obtidos, o qual se considera promissor para os cenários desenvolvidos. Portanto, o metamodelo ajudará a entender como é o processo de geração de dados clínicos e sua posterior preservação.

Palavras-Chave: Preservação de dados clínicos, preservação do prontuário eletrônico do paciente, persistência de informação clínica, metamodelo, processos clínicos.

Autor(res):Jonnathan dos Santos Carvalho

Resumo:

Análise de sentimentos é a tarefa que identifica automaticamente opiniões expressas em textos, tais como tweets, que são mensagens limitadas a 140 caracteres publicadas no Twitter. Este tipo de mensagem tem sido o foco da análise de sentimentos nos últimos anos, em função da grande quantidade de opiniões expressas, a todo instante, sobre assuntos diversos. Nesse contexto, muitos trabalhos utilizam diferentes métodos para determinar a polaridade dessas opiniões e incluem, em sua maioria, técnicas de aprendizado de máquina supervisionado. Assim, diferentes tipos de atributos têm sido propostos para aumentar o poder preditivo da classificação das opiniões expressas em tweets. Estes atributos incluem n-gramas, meta-features e atributos derivados de word embeddings.

Com essa grande quantidade de atributos disponíveis, nesta tese, propõe-se investigar a aplicação de diferentes conjuntos de atributos na classificação de opiniões em tweets de domínios distintos. Com esse objetivo, é realizada uma avaliação de cada conjunto de atributos, em vinte e duas bases de dados, para determinar o conjunto de atributos mais relevante na análise de sentimentos em tweets. Além disso, esta tese apresenta um estudo das meta-features e de diferentes modelos pré-treinados de word embeddings propostos na literatura. Mais precisamente, é proposta a categorização de meta-features identificadas na literatura para determinar os tipos de meta-features mais adequados para esta tarefa. Ainda, é apresentado um estudo da qualidade de diferentes modelos de word embeddings, genéricos e afetivos, na classificação do sentimento expresso em tweets.

Apesar dos diferentes tipos de atributos propostos na literatura, nenhum trabalho avalia de forma detalhada como atributos de diferentes tipos podem se complementar na classificação das opiniões expressas em tweets. Nesse contexto, nesta tese, é apresentado um estudo para avaliar a eficácia da combinação destes diferentes conjuntos de atributos, isto é, n-gramas, meta-features e atributos derivados de word embeddings, utilizando uma técnica de concatenação de vetores de atributos e métodos de combinação de classificadores ou ensemble de classificadores. Para os métodos de ensemble, é explorada uma abordagem que adota classificadores base obtidos através de diferentes algoritmos de classificação, cada um utilizando, como entrada, um conjunto específico de atributos.

O estudo conduzido nesta tese indica que todos os tipos de atributos podem contribuir na classificação do sentimento expresso em tweets, incluindo a controversa representação derivada dos n-gramas. Esta representação acarreta a esparsidade das bases de dados, devido à grande quantidade de termos infrequentes. Nesse contexto, é proposta uma estratégia de enriquecimento dos termos contidos nos tweets, que identifica e utiliza termos do vocabulário que possuam alguma relação semântica, com o objetivo de enriquecer a representação esparsa derivada dos n-gramas. Os resultados obtidos demonstram que esta estratégia contribui de forma efetiva na análise de sentimentos em tweets.

Palavras-chave: análise de sentimentos, Twitter, n-gramas, meta-features, word embeddings, ensemble de classificadores, esparsidade

Autor(res):Carlos Eduardo Pantoja

Resumo:

O desenvolvimento de sistemas onipresentes e difundidos considera o uso de componentes eletrônicos e sistemas de computador para aprimorar objetos diários com alguma inteligência computacional para ajudar os usuários em suas tarefas de maneira difundida. A Ambient Intelligence (AmI) é um ramo da computação onipresente que fornece um ambiente cheio de dispositivos interconectados e pode fornecer comunicação de dados e colaboração entre os dispositivos do sistema. Da mesma forma, a Internet das Coisas (IoT) fornece dispositivos ou itens identificados exclusivamente em uma rede para ajudar os usuários em suas atividades. Os sistemas multi-agente (MAS) são sistemas inteligentes em que os agentes são responsáveis ​​por raciocinar, competir e usar recursos para alcançar metas desejáveis ​​de forma proativa e autônoma. A abordagem do agente MAS é adequada para sistemas AmI, pois ambos compartilham as mesmas características. Nesse cenário, os agentes têm sido empregados em várias abordagens e trabalhos nos últimos anos. No entanto, nenhum deles considerou o MAS incorporado autônomo responsável pelos objetos IoT para ambientes abertos em um sistema AmI. Portanto, esta tese propõe uma arquitetura para o desenvolvimento de sistemas AmI que usam objetos IoT como coisas inteligentes com MAS incorporado para interface com sensores e atuadores e são capazes de se comunicar e interagir com outros objetos IoT em uma rede IoT. Em seguida, apresentamos a Internet das Coisas Inteligentes (IoST), que é uma arquitetura para gerenciamento de recursos, na qual vários Objetos IoT podem fazer parte de ambientes representados virtualmente e ficam disponíveis para serem acessados ​​pelos usuários através do uso de aplicativos. A arquitetura é composta por três camadas que representam objetos da IoT, a solução em nuvem e aplicativos. Além disso, o IoST é estendido para criar uma camada dependente de recursos para que os agentes de planejamento contextual explorem os recursos físicos de qualquer objeto IoT disponível.

Palavras-chave: Sistemas Multi-agentes, sistemas embarcados, computação ubíqua.

Autor(res):Ruben Interian Kovaliova

Resumo:

Nesta tese, desenvolvem-se e apresentam-se contribuições para problemas de otimização em redes. A primeira e principal contribuição aborda dois aspectos diferentes do problema de polarização em redes sociais, de interação e de comunicação. Primeiro, uma abordagem probabilística é usada para derivar uma nova e melhor medida para o fenômeno da polarização. Em seguida, um novo problema de otimização é definido, abordando a questão da redução de polarização usando adições mínimas de arestas, de acordo com o princípio de intervenções externas mínimas. Prova-se que o problema é NP-difícil e formulações de programação inteira e heurísticas são propostas para resolvê-lo.

Além disso, cinco outras contribuições são desenvolvidas nesta tese, correspondendo a abordagens para problemas de otimização representados em grafos e redes. A segunda contribuição aborda uma variante tipo Steiner do problema do caixeiro-viajante. A terceira descreve uma abordagem para calcular uma combinação ótima de métodos de verificação e validação que cobre as características de qualidade do software. A quarta contribuição apresenta um método para visualizar grandes grafos de histórico de commits, minimizando o número de nós exibidos e preservando a estrutura do grafo. O quinto tema tratado propõe um algoritmo que identifica o grau do polinômio implícito ótimo para ajustar curvas e superfícies. O sexto tema apresenta uma abordagem que deduz a estrutura de vizinhança e regras para um autômato celular baseado em redes regulares que aproxima o comportamento de certos tipos de tumores.

Abordagens exatas (como programação inteira e algoritmos tratáveis por parâmetro fixo) e heurísticas (como GRASP, reconexão de caminhos e busca iterada gulosa) são usadas para resolver os problemas de otimização mencionados acima. Juntos, estes problemas abrangem uma ampla gama de áreas da Ciência da Computação, como análise de redes, roteamento e logística, engenharia de software e visão computacional.

Palavras-chave: otimização em redes, otimização combinatória, métodos exatos, heurísticas, polarização, problema de roteamento, problema de Steiner, problema de cobertura, ajuste de curvas e superfícies, programação inteira, GRASP, reconexão de caminhos.

Autor(res):Jorge Reynaldo Moreno Ramírez

Resumo:

Nesta tese foram estudados os problemas The Minimum d-Branch Vertices, The Rainbow Cycle Cover e The Rainbow Spanning Forest. O problema The Minimum d-Branch Vertices possui aplicações no desenho de redes ópticas, visando a construção de uma rede com o menor número de replicadores de sinal. Por sua vez, The Rainbow Cycle Cover e The Rainbow Spanning Forest são usados no estudo de redes sociais e de transporte. Esses dois últimos problemas pertencem à classe de problemas sobre grafos com cores nas arestas e visam a obtenção de componentes em que cada cor aparece no máximo uma vez. Diferentes estratégias foram desenvolvidas para resolver esses problemas, como a redução

do tamanho das instâncias baseada em propriedades dos grafos, o uso de estruturas de dados eficientes e a implementação de heurísticas. Dentro das contribuições deste trabalho está a definição do conceito de co-classe, que foi usado para o pré-processamento das instâncias, assim como para a definição de inequações válidas. Além disso, foram implementados diferentes níveis de colaboração entre métodos heurísticos e exatos. Como resultado, foram desenvolvidas novas formulações matemáticas e heurísticas que resultaram ser mais efetivas do que as encontradas na literatura consultada.

Palavras-chave: Metaheurística; ramificação e poda; matheurística; cortes; otimização combinatória.

Autor(res):Edcarllos Gonçalves dos Santos

Resumo:

Problemas de otimização são encontrados em diversos setores da produção industrial, buscando em geral minimizar os custos e maximizar os lucros. No contexto das Cidades Inteligentes, se torna prioridade a transparência para o cidadão e uma logística efetiva de transporte de pessoas e bens de consumo, motivando uma série de propostas acadêmicas para o tema. O estudo desses problemas é essencial para se manter a competitividade de cadeias produtivas, também sendo um desafio a tarefa de encontrar uma solução de boa qualidade em um tempo computacional baixo. De forma específica, a logística têm sido bastante estudada devido a seu grande número de aplicações práticas e, neste sentido, este trabalho explora o estudo de dois problemas de transportes. O Problema de Caminho com Coleta de Prêmios, consiste em encontrar um ($s$, $t$)-caminho que minimiza a soma dos pesos de suas arestas (tempo total de transporte) menos o prêmio total dos nós em tal caminho. Por sua vez, para o Problema de Roteamento de Veículos para o Transporte de Funcionários, deve-se minimizar os custos de transporte e, respeitar em contrapartida, as restrições de qualidade de serviço para os funcionários. Ambos os problemas estão presentes no núcleo de diversas aplicações relevantes em áreas como Telecomunicações, Transporte Público e Manutenção de Equipamentos. Neste trabalho serão exploradas diferentes técnicas de resolução que vão desde métodos exatos até heurísticas inteligentes.

Palavras-chave: Coleta de Prêmios; Roteamento de Veículos; Treewidth.

Autor(res):Eric Zanghi

Resumo:

A medição de energia é uma das questões mais importantes no ambiente atual das redes elétricas. A qualidade do serviço oferecido pelas concessionárias de energia elétrica tem sido avaliada modernamente com base na exploração de tecnologia aplicada na medição em sistemas de distribuição de média e baixa tensão. Especificamente em redes de baixa tensão, a grande quantidade de medidores nas regiões urbanas e, por outro lado a sua pouca quantidade em regiões rurais, geram alta complexidade para a implementação de medição remota. Tal fato abre uma gama de possíveis soluções para o problema, fruto de intensas pesquisas multidisciplinares.

Esta tese apresenta novas ideias para a medição remota e objetiva fornecer elementos para a construção de sistemas de medição remota que enfrentem o problema de aquisição distribuída e massiva de dados em redes elétricas que agregam novas tecnologias. Assim sendo, propõe-se aqui um Sistema Colaborativo de Medição Inteligente (SCMI), com base na tecnologia conhecida por Cadeia de Blocos (Blockchain), constituindo-se em ferramenta operacional importante para auxiliar concessionárias de energia elétrica a atingirem índices de qualidade de serviço estabelecidos por órgãos reguladores. Por meio de sistemas colaborativos, a solução proposta leva a investimentos substancialmente menores em custos de implementação e manutenção de infraestruturas de comunicação.

A abordagem proposta foi validada como “prova de conceito”, a partir da construção de um simulador do SCMI, tendo sido realizados testes correspondendo a diferentes situações adversas nas quais o sistema pode estar exposto. Os resultados obtidos evidenciam o potencial da abordagem proposta como solução para a aquisição, validação e comunicação de dados em redes elétricas modernas.

Palavras-chave: blockchain, engajamento do consumidor, redes colaborativas, redes inteligentes, sistemas de potência.

Autor(res):Cledson Oliveira de Sousa

Resumo:

O rápido crescimento das tecnologias de redes sem fio, o surgimento de novos e variados dispositivos que oferecem ou precisam de interconexão com a Internet e uma brutal demanda reprimida por acesso banda larga esbarram no problema do esgotamento do espectro de freqüência dos serviços de telecomunicações. O necessário uso mais eficiente do espectro passa por algumas soluções, entre elas, o aperfeiçoamento e implementações de redes de rádios com capacidade cognitiva que possam compartilhar essas faixas de maneira transparente com pouca ou nenhuma interferência usuários primários em suas faixas licenciadas ociosas. Assim, o problema tratado nesse trabalho pode ser brevemente resumido na seguinte sentença: como dois dispositivos de comunicação, sem sincronização ou prévio conhecimento da presença um do outro, podem se encontrar no tempo e na frequência, em múltiplos canais de maneira garantida, para construção de um canal robusto que permita a troca de mensagens com mínima interferência na comunicação destes usuários primários? Deste modo, propomos o BiRD, um mecanismo assíncrono, distribuído, flexível e robusto que emprega um conceito bidimensional de escalonamentos, os externos visando baixa sobrecarga de controle e os D-designs, novos escalonamentos internos ótimos, para promover o encontro e a comunicação entre dois ou mais rádios cognitivos em tempo finito. Esse trabalho também inova na avaliação, abordando além de cenários ideais, os cenários com perdas, mostrando que o BiRD e os D-designs superam os similares presentes na literatura em até 150% no tempo médio para o primeiro encontro para uma dada sobrecarga de controle.

Palavras-chave: redes sem fio, rádios cognitivos, reúso espectral.

Autor(res):Peron Rezende de Sousa

Resumo:

A popularização dos dispositivos móveis com múltiplos recursos, a localização em tempo real e a disponibilidade da “computação humana”, provida por uma multidão global de usuários, motivaram o surgimento dos sistemas de Mobile Crowdsourcing. Esse novo paradigma apresenta vários requisitos, como assertividade na atribuição de tarefas, segurança, mecanismo de incentivo, suporte à mobilidade e escalabilidade. Nesta tese, escalabilidade é a capacidade de atender a uma demanda crescente sem perda de performance, ponto ignorado em muitas propostas que fazem uso do modelo tradicional (cliente-servidor). A solução deste problema também é o foco principal deste trabalho. Para resolver a questão revisamos o estado da arte e analisamos onde cada proposta falhou. Idealizamos uma nova arquitetura, intitulada Snow Flurry, e trabalhamos na implementação da mesma para realização de uma prova de conceito que confirmou sua viabilidade. Experimentos avaliaram o desempenho dos componentes que integram a solução e os resultados mostraram que a arquitetura oferece uma redução na latência entre 26,31% e 32,03%. Outro ponto interessante é que a Snow Flurry, ao contrário do estado da arte, não apresenta sobrecargas, alto custo e a necessidade de gerenciar dezenas de máquinas espalhadas pelo mundo. Ela também foi a primeira com suporte à mobilidade para sistemas de Mobile Crowdsourcing. Adicionalmente, esta tese contribui com a implementação do MktPoints que é um novo mecanismo de incentivo atrelado a um serviço de reputação. Inspirado em marketing de rede e nos efeitos psicológicos das recompensas variáveis, o MktPoints não compromete a escalabilidade do sistema e atua na atração/manutenção de trabalhadores sem necessariamente envolver motivadores extrínsecos.

Palavras-chave: Crowdsourcing, Internet do Futuro, Escalabilidade.

Autor(res):Carolina Medeiros Carvalho

Resumo:

Objetivando-se a redução dos erros nos diagnósticos, Sistemas de Suporte à Decisão Clínica (CDSS) têm sido utilizados para auxiliar os profissionais da saúde na avaliação e diagnóstico de pacientes. Tais sistemas sugerem, com base nos registros de saúde de certo paciente, um diagnóstico mais provável, o qual pode ser levado em consideração pelo médico ao decidir quanto ao diagnóstico do paciente. Para a sugestão do diagnóstico mais provável, os registros de saúde do paciente são casados com os atributos de um modelo previamente construído utilizando aprendizado de máquina, daqui para frente referenciado como modelo de decisão. Um problema atual é que a maioria dos CDSS está baseada em modelos de decisão estáticos. Nos modelos de decisão estáticos, o aprendizado do modelo é realizado uma única vez, antes do sistema de apoio ao diagnóstico ser posto em operação. Tais modelos estáticos não são refinados ou reconstruídos durante o uso do sistema e, portanto, não permitem que o médico especialista reporte o diagnóstico final para a melhoria do modelo. Na literatura, existem alguns trabalhos baseados em modelos de decisão dinâmicos, mas estes não são adequados à utilização simultânea por centros de saúde distintos que utilizam diferentes conjuntos de exames para diagnosticar a mesma doença, ou seja, utilizam práticas diagnósticas distintas. Nesta tese, propõe-se um modelo de decisão dinâmico e flexível, o qual é alimentado pelos diagnósticos finais reportados por médicos especialistas, sendo adequado a centros de saúde empregando práticas diagnósticas distintas, uma vez que permite que novos exames sejam definidos pelos médicos e o modelo de decisão automaticamente os inclui como atributos, caso sejam potencialmente relevantes para diagnosticar. O modelo de decisão dinâmico proposto baseia-se em um processo de aprendizado de máquina supervisionado que retreina o modelo através da seleção dos atributos considerados potencialmente relevantes, avaliação de vários cenários de pré-processamento e classificadores e seleção da combinação de cenário e classificador que alcança melhor desempenho na classificação considerando um conjunto de medidas. Na aplicação do modelo dinâmico proposto ao diagnóstico do comprometimento cognitivo, um CDSS foi projetado e desenvolvido para auxiliar médicos menos experientes ou especializados a decidirem sobre o diagnóstico de Demência, Doença de Alzheimer (DA) e Comprometimento Cognitivo Leve (CCL). Para cada paciente, o CDSS sugere o diagnóstico mais provável, os registros de saúde mais relevantes que levaram ao diagnóstico sugerido e, no caso de um fator de certeza baixo, o CDSS recomenda testes neuropsicológicos a serem realizados para confirmar ou refutar a sugestão diagnóstica inicial. O CDSS proposto é adequado para centros de saúde que utilizam diferentes conjuntos de testes neuropsicológicos para diagnosticar Demência, DA e CCL. Dados de pacientes do Centro de Doença de Alzheimer e outras Desordens Mentais na Velhice (CDA) do Instituto de Psiquiatria da Universidade Federal do Rio de Janeiro (UFRJ) e do Centro de Referência em Atenção à Saúde dos Idosos (CRASI) do Hospital Universitário Antonio Pedro da Universidade Federal Fluminense (UFF) foram usados para a realização de testes experimentais. CDA e CRASI aplicam conjuntos distintos não disjuntos de testes neuropsicológicos aos pacientes. Quando os dados do CRASI foram adicionados aos dados do CDA, o classificador final obtido para diagnóstico de CCL melhorou sua generalização com a inclusão de exames exclusivos do CRASI. Além disso, os testes experimentais mostraram que os classificadores obtidos para Demência, DA e CCL alcançaram desempenho competitivo na comparação com outros trabalhos da literatura baseados em modelos dinâmicos.

Palavras-chave: Modelo de Decisão Dinâmico; Sistemas de Suporte à Decisão Clínica; Diagnóstico Auxiliado por Computador; Modelos Preditivos; Demência; Doença de Alzheimer; Comprometimento Cognitivo Leve.

Autor(res):Igor Cesar Gonzalez Ribeiro

Resumo:

As Redes Elétricas Inteligentes representam uma evolução do sistema elétrico atual e são projetadas para atender, de forma segura e confiável, a crescente demanda por energia. Para tanto, além de uma infraestrutura de transmissão e distribuição de energia, as Redes Elétricas Inteligentes também implementam uma rede de comunicação de dados, utilizada para coletar informações e enviar comandos para os diversos componentes do sistema elétrico. Um desses componentes, conhecido como Infraestrutura de Medição Avançada (IMA), é responsável por garantir a comunicação entre os medidores de energia, agora conhecidos como medidores inteligentes, e o restante da rede de dados. Diferentes tecnologias de comunicação foram propostas para a implementação da IMA, mas dentre elas as Redes em Malha Sem Fio (RMSF) oferecem uma maior flexibilidade e capacidade de recuperação de falhas, garantindo maior resiliência. Entretanto, mesmo com os esses benefícios, quando um gateway falha na IMA, a rede pode levar algumas dezenas de segundos para se recuperar, provocando a perda de pacotes críticos. Em alguns casos, quando a falha é maliciosa, a rede pode nunca se recuperar, interrompendo a comunicação de certos medidores por um período indeterminado. Visando aumentar a resiliência da rede, este trabalho propõe o framework THOR, que utiliza proativamente um conjunto de gateways, de forma que se um deles falhar, as mensagens poderão continuar a ser entregues através dos demais, sem a necessidade de esperar o tempo de recuperação da rede. Além do framework em si, este trabalho também apresenta algumas propostas de implementação. Uma delas, denominada MDSA, foi capaz de entregar aproximadamente 100% das mensagens enviadas por todos medidores, mesmo em cenários com falha de
gateays, mas sem causar uma sobrecarga significativa na latência das mensagens, como ocorre em outra proposta relacionada encontrada na literatura.

Autor(res):Marcos Antonio Guerine Ribeiro

Resumo:

Uma tendência bastante comum na área de otimização combinatória é a concepção de abordagens híbridas. A metaheurística Data Mining GRASP (DM-GRASP), que combina a metaheurística GRASP com técnicas de mineração de dados, foi proposta baseando-se na hipótese de que padrões extraídos de soluções subótimas representam características des- sas boas soluções e, assim, poderiam ser usados para guiar a busca por melhores soluções. O DM-GRASP obteve sucesso em diversos problemas de otimização combinatória, tanto em termos de qualidade de solução, quanto em termos de tempo computacional. A hibri- dização de mineração de dados com metaheurísticas, no entanto, foi investigada somente em heurísticas multipartidas, principalmente as baseadas na metaheurística GRASP.

Neste contexto, o primeiro objetivo deste trabalho é ampliar o escopo da hibridiza- ção de metaheurísticas com técnicas de Mineração de Dados, utilizando a metaheurística Simulated Annealing (SA) como base. O principal desafio deste trabalho é, considerando essa nova estrutura de metaheurística, definir o tipo de padrão a ser extraído, em que momento a mineração será realizada e, ainda, como utilizar os padrões em benefício da heurística. Para realizar este estudo, dois problemas de otimização combinatória foram considerados: o Problema de Rotulação Cartográfica de Pontos e o Problema de Agru- pamento Capacitado com Centro Geométrico. Nesses problemas, a proposta consiste em inserir o módulo de mineração de dados em duas heurísticas baseadas em SA já existentes na literatura e competitivas com o estado-da-arte dos respectivos problemas.

O segundo objetivo desta Tese é explorar um novo problema de otimização combina- tória, denominado Problema de Dispersão de Arquivos em Serviços de Armazenamento em Nuvem. Esse problema teve origem em uma aplicação real, cujo objetivo é preservar a confidencialidade de dados gerados a partir da execução de workflows. Para isso, deve- se criar um plano de dispersão para distribuir os arquivos produzidos/consumidos por esses workflows em diversos serviços de armazenamento em nuvem, buscando minimizar os custos envolvidos no armazenamento e transferência de dados, respeitando a capaci- dade desses serviços e evitando que arquivos que contenham qualquer relação estrutural ou semântica entre si sejam alocados juntos. Assim, após a definição do problema no contexto de otimização combinatória, foram propostos um modelo matemático utilizando programação linear inteira e duas heurísticas baseadas nas metaheurísticas GRASP e SA.

Palavras-chave: Metaheurística, Simulated Annealing, GRASP, Mineração de Dados, Otimização Combinatória

Autor(res):Bruno Queiroz Pinto

Resumo:

Esta tese relata, na forma de uma coletânea de três artigos, aplicações de heurísticas baseadas em algoritmos genéticos com chaves aleatórias tendenciosas (BRKGA) em dois diferentes problemas de otimização: quasi-clique de cardinalidade máxima (MQCP) e minimização do número total de comprimentos de onda necessários para rotear demandas de caminhos óticos programadas (RWA-SSLD). Para o primeiro problema, as variantes de BRKGA propostas obtiveram melhores resultados quando comparadas aos obtidos pela heurística estado-da-arte da literatura. Já para o RWA-SSLD, os resultados do BRKGA proposto superaram os alcançados por uma heurística construtiva multipartida, e os obtidos pela heurística estado-da-arte da literatura. Todos os dados de entrada para as instâncias utilizadas nos experimentos computacionais relatados na tese e nos artigos associados estão disponíveis na plataforma Mendeley.

Palavras-chave: Algoritmos genéticos com chaves aleatórias tendenciosas; metaheurísticas; heurísticas; quasi-clique de cardinalidade máxima; minimização do número total de comprimentos de onda necessários para rotear demandas programadas.

Autor(res):Alexandre Ribeiro Silva Júnior

Resumo:

O recente avanço nas tecnologias e no mercado de Realidade Virtual vem abrindo novas oportunidades de interação e imersão. Juntamente com isto, técnicas mais acuradas de visão computacional, inteligência artificial e sensores de profundidade permitem realizar com mais precisão mapeamentos do mundo real, transpondo diversas informações para o cenário virtual. De fato, o conceito de realidade mista tem se tornado mais popular e inclusive substituído a terminologia de realidade virtual ou realidade aumentada, em muitos casos. Neste trabalho observamos que a tradicional taxonomia de Milgram e Colquhoun não são capazes de abranger com exatidão o potencial e as capacidades da realidade mista. Assim sendo, propomos inicialmente uma extensão de tal taxonomia e propomos o conceito de Realidade Virtual Pervasiva (RVP), sendo este um ambiente acrescido de elementos reais/físicos, incorporados ao ambiente virtual como objetos e usando dispositivos sensíveis ao contexto (por exemplo, sensores e tecnologia wearable). Além disto, propomos um detalhamento de requisitos e características da RVP, capaz de descrever a engenharia deste tipo de sistemas. Propomos também uma arquitetura e uma implementação de um sistema que atende parcialmente estes conceitos. Como prova de conceito, apresentamos a incorporação deste sistema em um game engine comercial, bem como exemplificamos seu uso em uma implementação prática.

Palavras-chave: Realidade Mista, Virtualidade Pervasiva, Pervasividade, Ciência de Contexto

Autor(res):Thiago Gouveia da Silva

Resumo:

O Problema da Árvore Geradora com Rotulação Mínima (MLSTP, do inglês minimum labeling spanning tree problem) é um problema de otimização combinatória que consiste em encontrar uma árvore de cobertura em um grafo com arestas rotuladas, isto é, um grafo no qual cada aresta possui um rótulo associado, utilizando o menor número de rótulos. Este problema é NP-difícil e tem atraído bastante atenção em pesquisas nos últimos anos. Por sua vez, o Problema Generalizado da Árvore Geradora com Rotulação Mínima (GMLSTP, do inglês generalized minimum labeling spanning tree problem) é uma generalização do MLSTP na qual se permite que múltiplos rótulos sejam associados a uma aresta. Ambos os problemas tem aplicações práticas em áreas importantes, como Projeto de Redes de Computadores, Projeto de Redes de Transporte Multimodais e Compactação de Dados. Esta tese aborda vários problemas de conectividade definidos em grafos com arestas rotuladas, em especial o Problema da Árvore Geradora com Rotulação Mínima e sua versão generalizada. As contribuições neste trabalho podem ser classificadas entre teóricas e práticas. Dentre as contribuições teóricas, introduzimos novos conceitos, definições, propriedades e teoremas úteis em relação a grafos com arestas rotuladas, bem como um estudo poliédrico sobre o GMLSTP. Dentre as contribuições práticas, propusemos novas heurísticas — como o algoritmo baseado na metaheurística MSLB e a heurística construtiva pMVCA — e métodos exatos — como novas formulações matemáticas e algoritmos branch-and-cut — para resolver o GMLSTP. Os experimentos computacionais realizados utilizando conjuntos de instâncias bem estabelecidos para o MLSTP são relatados, mostrando que as novas abordagens introduzidas neste trabalho alcançaram os melhores resultados para métodos heurísticos e exatos em comparação com estado da arte da literatura.

Palavras-chave: Grafo com arestas rotuladas; Árvore de cobertura; Meta-heurística; Combinatória poliédrica; Branch-and-bound.

Autor(res):Átila Arueira Jones

Resumo:

Resumo:

Esta tese aborda dois diferentes problemas. O primeiro é focado na classe dos cografos, onde usamos a representação de coárvores para desenvolver um algoritmo capaz de gerar, sem isomorfismos, todos os cografos com n vértices, cujo tempo de geração entre dois cografos consecutivos foi feito em tempo O(n). Em seguida aplicamos este procedimento para conjecturar uma nova cota para o número b-cromático de um cografo conexo, dada em termos do raio espectral. O segundo problema abordado é o estudo da complexidade do problema de obter o menor número de cliques disjuntas em arestas necessárias para particionar as arestas de G, chamado cp(G) Este problema já é conhecido como NP-completo para grafos em geral, inclusive para split, grafos K₄-livres e grafos cordais. Provamos que a NP-completude é mantida para a classe dos grafos 3-coloríveis, subclasse dos K₄-livre. Além disso, conseguimos obter a complexidade do problema para grafos (k,l), aqueles cujo conjunto de vértices pode ser particionado em k independentes e l cliques, estabelecendo quando o problema é NP-completo ou polinomial para cada k e l fixados.

Palavras-chave: cografo, gerador, partição de arestas em cliques, grafo-(k,l).

Autor(res):Giomar Oliver Sequeiros Olivera

Resumo:

Resumo:

Em aplicações médicas, o registro de imagens tem se tornado uma tarefa fundamental, permitindo aos especialistas interpretar e analisar imagens obtidas com diferentes tecnologias de aquisição ou em tempos distintos. Esta tese apresenta uma metodologia que permite registrar imagens térmicas da mama de protocolo dinâmico de aquisição, para isso é utilizada uma abordagem baseada na correspondência entre grafos geométricos. A metodologia tem seis etapas: pré-processamento de imagens; obtenção de estruturas lineares do termograma; representação por grafos da estrutura obtida; correspondência entre grafos; registro das imagens; e avaliação. Na primeira etapa, um pré-processamento nas imagens é realizado com o intuito de facilitar sua segmentação. Seguidamente, as estruturas internas das imagens são extraídas utilizando uma adaptação do algoritmo de Watershed por imersão seguido de uma esqueletização. Depois, estas estruturas são representadas mediante um grafo geométrico. Após isso, a correspondência entre grafos é determinada utilizando uma adaptação da distância de edição entre vértices, que além de considerar os relacionamentos estruturais de um vértice do grafo, utiliza a informação visual da imagem na vizinhança da aresta que liga dois vértices. A distância de edição é uma medida de similaridade e representa uma abordagem poderosa dentro dos métodos tolerantes a erros para correspondência entre grafos. Esta distância envolve operações básicas tais como remoção, adição, ou substituição de vértices e arestas. Na próxima etapa, é determinada uma transformação que possibilita alinhar uma imagem de entrada (sensível) a uma imagem fixa (de referência). Finalmente, para validar o método proposto são utilizadas medidas de similaridade baseadas na concordância (coeficiente de Dice, Jaccard, Sobreposição da referência) e de distância de Hausdorff das imagens. Essa abordagem é inédita em aplicações de termografia pois considera os relacionamentos estruturais presentes na imagem e é independente do banco de dados utilizado. Os experimentos realizados em imagens térmicas da mama mostram resultados positivos após a realização do registro em comparação com outras técnicas.

Palavras-chave: Registro de imagens, correspondência entre grafos, distância de edição, termografia

Autor(res):Claiton Luiz Soares

Resumo:

Resumo:

A infraestrutura celular está sobrecarregada com o crescente número de dispositivos e aplicações móveis. De acordo com a Cisco, o tráfego global de dados das redes celulares representa hoje 20% do tráfego IP na Internet quando em 2016 representava apenas 8%. Além disso, em 2021, o tráfego gerado por smartphones vai ultrapassar o tráfego gerado por computadores pessoais.  Uma solução para este problema é descarregar parte do tráfego da rede utilizando outra rede como canal de comunicação secundário. Muitos trabalhos na literatura propõem o uso de redes oportunistas como esse canal secundário. As redes oportunistas permitem que dois nós consigam se comunicar mesmo que nunca exista um caminho fim-a-fim entre eles.

Para se ter sucesso na comunicação oportunista, entretanto, os nós precisam cooperar uns com os outros para encaminhar mensagens e confirmar para a infraestrutura o recebimento das mensagens encaminhadas por outros nós. Esta tese avalia a influência dos nós egoístas no descarregamento de tráfego com redes oportunistas através de um estudo de caso. Nós egoístas são aqueles que não encaminham mensagens para outros nós ou não enviam reconhecimentos positivos para infraestrutura ou que combinam ambos os comportamentos. O impacto dos nós egoístas no descarregamento de tráfego com rede oportunista é avaliado por simulação. Resultados mostram que a eficiência do descarregamento é reduzida de 77% para até 19% com a presença de nós egoístas na rede. 

Em função dos resultados obtidos, esta tese propõe contramedidas com o objetivo de minimizar os efeitos da presença de nós egoístas, chamadas de ACKs duplamente identificados e ranking de encaminhamento. Com o ACK duplamente identificado, no momento em que um nó recebe a cópia de uma mensagem através do canal secundário, ele encaminha um ACK para a infraestrutura informando que recebeu a mensagem e de qual nó a recebeu na oportunidade do contato. Desta forma, a infraestrutura terá o controle de quais nós não estão enviando ACKs e prejudicando o calculo da taxa de infecção. Com o ranking de encaminhamento, a infraestrutura contabiliza o número de mensagens encaminhadas por cada nó com base nos ACKs enviados. A lista ordenada com o número de encaminhamento de cada nó servirá como critério de escolha para determinar para quais nós a infraestrutura irá enviar cópias da mensagem inicialmente e na fase de reinjeção para atender a função objetivo. Os resultados apresentaram uma diminuição  na carga de tráfego da infraestrutura em todos os cenários analisados, aumentando assim a eficiência do descarregamento de tráfego na presença de nós egoístas. No cenário em que os nós não enviam ACK e mensagens, com 60% de nós egoístas usando a função de objetivo Slow Start, à um aumento de eficiência no descarregamento de tráfego de 19% para 44%.

Palavras-chave: Redes Oportunistas, Redes tolerantes a atrasos e desconexões, comportamento egoísta, segurança.

Autor(res):Rogério Melo Nepomuceno

Resumo:

Resumo:

A árvore geradora de custo mínimo de um grafo G não direcionado, conexo e com custos nas arestas é uma árvore geradora onde o somatório dos custos das arestas é mínimo. O diâmetro dessa árvore é definido como o número máximo de arestas dentre todos os caminhos da árvore. O problema da árvore geradora mínima com diâmetro limitado (Bounded-Diameter Minimum Spanning Tree Problem – BDMSTP) consiste em encontrar uma árvore geradora para G cujo diâmetro não exceda a um limite D, 2 £ D £ n – 1, onde n é o número de vértices de G, e que tenha custo mínimo. Esse problema é NP-difícil para 4 £ D < n – 1. Aplicações da árvore geradora de custo mínimo com diâmetro limitado surgem em problemas de engenharia, como projetos de redes de telecomunicações e de fibra ótica, problemas de compressão de dados e projeto de sistemas distribuídos, quando considerada a exclusão múltipla. Métodos exatos para resolver o BDMSTP só conseguem resolver pequenas instâncias do problema, com no máximo 161 vértices e diâmetro menor ou igual a oito. Desse modo, heurísticas construtivas e heurísticas baseadas em metaheurísticas tentam encontrar uma solução próxima do ótimo para o problema em um tempo aceitável. Se os vértices do grafo de entrada estão associados a pontos no plano Cartesiano, temos o Euclidean Bounded-Diameter Minimum Spanning Tree Problem – EBDMSTP. Esta tese apresenta e analisa as heurísticas mais conhecidas na literatura para o EBDMSTP, propõe uma nova heurística construtiva para o problema, e ainda outra heurística baseada no método Iterated Local Search (ILS), analisando os seus resultados com os existentes na literatura.

Palavras-chave: Árvore geradora, Árvore geradora Euclidiana de custo mínimo com diâmetro limitado, Iterated Local Search, ILS, Heurísticas.

Autor(res):Helga Dolorico Balbi

Resumo:

Resumo:

A instabilidade de associação é um fenômeno comum em redes IEEE 802.11 densas. A decisão de realização de handoff entre pontos de acesso é uma prerrogativa exclusiva das estações cliente. Mesmo sem mobilidade, estes dispositivos podem decidir migrar para um novo ponto de acesso com o objetivo de obter melhor desempenho. Entretanto, os critérios utilizados para a realização do handoff não são definidos no padrão, ficando a cargo das implementações dos fabricantes. Nesta tese, resultados de uma análise baseada em dados obtidos a partir de uma rede de larga escala em produção na Universidade Federal Fluminense demonstram que tais implementações são comumente deficientes, resultando em grande instabilidade de associação. Após a análise do código fonte implementado em dispositivos comumente encontrados na rede e realização de testes experimentais em redes reais, conclui-se que esta instabilidade, conhecida por efeito “ping-pong”, ocorre devido ao uso direto de amostras de RSSI, que, conforme será mostrado, apresentam grande variabilidade no tempo. Após profunda análise de traces de RSSI coletados utilizando-se o testbed FIBRE em ambientes indoor, conclui-se que a série temporal do RSSI apresenta distribuição multimodal com modas locais referentes a RSSIs com valores baixos, ou seja, deslocadas à esquerda da moda global. Estas modas são referentes a vales de RSSI que ocorrem frequentemente em rajadas com pequenos tamanhos. Tendo este comportamento como motivação, um novo e simples mecanismo de filtragem denominado Máximo é proposto com o objetivo de eliminar os vales da série temporal do RSSI. Isto é alcançado através da escolha do valor máximo do RSSI a partir de uma janela deslizante contendo as últimas amostras recebidas. Por fim, emulações baseadas em traces reais de RSSI em cenários estáticos e móveis são realizadas para comparação do desempenho do filtro Máximo em relação a mecanismos comumente encontrados na literatura. Os resultados mostram que, dentre os mecanismos testados, o Máximo é capaz de oferecer melhor tradeoff em relação ao atraso e estabilidade em cenários móveis, além de efetivamente eliminar 100% dos ping-pongs na maioria dos cenários estáticos.

Palavras-chave: redes IEEE 802.11 densas, WLAN, handoff, efeito ping-pong, instabilidade de associação

Autor(res):Wilton de Paula Filho

Resumo:

Resumo:

Tweets, no cenário eleitoral, têm sido utilizados em pesquisas científicas sob diversas perspectivas, por exemplo para predizer o resultado de eleições presidenciais e para investigar reações de eleitores durante eventos, como debates eleitorais. A mineração de opiniões tem sido uma das abordagens utilizadas para avaliar a opinião expressa por usuários nesse tipo de mensagem. Melhorar a acurácia do sentimento dessa categoria de tweet tem sido um dos desafios enfrentados pelos pesquisadores, devido alguns fatores, tais como a quantidade limitada de caracteres permitidos em um tweet e o uso de hashtags e slogans de campanha para expressar opiniões políticas sobre candidatos. No cenário de eleições, hashtags têm sido utilizadas em tweets com uma frequência cada vez maior. Em diversos trabalhos reportados na literatura, hashtags têm sido utilizadas para coletar e selecionar tweets, rotular mensagens, além de receberem tratamentos especiais na fase de pré-processamento ou são simplesmente descartadas das análises. A contribuição de hashtags na análise de sentimentos de tweets no cenário eleitoral tem sido pouco explorada. Neste trabalho, são consideradas duas categorias de hashtags, as políticas e as não-políticas, e dois novos atributos baseados em hashtags políticas, denominados TPSB e DPSB, que refletem na melhoria do desempenho de algoritmos de aprendizado de máquina supervisionado, utilizados no processo de classificação do sentimento de tweets no cenário eleitoral. A análise experimental proposta neste trabalho, foi realizada a partir de duas amostras rotuladas manualmente contendo mensagens coletadas em períodos de eleições presidenciais, cada uma com, aproximadamente, 4.000 tweets. Foi avaliada a contribuição do uso das hashtags contidas em tweets e em descrições de perfis de usuários, e atributos para a melhoria da acurácia de classificadores baseados em Naive Bayes (NB), Multinomial Naive Bayes (MNB) e Support Vector Machine (SVM). Nos testes realizados com uma das amostras, as hashtags políticas foram responsáveis por aumentar, com significância estatística, as acurácias de todos os classificadores. Em outro dataset, as acurácias de todos os classificadores foram incrementadas e, em 66% dos casos, os aumentos obtidos foram estatisticamente significantes. Em um dos experimentos propostos, a acurácia do algoritmo NB, utilizando o formato unigrama, foi incrementada em 3,2% ao considerar hashtags políticas nas análises. Os resultados obtidos sugerem que hashtags contendo palavras fazendo referência a candidatos, a partir do primeiro nome e/ou sobrenome deles associado a outras palavras/números, slogans de campanha e palavras de repúdio, podem ser úteis na classificação do sentimento de tweets políticos e que usuários do Twitter, durante períodos de campanha eleitoral, expressam opinião política não somente a partir de tweets, mas também a partir de suas descrições de perfis.

Palavras-chave: twitter, tweet, hashtag, descrição do perfil do usuário, política, mineração de opinião, análise de sentimentos.

Autor(res):Matheus Bousquet Bandini

Resumo:

Resumo:

Supercomputadores e Data centers cada vez maiores são utilizados para auxiliar pesquisadores a resolverem os complexos problemas científicos. Porém, para torná-los economicamente viáveis, eles devem ser compartilhados, transformando-os em sistema multi usuários. Já se foi o tempo em que os usuários detinham acesso exclusivo aos recursos, pois em sistemas relativamente pequenos, a taxa de utilização desses recursos era baixa. Portanto, sistemas de gerenciamento de recursos agora têm a responsabilidade de prover recursos dedicados para cada usuário do ambiente, enquanto promovem também o compartilhamento dos recursos do sistema compartilhado de maneira eficiente.

A maioria dos sistemas escalonadores de aplicações empregam um esquema de fila que fazem as aplicações aguardarem até que os recursos que elas necessitam para executar estejam disponíveis. O conjunto de recursos utilizados é definido pelo usuário e é tipicamente a quantidade necessária para minimizar o tempo de execução da aplicação. Isto, no entanto, tende a causar um efeito adverso sobre a utilização do sistema, pois alguns recursos podem permanecer ociosos, e sobre o tempo de turnaround da aplicação, uma vez que essa abordagem pode aumentar o tempo que a aplicação precisa aguardar na fila até que os recursos solicitados fiquem disponíveis. Em contraste a essa abordagem tradicional, na qual os recursos são alocados exclusivamente a uma aplicação, esta tese propõe e avalia a adoção de uma estratégia descentralizada de escalonamento de aplicações que contempla o compartilhamento de recursos entre as aplicações. Ao invés de um ou mais gerenciadores de recursos, cada aplicação é responsável pela sua própria alocação de recursos, o que permite uma utilização mais dinâmica e aprimorada do sistema. A avaliação da estratégia proposta foi realizada por meio da execução simultânea de aplicações que compartilharam recursos de processamento. Os experimentos mostraram que a adoção da estratégia proposta permite aumentar a vazão dos recursos de processamento, o que beneficia os provedores de serviços. Ao mesmo tempo, foi possível também reduzir o tempo necessário para executar o conjunto de aplicações, resultado relevante para os provedores de serviço como para os usuários. Por ser capaz de ajustar a grau de compartilhamento entre aplicações, acreditamos que esta nova abordagem seja mais flexível no que se refere a possíveis escalonamentos de aplicações. Por ser também uma abordagem distribuída, pode tornar o problema de escalonamento de aplicações em maiores escalas mais tratável. Estas aplicações autonômicas exploram o uso dos recursos para reduzir o tempo necessário para executar um workload (ou conjunto de aplicações). Isso é alcançado por intermédio da capacidade da aplicação paralela de medir a sua utilização em cada um dos recursos do ambiente que ela utiliza e por meio da adoção de um esquema inovador usado para simular as políticas de fila das abordagens tradicionais.

Palavras-chave: Escalonamento de aplicações autonômicas,  Compartilhamento de recursos computacionais, Escalonamento decentralizado.

Autor(res):Philippe Leal Freire dos Santos

Resumo:

Resumo:

O Problema da Partição Cromática de Custo Mínimo (PPCCM), considerado uma das diversas variantes do Problema Clássico de Coloração de Grafos (PCG), utiliza números reais como custos das cores, tendo como objetivo colorir os vértices de um grafo de modo que os adjacentes tenham cores diferentes e a soma dos custos das cores utilizadas seja mínima. Embora seja um problema NP-Difícil para grafos em geral, foram elaborados algoritmos polinomiais para algumas poucas classes de grafos. Do ponto de vista prático, o mesmo foi empregado no projeto de circuitos VLSI e na solução de determinados problemas de escalonamento modelados como grafos de intervalo. Nesta tese são propostos algoritmos para o PPCCM considerando um grafo simples não-direcionado como entrada. Inicialmente foram desenvolvidas duas heurísticas baseadas na metaheurística Algoritmos Genéticos com Chaves Aleatórias Tendenciosas (Biased Random Key Genetic Algorithms – BRKGA, em inglês). Posteriormente, foi implementada uma heurística de trajetória que faz uso de duas estratégias de busca local seguidas por um procedimento de path-relinking. Para os experimentos computacionais foram geradas instâncias para o problema a partir de grafos comumente empregados no PCG.

Palavras-chave: Problema da Partição Cromática de Custo Mínimo, Coloração de Grafos, Heurísticas, Metaheurísticas, Busca Local, Algoritmos Genéticos.

Autor(res):Leonardo Maricato Musmanno

Resumo:

Resumo:

O conceito de similaridade entre objetos é fundamental na área de reconhecimento de padrões. Na chamada “abordagem estrutural”, grafos são frequentemente utilizados para representar objetos. Assim sendo, é preciso definir um meio de medir a similaridade entre dois grafos. Uma das ferramentas mais utilizadas para realizar essa medição é a distância de edição, que consiste em medir a distância entre dois grafos de acordo com o grau de distorção necessário para transformar um grafo no outro. O grafo mediano generalizado de um conjunto de grafos S é aquele que minimiza a soma das distâncias dos grafos de S a ele e que melhor captura as informações desse conjunto de grafos, podendo ser considerado um representante deste conjunto. O conceito de grafo mediano já foi aplicado com sucesso em áreas como reconhecimento de símbolos gráficos, identificação biométrica e clusterização de imagens, entre outros. No entanto, computar o grafo mediano generalizado de um conjunto de grafos é uma tarefa complexa. Por si só, a versão de decisão do problema de cálculo da distância de edição entre dois grafos é NP-Completo. Algoritmos exatos lidam apenas com grafos de tamanho relativamente pequeno, sendo de pouca utilidade prática. Nesta tese são propostos três algoritmos aproximados para o problema, um deles baseado em uma estratégia gulosa e os outros dois baseados nas meta-heurísticas GRASP e BRKGA, além de dois novos resultados teóricos, um deles servindo de base para uma variação do algoritmo BRKGA. Os resultados obtidos indicam que os algoritmos podem ser utilizados para encontrar soluções aproximadas de boa qualidade em tempos computacionais razoáveis.

Palavras-chave: Reconhecimento de padrões, correspondência entre grafos, distância de edição, algoritmos gulosos, GRASP, BRKGA, grafo mediano.

Autor(res):Julio Cesar Ferreira

Resumo:

As abordagens tempo-frequência são ferramentas fundamentais para a representação e a análise de sinais com conteúdo espectral variável no tempo, as mais tradicionais dentre elas sendo a transformada de Gabor, a transformada de Wigner e a  transformada S. As transformadas de Gabor sintonizadas (Signal-Tuned Gabor Transforms – STGT) são uma abordagem recente que incorpora aspectos das três anteriores, e que apresenta a característica de analisar cada sinal por meio de funções de representação do próprio sinal. A STGT foi originalmente introduzida em duas versões – uma no domínio temporal, e outra no domínio espectral – mas extensões e generalizações já foram propostas, permitindo, por exemplo, a análise de um sinal pelas funções de representação das suas derivadas em qualquer ordem. Aqui nós reportamos os resultados de um estudo sobre a abordagem de Gabor sintonizada em suas múltiplas versões, focando numa área de aplicação específica: a análise de distúrbios em sistemas elétricos de potência (SEP). O nosso trabalho investigou o desempenho da abordagem sintonizada em tarefas de identificação e classificação de distúrbios dos SEP, considerando, para efeito comparativo, também as transformadas de Gabor, S e de Wigner.  Bancos de sinais sintéticos e reais foram empregados nesse estudo, assim como diferentes estratégias de classificação, entre elas as Redes Neurais Artificiais, as Máquinas de Vetor de Suporte e as Árvores de Decisão. A nossa análise indica que, de modo geral, a abordagem sintonizada fornece representações tempo-frequência de melhor qualidade, e alcança taxas de classificação mais elevadas do que aquelas fornecidas pelas transformadas tradicionais, destacando-se a STGT espectral e as variantes baseadas na representação da primeira derivada do sinal. Uma aproximação da STGT aqui introduzida, a STGTω₀, também pode se mostrar vantajosa em aplicações a sistemas de potência.

Palavras-chave:  Análise Tempo-Frequência; Transformada de Gabor Sintonizada; Sistemas Elétricos de Potência; Classificação de Distúrbios.