[pt] Este trabalho procura motivar e propor direções para uma abordagem de rudimentos da Teoria de Grafos nos anos finais da educação secundária brasileira. Os conceitos básicos da teoria são apresentados no contexto de desafios lúdicos e situações cotidianas. Procura-se ainda destacar a interdisciplinaridade e a atualidade do tema, apresentando exemplos provenientes de ramos tão diversos como eletrônica, transportes, arqueologia e genética. / [en] This work makes a case for the inclusion of some rudimentary Graph Theory in the final years of secondary education in Brazil, and also puts forward some suggestions of approach. The most basic concepts are presented in a light key, taking advange of puzzles and day to day situations. An effort was made to highlight the connections and applications of the theory to many branches of science and technology, such as electronics, transports, archeology and genetics.

[pt] A área das telecomunicações tem presenciado consideráveis avanços tecnológicos dos dispositivos móveis (e. g. telefones inteligentes, relógios inteligentes, tablets, reprodutores de música, entre outros) e da sua crescente popularidade. Dado que esses equipamentos possuem uma série de sensores embutidos como o sistema de posicionamento global, câmera, microfone, bússola, acelerômetro entre outros, e ao mesmo tempo mantêm acesso contínuo às redes de comunicações, eles apresentam uma oportunidade para realizar sensoriamento em grande escala de possíveis eventos do mundo físico e compartilhar os dados obtidos através da internet. Este novo tipo de sensoriamento é conhecido como sensoriamento coletivo móvel ou MCS (Mobile crowd sensing) por sua sigla em inglês, e recentemente tem sido o foco de diversas pesquisas. O maior potencial do MCS é a opção de desenvolver um inúmero de funcionalidades a partir dos próprios recursos internos dos dispositivos móveis e aproveitar seu modelo de mobilidade, baseado no comportamento humano. Em contrapartida existem questões que devem ser consideradas na hora de desenvolver uma rede baseada em MCS. Neste trabalho, apresenta-se a análise realizada sobre os pontos críticos para a criação de uma rede MCS e a partir dos mesmos são apresentadas soluções que permitam criar uma implementação o mais próximo possível da realidade. Foi desenvolvido um modelo de mobilidade para a cidade de Rio de Janeiro baseado na teoria dos grafos, considerando que as atividades diárias das pessoas serão as que definam seu padrão de movimento. A cooptação de usuários é outro dos principais problemas que tem que ser abordado quando se pensa no sensoriamento coletivo móvel. Propõe-se dois modelos de incentivo que consideram e modelam como variáveis as motivações intrínsecas e extrínsecas dos usuários na decisão de participação em uma rede MCS. Consideram também distintos graus de motivação para cada usuário com a finalidade de demonstrar que a resposta dos participantes aos incentivos não é homogênea. O primeiro modelo baseia-se nas respostas consecutivas dos usuários e o segundo baseia-se na teoria de jogos. Em ambos, as decisões tomadas pelos usuários só consideram informações locais ou próprias. Os resultados obtidos permitiram comprovar que os modelos de incentivo propostos conseguem estimar satisfatoriamente o tipo de usuário com o qual está se interagindo e a quantidade de incentivo que deve ser oferecido a cada um deles, além de demonstrar as vantagens de um sistema de incentivo que considera pagamentos variáveis. Também foram analisadas as vantagens de considerar a mobilidade humana neste tipo de abordagem e como a mesma reflete nos modelos de incentivo. / [en] The world of telecommunications has witnessed the growing popularity of mobile devices and its huge technological advancements and innovations (e.g. smartphones, smartwatches, tablets, music players among others). These devices have a series of built-in sensors that measure motion, orientation, and various environmental conditions (e.g. Global Positioning System, camera, microphone, compass, accelerometer, among others). In addition, these devices have continuous network connectivity. So these devices can be seen as a huge opportunity to carry out large-scale sensing of events in the physical world and have the ability of sharing the data obtained through the internet. This new kind of sensor application is known as Mobile crowd sensing (MCS) and it has been a research focus lately. The greatest potential of MCS is found on the versatility that the embedded resources of the mobile devices offer in the development of innumerable functionalities and its mobility model that is based on human behavior. On the other hand, there are issues that must be considered when a MCS-based network is developed. This work presents the analysis performed in order to define issues that are considered critical for the creation and development of an MCS network. From these definitions solutions are proposed that allow to create an implementation as close as possible to reality. A mobility model was developed for the Rio de Janeiro city based on graph theory, and assuming that daily activities of the people will define their movement pattern. Attracting and convincing users is another problem that has to be addressed. Two user incentive models are proposed. Both consider and model the decision of a user to participate in an MCS network based on the intrinsic and extrinsic motivations of the user. The idea is to comprise different levels of motivation for each user in order to demonstrate that the response of the participants to the incentives is not homogeneous. Thus, the first model is based on the consecutive answers of the users and the second model is based on game theory. The results obtained allowed us to prove that the proposed incentive models can satisfactorily estimate the type of user with which we are interacting and the amount of incentive that should be offered to each one of them, besides demonstrating the advantages of an incentive system that considers variable payments. The advantages of considering human mobility in this type of approach and how it affects the incentive models was also analyzed.

