CCM-001 - Análise de Algoritmos e Estruturas de Dados (2019 Q1)
| Professores: | Carla Negri Lintzmayer, Sala 508-2 |
| Guilherme Oliveira Mota, Sala 530-2 |
Avisos importantes (fique atento sempre!)
[02/05] Liberada explicação mais completa sobre o exercício 7 da lista 3.[29/04] Lista 4 atualizada com todas as definições necessárias.
[22/04] Disponibilizada nova lista de exercícios.
[12/04] Disponibilizada lista extra, valendo nota. Verifique o SIGAA (comunique quaisquer erros por e-mail).
[05/04] Disponibilizada lista de exercícios sobre algoritmos gulosos.
[28/03] Grupo de estudos para a prova 1 (organizado pelos alunos): dia 29/03, das 13h às 17h, sala A109, SA.
[20/03] Disponibilizada lista de exercícios.
[11/03] A aula de hoje está cancelada devido aos alagamentos, bem como o atendimento do prof. Guilherme.
[26/02] Grupo de WhatsApp para discussão entre alunos (criado e mantido pelos alunos).
[18/02] Disponibilizada lista de exercícios.
[14/02] ATENÇÃO! Houve mudança definitiva nos locais de aula.
[12/02] A aula do dia 13/02 será na sala S-301-1 (terceiro andar, torre 1).
[29/01] Página da disciplina no ar.
Conteúdo dessa página
 |
Dias, horários e local das aulas (voltar ao topo)
Segundas-feiras, das 14h às 16h, na sala S-301-2 (torre 2).Quartas-feiras, das 14h às 16h, na sala S-301-1 (torre 1).
Dias, horários e local de atendimento (voltar ao topo)
Segundas-feiras, das 13h às 14h, na sala 530-2 do bloco A (prof. Guilherme).Quartas-feiras, das 13h às 14h, na sala 508-2 do bloco A (profa. Carla).
Excepcionalmente, 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.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).
- 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 Programação Estruturada, da prof. Carla Lintzmayer (introdução à programação em C, recursão, vetores e listas).
Bibliografia e outros materiais (voltar ao topo)
- Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 2nd ed. MIT Press. 2002.
- Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
- Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
- Dasgupta, S.; Papadimitriou, C.; Vazirani, U.. Algorithms. Boston: McGraw-Hill. 2008.
- Kleinberg, J.; Tardos, E.. Algorithm design. Pearson/Addison-Wesley. 2006.
- Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados. (em constante atualização).
- Site com execução passo a passo de vários algoritmos em grafos.
- Site Geeks for Geeks, muito bom, com implementações em várias linguagens.
- Grupo de WhatsApp para discussão entre alunos (criado e mantido pelos alunos).
Cronograma (voltar ao topo)
Os tópicos listados abaixo podem ser vistos detalhados aqui.Sobre as notas de aula da prof. Carla, participe do banco de informantes.
| Aula | Data | Conteúdo |
|---|---|---|
| 1 | 11/2 | Introdução ao curso. Multiplicação e Fibonacci. Indução. (notas de aula parte 1 e parte 2) |
| 2 | 13/2 | Insertion Sort com análise. Notação assintótica. (notas de aula) |
| 3 | 18/2 | Estruturas de dados. Exercícios de notação assintótica. (notas de aula) |
| 4 | 20/2 | Introdução a Divisão e Conquista. Mergesort. Recorrências. (notas de aula) |
| 5 | 25/2 | Solução de recorrências: substituição e iteração. |
| 6 | 27/2 | Solução de recorrências: árvore de recursão e Teorema Mestre. |
| 04/3 | ---- Recesso carnaval ---- | |
| 06/3 | ---- Recesso carnaval ---- | |
| 11/3 | ---- Cancelada ---- | |
| 7 | 13/3 | Quicksort. |
| 8 | 18/3 | Selection Sort. Fila de prioridades. Heapsort. |
| 9 | 20/3 | Grafos. Busca em largura. |
| 10 | 25/3 | Busca em profundidade. |
| 11 | 27/3 | Revisão e resolução de exercícios. |
| 12 | 01/4 | Primeira prova |
| 13 | 03/4 | Discussão sobre a prova. Introdução a Algoritmos Gulosos: escalonamento de tarefas. (materiais extra para estudo: site prof. Feofiloff, texto prof. Flávio Miyazawa, vídeo aulas prof. Roughgarden) |
| 08/4 | ---- Feriado municipal em SA ---- | |
| 14 | 10/4 | Mochila Fracionária. Árvore geradora mínima. |
| 15 | 15/4 | Algoritmo de Kruskal. Caminhos mínimos. |
| 16 | 17/4 | Algoritmo de Dijkstra. |
| 17 | 22/4 | Introdução a Programação Dinâmica: corte da barra de ferro e mochila inteira. (material extra: notas de aula prof. Carla) |
| 18 | 24/4 | Redução de problemas. Classes P e NP. |
| 19 | 29/4 | Classes NP-Completo e NP-Difícil. Abordagens para tratamento de problemas nessas classes. |
| 01/5 | ---- Feriado: Dia do trabalho ---- | |
| 20 | 06/5 | Revisão e resolução de exercícios. |
| 21 | 08/5 | Segunda prova |
| 22 | 13/5 | Prova substitutiva/Recuperação |
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
- 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.
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.
- Prova 1 vale 40% da nota.
- Prova 2 vale 60% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.4 x P1 + 0.6 x P2 - 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
- No decorrer do curso serão disponibilizadas listas de exercícios. Elas não valem nota, visto que o objetivo principal é prover ao aluno uma lista de problemas representativos dos conceitos vistos.
- Lista 1
- Lista 2
- Lista 3
- Lista 4
Mecanismo de recuperação (voltar ao topo)
- A recuperação será aplicada apenas aos alunos que tiverem conceito final F e cujas ausências não excederem 25% da quantidade de aulas.
- Consistirá numa prova, em formato similar às aplicadas ao longo do curso.
- 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 + NR) / 2}
- O conceito final obtido na recuperação substituirá o conceito original
e será
C, se NFR ≥ 5.0
F, se NFR < 5.0