A importância dos algoritmos para um engenheiro de software

Estou muito satisfeito por estar a ajudar a renovar as equipas que vão representar a FEUP nos concursos de programação da ACM. Há muitos alunos novos que estão a ver este "mundo" pela primeira vez e foi giro ver a sua reacção no concurso interno que fizemos esta semana :-)

No entanto, apesar deste interesse inicial dos alunos, uma pergunta natural é: porque é que isto é importante? Ou, por outras palavras, porque é que eles hão de despender parte do seu tempo livre a aprender mais sobre algoritmos, estruturas de dados e tudo o resto que está relacionado com os concursos?

Parte da resposta já foi dada noutros sítios. Neste post vou apenas realçar algumas das razões.
Eu sugiro a leitura do tutorial do TopCoder sobre a importância dos algoritmos e o artigo da Academia ONI sobre a análise de algoritmos.

Antes de mais.. o que é um algoritmo?
Um algoritmo pode ser definido como uma sequência de passos que transforma um dado input (um valor ou conjunto de valores) no resultado pretendido - output - sendo este tipicamente um valor ou conjunto de valores.
Na prática, um engenheiro de software gasta grande parte do seu tempo a implementar algoritmos. Para cada parte do projecto de desenvolvimento de software, existem um conjunto de desafios e é necessário definir qual vai ser a abordagem para os ultrapassar. Estes desafios podem ser coisas simples como ler um ficheiro de texto e apresentar a informação ao utilizador ou coisas mais avançadas como o processamento de giga, tera ou mais bytes de dados para determinar alguma estatística.

Análise do tempo de execução de algoritmos
Imaginem que têm este problema: dados N números inteiros, existem 2 números que somados dão um número S?
Uma solução natural é testar todos os pares de números e verificar se a sua soma dá S. Exemplo em C++:

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int soma) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == soma) return true; return false; }

O código é simples e tudo indica que dá a resposta certa. No entanto, um factor importante na vida real é saber se esta performance chega para as nossas necessidades. Qual é a quantidade máxima de números que este algoritmo suporta se o nosso programa tiver no máximo 1 segundo para executar?

Para responder a esta pergunta, é necessário analisar o tempo de execução do algoritmo apresentado. A notação mais popular para representar o tempo de execução (ou complexidade temporal) é a notação Ó-grande e é expressa em função do tamanho do input. Neste caso, é em função do número N de elementos do array.

Para cada número do array (ciclo i), é verificada a sua soma com todos os outros números (ciclo j). Assim, para cada iteração do ciclo i, o ciclo j tem N-1, N-2, N-3, .., 1, 0 iterações.
O número total de iterações é a soma dos números [0, N-1] que é a soma da conhecida progressão aritmética de passo 1, igual a N*(N-1)/2 = (N² - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,

• O((N² - N) / 2) = O(N² / 2), ignoramos o factor N porque este é dominado pelo factor N²
• O(N² / 2) = O(N²), ignoramos o factor 1/2 visto que é uma constante.

Deste modo, conseguimos uma definição compacta para a complexidade temporal do algoritmo proposto (ler os links dados para mais detalhes): O(N²). O processo pode parecer complexo ou envolvendo muita matemática mas na verdade é tipicamente muito simples porque ignoramos as constantes e outros factores dominados (e.g. o N acima).

Agora que sabemos qual é o tempo de execução, falta-nos estimar o N máximo para que o programa execute no máximo em 1s. O meu portátil tem um processador com frequência de 2.53 GHz, isto significa que o processador executa cerca de 2.53 * 10⁹ instruções por segundo. No entanto, o processador não está 100% dedicado ao nosso programa e aquilo que programamos é tipicamente traduzido em mais do que uma instrução do processador.

A experiência diz-nos que uma estimativa razoável é considerar que 100 milhões de operações são executadas em 1 segundo. Como o nosso programa tem um tempo de execução O(N²), o nosso programa pode processar √10⁸ = 10000 números em 1s. A tabela seguinte contém algumas estimativas do tempo de execução em função do tamanho do input (ver análise de algoritmos).

Nota: como diz no artigo, estes tempos consideram apenas ciclos que demoram um determinado tempo, ignorando o resto do programa. Daí a diferença de 1s para 0.1s, 1s é uma estimativa mais conservadora.

Exercício para o leitor: a solução apresentada é propositadamente ineficiente. Como fazer melhor do que 2 ciclos encadeados? Isto é, como fazer melhor do que O(N²)?

Impacto na vida real e no meu estágio na Google
Não há necessidade de reinventar a roda nestes posts. Volto a sugerir a leitura dos links referidos para obtenção de mais informação. Existem diversos tipos de algoritmos e conhecimento é poder.
Este conhecimento de determinados algoritmos ou técnicas pode permitir transformar uma ideia que parecia impossível (como vimos acima, um algoritmo poderia demorar centenas de anos ou mais até dar a resposta) numa feature bem real e popular que torna a nossa aplicação melhor do que a concorrência.

Muitos dos problemas dos concursos de programação são apresentados via uma história que pode parecer irrealista. No entanto, os algoritmos usados para resolver estes problemas são úteis para as situações que aparecem na vida profissional de um engenheiro de software.

As skills desenvolvidas ao participar nos concursos de programação são úteis no desenho e implementação de soluções para os desafios do software. Não só a parte dos algoritmos, mas também a capacidade de trabalho sob pressão, debugging e coding skills. Com a experiência destes concursos, e lendo soluções de outros concorrentes se possível (e.g. TopCoder, CodeChef), nós aprendemos a estruturar os nossos algoritmos da forma mais simples possível, resultando tipicamente em código bastante sucinto e eficiente.

Eu já resolvi alguns milhares de problemas online, seja em treino, seja por hobby. Assim, já enfrentei desafios muito diversos e também problemas semelhantes mas com restrições ou enquadramentos diferentes.
Deste modo, o meu cérebro foi treinado ao longo do tempo para analisar e identificar rapidamente quais são os requisitos e as restrições verdadeiramente importantes de diversas situações, seguido-se a identificação da solução mais apropriada para cada situação.
A consequência disto foi estar à vontade durante as entrevistas e conseguir um estágio na Google. Além disso, quer se queira, que não, parte do desenvolvimento de software é pouco desafiante e/ou repetitivo. A experiência adquirida ao resolver este tipo de exercícios permitia-me resolver as minhas tarefas muito rapidamente porque estava (tipicamente) perante problemas (mais fáceis ou mais difíceis) que já tinha enfrentado antes. Daí o ganho na produtividade.
Frequentemente, os meus superiores tinham de me arranjar outros projectos para me manter ocupado ("I have to find something to keep this guy busy"), enquanto que eles tentavam arranjar tempo para me fazerem code reviews :-)

Preparação para concursos de programação

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 :-)