Trabalho de Formatura

Autor: Antonio Roberto de Campos Junior

Supervisor: Professor Doutor Carlos Eduardo Ferreira

Monografia Poster Subjetiva Apresentação

Tema

Teoria dos Números e Computação: Uma abordagem utilizando problemas de competições de programação.

Resumo

Teoria do Números é um vasto ramo da matemática que estuda números inteiros. Números primos, fatorização de números inteiros, funções aritméticas, são alguns dos tópicos mais estudados e também importantes para resolução de problemas computacionais.

Hoje em dia a importância da Teoria do Números na Computação é inquestionável, e desse modo, esse trabalho vem ilustrar como a teoria pode ser aplicada na criação de algoritmos para resolução de problemas computacionais, em especial problemas de competições de programação.

Equações diofantinas, Congruência Modular, Números de Fibonacci, são alguns dos assuntos que serão abordados nesse trabalho. Após a devida demostração da teoria serão exibidos alguns problemas de competições de programação que aplicam essa teoria, seguido da implementação e análise do algoritmo que resolve o problema abordado.

Motivação

Desde que eu era calouro eu me interessei por competições de programação. Logo no segundo ano, em 2011, alguns amigos e eu começamos a estudar praticamente todos os dias, com a esperança de nos classificarmos para final brasileira da maratona de programação pelo menos uma vez antes de terminar a graduação.

Hoje em dia, conquistamos alguns resultados expressivos, como:

• 1ª Colocação na final brasileira da maratona de programação em 2014;

• 2ª Colocação na final brasileira da maratona de programação em 2013;

• Classificados para final mundial da maratona de programação em 2014 e 2015;

A experiência que eu adquiri nos últimos anos me preparando para ACM-ICPC (International Collegiate Programming Contest), meu interesse sobre Matemática e a falta de um bom material que unifique diversos tópicos relacionados à Teoria dos Números e Programação, me levaram a trabalhar nesse tema.

Objetivos

• Estudar tópicos específicos relacionados à Teoria dos Números;

• Criar um material que mostre a aplicação direta dessa teoria na solução de problemas de competições de programação;

• Demonstração da teoria e implementação dos algoritmos que resolvem os problemas que serão abordados;

Atividades já realizadas

• Seleção e Estudo de alguns dos problemas que serão abordados nesse trabalho;

• Implementação dos algoritmos que resolvem esse problemas;

Cronograma

---