Exercícios Resolvidos sobre o Teorema Mestre

Por
| 

O objetivo deste artigo é disponibilizar ao leitor uma lista de exercícios resolvidos sobre o teorema mestre. A maioria dos exercícios foi retirada do livro Algoritmos: teoria e prática (CORMEN et al, 2012).

O teorema mestre é utilizado para resolver recorrências de algoritmos do paradigma de divisão e conquista. Ele fornece a solução de três tipos específicos de recorrências, porém esses três tipos abrangem boa parte das recorrências dos algoritmos desse paradigma.

Exercícios sobre o Teorema Mestre

Comentários 0

Teorema Mestre e Exemplos Resolvidos

Por
| 

O teorema mestre é um dos métodos mais conhecidos para resolver relações de recorrências provenientes de algoritmos do paradigma de divisão e conquista.

Comparado com outros métodos, ele é simples e intuitivo. Além disso, ele resolve boa parte das relações de recorrência desse paradigma. É claro, não estou dizendo que ele é fácil ou difícil, pois isso depende de cada um.

O objetivo da postagem é apresentar o teorema mestre e alguns exemplos resolvidos.

O texto tem caráter complementar, portanto eu recomendo que você consulte livros que abordam o assunto para ter referências mais ricas sobre o teorema mestre e não limite-se apenas a este artigo.

Teorema mestre

Comentários 0

Questões do POSCOMP sobre Complexidade de Algoritmos #06

Por
|  

As questões desta postagem são das provas do POSCOMP dos anos 2010, 2014 e 2015 sobre Complexidade de Algoritmos.

Se as fórmulas matemática não aparecerem ou ficarem estranhas, recarregue a página. Se o problema persistir, por favor, deixe um comentário para que eu possa averiguar o problema ou preencha o formulário de contato.

Comentários 0

Potenciação por Quadrados

Por
|  

Nesta postagem, apresento um algoritmo que permite calcular potências com expoente inteiro em tempo logarítmico e a implementação dele nas linguagens de programação Java e C.

Trata-se de um algoritmo de divisão e conquista que calcula uma potência utilizando quadrados (x2), por isso o nome "potenciação por quadrados" (do inglês, power by squaring ou exponentiation by squaring).

Comentários 0

Algoritmo Clássico de Multiplicação de Matrizes

Por
|  

Uma operação frequentemente utilizada na Matemática é a multiplicação de matrizes. Existe mais de um algoritmo que realiza essa operação, mas nesta postagem irei apresentar o algoritmo de multiplicação usual, que é ensinado no ensino médio (por isso coloquei "clássico" no título). Também disponibilizarei o algoritmo codificado na linguagem Java.

Comentários 0

Questões do POSCOMP sobre Complexidade de Algoritmos #01

Por
|  

O intuito desta postagem é apresentar a solução de algumas questões do POSCOMP sobre Complexidade de Algoritmos. O POSCOMP (Exame Nacional para Ingresso na Pós-Graduação em Computação) "testa conhecimentos na área de Computação e tem como objetivo específico avaliar os conhecimentos de candidatos a Programas de Pós-Graduação em Computação oferecidos no Brasil" (SBC sobre o POSCOMP).

Comentários 0

Algoritmo da Equação do Terceiro Grau

Por
|  

Introdução

Algoritmo da Equação do Terceiro Grau

Assim como a equação do segundo grau, a equação do terceiro grau possui uma fórmula para extração das raízes a partir de seus coeficientes. Entretanto, a fórmula em questão, conhecida como fórmula de Tartaglia-Cardano ou apenas fórmula de Cardano, não é tão simples quanto a fórmula de Bhaskara.

Evidentemente, a implementação da fórmula de Tartaglia-Cardano numa linguagem de programação também não é tão trivial. Pensando nisso, este artigo foi escrito com o intuito de apresentar algumas implementações da fórmula em diferentes linguagens.

O texto inicia com uma breve síntese de como a fórmula funciona e, em seguida, os códigos são apresentados. Caso o leitor queira se aprofundar, também há um conteúdo extra sobre como a fórmula é deduzida e referências sobre o assunto.

Tenha em mente que o objetivo do artigo não é ensinar como resolver equações do terceiro grau, mas apresentar um algoritmo que computa as raízes de uma a partir de seus coeficientes.

Veja também: Calculadora de Equações do Terceiro Grau

Comentários 2

Complexidade Algorítmica do Teorema de Laplace no Cálculo de Determinantes

Por
|  

Antes de começar, é importante alertar o leitor que este não é um artigo com o intuito de ensinar o teorema de Laplace. Aqui, faço uma análise do teorema do ponto de vista computacional. Caso você precise de um artigo para aprender o teorema, procure outra fonte.

Introdução

O teorema de Laplace (Laplace Expansion, em inglês) permite calcular o determinante de matrizes de qualquer ordem através de uma expansão em cofatores. Na prática, o cálculo do determinante é realizado calculando-se os determinantes de matrizes de ordem inferior. Por exemplo, o determinante de uma matriz de ordem cinco é calculado a partir dos determinantes de cinco matrizes de ordem quatro.

O intuito deste texto é analisar a complexidade do teorema na resolução de determinantes. Tal análise faz uso de conceitos um tanto avançados de Cálculo Diferencial, portanto é importante ter noções de Cálculo para compreender o artigo.

Inicialmente, é feita uma rápida revisão sobre o teorema com o intuito de compreendê-lo. Depois, faço uma análise das chamadas recursivas necessárias para computar um determinante através do teorema. Em seguida, apresento a equação de recorrência do algoritmo e resolvo-a considerando dois casos distintos. Por fim, realizo algumas observações finais.

Comentários 0

O Método de Akra-Bazzi na Resolução de Equações de Recorrência

Por
| 

Introdução

O método de Akra-Bazzi é um dos métodos mais poderosos para solucionar relações de recorrência advindas, principalmente, de algoritmos de divisão e conquista. Tal método abrange uma quantidade muito maior de relações de recorrência que o Teorema Mestre.

Enquanto o Teorema Mestre resolve apenas recorrências do tipo $$T(n) = aT(n/b) + f(n), \quad \text{(1)}$$ com certas restrições em $f(n)$, o método de Akra-Bazzi é capaz de resolver relações de recorrência da forma $$T(n)=\begin{cases} c_0,\quad n=x_0\\ \sum_{i=1}^k a_iT\left(b_i n\right)+f(n),\quad n>x_0 \end{cases} \quad \text{(2)}$$ onde $a_i > 0$, $0 < b_i < 1$, $c_0\in\mathbb{R}$, $x_0\in\mathbb{N}$, $k\geq 1$ e $f(n)$ é uma função que deve satisfazer a condição de crescimento polinomial

Versão original do método é bem mais detalhada. Aqui, estou utilizando a versão do método apresentada por Cormen em seu livro "Algortimos - Teoria e Prática", porém foram feitas algumas simplificações que serão suficientes para os objetivos do presente texto, entretanto a "essência" do método é a mesma.

Comentários 0