MCTA003-17 - Análise de Algoritmos - Diurno (2019 Q2)

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

Avisos importantes (fique atento sempre!)

[10/09] Avisos finais: ― novos ↑ ―

[31/08] Atenção! Avisos semifinais: [26/08] Atenção! A sala da prova será diferente da sala normal: S205-0. Lembrem-se que o horário é às 8h.
[07/08] Lista 4 disponibilizada.
[05/08] Horários extras de atendimento (basta aparecer na minha sala): [02/08] Notas da prova 1 disponibilizadas. Vistas de prova poderão ser feitas em qualquer um dos horários de atendimento. Se necessário, me mande um e-mail para marcar outro horário.
[26/07] Lista 3 disponibilizada.
[21/07] Data da prova de recuperação definida para o dia 04/09, conforme calendário atualizado pela Prograd.
[12/07] Lista 2.5 disponibilizada.
[08/07] Sites para visualização dos algoritmos: prof. David Galles e VisuAlgo.
[26/06] Lista 2 disponibilizada.
[17/06] Atenção para mudança no cronograma!! Houve mudança nas datas das provas e das listas.
[13/06] A aula do dia 14/06 está oficialmente cancelada. Aproveitem para começar a lista. Por enquanto não haverá mudança nas datas das provas.
[12/06] Lista 1 disponibilizada.
[24/05] Atenção: não haverá aula no dia 5/06. A primeira aula será no dia 7/06 (sexta-feira).
[24/05] 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 10h às 12h, sala A-113-0.
Sextas-feiras, das 8h às 10h, sala A-113-0.

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

Quintas-feiras, das 13h15 às 15h15 e das 17h às 19h, na sala 508-2 do bloco A.

Ementa da disciplina (voltar ao topo)

(Disponível na pg. 54 do projeto pedagógico.)
Conceitos básicos: recorrências, medidas de complexidade: melhor caso, caso médio e pior caso. Técnicas gerais de projeto de algoritmos: divisão e conquista, método guloso e programação dinâmica. Classes de complexidade: P, NP e NP-completude.
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)

