Trabalho de conclusão de curso

Transformada rápida de Fourier e aplicações em problemas de programação competitiva.

Aluno

Luis Gustavo Bitencourt Almeida

Supervisor

José Coelho de Pina

Polinômios são ferramentas matemáticas poderosas, mas que exigem poder computacional. Especialmente o produto de dois polinômios, se feito de maneira ingênua, pode ser extremamente custoso. A Transformada Rápida de Fourier (Fast Fourier Transform - FFT) é um algoritmo de divisão e conquista que apresenta uma solução eficiente para este problema.

Problemas que envolvem FFT têm se tornado comuns em competições de programação e aparecem de formas cada vez mais inusitadas. Por exemplo:

A distância de Hamming entre duas strings de mesmo comprimento é o número de posições nas quais elas diferem entre si. Uma string é dita K-semelhante de outra string se e somente se elas são do mesmo comprimento e a distância de Hamming entre elas não é maior que K. Dadas strings A e B, quantas substrings distintas de A são K-semelhantes a B. ICPC Hefei 2009 - K-neighbor substrings

Este trabalho tem como objetivo servir como material de estudo para estudantes que queiram aprender o algoritmo da Transformada Rápida de Fourier. Em especial, pretende ser uma fonte de preparação para o uso do FFT em competições da Maratona de Programação pelos competidores do MaratonIME.

Cronograma