2022 Q1

CCM-001 - Análise de Algoritmos e Estruturas de Dados (Pós)

COMPARTILHADA: MCTA003-17 - Análise de Algoritmos

Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br

piadinha


🚨 Avisos importantes (fique atento sempre!)

📌 [20/06] Avisos finais:
  1. Corrigi a prova de recuperação. Se você a fez, enviei no Moodle sua prova com comentários.
  2. As notas finais estão na planilha na seção de notas.
  3. Se você deseja solicitar revisão de nota, me envie mensagem pelo Discord indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
    Peço que isso seja feito até o dia 25/06.
[23/05] Avisos (semi-)finais importantes:
  1. Corrigi a prova 2 e as listas 5 e 6. Alguns comentários foram enviados no Discord.
  2. As notas finais (pré-rec) estão na planilha na seção de notas.
  3. A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F.
    A prova ficará disponível no Moodle na data e horário descritos no cronograma.
  4. Se você deseja solicitar revisão de qualquer nota, me envie mensagem PELO DISCORD indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
    Faça isso até o final desta semana.
  5. Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.
[03/05] Atenção! Haverá um atendimento extra no dia 9/05, às 18h, e a lista 6 poderá ser entregue até Às 20h do dia 12/05.
[02/05] As notas das listas 2, 3 e 4 estão disponíveis na seção de notas.
[22/04] A lista 6 está disponível.
[18/04] Corrigi a prova 1. Se você a fez, veja os comentários no seu PDF, que estão disponíveis no Moodle. As notas e os critérios estão na planilha na seção de notas. Veja também a mensagem no Discord. Em caso de problemas ou dúvidas, mande mensagem privada no Discord!
[07/04] Atenção! Haverá atendimento normalmente no dia 13/04 (geral e individual).
[06/04] A lista 5 está disponível.
[01/04] Hoje teremos um atendimento geral extra, das 16h às 17h30.
[27/03] A lista 4 está disponível.
[24/03] As listas 2 e 3 podem ser entregues até às 18h de hoje.
[16/03] Corrigi a lista 1 e enviei as anotações no Moodle. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[10/03] A partir de 14/03 teremos monitoria! Segundas-feiras, das 20h30 às 22h, e quintas-feiras, das 20h às 22h, pela Beatriz Favini.
[01/03] As listas 2 e 3 estão disponíveis.
[27/02] Os atendimentos gerais passarão a ter duração de 1h30 (das 16h às 17h30), seguidos ainda dos atendimentos individuais.
[25/02] O horário de atendimento geral de hoje começará às 15h15, para ter mais tempo de duração.
[18/02] Há uma nova versão da lista 1, com correções no enunciado do exercício 2 apenas.
[17/02] Atenção! Você deve marcar horário de atendimento individual com pelo menos 4 (quatro) horas de antecedência! Organize-se para não perder as oportunidades.
[05/fev] Leia a seção sobre 🔥🔥🔥 COMO SERÁ A DISCIPLINA 🔥🔥🔥 sem falta e com atenção!
[05/fev] Apenas para matriculados e alunos especiais (ou ouvintes que me enviaram e-mail): 🔥🔥🔥 servidor no Discord 🔥🔥🔥 e formulário de início de curso para alunos da graduação e para alunos da pós-graduação.
[05/fev] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova.


🙋 Como será a disciplina?

Nosso meio de comunicação principal será pelo servidor na ferramenta Discord (baixe o aplicativo e crie uma conta).
Por favor, participe do servidor apenas se você está matriculado na disciplina ou conversou comigo sobre ser ouvinte.
O site sempre será atualizado com avisos, porém comunicados menores e atendimentos serão pelo Discord.

Aliás, o servidor no Discord pode e deve ser utilizado em qualquer horário, para atendimento assíncrono.
Eu certamente responderei dentro de 24h, exceto talvez pelos finais de semana.

Usaremos também o Moodle, mas apenas para entrega das atividades.

As videoaulas com os conteúdos da disciplina serão disponibilizadas apenas aqui no site, na seção Cronograma.
Os conteúdos foram distribuídos da forma como eles seriam dados em um curso presencial.
É muito importante que você não só veja os vídeos, mas também consiga ler as notas de aula, que foram preparadas com muito carinho ao longo de outras instâncias do curso.
Particularmente, o conteúdo da Parte I vai te auxiliar muito.

Atenção! Três aulas serão dadas de forma síncrona, como pode ser visto no cronograma.
A sua participação é essencial nelas, mas elas serão gravadas e disponibilizadas logo em seguida, para quem não puder participar.

Em vários dias, estarei online pela ferramenta Google Meet para atendimento:

A maioria desses encontros são às sextas-feiras, porém em abril alguns serão às quartas-feiras.
As datas exatas estão no cronograma.

