CCM-001 - Análise de Algoritmos e Estruturas de Dados (2020 Q1, ECE)
MCTA003-17 - Análise de Algoritmos
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
Grupo no Discord (para alunos!)
🚨 Avisos importantes (fique atento sempre!)
🆕 [29/06] As notas finais (pós REC) estão disponíveis.[22/06] Atenção! Avisos semifinais:
- As notas finais (antes da REC) estão disponíveis. Se você fez a P2, confira seu e-mail para mais informações.
- Farei um atendimento no Discord no dia 24/06, das 16h às 18h.
- Se possível, preencha o formulário anônimo de avaliação final da disciplina (sim, mais um, mas garanto que o último 🤓).
- Para fazer a REC (dia 25/05), você precisa me enviar um e-mail.
[09/06] Haverá atendimento nos dias 15/06 e 17/06, ambos das 16h às 19h no Discord.
[08/06] As datas das avaliações foram atualizadas (veja cronograma). Aos que decidiram realizá-las pessoalmente, entrem em contato quando tais atividades forem possíveis.
[07/06] Haverá atendimento extra da Poliana amanhã, dia 8/06, das 18h às 20h, no Discord.
[07/06] Notas da lista 2.5. Um e-mail com explicações foi enviado a cada um. A mesma mensagem foi enviada no Discord.
[30/05] Considerando a situação crítica do país em relação à pandemia, o indicativo de que o distanciamento físico deve perdurar por mais alguns meses, e que o prazo para finalização remota dos ECE foi estendido até o dia 27 de junho, as avaliações finais desta disciplina poderão ser feitas à distância.
O conteúdo das aulas terminará como previsto, no dia 3/06 e a entrega da última lista está para o dia 7/06 e não será adiada. O período de extensão que nos foi dado será utilizado apenas para a realização das avaliações.
Acesse este formulário até o dia 7 de junho para verificar o novo plano e indicar se você irá aderir ao mesmo. Considero que os que não responderem ao formulário não têm interesse em realizar as avaliações à distância.
[20/05] Lista 4 disponível. O prazo de entrega da lista 3 foi alterado.
[15/05] Houve pequena alteração no enunciado do exercício 5 da lista 3.
[11/05] O horário de atendimento da Poliana mudou! [07/05] Lista 3 disponível.
[24/04] Lista 2.5 disponível.
[18/04] Atenção! A partir do dia 20/04, retornaremos as atividades em esquema de Estudo Continuado Emergencial (ECE).
Veja este vídeo para mais informações sobre como serão nossas atividades.
É muito importante que você faça parte do grupo no Discord.
Conteúdo dessa página
 |
