2025 Q1

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

Professora: Carla Negri Lintzmayer

🚨 Avisos importantes (fique atento sempre!)

📌 [2/mai] A prova 2 terá duração de 3h.

[13/abr] Disponibilizei as notas da Prova 1, na seção Notas. As vistas de provas devem ser feitas nos horários de atendimento ou entre 16h e 16h30 nas terças-feiras (na sala de aula). Caso não consiga comparecer em nenhum desses horários, me mande um e-mail para marcamos outro horário.
[2/abr] Disponibilizei algumas soluções das listas 4, 5 e 6 de exercícios.
[21/mar] A prova 1 terá duração de 3h, conforme pedido em sala hoje.
[26/fev] Disponibilizei algumas soluções da lista 2 de exercícios.
[14/fev] Todas as notas de aula das aulas anteriores à prova 1 já estão disponíveis!
[03/fev] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em avaliação!

📝 Dias, horários e locais das aulas

Terças-feiras, das 14h às 16h, na sala S-308-2.

Sextas-feiras, das 14h às 16h, na sala S-308-2.

🙋 Dias, horários e locais dos atendimentos

Sextas-feiras, das 16h às 18h, na sala de aula ou na sala da docente. Basta aparecer!

Atenção! Eu não faço atendimento por e-mail!

🧐 Ementa da disciplina

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

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.

🖖 Recomendação

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).

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.

⚠ Revise, no mínimo, indução e recursão antes das aulas começarem!!!⚠
Veja a lista 0 de exercícios!

Outros materiais de apoio:

Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
Videoaulas de Fundamentos da matemática para computação, do prof. Cláudio Possani, da USP.
Meus vídeos com definição e exemplos de indução.
Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
Videoaulas de Algoritmos e Estruturas de Dados I, do prof. Mário San Felice, da UFSCar.
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).

📚 Bibliografia e outros materiais

