Resumo de Projeto e Análise de Algoritmo II §

---

1. Teorema Mestre §

O Teorema Mestre é uma ferramenta utilizada para resolver recorrências que surgem em algoritmos de Divisão e Conquista. A forma geral da recorrência é:

onde:

• é o número de subproblemas,
• é o fator de redução do tamanho do problema,
• é o custo do trabalho fora das chamadas recursivas.

Casos do Teorema Mestre:

1. Caso 1: Se onde , então .
2. Caso 2: Se , então .
3. Caso 3: Se onde e para , então .

---

2. Árvore de Recursão §

A árvore de recursão é uma representação visual das chamadas recursivas de um algoritmo. Ela ajuda a entender a estrutura e o custo de tempo da execução de algoritmos recursivos.

Estrutura:

• Nó raiz: Representa a chamada inicial ().
• Níveis da árvore: Cada nível representa uma chamada recursiva, com os nós filhos representando as sub chamadas.
• Custo por nível: O custo de cada nível (mesma linha) é somado para encontrar o custo total da árvore.

Exemplo: Para , a árvore terá:

• Raiz: Custo
• Nível 1: 2 nós de custo
• Nível 2: 4 nós de custo

Custo Total: A soma dos custos de cada nível fornece o tempo total de execução.

---

3. Análise de Algoritmo §

A análise de código envolve avaliar a eficiência de algoritmos em termos de tempo e espaço.

• Complexidade de Tempo: Determina o tempo que um algoritmo leva para executar em função do tamanho da entrada.
• Complexidade de Espaço: Refere-se ao espaço adicional que o algoritmo utiliza, além da entrada.
• Notações Assintóticas:
  • O (Big O): Limite superior do tempo de execução.
  • Ω (Omega): Limite inferior do tempo de execução.
  • Θ (Theta): Limite exato do tempo de execução.

Passos para análise:

1. Identificar loops e chamadas recursivas.
2. Contar operações elementares (atribuição, comparação, cálculos aritméticos, etc).
3. Usar notações assintóticas para descrever a complexidade.

---

4. Enumeração §

A enumeração é um método que envolve listar todas as possíveis soluções ou estados de um problema (essência do Backtracking.

• Problemas de Enumeração: Exemplos incluem a geração de combinações, permutações e subconjuntos.
• Complexidade: O tempo e o espaço necessários para enumerar todos os elementos podem ser exponenciais (algoritmos exponenciais) em relação ao tamanho da entrada, dependendo do número de combinações.

Conceitos fundamentais:

• Sequência: Uma lista ordenada de elementos, onde a ordem importa. Exemplo:
• Subsequência: Uma sequência derivada de outra, mantendo a ordem original, mas não necessariamente os elementos são adjacentes. Exemplo: A subsequência de pode ser .
• Conjunto: Uma coleção de elementos distintos, sem uma ordem específica. Exemplo: .
• Segmento: é uma subsequência “contígua”, definido por um intervalo de índices.
  • Prefixo: Um segmento que inclui os primeiros elementos da sequência. Exemplo: Para , um prefixo pode ser .
  • Sufixo: Um segmento que inclui os últimos elementos da sequência. Exemplo: Um sufixo para pode ser .

---

5. Backtracking §

Backtracking é uma técnica de busca que tenta resolver um problema explorando todas as soluções possíveis e retrocedendo quando uma solução parcial não é viável.

• Estrutura: O algoritmo constrói soluções parciais e, ao encontrar um impasse, retorna (backtrack) para explorar outras opções.
• Aplicações: Usado em problemas como Sudoku, jogos de tabuleiro (ex: N-Rainhas, Resta Um), e problemas de caminho.

Exemplo:

function backtrack(solution):
    if solution is complete:
        print solution
        return
    for option in options:
        if isValid(option):
            add option to solution
            backtrack(solution)
            remove option from solution (backtrack)

Complexidade: Pode ser exponencial (Algoritmo exponencial), mas otimizações como poda podem reduzir o espaço de busca.