2020 QS
CCM-001 - Análise de Algoritmos e Estruturas de Dados (Pós)
MCTA003-17 - Análise de Algoritmos (A1 - noturno)
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
🚨 Avisos importantes (fique atento sempre!)
📌 [26/dez] Avisos finais:- Corrigi as provas de recuperação. Se você a fez, enviei por email com alguns comentários.
- As notas finais e os critérios estão na planilha na seção de notas.
- Peço que se você ficou com alguma dúvida na nota que foi dada ou acha que eu dei uma nota incorreta, me mande um e-mail dizendo qual é a questão e justificando porque você acha que esse é o caso.
Por favor, não diga apenas "acho que a minha questão está correta".
Preciso subir as notas no sistema ainda este ano, então por favor faça isso até o dia 29/12.
[13/dez] Avisos (semi-)finais importantes:
- Eu corrigi a lista 6 e fiz anotações em cada uma, porém perdi todos os arquivos 😥 Me desculpem. Vou fazer sob demanda: quem quiser mais detalhes, me avise que eu faço.
- Corrigi as provas. Se você a fez, enviei por email com alguns comentários.
- A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F.
Estou considerando que se você não fez nenhuma atividade, desistiu da disciplina e por isso ficou com conceito O.
Se você deseja fazê-la, me envie um email informando isso.
A PROVA SERÁ ENVIADA APENAS PARA QUEM MANIFESTAR INTERESSE. - Fiz um formulário anônimo de fim de curso com perguntas específicas dessa modalidade à distância.
Peço que você gaste mais esses minutinhos com a disciplina para me ajudar a melhorar: clique aqui. - As notas finais (pré-rec) estão na planilha na seção de notas.
Amanhã temos os dois atendimentos, que podem ser utilizados para discutir a prova ou tirar dúvidas para a recuperação.
[23/nov] Adiei o prazo da lista 5 para o dia 26/11.
[12/nov] Corrigi a lista 4 e enviei e-mail com anotações para cada um. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[2/nov] Atenção! Todas as listas e quizzes já estão liberados. Observe as datas com atenção.
[2/nov] Corrigi a lista 3 e enviei e-mail com anotações para cada um. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[27/out] Corrigi a lista 2 e enviei e-mail com anotações para cada um. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[19/out] Adiei o prazo da lista 3 para o dia 29/10.
[13/out] Corrigi a lista 1 e enviei e-mail com anotações para cada um. As notas estão na planilha na seção de notas. Veja o Discord se você não enviou a lista, também deixei informações lá.
[6/out] Solução de alguns exercícios sobre notação assintótica. Lembrem-se de usar isso como apoio, mas não como a única forma de responder esses exercícios.
[21/set] Atenção! Os links das aulas ao vivo e dos atendimentos serão disponibilizados apenas no Discord.
[18/set] Seção cronograma atualizada com as videoaulas.
[3/set] Leia a seção sobre como será a disciplina sem falta!
[3/set] Apenas para matriculados: grupo no Discord e formulário de início de curso para graduação e para pós-graduação.
[3/set] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova (Será que não vai? 🤔).
🙋 Como será a disciplina?
Nosso meio de comunicação principal será o grupo na ferramenta Discord.
Por favor, participe do grupo apenas se você está matriculado na disciplina ou é aluno especial.
O site sempre será mantido atualizado, porém comunicados menores e atendimentos serão pelo Discord.
Aliás, esse grupo no Discord pode e deve ser utilizado em qualquer horário, para atendimento assíncrono.
(Na maioria das vezes, é síncrono 🙈)
As videoaulas com os conteúdos da disciplina serão disponibilizadas na seção Cronograma.
Os conteúdos foram distribuídos da forma como eles seriam dados no presencial.
É muito importante que você não só veja os vídeos, mas também consiga ler as notas de aula, que foram preparadas com muito carinho ao longo de outras instâncias do curso.
Pequenos erros seguem sendo atualizados constantemente, mas todo o conteúdo dessa disciplina já está disponível.
Particularmente, o conteúdo da Parte I vai te auxiliar muito no começo da disciplina.
Atenção! Três aulas serão dadas de forma síncrona, como pode ser visto no cronograma.
A sua participação é essencial nelas, mas elas serão gravadas e disponibilizadas logo em seguida, para quem não puder participar.
Nos horários previstos das aulas, estarei online pela ferramenta Google Meet, e alunos de ambas as turmas podem aparecer em qualquer um dos horários:
- Segundas-feiras, das 16h às 18h ou então das 19h às 21h
- Quintas-feiras, das 16h às 18h ou então das 21h às 23h
A ideia é seguir o cronograma: se no dia está previsto o conteúdo ×, então use o atendimento para tirar dúvidas sobre ×, mesmo que você tenha só aquele horário para assistir aos vídeos.
Como eu estarei online, você pode pausar o vídeo e pedir para que eu explique algo melhor.
Mas mesmo que você não consiga seguir esse "comportamento ideal", não deixe de usar os horários de atendimento 🥺!
Como estamos fazendo a disciplina à distância, eu preciso confiar no material que vocês vão me entregar.
Meu maior pedido é: seja o autor das suas atividades.
Isso basicamente significa: não copie solução encontrada na internet ou feita por outra pessoa.
É claro que você pode e deve trocar ideias com os colegas, porque isso realmente ajuda no aprendizado.
Eventualmente, ver soluções já prontas também ajuda, mas apenas se você entendê-las tão bem que possa, depois, responder sozinho o mesmo problema.
Qualquer violação às regras descritas na seção sobre plágio 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.
Veja detalhes sobre a avaliação na seção Avaliação.
Por fim, o site tem bastante informação, então leia ele com bastante cuidado.
Não sei se já falei, mas as notas de aula estão muito boas 😉, dê uma olhada.
Meu objetivo aqui é que você aprenda o conteúdo dessa disciplina da melhor forma possível.
Por isso, converse comigo sempre.
Qualquer dúvida e feedback são bem vindos, de verdade.
Acho que é isso, boas aulas!
Importante!
Todas as aulas, com e sem participação dos alunos, serão gravadas e disponibilizadas online segundo a Licença Creative Commons Atribuição-Não Comercial 4.0 Internacional (CC-BY-NC).
Todos os participantes do curso dão sua tácita e irrevogável autorização para que suas imagens e falas sejam transmitidas, gravadas e editadas segundo a licença acima pelo docente responsável, sem nenhuma cobrança, para uso em distintos canais de comunicação e peças publicitárias sem fins comerciais.
🧐 Ementa da disciplina
MCTA003-17 - Análise de Algoritmos
CCM-001 - Análise de Algoritmos e Estruturas de Dados
Objetivos:
- Apresentar noções e conceitos de complexidade de computação;
- 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;
- 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;
- Apresentar noções básicas de Classes de Complexidade, em particular as classes P, NP e NP-Completo.
🖖 Recomendação
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).
Dê uma olhada na lista 0 de exercícios e veja se está confortável com aquele conteúdo (ao menos já viu antes).
Materiais de apoio para esses tópicos:
- Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
- Fundamentos da matemática para computação, (videoaulas) do prof. Cláudio Possani, da USP.
- Meus vídeos com definição e exemplos de indução.
- 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 Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).
- Notas de aula, da disciplina de Programação Estruturada (introdução à programação em C, recursão, vetores e listas).
📚 Bibliografia e outros materiais
- [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados (o conteúdo dessa disciplina está completo no livro, mas sempre existem atualizações - verifique sempre sua versão).
- [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.
- [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/Alison-Wesley. 2006.
- Grupo do Whatsapp criado e mantido pelos alunos.
📆 Cronograma
- Sobre qualquer material feito por mim, participe do banco de informantes.
- Cada aula é acompanhada de um quiz, que te ajudará a fixar o conteúdo da mesma.
- Playlist completa dos vídeos.
Aula 1 - 21/set 🎥 LIVE!! (Em ambos os horários)
|
| Aula 2 - 24/set |
| Aula 3 - 28/set |
Aula 4 - 01/10
|
| Aula 5 - 05/10 |
Aula 6 - 08/10
|
| 💥💥💥 Entrega da Lista 1 - 11/10 💥💥💥 |
| Aula 7 - 12/10 (Feriado) Não haverá atendimento síncrono nesse dia. |
| Aula 8 - 15/10 |
Aula 9 - 19/10 🎥 LIVE!! (Em ambos os horários)
|
Aula 10 - 22/10
|
| 💥💥💥 Entrega da Lista 2 - 25/10 💥💥💥 |
Aula 11 - 26/10
|
| 💥💥💥 Entrega da Lista 3 - 29/10 💥💥💥 |
Aula 12 - 29/10
|
| Aula 13 - 02/11 (Feriado) Não haverá atendimento síncrono nesse dia.
|
Aula 14 - 05/11
|
| 💥💥💥 Entrega da Lista 4 - 08/11 💥💥💥 |
Aula 15 - 09/11
|
Aula 16 - 12/11
|
Aula 17 - 16/11
|
Aula 18 - 19/11
|
| Aula 19 - 23/11 |
| 💥💥💥 Entrega da Lista 5 - 26/11 💥💥💥 |
Aula 20 - 26/11
|
Aula 21 - 30/11 🎥 LIVE!! (Em ambos os horários)
|
Aula 22 - 03/12
|
| 💥💥💥 Entrega da Lista 6 - 06/12 💥💥💥 |
Aula 23 - PROVA - 07/12
|
Atendimento extra - 14/12
|
Aula 24 - RECUPERAÇÃO - 16/12
|
👎 Plágio
- 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:
- 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.
- Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!
🏋 Listas de exercícios
- As soluções das listas deverão ser feitas à mão (capriche na letra!), escaneadas em um único arquivo PDF e entregues pelo Google Forms nos links disponibilizados abaixo, com os respectivos prazos.
- Se algo te impossibilita de fazer a lista à mão, converse comigo antes de enviar em outro formato, pois caso contrário sua nota naquela lista será zero.
- Sugestão de aplicativo para escanear a lista: CamScanner (disponível para Android e iPhone).
- Certifique-se de que o resultado final está legível.
- Não entregue sua primeira solução! Passe a limpo antes.
- Os prazos de entrega não são arbitrários e foram pensados com muito cuidado. Eles respeitam o conteúdo do cronograma. Não me peça para mudá-los sem uma justificativa muito boa.
- Listas entregues com até um dia de atraso valerão 50% da nota.
- Finalmente:
- Lista 0 (revisão)
Não vale nota. - Lista 1 (tempo de execução, notação assintótica e corretude de algoritmos iterativos)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia 11/10 (se não conseguir fazer todos, tudo bem):- Graduação: 2, 3, 4(d), 4(h), 4(m), 5(b), 6(e), 14, 16
- Pós: 2, 3, 4(c), 4(d), 4(h), 4(m), 5(b), 6(e), 7(c), 9, 14, 16, 18
- Lista 2 (recorrências e corretude de algoritmos recursivos)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia 25/10 (se não conseguir fazer todos, tudo bem):- Graduação: 2, 3(a), 3(e), 3(g-j), 3(r), 8
- Pós: 2, 3(a), 3(d), 3(e), 3(g-j), 3(r), 8, 9
- Lista 3 (ordenação)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia25/1029/10 (se não conseguir fazer todos, tudo bem):- Graduação: 1, 6, 7, 9
- Pós: 1, 6, 7, 9, 12
26/1030/10 valerão 50%. - Lista 4 (introdução a grafos)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia 08/11 (se não conseguir fazer todos, tudo bem):- Graduação: 1, 2, 4
- Pós: 1, 2, 4, 7
- Lista 5 (algoritmos gulosos e programação dinâmica)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia24/1126/11 (se não conseguir fazer todos, tudo bem):- Graduação: 2, 3, 5, 11, 13
- Pós: 2, 3, 4, 5, 11, 13
25/1127/11 valerão 50%. - Lista 6 (complexidade)
Faça o maior número de exercícios que puder, sempre.
Entregue os seguintes exercícios AQUI até o dia 06/12 (se não conseguir fazer todos, tudo bem):- Graduação: 1, 6, 8, 11
- Pós: 1, 6, 8, 11
- Lista 0 (revisão)
🎓 Critérios de avaliação
- A avaliação da disciplina constituirá da nota de uma prova, denotada P, e da média simples das notas das listas 1 a 6, denotada L.
- A prova vale 50% da nota.
- A prova será enviada por e-mail, juntamente com o link para entrega e instruções, no dia e horário especificados na seção Cronograma.
- O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
- As listas valem 50% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.5 × P + 0.5 × L
- Se você é aluno da pós-graduação, 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
- Se você é aluno da graduação, 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
O, se menos de 2 atividades forem entregues
😬 Notas
- Acompanhe aqui a entrega das atividades.
- Acompanhe aqui as notas das atividades.
- Essas planilhas são atualizadas automaticamente.
Se detectar qualquer problema, me avise o quanto antes, por favor.
💪 Mecanismo de recuperação
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que manifestarem interesse em realizá-la.
- Pode ser cobrada a entrega de outros exercícios das listas.
- 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}
- Se você é aluno da pós-graduação, o conceito final obtido na recuperação substituirá o conceito original e será
B, se NFR ≥ 7.0
C, se NFR ≥ 5.0
F, se NFR < 5.0
- Se você é aluno da graduação, 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
- Uma prova substitutiva poderá ser aplicada ao aluno que possuir justificativa que o impeça de realizar a prova no período normal.
- A data para realização da mesma 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