Cálculo da complexidade exata de algoritmos do tipo divisão-e-conquista através das equações características
Fecha
2000Autor
Tutor
Co-director
Nivel académico
Maestría
Tipo
Resumo
A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a compl ...
A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista. ...
Institución
Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Colecciones
-
Ciencias Exactas y Naturales (5041)Matemática Aplicada (281)
Este ítem está licenciado en la Creative Commons License