Sugestão de organização dos estudos: assista aos vídeos com atenção, sem fazer anotações. Depois, leia os materiais de apoio enquanto faz anotações. Existem mais exemplos nesses materiais e detalhes que podem passar despercebidos nos vídeos.

Idealmente, siga o cronograma: veja o conteúdo no dia previsto e tire dúvidas naquela mesma semana.
Mesmo que você não consiga seguir esse "comportamento ideal", não deixe de usar os horários de atendimento!

Como estamos fazendo a disciplina à distância, eu preciso confiar no material que você vai me entregar.
Meu único pedido é: seja o autor das suas atividades.
Isso basicamente significa: não copie solução encontrada na internet ou feita por outra pessoa.
É claro que você pode e deve trocar ideias com os colegas, porque isso realmente ajuda no aprendizado.
Eventualmente, ver soluções já prontas também ajuda, mas apenas se você entendê-las tão bem que possa, depois, responder sozinho o mesmo problema.
Qualquer violação às regras descritas na seção sobre plágio 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. Veja detalhes sobre a avaliação na seção Avaliação.

Por fim, o site tem bastante informação, então leia-o com bastante cuidado.
Não sei se já falei, mas as notas de aula estão muito boas 😉, dê uma olhada.
Meu objetivo aqui é que você aprenda o conteúdo dessa disciplina da melhor forma possível.
Por isso, converse comigo sempre.
Qualquer dúvida e feedback são bem vindos, de verdade.
Acho que é isso, boas aulas!

Importante!

Todas as aulas, com e sem participação dos alunos, serão gravadas e disponibilizadas online segundo a Licença Creative Commons Atribuição-Não Comercial 4.0 Internacional (CC-BY-NC).
Todos os participantes do curso dão sua tácita e irrevogável autorização para que suas imagens e falas sejam transmitidas, gravadas e editadas segundo a licença acima pelo docente responsável, sem nenhuma cobrança, para uso em distintos canais de comunicação e peças publicitárias sem fins comerciais.



🧐 Ementa da disciplina

CCM-001 - Análise de Algoritmos e Estruturas de Dados

Objetivos:



🖖 Recomendação

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

Dê uma olhada na lista 0 de exercícios e veja se está confortável com aquele conteúdo (ao menos já viu antes).

Preparei também esse material de 🔥revisão🔥 que contém tudo que precisamos na disciplina. Também tenho vídeos com definição e exemplos de indução.

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. [CLRS2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 2nd ed. MIT Press. 2002.
  3. [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
  4. [R] Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
  5. [DPV] Dasgupta, S.; Papadimitriou, C.; Vazirani, U.. Algorithms. Boston: McGraw-Hill. 2008.
  6. [KT] Kleinberg, J.; Tardos, E.. Algorithm design. Pearson/Alison-Wesley. 2006.
  7. Grupo do Whatsapp criado e mantido pelos alunos.


📆 Cronograma



Acesse aqui um calendário resumido das atividades.

Aula 1 - 16/fev
Aula 2 - 18/fev
  • Conteúdo: Introdução à análise de algoritmos. Corretude de algoritmos (iterativos).
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 16h40 (link no Discord); atendimento individual das 16h40 às 18h30 (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 82min):
  • Quiz.
  • Referências: Cap. 2 e 3 [LM], Cap. 1 e 2 [CLRS2].
Aula 3 - 23/fev
  • Conteúdo: Tempo de execução. Notação assintótica.
  • Formato: videoaulas (aula assíncrona)
  • Vídeos: em breve
  • Vídeos (tempo total = 92min):
  • Quiz.
  • Referências: Cap. 4 e 5 [LM], Cap. 3 [CLRS2].
  • Exercícios resolvidos:
  • Material complementar: Vídeos 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
Aula 4 - 25/fev
  • Conteúdo: Tempo com notação assintótica. Insertion Sort.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 16h40 (link no Discord); atendimento individual das 16h40 às 18h30 (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 76min):
  • Quiz.
  • Referências: Cap. 6 e 15 [LM], Cap. 2.1, 2.2, 3.1, 3.2 [CLRS2],
  • Extra: execução Insertion Sort.
02/mar (Feriado Carnaval)
  • Reposição em 12/mai (quinta-feira).
Aula 5 - 04/mar
  • Conteúdo: Corretude e tempo de execução em algoritmos recursivos. Recorrências.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 42min):
  • Quiz.
  • Referências: Cap. 7 e 8 (intro) [LM], Cap. 2.3, 4 (intro) [CLRS2],
  • Material complementar: Vídeos 4.1 [R].
07/mar: Data de entrega da Lista 1.
Aula 6 - 09/mar
Aula 7 - 11/mar
  • Conteúdo: Solução de recorrências: substituição e iteração.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 63min)
  • Quiz.
  • Referências: Cap. 8.1 e 8.2 [LM], Cap. 4 [CLRS2].
