Orientadores : Carlos R. P. Hartmann, Dalton Soares Arantes

Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas

Resumo: Recentemente J. Massey abordou o estudo da complexidade de certos tipos de algoritmos como um problema e codificação de fontes. Ele aplicou alguns resultados da Teoria da Informação a esse problema e obteve limites inferiores e superiores para a medida da eficiência de certos tipos de...

Resumo: Recentemente J. Massey abordou o estudo da complexidade de certos tipos de algoritmos como um problema e codificação de fontes. Ele aplicou alguns resultados da Teoria da Informação a esse problema e obteve limites inferiores e superiores para a medida da eficiência de certos tipos de algoritmos. Esses limites são facilmente calculados e possibilitam a. construção, em alguns casos, de algoritmos eficientes. Nesse trabalho nos generalizamos o procedimento introduzido por Massey. Novamente utilizando alguns resultados da Teoria da Informação, estabelecem6s novos limites superiores que são menores ou iguais aos por ele estabelecidos. Com a ajuda desses novos limites pudemos então construir algoritmos mais eficientes. Estudamos também a complexidade para essa nova construção, e sugerimos, finalmente, um método para construção de algoritmos ainda mais eficientes

Abstract: Recently J. Massey has studied the complexity of certain algorithms as a source coding problem. He has applied some results from Information Theory to this problem and found upper and lower bounds for the measure of the efficiency of these algorithms. These bounds can be easily calculated...

Abstract: Recently J. Massey has studied the complexity of certain algorithms as a source coding problem. He has applied some results from Information Theory to this problem and found upper and lower bounds for the measure of the efficiency of these algorithms. These bounds can be easily calculated and also can be used to design, in some cases, efficient algorithms. In this work we generalize the Massey's procedure. Again, - using some results from Information Theory, we obtained new upper bounds on the efficiency of this algorithms which are, in general, more tight than Massey's. With these new upper bound we can construct more efficient algorithms. We have studied the complexity required in the design of these new algorithms and also suggest a method for the design of more efficient ones