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:- Notas da prova de recuperação.
- Por favor, preencha o formulário anônimo de avaliação da disciplina.
- Horários de atendimento para vista de provas/listas/faltas: estarei todos os dias do recesso na minha sala e peço que quem quiser me mande um e-mail para combinarmos um horário. No começo do Q3 também será possível, pois as notas serão lançadas no sistema no dia 14/10.
[31/08] Atenção! Avisos semifinais:
- Notas da prova 2 e das listas disponibilizadas. Me avise sobre qualquer problema!
- Por favor, preencha o formulário anônimo de avaliação da disciplina.
- Horários de atendimento para a rec e/ou vista de provas/listas/faltas: 03/09, das 9h às 12h30 e das 18h às 21h30.
- Me mande um e-mail se você for realizar a rec! Lembrem-se que será às 8h do dia 04/09.
[07/08] Lista 4 disponibilizada.
[05/08] Horários extras de atendimento (basta aparecer na minha sala):
- 12/08 (segunda) - 17h às 22h
- 13/08 (terça) - 10h às 12h
- 16/08 (sexta) - 10h às 12h
- 20/08 (terça) - 10h às 13h
- 20/08 (terça) - 17h às 22h
- 23/08 (sexta) - 10h às 12h
[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
 |
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:
- 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)
- [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)
- 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.
- Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC.
- Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima.
- Abaixo uma versão resumida, que não substitui de modo algum sua leitura.
- Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!
- Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
- Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
- Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
- Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
- 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.
- Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.
Listas de exercícios (voltar ao topo)
- Ao todo teremos 4.5 listas, cujos enunciados serão disponibilizados aqui, nas datas indicadas abaixo.
- As soluções das listas de exercícios deverão ser feitas à mão (capriche na letra!), escaneadas e um único arquivo formato PDF deve ser entregue (sugestão de aplicativo: CamScanner).
- A entrega deverá ser feita apenas pelo tidia (a menos que haja problemas no tidia nas datas em questão, caso em que elas podem ser entregues por e-mail).
- Todos os prazos de entrega já estão definidos (marque na sua agenda!).
- Soluções entregues fora do prazo valerão 0.
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, e da média simples das notas das listas de exercícios, denotada por L.
- A prova 1 vale 35% da nota.
- A prova 2 vale 45% da nota.
- As listas valem 20% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.35 x P1 + 0.45 x P2 + 0.2 x L - Seu conceito final será
A, se MF ≥ 8.5
B, se 7.0 ≤ MF < 8.5
C, se 6.0 ≤ MF < 7.0
D, se 5.0 ≤ MF < 6.0
F, se MF < 5.0
Mecanismo de recuperação (voltar ao topo)
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou 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 ≥ 6.0
D, se 5.0 ≤ NFR < 6.0
F, se 0.0 ≤ NFR < 5.0
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