Este projeto de pesquisa é a continuação do projeto que estudou grafos rotulados, grafos graciosos e problemas de coloração com restrições nas arestas (PIB-E/0217/2014 - Sobre Grafos Rotulados, Graciosos e Colorações), do Programa de Iniciação Científica 2014/2015, do CNPq e da UFAM, do qual a presente aluna é bolsista. No PIBIC anterior, estudou-se alguns casos especiais de rotulação de grafos. O foco estava nos chamados grafos graciosos e em alguns problemas de coloração. Um grafo gracioso é um grafo rotulado onde o módulo da diferença entre os rótulos de dois vértices adjacentes é igual a um rótulo único para cada aresta, de modo que as arestas recebem uma sequência de inteiros como rótulos. Com esta proposta de renovação, se dará continuidade ao estudo de variações do problema, agora enfatizando o problema da t-coloração em grafos, onde existe um conjunto proibido de valores a serem considerados na restrição de adjacência para coloração dos vértices do grafo.

Este projeto de pesquisa é a continuação do projeto PIBIT PIT-E/0023/2014, do Programa de Iniciação Científica 2014/2015, do CNPq e da UFAM, do qual o presente aluno é bolsista. No PIBIT, está sendo desenvolvida uma ferramenta computacional para a determinação do DAP (Diâmetro da Altura do Peito), através de uma fotografia digital, que envolve conceitos de geometria computacional, processamento de imagens e fotogrametria, de tal forma que possa agilizar o processo de inventário florestal realizado em campo, que também pode compor um sistema computacional de todo o processo. Deste modo, a proposição deste PIBIC dará continuação ao estudo técnico-científico iniciado, onde agora, objetiva-se estudar modelos teóricos de otimização combinatória aplicados ao entendimento de sistemas ambientais e florestais, através da aplicação de técnicas de sensoriamento remoto e de aprendizagem de máquina. Um dos pontos é tentar otimizar o processo de detecção de clareiras (por desmatamento, fenômenos físicos ou geológicos) em imagens de satélite, radar e de LiDAR, utilizando tal ferramental teórico.

Nesta tese estudam-se as implicações da introdução no modelo de Computação Quântica do conceito de Sistema de Representação Redundante, em particular no que concerne à eficiência de Algoritmos para Aritmética. Têm vindo a ser apresentadas diversas considerações favoráveis sobre a exequibilidade de modelos de Computação Quântica em que a unidade de informação, o qudit, admite mais do que os dois níveis distintos proporcionados pelo qubit. O problema da equivalência, ou não, em termos de Complexidade Computacional entre modelos baseados em qubits e aqueles baseados em qudits encontra-se apenas parcialmente resolvido. A análise da Complexidade Computacional de modelos em que se consideram misturas de diferentes unidades de informação, denominados Sistemas Quânticos Híbridos, é uma área praticamente inexplorada. Assim, propõe-se um modelo formal para Computação Quântica nestes sistemas híbridos, generalizando, por inclusão, os modelos baseados em qubits e qudits. Com base no modelo proposto, desenvolvem-se duas classes de circuitos quânticos, com profundidade constante, para a adição das representações de dois números num qualquer sistema redundante. Estabelecem-se ainda condições para a aplicação de um algoritmo de adição, em tempo constante, de um número polinomial de representações redundantes de números. Como consequência, justifica-se a existência de classes de circuitos quânticos, com profundidade constante, para aproximar a soma de um número polinomial de representações redundantes. Por fim, descrevem-se as principais características de um Simulador Simbólico para Algoritmos em Computação Quântica, seguindo-se uma análise de resultados obtidos em simulações do algoritmo de Grover.

Esta dissertação tem como principal objectivo a apresentação de um conjunto de algoritmos que determinam invólucros convexos no espaço bidimensional e no espaço tridimensional. Para tal, começa-se por efectuar um estudo breve sobre conjuntos convexos, apresentando os resultados mais significativos deste tipo de conjuntos. Em seguida, são apresentados algoritmos que determinam invólucros convexos no plano, efectuando-lhes um estudo em termos de complexidade e comparando-os, sempre que oportuno, com outros algoritmos. Finalmente, é feita a extensão de dois destes algoritmos ao espaço tridimensional.

Nas últimas décadas, os avanços na indústria de semicondutores possibilitaram um grande desenvolvimento no campo de sistemas multimédia, principalmente devido ao contínuo aumento de poder computacional e à disponibilidade de infraestruturas de comunicação confiáveis. Diversos padrões de compressão de vídeo foram desenvolvidos neste período com o objetivo de reduzir as taxas de bits sem afetar a qualidade do vídeo codificado. O padrão High Efficiency Video Coding (HEVC), recentemente lançado pelo Joint Collaborative Team on Video Coding (JCT-VC), tornou-se o estado-da-arte em compressão de vídeo e deve gradualmente substituir o seu predecessor, o H.264/AVC, dentro de poucos anos. O HEVC provê elevados níveis de compressão em comparação com outros padrões, mas tais ganhos são associados a grandes aumentos na complexidade computacional e, consequentemente, no tempo da codificação, prejudicando ou até mesmo impedindo a operação do codificador em dispositivos portáteis e em sistemas de tempo real, especialmente para vídeos de alta resolução. O foco desta tese concentra-se na complexidade computacional de codificadores HEVC, com contribuições que se estendem desde a análise da eficiência de compressão e da complexidade computacional do padrão até a redução e o ajuste dinâmico da sua complexidade de codificação. A primeira contribuição desta tese é uma análise detalhada das funcionalidades e ferramentas de codificação que compõem o HEVC, a qual foi realizada com vistas à identificação das operações mais complexas do processo de codificação. Cinco algoritmos para escalonamento dinâmico da complexidade de codificação representam a segunda contribuição da tese. Todos eles se baseiam no ajuste das novas estruturas de particionamento de trama introduzidas pelo novo padrão, nomeadamente as Unidades de Codificação e as Unidades de Predição, as quais foram identificadas como responsáveis por uma grande parcela da complexidade computacional do codificador HEVC. O melhor algoritmo de escalonamento desenvolvido provê reduções de até 50% na complexidade computacional com perdas negligenciáveis na eficiência da compressão e reduções de até 80% com perdas pequenas ou médias. A terceira contribuição desta tese consiste em um conjunto de esquemas de finalização antecipada baseados em técnicas de mineração de dados, os quais procuram reduzir a complexidade computacional demandada pelos processos de decisão das melhores estruturas de particionamento de trama, nomeadamente as Árvores de Codificação, as Unidades de Predição e as Árvores Residuais Quadráticas. Embora os esquemas não permitam escalonamento dinâmico, reduções de até 65% na complexidade computacional foram obtidas com perdas muito pequenas na eficiência de compressão. Finalmente, a quarta contribuição da tese consiste em um sistema de controlo que utiliza as três contribuições anteriores com a finalidade de ajustar o tempo de codificação sempre que necessário, com o objetivo de mantê-lo abaixo de um determinado alvo. O sistema de controlo utiliza configurações de codificação pré-definidas, as quais foram criadas a partir de combinações dos esquemas de finalização antecipada e de modificações na parametrização das ferramentas com maior complexidade computacional no codificador HEVC. Sobretudo, os métodos propostos nesta tese são especialmente úteis em dispositivos multimédia portáteis com limitação energética, possibilitando a redução do consumo de energia elétrica e um consequente prolongamento da duração das suas baterias. Além disso, os métodos também podem ser aplicados a dispositivos multimédia portáteis e não-portáteis que operam em tempo real com recursos computacionais limitados.