MCCC004-23 -- Análise de Algoritmos I -- 2026.1N

Expediente

• Professor: Aritanan Gruber , sala S-539.2
• Aulas: Seg 21–23h (S-208.0) e Qui 19–21h (A-107.0)
• Atendimento: Qui 18–19h (S-539.2) ou por agendamento
• Moodle: AA1-Q26.1N
  andamento do curso, links úteis, material, avaliações, notas, mensagens, etc.

Ementa

Tempo de execução e análise assintótica. Corretude de algoritmos iterativos e recursivos. Recorrências e técnicas de solução de recorrências. Enumeração e backtracking. Divisão e conquista (sugestões de exemplos: Mergesort, multiplicação de inteiros, matrizes, par mais próximo, contagem de inversões). Aleatorização (sugestões de exemplos: Quicksort aleatorizado, problema da seleção). Tópicos opcionais: análise amortizada.

Objetivos

Este curso objetiva capacitar o aluno em projeto e análise de algoritmos. Ao término do curso, espera-se que o discente seja capaz de demostrar a correção de um algoritmo iterativo ou recursivo, analisar o tempo de execução de um algoritmo, usar a notação assintótica para descrever o tempo de execução de um algoritmo, manipular recorrências. Além disso, espera-se que o discente seja capaz de projetar e compreender algoritmos que utilizam as técnicas de enumeração, backtracking, divisão e conquista e aleatorização.

Recomendação

Matemática Discreta II; Matemática Discreta I; Algoritmos em Grafos; Algoritmos e Estruturas de Dados I; Algoritmos e Estruturas de Dados II; Programação Estruturada; Processamento da Informação; Funções de Uma Variável

Avaliações e critérios

• listas de exercícios serão disponibilizadas no Moodle no decorrer do quadrimestre;
  devem ser feitas (fazem parte do seu estudo), mas não valem nota;
  
• duas provas regulares $P_1$ e $P_2$ e uma prova substitutiva $P_3$ aberta;
  média aritmética das 2 melhores dentre as 3 possibilidades
  • P1 : Qui 12/03 @ 19h/21h
  • P2 : Qui 23/04 @ 19h/21h
  • P3 : Seg 27/04 @ 21h/23h

Nota nominal: $$ N = \frac{1}{2}\max\left\{\sum_{j\in S}P_j\,:\,S\in\binom{[3]}{2}\right\} = \frac{1}{2}\max\left\{P_1+P_2,P_1+P_3,P_2+P_3\right\}, $$ com $P_i\in[0,10]$.

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Recuperação

Caso seu conceito $C_N$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova de recuperação $P_R$ em Seg 04/05 @ 12-23h. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Note que seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Bibliografia

Primária

• [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT University Press (2009)
  Versão em Português: Algoritmos: Teoria e Prática, 3a ed., Elsevier (2012)
• [KT] J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, Inc. (2006)

Secundária

• [AU] A. Aho, J.D. Ullman, Foundations of Computer Science (C edition), , W.H. Freeman (1994)
• [DPV] S. Dasgupta, C. Papadimitriou e U. Vazirani, Algorithms, McGraw-Hill (2006)
  Versão em Português: Algoritmos, AMGH (2009)
• [Eri] J. Erickson, Algorithms, self-published (2019)
• [Fe1] P. Feofiloff, Minicurso de Análise de Algoritmos, self-published (2009)
• [Fe2] P. Feofiloff, Aulas de Análise de Algoritmos, em html (2021)
• [Mun] U. Mamber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, (1989)
• [SF] R. Sedgewick, P. Flajolet, An Introduction to the Analysis of Algorithms, 2nd ed., (2013)
• [SW] R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley (2011) 955 p.

Requisitos

• [LLM] E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science, MIT CC3.0 (2018)
• [Fle] M.M. Fleck, Building Blocks for Theoretical Computer Science

Lista de livros no assunto curada por Paulo Feofiloff.

Lista de tópicos por semana (tentativa)

Detalhes de cada tópico (coberto nas aulas) serão atualizados no Moodle ao longo do quadrimestre.

[*] se o tempo permitir; em caso contrário, as aulas serão usadas para terminar os tópicos das aulas anteriores.

Estudando para esta disciplina

A natureza do tópico, o posicionamento do curso na grade, e a lista de pré-requisitos indicam que esta é uma disciplina de nível intermediário; e será tratada como tal. Você deve assistir às aulas, estudar a bibliografia indicada, e dedicar-se às listas de exercícios.

Caso seus pré-requisitos não estejam tão sólidos quanto desejável (falta de familiaridade com formalismo matemático e raciocínio algorítmico, atitude passiva com relação ao aprendizado, tempo dedicado insuficiente, etc.), será possível fazer confusões e sentir-se perdido no início.

Alguns procedimentos que costumam funcionar em cursos introdutórios para mitigar os motivos relacionados também costumam funcionar por aqui:

• Refaça os exemplos e re-prove os resultados fornecidos em sala de aula.
• Preste atenção aos processos de solução (aprenda-os!) e não foque somente nos resultados finais.
• Assista ativamente às aulas; resolva os exercícios nelas propostos e os contidos nas listas.
• Estude a bibliografia indicada, monte grupos de estudo, e faça um bom uso dos horários de atendimento.
• Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo. “Ouvir” às aulas e “ler” os livros tem pouco ou nenhum efeito neste curso – e em qualquer disciplina matemática/algorítmica que o valha.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Note que você não será convidado a regurgitar respostas fornecidas em aula ou presente nos livros. As questões em listas e provas testarão sua capacidade de entender os problemas e apresentar uma solução para eles. Às vezes, serão uma adaptação simples ou uma extensão direta do que foi visto. Outras, será necessário relacionar dois ou mais métodos ou conceitos apresentados. Outras ainda, irão requerer análise e raciocínio mais profundo (o que leva tempo, então não deixe nada para a última hora!).

Tenha em mente: além do escrito acima, para aproveitar bem este curso, você deve familiarizar-se com o material na leitura sugerida correspondentes antes da aula, e estudá-los com afinco depois.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

• I - fraudem avaliações;
• II - fabriquem ou falsifiquem dados;
• III - plageiem ou não creditem devidamente autoria;
• IV - aceitem autoria de material acadêmico sem participação na produção;
• V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.

LLMs

Representam um grande avanço da inteligência artificial generativa. O uso para estudo é encorajado, mas cuidado com alucinações e respostas incorretas. Note que o uso de tais ferramentas durante avaliações enquadram-se no Artigo 25 acima.

Para pensar ao longo do curso: Do que adianta as máquinas aprenderem e os alunos não?