[pt] O PROBLEMA DE TESTE DE GRUPO VIA GRAFOS SPARSOS EM CÓDIGOS

[en] THE GROUP TESTING PROBLEM VIA SPARSE GRAPH CODES

[pt] PEDRO ABDALLA TEIXEIRA

[pt] OTIMIZACAO COMBINATORIA

[pt] COMUNICACOES DIGITAIS

[pt] CIENCIA DOS DADOS

[pt] TESTE DE GRUPO

[pt] GRAFOS ALEATORIOS ESPARSOS

[en] COMBINATORIAL OPTIMIZATION

[en] DIGITAL COMMUNICATION

[en] DIGITAL COMMUNICATION

[en] GROUP TESTING

[en] RANDOM SPARSE GRAPHS

[pt] Ciência dos dados é um dos ramos mais ativos em pesquisa, nas últimas décadas, o número de matemáticos, cientistas da computação, estatísticos e engenheiros atuando nesta área cresceu tremendamente. A partir do momento em que nos inserimos no mundo digital, nossos dispositivos eletrônicos estão armazenando e processando dados todo o tempo, então algoritmos de rápida eficiência são muito úteis para poupar tempo, recursos financeiros e até mesmo consumo de energia. O problema chamado de teste de grupo aparece em inúmeras áreas como aprendizado de máquina, teoria dos códigos, medicina e processamento de sinais, devido à sua capacidade de atingir níveis de baixa complexidade computacional. O objetivo deste problema é identificar uma população de K itens nomeados de defeituosos dentre uma população total de n, através de testes que retornam positivo caso haja pelo menos um defeituoso no grupo testado e retorna negativo caso ao contrário. Neste trabalho apresentamos o algoritmo SAFFRON (Sparse GrAph codes Framework for GROup TestiNg) proposto pelos autores Kangwook Lee, Ramtin Pedarsani and Kannan Ranchamdran. Discutimos a matemática sofisticada utilizada, generalizações, além disso apresentamos garantias de funcionamento através de demonstrações e por fim damos suporte ao trabalho com simulações numéricas.

[en] Data Science is one of the most active fields of research, over past decades, the number of mathematicians, statisticians, computer scientists and engineers working on the different subareas of data science has grown tremendously. Since we live in a digital era, our devices are storing and processing data all the time, then fast algorithms are useful to save time, money and energy consumption. Group Testing problem arises in numerous areas of technology such as machine learning, coding theory, medicine and signal processing due to its low complexity. The main goal is to recover a set of K defective items from a total set of n items by performing the minimum quantity of tests as possible. Each test is related to a chosen subset of n. The test returns positive if there is at least one defective item in the subset tested and negative otherwise. In this work we present the algorithm SAFFRON (Sparse GrAph codes Framework for GROup TestiNg) proposed by the authors Kangwook Lee, Ramtin Pedarsani and Kannan Ranchamdran. We discuss the sophisticated mathematics used, generalizations, we present the theoretical guarantees of the algorithm and we also support our work with numerical simulations as well.

MARCO ANTONIO GRIVET MATTOSO MAIA

2018-07-04

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=34313@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=34313@2

https://doi.org/10.17771/PUCRio.acad.34313