[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 pequenas atualizações - verifique sempre sua versão).
[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.

⏰ Datas importantes

Resumo das datas importantes:

Prova 1: 25/março
Prova 2: 16/maio
Prova de recuperação: 7/junho (10h)

📆 Cronograma

ATENÇÃO! O conteúdo exato e materiais de apoio de cada aula são atualizados durante o quadrimestre e as aulas que já foram ministradas estão coloridas.
Ou seja, as aulas que ainda não estão coloridas podem ter o conteúdo alterado!

Aula 1 - 11/fev

Conteúdo: Sobre o curso.
Referências: Cap. 1 [LM], Apêndices A e B [CLRS3]. Veja também a seção de recomendação.
Material complementar: slides de introdução ao curso e revisão; Lista 0; vídeos sobre indução:

Aula 2 - 14/fev

Conteúdo: Introdução à análise de algoritmos. Corretude de algoritmos (iterativos).
Referências: Cap. 2 e 3 [LM], Cap. 1 e 2 [CLRS3].
Material complementar: notas de aula.

Aula 3 - 18/fev

Conteúdo: Tempo de execução. Notação assintótica.
Referências: Cap. 4 e 5 [LM], Cap. 3 [CLRS3].
Material complementar: notas de aula.

Aula 4 - 21/fev

Conteúdo: Tempo com notação assintótica.
Referências: Cap. 6 e 15 [LM], Cap. 2 [CLRS3],
Material complementar: notas de aula.

Aula 5 - 25/fev

Conteúdo: Insertion Sort. Recursão. Corretude e tempo de execução em algoritmos recursivos.
Referências: Cap. 7 e 8 (intro) [LM], Cap. 2.3, 4 (intro) [CLRS3],
Material complementar: notas sobre o Insertion Sort. notas sobre recursão.
Extra: execução Insertion Sort.

Aula 6 - 28/fev

Conteúdo: Corretude e tempo de execução em algoritmos recursivos. Divisão e Conquista. Mergesort. Recorrências.
Referências: Cap. 16 [LM], Cap. 4 [CLRS3].
Material complementar: notas de aula.
Extra: execução Mergesort, execução Mergesort com código.

04/mar (Feriado Carnaval)

Reposição em 6/mai (terça-feira).

Aula 7 - 07/mar

Conteúdo: Solução de recorrências: substituição e iteração.
Referências: Cap. 8.1 e 8.2 [LM], Cap. 4 [CLRS3].
Material complementar: notas de aula.

Aula 8 - 11/mar - Sem aula presencial!

Sem aula presencial. Aproveite para resolver exercícios!

Aula 9 - 14/mar

Conteúdo: Solução de recorrências: árvore de recursão e método Mestre. Selection Sort.
Referências: Cap. 8.3 e 8.4 [LM], Cap. 4 [CLRS3].
Material complementar: notas de aula.

Aula 10 - 18/mar

Conteúdo: Selection Sort. Heap. Heapsort. Fim de ordenação
Referências: Cap. 12 e 17 [LM], Cap. 6 [CLRS3].
Material complementar: notas de aula.
Extra: execução SelectionSort, execução Heap, execução Heap e Heapsort, execução Heapsort, execução ordenação, limite inferior ordenação;

Aula 11 - 21/mar

Conteúdo: Ajuste de conteúdo. Revisão e dúvidas para prova.

Aula 12 - 25/mar

Prova 1

Aula 13 - 28/mar

Conteúdo: Introdução a grafos (grafos, digrafos, Teorema do Aperto de Mãos, subgrafos, passeios/caminhos, conexidade e distância). Introdução à análise de algoritmos em grafos (representação em listas e matriz de adjacências e cálculo do grau).
Referências: Cap. 23 (até seção 23.8) [LM], Cap. 22 [CLRS3].
Material complementar: texto completo da aula, implementações.

Aula 14 - 01/abr

Conteúdo: Árvores. Busca em grafos e busca em largura.
Referências: Seções 23.8, 23.9, 23.10 e 24.1 [LM], Cap. 22 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução BFS, execução BFS.

Aula 15 - 04/abr

Conteúdo: Busca em profundidade. Aplicações das buscas. Busca em digrafos. Introdução a algoritmos gulosos.
Referências: Seções 24.2, 24.3, 24.4 e 24.5 [LM], Cap. 22 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução DFS.

08/abr (Feriado Aniversário Santo André)

Reposição em 9/mai (sexta-feira).

Aula 16 - 11/abr

Conteúdo: Escalonamento de tarefas compatíveis e mochila fracionária.
Referências: intro 21, 21.1 [LM], Cap. 16 [CLRS3].
Material complementar: texto completo da aula.

Aula 17 - 15/abr

Conteúdo: Término da mochila fracionária. Árvore geradora mínima. Algoritmo de Kruskal. Union-Find.
Referências: Seção 21.2, 25 e 13 [LM], Cap. 23 e 21 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução Union Find; outra execução Union Find; execução Kruskal; outra execução Kruskal.

18/abr (Feriado Paixão de Cristo)

Reposição em 13/mai (terça-feira).

Aula 18 - 22/abr

Conteúdo: Kruskal com Union-Find. Introdução à Programação Dinâmica. Corte de barra de ferro.
Referências: Seção 25.1, intro Cap. 22, Seção 22.3 [LM], Cap. 15 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução Mochila com código.

Aula 19 - 25/abr

Conteúdo: Mochila inteira. Alinhamento de sequências.
Referências: Seção 22.4 e Cap. 27 e Seções 27.1 e 27.2 [LM], Cap. 15 e 24 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução Alinhamento.

Aula 20 - 29/abr

Conteúdo: Caminhos mínimos em grafos. Algoritmo de Dijkstra. Algoritmo de Floyd-Warshall.
Referências: Cap. 28 [LM], Cap. 24 e 25 [CLRS3].
Material complementar: texto completo da aula.
Extra: execução Dijkstra, outra execução Dijkstra, execução Floyd-Warshall.

02/mai (Recesso Dia do Trabalho)

Reposição em 16/mai (sexta-feira).

Aula 21 - 06/mai

Conteúdo: Redução entre problemas. Classes P e NP.

Referências: Cap. 29 [LM], Cap. 34 [CLRS3].

Material complementar: slides da aula.

Aula 22 - 09/mai

Classes NP-completo e NP-difícil. Problemas NP-completos.
Referências: Cap. 29 [LM], Cap. 34 [CLRS3].
Material complementar: slides da aula.
Extra: Curso de otimização combinatória - como lidar com problemas NP-difíceis.

Aula 23 - 13/mai

Conteúdo: Ajuste de conteúdo. Revisão e dúvidas para prova.

Aula 24 - 16/mai

Prova 2
Atenção! Não haverá atendimento após a aula neste dia!

RECUPERAÇÃO - 07/jun (quadrimestre seguinte)

Prova de recuperação para os alunos que ficaram com conceito F ** E QUE ** enviarem e-mail indicando interesse em realizá-la.
Das 10h às 12h em sala a decidir.

👎 Plágio

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:

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.

Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

🏋 Listas de exercícios

Sobre gabaritos de listas de exercícios:
eu acredito que o objetivo de um exercício teórico não é a resolução do problema em si, mas sim praticar a resolução de problemas;
você precisa chegar nas soluções por conta própria (com algumas dicas da minha parte) ao invés de apenas ler um gabarito (que mostrará uma única solução possível);
por isso, eu não disponibilizo gabaritos completos das minhas listas;
a melhor forma para você saber se resolveu o exercício corretamente é me procurando em horários de atendimento e me mostrando a sua solução.
Sobre descrição de algoritmos nos exercícios: veja essa página.

Ao todo teremos 6 listas, cujos enunciados estão disponibilizados abaixo.
O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
Procure atendimento sempre que tiver dúvidas nos exercícios.
Faça o maior número de exercícios que puder, sempre.
- Vale moral!!
  Qualquer exercício extra que for feito pode ser entregue nos dias das provas para serem considerados como evidência do seu esforço.
  Participar das aulas e dos atendimentos também vale moral.
  Alunos com moral terão direito a pedir arredondamento de conceitos e notas ou abono de alguma falta ao final do curso.
  Em nenhuma hipótese será feito o arredondamento de conceitos ou abono de faltas para alunos sem moral.
- Lista 0 (revisão)
  Vocês podem ver as soluções de alguns exercícios neste documento.
- Lista 1 (tempo de execução, notação assintótica e corretude de algoritmos iterativos - Aulas 1 a 4)
  Vocês podem ver as soluções de alguns exercícios neste documento ou então nestes vídeos:
- Lista 2 (recorrências e corretude de algoritmos recursivos - Aulas 5 a 9)
  Vocês podem ver as soluções de alguns exercícios neste documento ou então nestes vídeos:
- Lista 3 (ordenação - Aulas 4, 6 e 10)
  Vocês podem ver as soluções de alguns exercícios neste documento.
- Lista 4 (introdução a grafos - Aulas 13 a 15)
  Vocês podem ver as soluções de alguns exercícios neste documento.
- Lista 5 (algoritmos gulosos e programação dinâmica - Aulas 16 a 20)
  Vocês podem ver as soluções de alguns exercícios neste documento.
- Lista 6 (complexidade - Aulas 21 e 22)
  Vocês podem ver as soluções de alguns exercícios neste documento.

🎓 Critérios de avaliação

A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, respectivamente.
- A prova 1 vale 50% da nota e 0 ≤ P₁ ≤ 10.
- A prova 2 vale 50% da nota e 0 ≤ P₂ ≤ 10.

Sua média final (MF), portanto, será

MF = 0.5 x P1 + 0.5 x P2

Seu conceito final será

A, se MF ≥ 8.5
B, se 7.0 ≤ MF < 8.5
C, se 6.0 ≤ MF < 7.0
F, se MF < 6.0

Não esqueça do vale moral!

💯 Notas

Veja planilha aqui!

💪 Mecanismo de recuperação

A recuperação será aplicada apenas aos alunos que tiverem conceito final F e que enviarem e-mail confirmando interesse.
O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
A nota obtida na prova de recuperação (NR) será usada para obter a nota final com recuperação (NFR), que consiste na fórmula a seguir:
NFR = max {MF, (MF + NR) / 2}
O conceito final obtido na recuperação substituirá o conceito original e será
C, se NFR ≥ 6.0
F, se NFR < 6.0

🤒 Mecanismos de avaliação substitutivos

Uma 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