CCM-001 - Análise de Algoritmos e Estruturas de Dados (2020 Q1)

MCTA003-17 - Análise de Algoritmos

Professora: Carla Negri Lintzmayer, Sala 508-2, carla.negri@ufabc.edu.br

🚨 Avisos importantes (fique atento sempre!)

🆕 [25/03] Atenção: [23/03] A suspensão das aulas continua até 29 de março, por enquanto (veja portaria).
[17/03] Criei um grupo no Discord para nos comunicarmos melhor durante essa pausa.
[15/03] Sobre a paralisação das aulas entre 16 e 22 de março: [10/03] Disponibilizada solução de alguns exercícios da lista 1.
[04/03] Disponibilizada lista 2 de exercícios.
[28/02] O enunciado do exercício 5 da lista 1 foi alterado.
[27/02] Definida sala do atendimento extra da monitora: S-311-2. Será no dia 29/02, das 13h às 15h.
[21/02] O enunciado do exercício 4 da lista 1 foi alterado.
[15/02] Disponibilizada lista 1 de exercícios.
[14/02] Grupo de Whatsapp criado e mantido pelos alunos.
[14/02] Disponibilizados horários extras de atendimento da monitora, com início em 18/02.
[05/02] Página da disciplina no ar.

Conteúdo dessa página

piadinha

🕐 Dias, horários e local das aulas (voltar ao topo)

Quartas-feiras, das 16h às 18h, sala A-106-0.
Sextas-feiras, das 16h às 18h, sala A-106-0.

🆘 Dias, horários e local de atendimento (voltar ao topo)

Quartas-feiras, das 18h às 20h, na sala 508-2 do bloco A, com a profa. Carla.
Sextas-feiras, das 18h às 20h, na sala 508-2 do bloco A, com a profa. Carla.
Em geral, pouco antes das aulas.
Terças-feiras, das 16h30 às 19h30, S-310-2, com a monitora Poliana.
Sextas-feiras, das 14h às 16h, S-309-2, com a monitora Poliana.

Nesse horários não é preciso confirmar ou marcar, apenas apareça!

Se não puder, me mande um e-mail para combinarmos outro horário.
Algumas dúvidas (mais simples) podem ser tiradas por e-mail.

🤓 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: Materiais de apoio para esses tópicos:

📖 Bibliografia e outros materiais (voltar ao topo)

[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.
[LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados. (em constante atualização).
[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.

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 e Heapsort, animação Heap, animação Heapsort, animação ordenação. Vídeos sobre heap: 12.1, 12.2, 12.3 [R].
18/03 Aula cancelada devido ao surto do COVID-19.
20/03 Aula cancelada devido ao surto do COVID-19.
10 ?? Heapsort. Grafos.
11 ?? Busca em grafos.
12 ?? Busca em grafos. Aplicações.
13 ?? Solução de exercícios.
* ?? Atendimento extra da monitora
14 ?? Prova 1
15 ?? Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária.
16 ?? Árvore geradora mínima. Algoritmo de Kruskal. Union-Find.
17 ?? Introdução a Programação Dinâmica. Corte da barra de ferro. Mochila inteira.
18 ?? Alinhamento de sequências. Algoritmo de Needleman-Wunsch.
19 ?? Caminhos mínimos em grafos. Algoritmo de Floyd-Warshall.
20 ?? Redução.
21 ?? Classes P, NP, NP-completo e NP-difícil.
22 ?? Solução de exercícios.
* ?? Atendimento extra da monitora
23 ?? Prova 2
24 ?? Prova de recuperação (sala e horário a definir)

👎 Plágio (voltar ao topo)

🎓 Critérios de avaliação (voltar ao topo)

🏋 Listas de exercícios (voltar ao topo)

Lista 1: notação assintótica e divisão e conquista (disponível em 15/02)
Lista 2: recorrências e ordenação (disponível em 04/03)
Lista 2.5: grafos (disponível em 18/03)
Lista 3: gulosos (disponível em 04/04)
Lista 4: programação dinâmica e complexidade (disponível em 18/04)

💪 Mecanismo de recuperação (voltar ao topo)

🤒 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