🕐 Dias, horários e local das aulas (voltar ao topo)
Videoaulas e quizzes serão disponibilizados semanalmente, até às terças-feiras, na seção Cronograma.
Os vídeos referentes ao conteúdo de uma aula prevista não ultrapassarão o total de 2h.
Os quizzes serão referentes ao conteúdo dos vídeos.
As respostas a eles serão utilizadas para avaliar a participação e engajamento dos alunos.
Eles terão prazo de uma semana para serem finalizados.
Todas as quartas-feiras e sextas-feiras, haverá atendimento online das 16h às 19h no Discord, preferencialmente sobre o conteúdo previsto no cronograma.
🆘 Dias, horários e local de atendimento (voltar ao topo)
Todas as quartas e sextas-feiras, a professora estará online das 16h às 19h no Discord.
Todos os sábados, das 14h às 17h a monitora Poliana estará online no Discord.
Atenção! O grupo no Discord pode e deve ser utilizado em qualquer horário.
🤓 Ementa da disciplina (voltar ao topo)
Notação assintótica. Distinção entre a especificação de uma estrutura de dados e a sua implementação. Tipos de dados primitivos. Conceitos e terminologia para estrutura da dados não primitivas. Estruturas de dados lineares. Descrição e implementação de operações ligadas a algumas estruturas lineares. Métodos de armazenamento. Estruturas de dados não lineares. Conceitos básicos, operações, representação e manipulação. Recorrências; Mergesort; Quicksort. Filas de prioridade e Heapsort. Ordenação em tempo linear. Programação dinâmica. Algoritmos em grafos. Árvore geradora mínima. Caminhos mínimos. Complexidade computacional.
Objetivos: (i) Apresentar noções e conceitos de complexidade de computação; (ii) 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; (iii) 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; (iv) Apresentar noções básicas de Classes de Complexidade, em particular as classes P, NP e NP-Completo.
🤯 Recomendação (voltar ao topo)
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).
- Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
- O que é uma prova matemática, do prof. Paulo Feofiloff, da USP.
- Matemática discreta para computação, dos profs. Anamaria Gomide e Jorge Stolfi, da Unicamp.
- Indução matemática, do prof. Cid Carvalho de Souza, da Unicamp.
- Portal da Matemática da OBMEP.
- Indução e contagem, do prof. Rogério Steffenon e Felipe Guarnieri, da Unisinos.
- Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
- Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
- Notas de aula, da disciplina de Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).
- Notas de aula, da disciplina de Programação Estruturada (introdução à programação em C, recursão, vetores e listas).
📖 Bibliografia e outros materiais (voltar ao topo)
- [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados. (em constante atualização).
- [CLRS2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 2nd ed. MIT Press. 2002.
- [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
- [R] Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
- [DPV] Dasgupta, S.; Papadimitriou, C.; Vazirani, U.. Algorithms. Boston: McGraw-Hill. 2008.
- [KT] Kleinberg, J.; Tardos, E.. Algorithm design. Pearson/Addison-Wesley. 2006.
- Site com execução passo a passo de vários algoritmos em grafos.
- [GFG] Site Geeks for Geeks, muito bom, com implementações em várias linguagens.
- Grupo de Whatsapp criado e mantido pelos alunos.
📆 Cronograma (voltar ao topo)
As referências utilizadas nas aulas serão atualizadas durante o curso.
Sobre qualquer material feito por mim, participe do banco de informantes.
O conteúdo a seguir já foi coberto durante as aulas presenciais:
| Aula | Data | Tópicos |
|---|---|---|
| 1 | 12/02 | Objetivo do curso. Revisão de conceitos importantes para o curso.
📖 Referências: veja materiais na seção de recomendação. ✏️ Material complementar: Vídeo 1.1 [R]. ✏️ Slides usados em sala: introdução ao curso e revisão. |
| 2 | 14/02 | Término da revisão. Introdução à análise de algoritmos. Corretude dos algoritmos de busca em vetor.
📖 Referências: Cap. 1 e 2 [LM], Cap. 1 e 2 [CLRS2]. |
| 3 | 19/02 | Tempo de execução. Notação assintótica.
📖 Referências: Cap. 3 e 4 [LM], Cap. 3 [CLRS2]. ✏️ Material complementar: Vídeo 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R]. |
| 4 | 21/02 | Notação assintótica. Insertion Sort.
📖 Referências: Cap. 4 e 13 [LM], Cap. 2.1, 2.2, 3.1, 3.2 [CLRS2], ✏️ Extra: animação InsertionSort. |
| 26/02 | ---- Feriado (Carnaval) ---- | |
| 5 | 28/02 | Recursão. Recorrências. Divisão e Conquista. Mergesort.
📖 Referências: Cap. 5, 6 e 14 [LM], Cap. 2.3, 4 (intro) [CLRS2], ✏️ Material complementar: 1.5, 1.6, 1.7 e 4.1 [R]. ✏️ Extra: animação Mergesort, animação ordenação, limite inferior ordenação. |
| * | 29/02 | Atendimento extra da monitora: Sala S-311-2, das 13h às 15h. |
| 6 | 04/03 | Corretude do Mergesort. Solução de recorrências: substituição.
📖 Referências: Cap. 6 [LM], Cap. 4 [CLRS2]. ✏️ Extra: Documento com a corretude do Mergesort. |
| 7 | 06/03 | Solução de recorrências: iteração e árvore de recursão.
📖 Referências: Cap. 6 [LM], Cap. 4 [CLRS2]. |
| 8 | 11/03 | Solução de recorrências: método Mestre. Mais exemplos de recorrências.
📖 Referências: Cap. 6 [LM], Cap. 4 [CLRS2]. ✏️ Extra: 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 [R]. |
| 9 | 13/03 | SelectionSort. Heap.
📖 Referências: Cap. 10 e 15 [LM], Cap. 6 [CLRS2]. ✏️ Extra: animação SelectionSort, animação Heap, Vídeos sobre heap: 12.1, 12.2, 12.3 [R]. |
| 16/03 | Aulas canceladas devido ao surto do COVID-19. |
Soluções de exercícios das listas 1 e 2:
Solução em PDF de alguns exercícios da lista 1.
Sobre a estrutura heap:
Como vai funcionar o ECE:
Revisão do conteúdo já visto:
O conteúdo a seguir será coberto durante o ECE:
| Aula | Data | Tópicos |
|---|---|---|
| 10 | 22/04 | Heapsort. Fim de ordenação.
⏰ Tempo total: 24 min 📝 Não esqueça de responder o quiz! (Prazo: 29/04) 📖 Referências: Cap 15 [LM], Cap. 6 [CLRS2]. ✏️ Extra: animação Heap e Heapsort, animação Heapsort, animação ordenação. |
| 11 | 24/04 | Introdução a grafos e a análise de algoritmos em grafos.
⏰ Tempo total: 73 min 📝 Não esqueça de responder o quiz! (Prazo: 01/05) 📖 Referências: Cap. 21 (até seção 21.8) [LM], Cap. 22 [CLRS2], 9.2[R]. ✏️ Extra: análise detalhada do algoritmo de grau máximo, implementações vistas nos vídeos, visualizador simples de grafos. |
| 12 | 29/04 | Conceitos de conexidade, distância e árvores. Busca em grafos e busca em largura.
⏰ Tempo total: 64 min 📝 Não esqueça de responder o quiz! (Prazo: 05/05) 📖 Referências: Seções 21.8, 21.9, 21.10 e 22.1 [LM], Cap. 22 [CLRS2], 10.1 10.2 [R]. ✏️ Extra: animação BFS, animação BFS. |
| 01/05 | ---- Feriado (Dia do trabalho) ---- | |
| 13 | 06/05 | Busca em profundidade. Aplicações das buscas. Busca em digrafos. 
⏰ Tempo total: 44 min 📝 Não esqueça de responder o quiz! (Prazo: 13/05) 📖 Referências: Seções 22.2, 22.3, 22.4 e 22.5 [LM], Seção 22.3 [CLRS2], ✏️ Extra: animação DFS. |
| 14 | 08/05 | Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária. 
⏰ Tempo total: 78 min 📝 Não esqueça de responder o quiz! (Prazo: 15/05) 📖 Referências: Seções 19.1 e 19.2 [LM]. ✏️ Extra: 3 [R], site prof. Feofiloff, texto sobre otimização combinatória. |
| 15 | 13/05 | Árvore geradora mínima. Algoritmo de Kruskal. Union-Find. 
⏰ Tempo total: 88 min 📝 Não esqueça de responder o quiz! (Prazo: 20/05) 📖 Referências: Cap. 23 e Seção 23.1 [LM], Cap. 23 [CLRS2]. ✏️ Extra: 10, 17, 18, 19, 20, 21 [R]. animação Union Find, outra animação Union Find, animação Kruskal, outra animação Kruskal. |
| 16 | 15/05 | Caminhos mínimos em grafos. Dijkstra. 
⏰ Tempo total: 55 min 📝 Não esqueça de responder o quiz! (Prazo: 22/05) 📖 Referências: Cap. 25 e Seção 25.1 [LM], Cap. 24.3 [CLRS2]. ✏️ Extra: animação Dijkstra, outra animação Dijkstra. |
| 17 | 20/05 | Introdução a Programação Dinâmica. Corte da barra de ferro. 
⏰ Tempo total: 76 min 📝 Não esqueça de responder o quiz! (Prazo: 27/05) 📖 Referências: Cap. 20, Seções 20.1 e 20.2 [LM], Cap. 15 [CLRS3]. ✏️ Extra: 39, 43 [R], animação Fibonacci, exemplo "real" em um problema de redimensionamento de imagem sensível ao conteúdo (mais detalhes aqui). |
| 18 | 22/05 | Mochila inteira. Alinhamento de sequências. 
⏰ Tempo total: 74 min 📝 Não esqueça de responder o quiz! (Prazo: 29/05) 📖 Referências: Cap. 20, Seções 20.3 e 20.4 [LM], Cap. 15 [CLRS3]. ✏️ Extra: 44, 45, 46, 47, 48 [R]. animação Mochila, animação Needleman-Wunsch. |
| 19 | 27/05 | Caminhos mínimos em grafos. Algoritmo de Floyd-Warshall. 
⏰ Tempo total: 32 min 📝 Não esqueça de responder o quiz! (Prazo: 03/06) 📖 Referências: Seção 25.2 [LM], Cap. 25.2 [CLRS3]. ✏️ Extra: animação Floyd-Warshall. |
| 20 | 29/05 | Redução entre problemas.
⏰ Tempo total: 88 min 📝 Não esqueça de responder o quiz! (Prazo: 05/06) 📖 Referências: Cap. 26 [LM], Cap. 34 [CLRS3]. ✏️ Extra: Slides usados na aula. |
| 21 | 03/06 | Classes P, NP, NP-completo e NP-difícil. 
⏰ Tempo total: 52 min 📝 Não esqueça de responder o quiz! (Prazo: 09/06) 📖 Referências: Cap. 26 [LM], Cap. 34 [CLRS3]. ✏️ Extra:  ,
Slides usados na aula,
P vs. NP and the Computational Complexity Zoo,Map of Computer Science (não exatamente relacionado com a aula), slides antigos meus, sobre otimização combinatória. |
| 22 | 11/06 | Prova 1 (será enviada por e-mail, às 18h). Conteúdo: Aulas 1 a 13. |
| 23 | 18/06 | Prova 2 (será enviada por e-mail, às 18h). Conteúdo: Aulas 14 a 21. |
| 24 | 25/06 | Prova de recuperação (será enviada por e-mail, às 18h) |
👎 Plágio (voltar ao topo)
- Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
- fraudem avaliações,
- fabriquem ou falsifiquem dados,
- plagiem ou não creditem devidamente autoria,
- aceitem autoria de material acadêmico sem participação na produção,
- 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.
🏋 Listas de exercícios (voltar ao topo)
- Ao todo teremos 4.5 listas, cujos enunciados serão disponibilizados aqui, nas datas indicadas abaixo.
- As soluções das listas deverão ser feitas à mão (capriche na letra!), escaneadas em um único arquivo PDF e entregues pelo Google Forms nos links disponibilizados abaixo, nas respectivas datas.
- Sugestão de aplicativo para escanear a lista: CamScanner (disponível para Android e iPhone.)
- Por favor, certifique-se de que o resultado final está legível.
- As listas 1 e 2, já disponibilizadas, não valem nota, mas serão consideradas como bônus.
- As listas 2.5, 3 e 4 valerão 30% da nota da disciplina.
- Atenção! As listas serão corrigidas e qualquer caso de detecção de plágio implicará em nota final 0 para os envolvidos.
🎓 Critérios de avaliação (voltar ao topo)
- A avaliação da disciplina constituirá da nota de duas provas, respectivamente denotadas por P1 e P2, da média simples das notas das listas 2.5, 3 e 4 de exercícios, denotada por L, e da média simples das notas dos quizzes, denotada por Q.
- A prova 1 vale 35% da nota.
- A prova 2 vale 30% da nota.
- As listas valem 30% da nota.
- Os quizzes valem 5% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.35 x P1 + 0.3 x P2 + 0.3 x L + 0.05 x Q - Se você é aluno da pós-graduação, seu conceito final será
A, se MF ≥ 8.5
B, se 7.0 ≤ MF < 8.5
C, se 5.0 ≤ MF < 7.0
F, se MF < 5.0
- Se você é aluno da graduação, seu conceito final será
A, se MF ≥ 8.5
B, se 7.0 ≤ MF < 8.5
C, se 6.0 ≤ MF < 7.0
D, se 5.0 ≤ MF < 6.0
F, se MF < 5.0
- As provas serão realizadas presencialmente, nas duas primeiras semanas de retorno das atividades presenciais na UFABC.
- Em caso excepcional, poderão ser aplicadas de forma online, e os alunos serão avisados com, no mínimo, 7 dias de antecedência.
Acompanhe a entrega das atividades aqui. Essa planilha é atualizada automaticamente.
💪 Mecanismo de recuperação (voltar ao topo)
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que responderem a ao menos 75% dos quizzes.
- Consistirá numa prova, em formato similar ao das avaliações regulares.
- Será realizada presencialmente, na terceira semana de retorno das atividades presenciais da UFABC. Em caso excepcional, poderão ser aplicadas de forma online, e os alunos serão avisados com, no mínimo, 7 dias de antecedência.
- O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
- A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média a seguir:
NFR = max {MF, (MF + 2 x NR) / 3}
- Se você é aluno da pós-graduação, o conceito final obtido na recuperação substituirá o conceito original e será
C, se NFR ≥ 5.0
F, se NFR < 5.0
- Se você é aluno da graduação, o conceito final obtido na recuperação substituirá o conceito original e será
C, se NFR ≥ 6.0
D, se 5.0 ≤ NFR < 6.0
F, se 0.0 ≤ NFR < 5.0
🤒 Mecanismos de avaliação substitutivos (voltar ao topo)
A prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas. A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.
A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br