MCTA003-17 -- Análise de Algoritmos -- 2022.2

Atualizado em 04/06
Página do curso entra no ar.

Expediente

• Professor: Aritanan Gruber
• Moodle: AA22.2
• Horário: Seg. 21–23h, Qua. 19–21h, na sala S-302.1
• Atendimento: Seg. 17–18h30 na sala S-539.2

Ementa

Conceitos básicos: recorrências, medidas de complexidade (melhor caso, caso médio e pior caso). Técnicas gerais de projeto de algoritmos: divisão e conquista, método guloso e programação dinâmica. Classes de complexidade: P, NP e NP-completude.

Recomendação: Matemática Discreta, Algoritmos e Estruturas de Dados I

Avaliações e critérios

• 2 provas presenciais ($P_1$ e $P_2$) com peso $4$ cada;
• 1 prova substitutiva presencial para caso de perda de uma das provas;
• 2 listas de exercícios ($L_1$ e $L_2$) com peso $1$ cada.
  (enunciados, datas de entrega e correções no Moodle)

Nota nominal: $$ N = (4\cdot P_1 + 4\cdot P_2 + L_1 + L_2) / 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.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4}\sigma \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova $P_R$ de recuperação – única e contempla 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$. Não haverá normalização na recuperação. 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) [é possível se virar com a 2a ed.]
  Versão em Português: Algoritmos: Teoria e Prática, 3a ed., Elsevier (2012)
  [Não confunda com a tradução da 2a edição pela Campus (2001), que tem baixa qualidade.]

Secundária

• [Fe1] P. Feofiloff, Minicurso de Análise de Algoritmos, self-published (2009)
• [Fe2] P. Feofiloff, Aulas de Análise de Algoritmos, em html (2021)
• [JEr] J. Erickson, Algorithms, self-published (2019)

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
• [DPV] S. Dasgupta, C. Papadimitriou e U. Vazirani, Algorithms , McGraw-Hill (2006)
  Versão em Português: Algoritmos, AMGH (2009)

Lista de livros no assunto curada por Paulo Feofiloff.

Lista/Tentativa de tópicos por semana

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

Estudando para esta disciplina

Este curso tem nível intermediário e contempla uma coleção de técnicas e problemas fundamentais na área. Alguns alunos fazem confusões e ficam confusos no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico.

• Refaça os exemplos fornecidos em sala de aula e re-prove os resultados.
• Preste atenção ao processo de solução e não foque somente no resultado final.
• 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.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

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.