[pt] As redes de sensores sem fio se constituem numa área que outorga grandes oportunidades para a oferta de uma série de aplicações inovadoras e com baixo custo. Os dispositivos destas redes são bastantes pequenos e sua fonte de alimentação são baterias. O tempo de vida destas é limitado, limitando assim o tempo da vida dos sensores e da rede como um todo. Por esta razão nos últimos anos o tema de eficiência energética tem atraído grande interesse de pesquisadores. O aumento do custo da energia e do consumo global da energia pelo setor de ICT (Information and Communications Technologies) têm crescido vertiginosamente devido ao aumento continuo do número de clientes e da demanda por aplicações de maior complexidade. Por tudo isso têm sido desenvolvidos distintos métodos e técnicas para economizar energia nas RSSF. Neste trabalho se implementam dois algoritmos que levam em conta critérios para economizar os custos de energia da rede e através de experimentos de simulação se avalia os mesmos. Nos resultados pode se observar as vantagens de trabalhar com sistemas que visam a eficiência energética. / [en] The WSNs (Wireless Sensor Networks) belong to an area that gives rise to great opportunities to spread innovative and low cost applications. These kinds of networks are composed of tiny devices with limited energy. The main source of power supply for WSNs are batteries, which are limited in cycle life, thus limiting the sensors lifetime and the network as a whole. Due to that fact, the energy efficiency network is becoming the main concern to be addressed by researchers. Rising energy prices and global energy consumption by the ICT (Information and Communications Technologies) sector have grown dramatically due to the continuous increase in customer number and the demand for more complex applications. For the reasons outlined above, different energy-saving techniques for WSNs have been developed. Two energy-saving algorithms for WSNs were implemented in this thesis, and they were tested by experimental evaluation using simulation. The results obtained from the simulations showed the advantages of working with systems aiming at energy efficiency.

[pt] Nessa dissertação vamos introduzir, elaborar e combinar ideias da Teoria de martingais, a Teoria de grafos aleatórios e o Teorema Central do Limite. Em particular, veremos como martingais podem ser usados para representar desvios de contagem de subgrafos. Usando esta representação e o Teorema Central do Limite para martingais, conseguiremos demonstrar um Teorema Central do Limite para a contagem de subgrafos livres de triângulos no grafo aleatório Erdos-Rényi G(n,m) . Além disso, nossa demonstração também nos trará informação sobre a taxa de convergência, mostrando que a distribuição dos desvios converge rapidamente para a distribuição normal. / [en] In this dissertation we shall introduce, elaborate and combine ideas from martingale Theory, random graph Theory and the Central Limit Theorem. In particular, we will see how martingales can be used to represent deviations of subgraph counts. Using this representation and the Central Limit Theorem for martingales, we will be able to demonstrate a Central Limit Theorem for the triangle-free subgraph count in the Erdos-Rényi G(n,m) random graph. Furthermore, our proof also gives us information about the rate of convergence, showing that the distribution of deviations converges rapidly to the normal distribution.

[pt] Essa dissertação explora o problema roteamento de linhas de transmissão (LT) através da solução do caminho mais curto em um grafo sem ciclos de melhoria, considerando custos quadráticos para arcos adjacentes. Esse problema é conhecido como o Problema do Caminho Mínimo Quadrático Adjacente (CMQA). Esse trabalho apresenta uma descrição teórica do CMQA, propõe uma extensão do algoritmo Dijkstra (aqDijkstra) para solução de CMQA em tempo polinomial e discute como o algoritimo pode ser utilizado em metodologias de roteamento de LT. Em seguida, apresentamos uma melhoria estendendo o algoritmo A estrela para sua forma adjacente quadrática (aqA estrela), incluindo uma etapa de busca reversa para estimação de custos de chegada. Foram feitos experimentos computacionais contemplando a variação de custos quadráticos, geração de instâncias aleatórias, testes de estresse e comparação com abordagens já utilizadas na literatura. Os resultados sugerem que: (i) aqA estrela teve o melhor desempenho, atingindo tempos de busca 40 vezes mais rápidos que aqDijkstra e 50 vezes mais rápido que a abordagem mais rápida apresentada pela literatura; (ii) a eficiência dos algoritmos não foi afetada pela variação dos custos quadráticos; (iii) os algoritmos propostos aqA estrela e aqDijkstra também foram mais eficientes nas instancias aleatórias, reafirmando a superioridade dos mesmos. Duas aplicações são apresentadas, uma de objetivo ilustrativo e outra para um caso real. O algoritimo aqA estrela foi usado para solução de um CMQA em um grafo de quase um bilhão de arcos quadraticos, resultado em uma rota proposta com custos adicionais três vezes menor. / [en] This dissertation explores the problem of transmission line (TL) routing through finding the shortest path on an undirected graph with no improving cycles, considering quadratic costs for adjacent arcs. This problem is known as the Adjacent Quadratic Shortest Path Problem (AQSPP). This work provides the theoretical background for the AQSPP, proposes an extension of Dijkstra s algorithm (aqDijkstra) for solving AQSPP in polynomial-time and discusses how AQSPP can be included in routing methodologies. Furthermore, it is presented an improvement to the algorithm: the adjacent quadratic A star (aq A star) with a backward search for cost-togo estimation, to speed up search. For computational experiments, aqDijkstra and aqA star are benchmarked with other algorithms from the technical literature. The search behavior of the algorithms is also studied within different tests, including: quadratic cost variation, randomly generated graph instances and increasingly larger instances. The numerical results suggests that: (i) aqA star outperformed all the other algorithms, being 40 times faster than aqDijsktra and 50 times faster than the fastest benchmark algorithm; (ii) the studied algorithms do not lose efficiency as quadratic costs increase; (iii) aqA star and aqDijkstra were faster benchmark algorithms under random graph instances, indicating their robustness. Two applications are provided, one for illustrative purposes, and another to study performance on a real application. The aqA star algorithm solved an AQSSP on a graph with almost a billion quadratic arcs and provided a route with three times lower additional costs.