Nosso treinamento continua com mais um tema de extrema importância: o paradigma de divisão e conquista! Nessa semana foi procurado abordar esse tema para aprofundar o estudo de recursões (iniciado com Busca Exaustiva) e começar a resolver problemas mais complexos. O assunto foi dividido basicamente no algoritmo de Karatsuba para multiplicação de números grandes, busca binária e busca ternária!
Assunto: Divisão e Conquista
Bibliografia principal:
- Competitive Programming, capítulo 3 (3.3) - Divide & Conquer
- Introduction to Algorithms, capítulo 4 - Divide-and-Conquer
- Top Coder - Binary Search
- Ternary Search (Wikipedia)
- Karatsuba Algorithm (Wikipedia)
Bibliografia complementar:
- Matemática Concreta, capítulo 1 - Problemas de Recorrência
- Golden Section Search (Wikipedia)
- Top Coder - Line Sweep Algorithms
Problemas sugeridos:
- UVa 11413 (Fill the Containers): busca binária na resposta e simulação.
- UVa 10341 (Solve It): método da bisseção para encontrar raízes de funções.
- SPOJ 7104 (Feanor The Elf): busca ternária na resposta. É bom tentar perceber, pelo menos intuitivamente, que a função de alcance parametrizada no ângulo de inclinação é unimodal.
- SPOJ 31 (Fast Multiplication): aplicação direta do algoritmo de Karatsuba.
- SRM 436 - Div 1 Hard (Circular Shifts): um bom problema para treinar a adaptação da multiplicação de Karatsuba. Também pode ser resolvido com FFT (transformada rápida de Fourier).
Nenhum comentário:
Postar um comentário