MCTA003-17 - Análise de Algoritmos Segundo Quadrimestre de 2022


Avisos importantes

  • 16/10 A nota da REC e o conceito final estão disponíveis.
  • 26/09 Alteração na data da REC devido as eleições do domingo.
  • 04/09 Notas da P2 liberadas. A vista da P2 ocorrerá no dia 19/09 às 13h (sala do professor).
  • 25/08 Definida a sala de realização das subs.
  • 18/08 Haverá um atendimento extra no dia 22 das 13h30 às 15h (na sala usual de atendimento) para tirar dúvidas sobre o conteúdo e exercícios de reduções e complexidade computacional.
  • 16/08 Alteração no horário de vista da P1. Novo horário: Qua 17/08 às 11h-13h.
  • 14/08 Notas da P1 disponíveis. Vista da prova: Qua 17/08 às 17h-19h.
  • 10/08 Adicionei algumas instruções no início da lista de PD sobre como resolver aqueles exercícios.
  • 08/08 Inclusão da data da avaliação substitutiva (avaliação para os casos excepcionais, por exemplo, ausência com atestado médico)
  • 25/07 Alteração no horário de monitoria da sexta-feira
  • 12/07 Corrigido o problema no site referente a omissão data da P1. A P1 será realizada no dia 20/07. Durante a P1 será obrigatório a apresentação de um documento de identificação.
  • 07/07 Alteração na data da P1
  • 05/07 Não haverá aula no dia 06/07
  • 28/05 Não haverá aula no dia 29/05
  • 27/05 Mudança na data da recuperação
  • 23/05 Atualização da seção de aulas
  • 21/05 Atualização da seção de aulas
  • 14/05 Atualização no horário da monitoria e inclusão dos materias da aula 2
  • 09/05 Atualização no horário da monitoria
  • 07/05
    • Atualização do número da sala de aula da quarta-feira
    • atualização da seção de bibliografia (inserção de links para materiais)
    • inserção do material de apoio da primeira aula (no futuro, eu não colocarei avisos desse tipo, pois, por padrão, eu disponibilizarei o material de apoio abaixo do heading da aula em questão no dia seguinte).
  • 30/05 - Atualização nas seções critério de avaliação e atendimento e na data da P1.
  • 22/05 - Página no ar.

Objetivos

  • Apresentar noções e conceitos de complexidade de computação;
  • Apresentar métodos e conceitos que permitam ao aluno, de maneira confiável, avaliar a qualidade de um algoritmo. A essência destes métodos e conceitos estará focalizada no cálculo de complexidade e prova de corretude de algoritmos;
  • Caracterizar técnicas gerais de desenvolvimento de algoritmos que permitam ao aluno melhor projetá-los conforme sua natureza. As técnicas gerais escolhidas a serem estudadas são Divisão e Conquista, Método Guloso e Programação Dinâmica;
  • Apresentar noções básicas de Classes de Complexidade, em particular as classes P, NP e NP-Completo.

Ementa da disciplina

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ções

Disciplinas: Matemática Discreta, Algoritmos e Estruturas de Dados I

aa_recomendacoes.png

Para facilitar o acompanhamento do curso, é recomendado que você possua:

  • conhecimentos de programação (em qualquer linguagem imperativa), com boas noções de algoritmos recursivos,
  • familiaridade com estruturas de dados básicas (vetores, listas, pilhas, filas e árvores),
  • capacidade para reconhecer argumentos lógicos em uma prova matemática (por indução, contradição, construção),
  • familiaridade com linguagem matemática (como quantificadores lógicos, somatórios e manipulação de funções).

Outros materiais de apoio:

Bibliografia e outros materiais

  1. [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados (o conteúdo dessa disciplina está completo no livro, mas sempre existem atualizações - verifique sempre sua versão).
  2. [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms . 3rd ed. MIT Press. 2009.
  3. [CLRS2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 2nd ed. MIT Press. 2002.

Critérios de avaliação regular

A média final antes da REC ( MF ) será calculada da seguinte forma:

\[ MF = \sqrt{P1 \times P2}, \]

onde,

  • P1 e P2 são as notas da primeira e segunda avaliações, respectivamente.

\[ CF = \begin{cases} \textbf{A} ,& \text{se } MF \in [8.5;10.0]\\ \textbf{B} ,& \text{se } MF \in [7.0;8.5) \\ \textbf{C} ,& \text{se } MF \in [6.0;7.0) \\ \textbf{D} ,& \text{se } MF \in [5.0;6.0) \\ \textbf{F} ,& \text{caso contrário} \end{cases} \]

🚨 Caso seja verificado ocorrência de fraude acadêmica, o aluno será automaticamente reprovado com F.

Mecanismo de recuperação

  • A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F .
  • Consistirá numa avaliação, cujo conteúdo englobará todos os temas vistos durante o quadrimestre.
  • A nota obtida na avaliação de recuperação (NR) será usada para obter a nota final com recuperação (NFR), que consiste na média:

\[NFR = \frac{MF + NR}{2} \]

  • O conceito final com recuperação (CFR) será calculado da seguinte maneira:

\[ CFR = \begin{cases} C, & \text{se } CF = D \text{ e } NFR \geq 6;\\ D, & \text{se } CF = D \text{ e } NFR < 6;\\ D, & \text{se } CF = F \text{ e } NFR \geq 5;\\ F, & \text{caso contrário}. \end{cases} \]

Plágio

🚨 Leitura obrigatória 🚨

Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:

  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.

Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC. Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima. Abaixo uma versão resumida, que não substitui de modo algum sua leitura. Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

  • Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
  • Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
  • Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
  • Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
  • Qualquer violação às regras descritas acima implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F.
  • Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.

Dias, horários e locais das aulas

  • Segundas-feiras: 10h - 12h (sala S-207-0);
  • Quartas-feiras: 8h - 10h (sala S-205-0).

Datas Importantes

  • Avaliação 1: 13/07 20/07 (Qua)
  • Avaliação 2: 24/08 (Qua)
  • Recuperação: 24/09 01/10 08/10 (Sáb) às 10h:00 (Sala A-103-0)
  • Avaliação substitutiva: 27/08 (Sáb) às 9:00 (S-311-2)

    Avaliação substitutiva está disponível apenas para casos excepcionais.

Atendimento

Local: Bloco A, Torre 2, Piso 5, Sala de Atendimento ao Aluno (perto do banheiro feminino)

  • Segundas-feiras: 18h - 19h (Monitor: Guilherme Aldeia)
  • Sextas-feiras: 14h - 15h (Monitor: Guilherme Gigeck)

Notas

Aulas

1 Introdução ao Curso

2 Correção de Algoritmos iterativos

3 Notação Assintótica

4 Análise de Algoritmos com Notação Assintótica

5 Projeto de Algoritmos Indutivos, Algoritmos Recursivos, Recorrências e Merge-Sort

6 Recorrências

7 Análise de Algoritmos Recursivos

8 SelectionSort, Heap & Heapsort

9 Grafos

10 Busca em Grafos

11 Programação Dinâmica

12 Algoritmos Gulosos

13 Reduções

  • 📚 LM: Capítulo 28
  • Slides
  • Exercícios (na próxima seção)

14 Complexidade Computacional

15 Gulosos - Código de Huffman

  • 📚 CLRS3: Capítulo 16.3
  • Slides