Aula 8 - 16/mar
  • Conteúdo: Solução de recorrências: árvore de recursão e método Mestre.
  • Formato: videoaulas (aula assíncrona)
  • Vídeos (tempo total = 51min)
  • Quiz.
  • Referências: Cap. 8.3 e 8.4 [LM], Cap. 4 [CLRS2].
  • Exercícios resolvidos:
  • Extra: Vídeos 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 [R].
Aula 9 - 18/mar
Aula 10 - 23/mar
  • Checkpoint: revisão e dúvidas para prova.
  • Formato: aula síncrona - horário normal de aula: das 16h às 18h (link no Discord)
  • Vídeo (tempo total = 120min):
24/mar: Data de entrega das Listas 2 e 3.
Aula 11 - 25/mar
  • Prova 1
  • Das 16h do dia 25/mar às 18h do dia 28/mar
  • Detalhes no Moodle.
Aula 12 - 30/mar
Aula 13 - 01/abr
  • Conteúdo: Conceitos de conexidade, distância e árvores. Busca em grafos e busca em largura.
  • Formato: videoaulas (aula assíncrona)
  • Vídeos (tempo total = 64min):
  • Quiz.
  • Referências: Seções 23.8, 23.9, 23.10 e 24.1 [LM], Cap. 22 [CLRS2], 10.1 10.2 [R].
  • Extra: execução BFS, execução BFS.
Aula 14 - 06/abr
  • Conteúdo: Busca em profundidade. Aplicações das buscas. Busca em digrafos.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 35min):
  • Quiz.
  • Referências: Seções 24.2, 24.3, 24.4 e 24.5 [LM], Seção 22.3 [CLRS2],
  • Extra: execução DFS.
Aula 15 - 08/abr
  • Conteúdo: Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária.
  • Formato: videoaulas (aula assíncrona)
  • Vídeos (tempo total = 78min):
  • Quiz.
  • Referências: Seções 21.1 e 21.2 [LM].
  • Extra: Vídeo 3 [R]; site prof. Feofiloff.
11/abr: Data de entrega da Lista 4.
Aula 16 - 13/abr
15/abr (Feriado Sexta-Feira Santa)
  • Reposição em 16/mai (segunda-feira).
Aula 17 - 20/abr
  • Conteúdo: Introdução a Programação Dinâmica. Corte da barra de ferro.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 76min):
  • Quiz.
  • Referências: Cap. 22, Seções 22.1 e 22.2 [LM], Cap. 15 [CLRS3].
  • Extra: Vídeos 39, 43 [R], execução Fibonacci, exemplo em um problema de redimensionamento de imagem sensível ao conteúdo (mais detalhes aqui).
Aula 18 - 22/abr
Aula 19 - 27/abr
Aula 20 - 29/abr
  • Redução entre problemas.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 88min):
  • Quiz.
  • Referências: Cap. 28 [LM], Cap. 34 [CLRS2].
02/mai: Data de entrega da Lista 5.
Aula 21 - 04/mai
Aula 22 - 06/mai
  • Problemas NP-completos.
  • Formato: videoaulas (aula assíncrona); atendimento para todos das 16h às 17h30 (link no Discord); atendimento individual das 17h30 às 19h (inscrição em link específico, disponível no Discord)
  • Vídeos (tempo total = 51min):
    .
  • Quiz.
  • Referências: Cap. 29 [LM], Cap. 34 [CLRS2].
  • Extra: Curso de otimização combinatória - como lidar com problemas NP-difíceis.
12/mai: Data de entrega da Lista 6.
Aula 23 - 12/mai (em uma quinta-feira, por ser reposição)
  • Checkpoint: revisão e dúvidas para prova.
  • Formato: aula síncrona - horário normal de aula: das 16h às 18h (link no Discord)
  • Vídeo (tempo total = 80min):
Aula 24 - 13/mai
  • Prova 2
  • Das 16h do dia 13/mai às 18h do dia 16/mai
  • Detalhes no Moodle.
RECUPERAÇÃO - 10/jun (quadrimestre seguinte)
  • Prova de recuperação para os alunos que ficaram com conceito F (ou D ou F no caso da graduação).
  • Das 18h do dia 10/jun às 20h do dia 13/jun
  • Detalhes no Moodle.


👎 Plágio



🏋 Listas de exercícios



🎓 Critérios de avaliação



💯 Notas

Acompanhe aqui as notas das atividades.

💪 Mecanismo de recuperação



🤒 Mecanismos de avaliação substitutivos




Carla Negri Lintzmayer - carla.negri@ufabc.edu.br