Compressão de Sequências Individuais e Fontes Parcialmente Ordenadas. - SILVA, Andresso da. (2022)
A maioria das aplicações da teoria da informação é baseada no uso de alfabetos com ordem total. Quando os sistemas considerados apresentam eventos com ordem parcial (e.g. sistemas concorrentes), a teoria da informação convencional fornece ferramentas incompletas devido à natureza dos processos. Isso se torna um assunto relevante ao con- siderar que o número de sistemas concorrentes tem crescido cada vez mais. Quando há ordem parcial, as principais ferramentas para a análise são os grafos de comutatividade e as classes de equivalência, induzidas por esses grafos. Nesta dissertação, busca-se de- senvolver novas medidas de informação para alfabetos com ordem parcial e aplicar essas medidas na análise e desenvolvimento de algoritmos que utilizam esses alfabetos. Como resultados, foram obtidos métodos de estimação e limitantes para o número de classes de equivalência. Além disso, foi proposta uma nova definição de entropia para alfabe- tos com ordem parcial, chamada de entropia de comutatividade. É demonstrado que essa definição permite superar algumas das limitações de entropias semelhantes propos- tas anteriormente. Além disso, é apresentado um novo algoritmo de compressão ótimo que considera a ordem parcial entre símbolos da sequência a ser comprimida. Quando as relações de ordem parcial são consideradas, é demonstrado que é possível obter maiores taxas de compressão de sequências.