Graph structures can often be used to describecomplex data sets. In many applications, the graph structureis not known but must be inferred from data. Furthermore, realworld data is often naturally described by sparse graphs. Inthis project, we have aimed at recreating the results describedin previous work, namely to learn a graph that can be usedfor prediction using an ℓ1-penalised LASSO approach. We alsopropose different methods for learning and evaluating the graph. We have evaluated the methods on synthetic data and real-worldSwedish temperature data. The results show that we are unableto recreate the results of the previous research team, but wemanage to learn sparse graphs that could be used for prediction. Further work is needed to verify our results. / Grafstrukturer kan ofta användas för att beskriva komplex data. I många tillämpningar är grafstrukturen inte känd, utan måste läras från data. Vidare beskrivs verklig data ofta naturligt av glesa grafer. I detta projekt har vi försökt återskapa resultaten från ett tidigare forskningsarbete, nämligen att lära en graf som kan användas för prediktion med en ℓ1pennaliserad LASSO-metod. Vi föreslår även andra metoder för inlärning och utvärdering av grafen. Vi har testat metoderna  på syntetisk data och verklig temperaturdata från Sverige.  Resultaten visar att vi inte kan återskapa de tidigare forskarnas resultat, men vi lyckas lära in glesa grafer som kan användas för prediktion. Ytterligare arbete krävs för att verifiera våra resultat. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

[pt] Os códigos IRA (Irregular Repeat-Accumulate) são uma classe de códigos criada com o objetivo de permitir codificação em tempo linear garantindo comunicação robusta a taxas próximas à capacidade do canal. Eles foram introduzidas por Jin, Khandekar and McEliece em 2000. O artigo no qual foram apresentados provou que os códigos IRA alcançavam a capacidade do canal de apagamento e mostravam desempenho cmparável ao dos códigos Turbo no canal AWGN (Additive White Gaussian Noise). Os desenvolvimentos teóricos por trás dos códigos IRA vieram da busca pelos primeiros códigos LDPC (Low Density Parity Check), ou códigos em grafos, que atingiriam a capacidade do canal AWGN. Os códigos LDPC - propostos originalmente por Robert Gallager em 1963 - se tornaram objeto de grande interesse nas últimas décadas após um longo período de ostracismo desde sua concepção, desenvolvendo seu potencial para codificação de canal em aplicações tão diversas quanto comunicações por satélite, redes sem fio e streaming via IP, bem como codificação distribuída de fonte. O objetivo desta dissertação é a avaliação dos códigos IRA e os efeitos de diferentes métodos de construção de grafos em seu desempenho. O uso das muitas variações do algoritmo PEG (Progressive Edge-Growth) foi testado em simulações no canal AWGN. / [en] Irregular Repeat-Accumulate codes are motivated by the challenge of providing a class of codes that use linear-time encoding and decoding while communicating reliably at rates close to channel capacity. They were introduced by Hui Jin, Khandekar and McEliece in 2000, their article proves that IRA codes achieve channel capacity for the binary erasure channel and exhibit remarkably good performance on the AWGN channel. The theoretical developments supporting IRA codes stem from the efforts ar the development of capacity achieving Low-Density Parity-Check codes. LDPC codes were first proposed by Robert Gallager in 1963 and became the subject of intense research during the past decade after being dormant for a long period since its conception. Efforts by many researchers have developed its potential for channel coding in applications as diverse as satellite communications, wireless networks and streaming over IP, as well as studies on its usage in Distributed Source Coding. The goal of this dissertation is the evaluation of IRA codes and the effects of different graph construction methods in its performance. The use of the many variations of the Progressive Edge-Growth algorithm with IRA codes was tested in simulations on the AWGN channel.

Cette thèse comporte deux parties majeures : la première partie est dédiée à l'étude du problème sparse CARP déterministe où nous avons développé une transformation du sparse CARP en un sparse CVRP. La seconde est consacrée au problème sparse CARP avec coûts sous incertitude. Nous avons donné une formulation mathématique du problème en min-max. Cette modélisation a permis d'identifier le pire scénario pour le problème robuste. Deux approches algorithmiques ont été proposées pour une résolution approchée. / This dissertation consists of two main parts : in the first part, we study the detreministic capacitated arc routing problem over sparse underlying graphs wher we have developed a new transformation techniquevof sparse CARP into sparse CVRP. The second part is consecrated about the sparse CARP with travel costs uncertainty. We have given a mathematical formulation of the probleme in min-max. A worst scenario for the robust problem is then identified, and two algorithmic approaches are proposed to determine a solution of the studied problem.