Please enable JavaScript.
Coggle requires JavaScript to display documents.
Paradigmas de Resolução de Problemas - Coggle Diagram
Paradigmas de Resolução de Problemas
Abordagem Gulosa (Greedy)
Ação Crítica: Provar a correção
Validade: Pode dar certo (AC) ou errado (WA)
Conceito: Escolha localmente ótima.
Exemplos Clássicos: Algoritmos de Prim e Kruskal (MST)
Frequência: Baixa
Programação Dinâmica (DP)
Conceito: Paradigma mais desafiador
Pré-requisitos: Recursão e recorrência
Técnicas Fundamentais
Memoization (Top-Down): Evita recomputar subproblemas
Tabulação (Bottom-Up): Preenche a tabela de estados sistematicamente
Relação com Grafos
Pode ser vista como um problema em um DAG (Grafo Acíclico Dirigido)
Minimizar/Maximizar é análogo a menor/maior caminho no DAG
Aplicações Clássicas
Problema do Troco (Coin Change)
Mochila 0-1 (Knapsack)
Subsequência Crescente Mais Longa (LIS)
Soma de Intervalo (RSQ)
Caixeiro Viajante (TSP)
Frequência: Alta