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.
― novos ↑ ―
[29/04] As listas 3 e 4 podem ser entregues no dia da Prova 2 e valerão até 2 pontos, que serão somados à nota da Prova 2.
[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

piadinha

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

Bibliografia e outros materiais (voltar ao topo)

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)

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

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.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br
Guilherme Oliveira Mota - g.mota@ufabc.edu.br