Projeto e Análise de Algoritmos, também conhecida como PAA, é a única disciplina obrigatória do programa de Mestrado em Ciência da Computação na UFMG. Isto significa que qualquer aluno que deseja obter o título de Mestre em Ciência da Computação, independente da sua área de pesquisa (IA, Redes, Sistemas Distribuídos, Engenharia de Software, etc.) precisa cursar esta disciplina.
A disciplina tem fama no departamento pela sua densidade e complexidade, unindo conceitos de álgebra e estrutura de dados. Na minha experiência em 2023/01 essa foi de longe a disciplina mais desafiadora que já cursei. Assim a ideia neste post é compartilhar como foi minha experiência, dando uma visão geral do conteúdo na esperança de que seja útil para outras pessoas também.
Não pretendo falar sobre o programa de mestrado neste post, apenas da minha experiência com a matéria. Talvez no futuro eu escreva sobre o programa. Se estiver aqui e quiser ler sobre o mestrado de forma geral recomendo este post do grande Rodrigo Brito.
Figura 1. “Big Red” por Alexander Calder
PAA é difícil?
O que muita gente quer saber antes de ingressar no programa, ou antes de se matricular em PAA, é se esta é uma disciplina tão difícil quanto dizem. A resposta que normalmente ouvimos quando fazemos essa pergunta a professores ou ex-alunos é: “depende”. Eu também acho que depende.
Se você se formou na graduação em uma boa universidade em um curso de computação, a ideia é que parte do conteúdo apresentado não seja novidade, principalmente a parte do conteúdo sobre algoritmos e estrutura de dados. Na minha turma muitos alunos graduados em Ciência da Computação no DCC da UFMG por exemplo não tiveram grandes dificuldades nas provas e trabalhos.
Esta é uma disciplina muito densa, muito conteúdo é apresentado em um período curto de tempo. Por isso, o nível de dedicação exigido fora do horário de aula é bem alto. Esse ritmo intenso não é novidade pra alunos de universidades públicas em geral, então se esse for seu caso, nada de muito novo por aqui. É impossível ir bem nas provas sem fazer muitos exercícios. O ritmo é acelerado, pra conseguir acompanhar o conteúdo você precisa manter regularidade nos exercícios.
Pra quem tem formação em outras áreas ou veio de uma universidade que te permite graduar sem uma dedicação extra classe muito intensa, esta disciplina pode ser bem mais complicada. Isso não significa que é impossível ser aprovado em PAA vindo de uma área fora da computação. Muitos dos meus colegas de turma tinham formação em cursos de Economia, Física e Biologia por exemplo, e foram aprovados. O que quero dizer é que a disciplina se torna bem mais desafiadora quando você não sabe por exemplo o que é um grafo, uma fila de prioridades, ou se você não for familiarizado com algoritmos básicos de ordenação como insertion sort e merge sort.
Muitos alunos optam por cursar exclusivamente esta disciplina durante o semestre. Pessoalmente acho essa uma boa ideia. Faz sentido evitar a sobrecarga de estudos tentando conciliar PAA com outras matérias. Isso também não é uma regra, claro. Conheço pessoas que cursaram PAA junto com outras disciplinas e foram aprovadas sem problemas. Na minha experiência como estudante em dedicação parcial, conciliar o trabalho de 8h fora da universidade com os estudos já é bem complicado. Conciliar PAA com outra disciplina, seria pra mim uma missão impossível. Só consegui ser aprovado me dedicando exclusivamente a PAA durante o semestre inteiro.
A matéria exige muito tempo para estudo. Se você assim como eu se formou em uma universidade privada e era um aluno com notas boas, aqui provavelmente vai descobrir que precisa estudar mais para manter as notas dentro da média. Este é o grande desafio da disciplina.
A dificuldade do conteúdo em si varia durante o semestre a depender do seu background. Em alguns módulos você pode se dar bem se tiver facilidade com manipulações algébricas, estatística, e lembrar de propriedades de logaritmos por exemplo. O desafio constante será manter o ritmo intenso de estudos, fazer todos os exercícios, reler trechos de capítulos do livro depois da aula, e manter essa mentalidade durante o semestre inteiro.
Conteúdo
A disciplina cobre tópicos necessários para que o aluno seja capaz de analisar e projetar algoritmos. Entendo que a ideia geral de PAA é estabelecer um vocabulário comum, e formalizar ideias que nos tornam capazes de comparar algoritmos, provar corretude, analisar sua complexidade, projetar novos algoritmos, e classificar problemas.
O livro base utilizado foi o famoso “Introduction to Algorithms”. T. Cormen, C. Leiserson, R. Rivest e C. Stein. Em alguns tópicos sobre paradigmas de algoritmos, e NP-completude , outro livro bastante utilizado foi o “Algorithm Design”. Jon Kleinberg e Eva Tardos.
Analisando algoritmos
No módulo 01 são apresentados alguns algoritmos simples de ordenação e seleção, e o foco está no estudo de técnicas para analisar estes algoritmos.
- Provas de corretude com loop invariantes
- Notação assintótica (funções little/big O, little/big Omega e Theta)
- Recursividade e equações de recorrência
- Análise probabilística e algoritmos aleatorizados
- Análise amortizada
Neste primeiro módulo usamos muitas notações matemáticas e manipulações algébricas. A quem saiu da graduação há muito tempo e não se lembra de propriedades básicas de funções, polinômios, indução matemática, teoria de conjuntos, e propriedades de logaritmos, recomendo fortemente que faça antes uma revisão com exercícios focados nas suas dificuldades.
Pessoalmente achei este o módulo mais difícil da disciplina. A combinação de Algebrismo com Estrutura de dados foi bem desafiadora, mas com muito estudo é possível ter boas notas. Um livro recomendado pelos professores que me ajudou bastante é o “Matemática Discreta e Suas Aplicações”. Kenneth H. Rosen, especialmente o capítulo 04 sobre indução matemática, indução completa e boa ordenação.
Algoritmos em grafos
O segundo módulo é dedicado ao estudo de algoritmos em grafos. São apresentados algoritmos para percorrer grafos de diferentes maneiras, encontrar caminhos mínimos, árvore geradora mínima (MST), fluxo máximo e corte mínimo em uma rede.
Além de entender como estes algoritmos funcionam, é importante saber utilizar as técnicas de análise apresentadas no módulo 01 para analisar e comparar estes algoritmos. Como podemos demonstrar a corretude de um algoritmo que encontra caminho mínimo em um grafo? Este é um exemplo de pergunta que estamos interessados em responder no módulo 02. São estudados neste módulo:
- Algoritmos elementares BFS e DFS, ordenação topológica
- Árvore geradora mínima (MST) com os algoritmos gulosos de Prim e Kruskal
- Caminhos mínimos 1 to all com os algoritmos de Bellman Ford e Dijkstra
- Caminhos mínimos all pairs com os algoritmos de Floyd Warshall e Johnson
- Fluxo máximo e corte mínimo com os algoritmos de Ford Fulkerson e Edmonds Karp
Aqui é apresentada uma grande variedade de algoritmos, e pode parecer desesperador ter que entender o funcionamento de todos com suas respectivas complexidades em apenas um módulo (1 mês). Mas quase todos estes algoritmos compartilham características fundamentais que, uma vez identificadas, podem ajudar muito na compreensão do funcionamento básico de boa parte deles.
Os algoritmos de Bellman Ford e Dijkstra que encontram caminhos mínimos, por exemplo, ambos se valem do mecanismo nomeado relaxation que compara o custo atual com o novo custo obtido ao utilizar uma nova aresta descoberta do grafo. Compreender estes princípios que fundamentam os algoritmos ajudam a construir a intuição que nos permite identificar como estes algoritmos se comportam com diferentes entradas.
Neste módulo é importante completar uma boa variedade de exercícios para se familiarizar com as muitas implicações de alguns teoremas.
Paradigmas de programação
O módulo 03 apresenta diferentes paradigmas que utilizamos para projetar algoritmos. Aqui rapidamente revisamos alguns paradigmas utilizados nos algoritmos que já foram apresentados, e logo começamos a ver implementações para novos problemas que utilizam destes mesmo paradigmas: guloso, divisão e conquista, e programação dinâmica.
Aqui desenvolvemos a intuição para projetar novos algoritmos a partir de ideias que já conhecemos e vimos aplicadas em exemplos clássicos. Estudamos algoritmos famosos que usam divisão e conquista, como: 3-way partitioning, randomized quicksort, closest pair of points e multiplicação de matrizes.
O mesmo acontece quando conhecemos algoritmos de programação dinâmica. A ideia de reutilizar valores previamente computados é apresentada e exemplificada em diversos problemas. Assim espera-se que sejamos capazes de aplicar esta ideia de memoização a novos problemas. Os algoritmos estudados incluem: interval scheduling, knapsack problem (também conhecido como “problema da mochila”), maximum subarray sum, e detecção de ciclos negativos em um grafo.
Neste módulo é esperado que sejamos capazes de utilizar estes paradigmas para implementar novos algoritmos, então a criatividade também é importante. Fazer muitos exercícios é o que te coloca em contato com problemas de diferentes tipos e te prepara para as avaliações.
NP-completude e intratabilidade computacional
A última parte da disciplina apresenta o conceito de tratabilidade computacional. Este módulo é mais focado em problemas do que em algoritmos, e a ideia é discutir como podemos classificar diferentes problemas de acordo com sua dificuldade relativa.
São apresentadas reduções polinomiais de Cook e estabelecidos conceitos de equivalência entre problemas. As categorias de problemas P e NP são introduzidas, bem como os conjuntos NP-completo, NP-difícil e CO-NP. Aprendemos reduções entre problemas de satisfabilidade como SAT/3-SAT, vertex-cover, independent set e set cover, e também problemas de sequenciamento como ciclo-hamiltoniano e clique em grafos.
O assunto P vs NP é um velho conhecido da comunidade científica. É um problema em aberto da Ciência da Computação, e tem também relevância em outras áreas de conhecimento. Trata-se basicamente de problemas matemáticos cuja resposta pode ser verificada em tempo polinomial, mas não podem ser resolvidos em tempo polinomial. Pode ser bem confuso entender a diferença entre verificar instâncias de um problema e efetivamente resolver o problema, por isso essa última parte pode ser um pouco confusa.
Muitos colegas acreditam que seria melhor se esse módulo sobre intratabilidade fosse parte de outra disciplina. É um assunto denso e complexo por si só, encaixar este conteúdo em PAA torna a experiência geral da disciplina ainda mais complicada. Minha dica é: não deixe pra levar a disciplina a sério só no final.
Vale a pena?
Se esforçar pra cursar essa disciplina com qualidade é um investimento que pode sim valer muito a pena. Independente da área de pesquisa ou atuação na indústria fora da universidade, algoritmos estão sempre presentes e desempenham papel fundamental em diversas áreas. Os conhecimentos adquiridos aqui certamente ficarão comigo por toda minha jornada profissional e acadêmica.
O conteúdo é muito denso, e apesar de ter acabado de concluir a disciplina, já não me lembro de todos os algoritmos e teoremas. Mas acredito que este não é o objetivo do curso. A intuição que construímos com o tempo transforma nosso processo de raciocínio ao encontrarmos um novo problema. Esta intuição é o que acredito ter maior valor, e sempre estará à disposição na minha “caixa de ferramentas”.
Quando estamos no meio do curso a rotina é tão corrida que às vezes fica difícil valorizar a oportunidade de estar no DCC da UFMG. O departamento possui excelentes professores, muitos são destaque em suas respectivas áreas na comunidade internacional, e estão todos ali acessíveis (bom, quase todos). Os professores de PAA são muito bons, e recomendo a quem puder, que tenham a experiência de cursar essa ou outras disciplinas oferecidas pelo DCC.
Figura 2. Álbum Graduation, Ye
Cursar PAA foi certamente uma experiência desafiadora, mas bastante enriquecedora. O sentimento de orgulho no fim é recompensador.
Se tiver alguma dúvida fique à vontade para me escrever, terei prazer em ajudar.
Bons estudos!