Estamos no início do ano lectivo e isso também significa que a nova temporada de concursos de programação (mais escolares) também está prestes a iniciar-se.
Os alunos do ensino básico e secundário são elegíveis para as
Olimpíadas Nacionais de Informática (ONI) e têm a hipótese de serem seleccionados para representar Portugal nas Internacionais,
International Olympiad in Informatics (IOI) 2014, em Taiwan. Por seu turno, os alunos universitários poderão competir na Maratona Inter-Universitária de Programação (MIUP) já em Outubro, de modo a qualificarem-se para o
South Western European Regional Contest (SWERC), concurso da nossa zona europeia que permite o acesso à final mundial do
International Collegiate Programming Contest (ICPC) da ACM.
Independentemente do nível de ensino, a pré-condição fundamental para participar é saber programar. A maioria dos concursos suportam as linguagens C, C++, Java e Pascal. Assim, o primeiro passo é escolher uma delas, estudá-la e praticar para se ser tão proficiente quanto possível.
O C++ é a linguagem mais popular e é a minha linguagem favorita. No entanto, um dos "erros" mais comuns é a falta de conhecimento da
Standard Template Library, particularmente os diversos algoritmos já disponíveis na biblioteca
algorithm (sort, lower_bound, upper_bound, next_permutation, etc).
Os problemas colocados nestas provas devem ser resolvidos com um programa desenvolvido pelos concorrentes. Para além destes programas serem obrigados a dar as respostas correctas, existem também restrições quanto ao tempo disponível para calcular as respostas e à memória (do computador) disponível.
Assim, os concorrentes devem encontrar as ideias certas para resolver os problemas de forma eficiente, isto é, encontrar o
Algoritmo certo para resolver os problemas e implementá-lo usando uma linguagem de programação.
Infelizmente, não conheço muitos recursos em português apropriados para a aprendizagem de algoritmos. As ONI criaram um espaço chamado
Academia ONI que contém alguns artigos: "
Noções Básicas de Análise de Algoritmos", "
Tipos de Problemas" comuns em concursos e "
Pesquisa Completa" de soluções. O forum Portugal-a-Programar contém uma secção de
Algoritmia e Lógica, da qual recomendo um
artigo sobre Grafos.
Dada esta escassez, convém dominar o inglês e explorar tanto os livros como a internet.
A Ciência da Computação é uma área muito vasta. Existem diversos tipos de algoritmos diferentes. Este conhecimento está tipicamente melhor estruturado nos bons livros:
- O meu preferido é o Introduction to Algorithms. Este pode ser considerado uma bíblia e é um pouco difícil de seguir mas é um recurso fenomenal.
- O Programming Challenges é um livro escrito especialmente para concursos e é encontrado facilmente online.
- Na disciplina de algoritmos na faculdade, era recomendado o Data Structures and Algorithm Analysis in C++, este não é tão completo mas o autor é bastante claro nas suas explicações.
- Outro livro muito recomendado é o Algorithm Design Manual, mas não o conheço.
Contudo, muitas vezes, quem está a começar nestas coisas não tem ainda vontade de estudar um livro, especialmente os mais jovens (eu também não tinha!). Existem outros tipos de recursos:
- O programa de treino da USACO é uma plataforma de treino para as olimpíadas de informática. Não conheço melhor recurso online para aprender algoritmos e estruturas de dados. Está dividido por módulos que contêm tanto textos de apoio como exercícios para aplicar os conhecimentos transmitidos nesses textos.
- Tutoriais curtos e objectivos. Eu recomendo vivamente os artigos referidos anteriormente em português, assim como os tutoriais do TopCoder.
- Existem cada vez mais cursos online. A disciplina de desenho e análise de algoritmos da Universidade de Stanford é oferecida no Coursera, estando dividida em parte 1 e parte 2.
À medida que os conhecimentos são adquiridos e fortalecidos, é importante exercitar estes conhecimentos. Existem diversos judges online como o
Sphere Online Judge. Estes judges disponibilizam um conjunto vasto de problemas e os utilizadores podem resolve-los livremente como treino.
Além dos judges, existem outros sites como o
TopCoder, o
Codeforces e o
CodeChef que organizam competições de treino (normalmente há pelo menos 1 por semana) e é publicado um editorial depois de cada concurso que explica como se poderiam resolver os exercícios.
O post já vai longo, mas já deu certamente para perceber uma coisa: é preciso trabalho, trabalho, trabalho. Tal como em tudo na vida, não existem fórmulas mágicas. No entanto, quem corre por gosto, não cansa :-)
