Análise de Algoritmos - A1 (noturno)

Prof. Ronaldo Cristiano Prati

Bloco A, sala 513-2

Avisos

Notas da Recuperação foram divulgadas
Notas da Conceitos preliminares foram divulgadas (revisão no horário de atendimento)
Notas da Prova2 foram divulgadas (revisão no horário de atendimento)
Notas da Prova1 foram divulgadas (revisão no horário de atendimento)
A lista 4 está disponível
A lista 3 está disponível
O gabarito da prova 1 está disponível
A lista 2.5 (grafos) está disponível
Você pode enviar a resolução da lista para ser corrigida pelo monitor
A lista 2 está disponível
A aula de 14/06 foi suspensa, de acordo com comunicado da reitoria
A lista 1 está disponível

Horário das aulas

Quartas-feiras, das 21h às 23h, sala A105-0.
Sextas-feiras, das 19h às 21h, sala A105-0.

Atendimento

Quartas-feiras, das 18h às 20, sala 513-2, bloco A

Ementa da disciplina

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

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

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

Materiais de apoio para esses tópicos:

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.
Como pensar como um cientista da computação (Introdução à programação em Python, recursão, listas)
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 materiais de apoio

[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 construçã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.
[M] Vídeo aulas do prof. Marcelo Carvalho (UFMS)

Cronograma

Aula	Data	Tópicos
1	05/6	[pdf] [html] Introdução ao curso. Multiplicação. Referências: [LM],
2	07/6	[pdf] [html] 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].
3	12/6	[pdf] [html] 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].
	14/6	cancelada
4	19/6	[pdf] [html] Divisão e Conquista. Mergesort. Recorrências. 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].
	21/6	---- Feriado ----
5	26/6	[pdf] [html] Solução de recorrências: substituição e iteração. Referências: Cap. 3 [LM], Cap. 4 [CLRS2].
6	28/6	[pdf] [html] 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].
7	03/7	[pdf] [html] Quicksort. Referências Cap. 14 [LM], Cap. 7 [CLRS2], 5.1, 5.2, 5.3, 5.4 [R].
8	05/7	[pdf] [html] Selection Sort. Heap. Heapsort. Referências: Parte II, Cap. 8 e 13.2 [LM], Cap. 6 [CLRS2], 12.1, 12.2, 12.3 [R].
9	10/7	[pdf] [html] Grafos. Estrutura de dados Busca em grafos. Cap. 19 e 20 [LM], Cap. 22 [CLRS2], 9.2, 10.1 [R].
10	12/7	[pdf] [html] Busca em grafos. Aplicações.Referências: Cap. 20 [LM], Cap. 22 [CLRS2], 10.2, 10.3, 10.4, 10.5 [R].
11	17/7	Solução de exercícios.
12	19/7	gabarito Prova 1
13	24/7	[pdf] [html] Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária. 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.
14	26/7	[pdf] [html] Á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.
15	31/7	[pdf] [html] 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.
16	02/8	[pdf] [html] 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
17	07/8	[pdf] [html] Alinhamento de sequências. Algoritmo de Needleman-Wunsch. Referências: Cap. 18 [LM], Cap. 15 [CLRS3], 47, 48 [R]. Extra: animação Needleman-Wunsch.
18	09/8	[pdf] [html] Caminhos mínimos. Algoritmo de Floyd-Warshall. Referências: Cap. 23 [LM], Cap. 25 [CLRS2], 62, 63, 64 [R].Extra: animação Floyd-Warshall.
29	14/8	[pdf] [html] Redução. Classes P, NP, NP-difícil e NP-completo. Referências: Cap. 24 [LM], Cap. 34 [CLRS2], 68, 69, 70, 71, 72 [R]. Extra: Uma pergunta de um milhão de dólares, P vs. NP and the Computational Complexity Zoo, Map of Computer Science (não exatamente relacionado com a aula).
20	16/8	[pdf] [html] Abordagens para problemas NP-difíceis.
21	21/8	Solução de exercícios.
22	23/8	Prova 2
23	28/8	Prova de recuperação (reposição do feriado, portanto aula às 19h)

Listas de exercícios

Serão disponibilizadas listas de exercícios
Não é necessário entregar a resolução das listas, mas...
Pelo menos 25% das provas terão exercícios será muito parecido com exercícios das listas
Você pode enviar a solução das listas 1 e 2 para serem corrigidas pelo monitor usando esse link até o dia 10/07
Lista 1 - notação assintótica e divisão e conquista
Lista 2 - Recorrências
Lista 2.5 - Grafos
Lista 3 - Algoritmos gulosos
Lista 4 - Programação dinâmica

Avaliação

A avaliação da disciplina constituirá da nota de duas provas ( $P1$ e $P2$ ).
A média final $MF$ será dada por
$MF = 0.4 * P1 + 0.6 * P2$
O conceito $CF$ $C F$ será atribuído com
- A, se $MF \ge 8.5$
- B, se $7.0 \le MF < 8.5$
- C, se $6.0 \le MF < 7.0$
- D, se $5.0 \le MF < 6.0$
- F, se $MF < 5.0$

Recupeção

A recuperação será aplicada apenas aos alunos que tiverem conceito final $D$ ou $F$ e cujas presença seja maior que 75% das 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 curso.
A nota obtida na prova de recuperação ( $NR$ ) serpa usada para calcular o conceito finall obtido na recuperação $CR$ :
- C, se $NR > 6.5$
- D, se $5.5 > NR \le 6.5$ , ou $NR<5.5$ e $CF$ = D
- F, se $NF < 5.5$ e $CF$ = F

Avaliação substitutiva

A prova substitutiva será aplicada ao aluno que tiver 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 substitui a prova para a qual o aluno tem justificativa.
A solicitação de avaliação substitutiva deve ser feita por e-mail, acompanhada de cópia digital da justificativa. A data para realização da prova substitutiva deverá ser combinada com a professor por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.