Disciplinas: Matemática Discreta; Algoritmos e Estruturas de Dados I.

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 05/6 Não haverá aula presencial: revisar base matemática e recursão.
Referências: material extra e outros
2 07/6 Introdução ao curso. Multiplicação e Fibonacci.
Referências: [LM], notas de aula, Cap. 1 [CLRS2], Cap. 0.2 [DPV], 1.1, 1.2 e 1.3 [R].
3 12/6 Insertion Sort com análise. Notação assintótica.
Referências: Cap. 1, 11 [LM], notas de aula, Cap. 2.1, 2.2, 3.1 [CLRS2], Cap. 0.3 [DPV], 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
Extra: animação InsertionSort.
14/6 ---- Aula cancelada (greve) ----
4 19/6 Notação assintótica.
Referências: Cap. 1, 11 [LM], notas de aula, Cap. 2.1, 2.2, 3.1 [CLRS2], Cap. 0.3 [DPV], 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
21/6 ---- Feriado (recesso por Corpus Christi) ----
5 26/6 Divisão e Conquista. Mergesort.
Referências: Cap. 3, 12, 16 [LM], notas de aula, Cap. 2.3, 4 (intro) [CLRS2], Cap. 2.3 [DPV], 1.5, 1.6, 1.7 e 4.1 [R].
Extra: animação Mergesort, animação ordenação, limite inferior ordenação.
6 28/6 Recorrências. Solução de recorrências: substituição e iteração.
Referências: Cap. 3 [LM], Cap. 4 [CLRS2].
7 03/7 Solução de recorrências: árvore de recursão e Teorema Mestre.
Referências: Cap. 3 [LM], Cap. 4 [CLRS2], 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 [R].
8 05/7 Quicksort. Selection sort.
Referências: Cap. 14 e 13.1 [LM], Cap. 7 [CLRS2], 5.1, 5.2, 5.3, 5.4 [R].
Extra: animação Quicksort, animação SelectionSort, animação ordenação.
9 10/7 Heap. Heapsort.
Referências: Parte II, Cap. 8 e 13.2 [LM], Cap. 6 [CLRS2], 12.1, 12.2, 12.3 [R].
Extra: animação Heap e Heapsort, animação Heap, animação Heapsort.
10 12/7 Grafos. Busca em grafos.
Referências: Cap. 19 e 20 [LM], Cap. 22 [CLRS2], 9.2, 10.1 [R].
Extra: implementação, visualizador simples.
11 17/7 Busca em largura e em profundidade. Aplicações.
Referências: Cap. 20 [LM], Cap. 22 [CLRS2], 10.2, 10.3, 10.4, 10.5 [R].
Extra: animação BFS e DFS, animação BFS, animação DFS.
12 19/7 Solução de exercícios.
Referências: listas.
13 24/7 Prova 1
14 26/7 Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária.
Referências: Cap. 17 [LM], Cap. 16 [CLRS2], 3, 5, 6, 7, 8 [R].
Extra: site prof. Feofiloff, texto prof. Flávio Miyazawa.
15 31/7 Árvore geradora mínima. Algoritmo de Kruskal. Union-Find.
Referências: Cap. 21 [LM], Cap. 23 [CLRS2], 10, 17, 18, 19, 20, 21 [R].
Extra: animação Union Find, outra animação Union Find, animação Kruskal, outra animação Kruskal.
16 02/8 Compressão de dados. Algoritmo de Huffman.
Referências: Cap. 17 [LM], Cap. 16 [CLRS2], 33, 34, 35, 36, 37, 38 [R].
Extra: animação Huffman.
17 07/8 Introdução a Programação Dinâmica. Corte da barra de ferro. Mochila inteira.
Referências: Cap. 18 [LM], Cap. 15 [CLRS3], 39, 43, 44, 45, 46 [R].
Extra: animação Fibonacci, animação Mochila, exemplo "real" em um problema de redimensionamento de imagem sensível ao conteúdo (mais detalhes aqui).
18 09/8 Alinhamento de sequências. Algoritmo de Needleman-Wunsch.
Referências: Cap. 18 [LM], Cap. 15 [CLRS3], 47, 48 [R].
Extra: animação Needleman-Wunsch.
19 14/8 Caminhos mínimos. Algoritmo de Floyd-Warshall.
Referências: Cap. 23 [LM], Cap. 25 [CLRS2], 62, 63, 64 [R].
Extra: Resumo das duas abordagens vistas em aula, animação Floyd-Warshall.
20 16/8 Redução. Classes P e NP.
Referências: Cap. 24 [LM], Cap. 34 [CLRS2], 68, 69, 70, 71, 72 [R].
Extra: Slides usados em aula, P vs. NP and the Computational Complexity Zoo, Map of Computer Science (não exatamente relacionado com a aula).
21 21/8 Problemas NP-completos e NP-difíceis. Abordagens para problemas NP-difíceis.
Referências: Cap. 24 [LM], Cap. 34 [CLRS2], 68, 69, 70, 71, 72 [R].
Extra: Slides usados em aula, slides antigos meus, sobre otimização combinatória, mais vídeos sobre abordagens.
22 23/8 Ajuste. Solução de exercícios.
Referências: listas.
23 28/8 Prova 2 (reposição do feriado, portanto aula às 8h)
24 04/09 Prova de recuperação (reposição do dia da greve, portanto aula às 8h)

Plágio (voltar ao topo)

Listas de exercícios (voltar ao topo)

Lista 1: notação assintótica e divisão e conquista (disponível em 12/06 - entrega até 30/06)
Lista 2: recorrências e ordenação (disponível em 26/06 - entrega até 14/07)
Lista 2.5: grafos (disponível em 12/07 - entrega até 23/0728/07)
Lista 3: gulosos (disponível em 26/07 - entrega até 13/08)
Lista 4: programação dinâmica e complexidade (disponível em 07/08 - entrega até 27/08)

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