2021 Q1
CCM-001 - Análise de Algoritmos e Estruturas de Dados (Pós)
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
🚨 Avisos importantes (fique atento sempre!)
📌 [07/06] Avisos finais:- Corrigi a prova de recuperação. Se você a fez, enviei por email com alguns comentários.
- As notas finais estão na planilha na seção de notas.
- Se você deseja solicitar revisão de nota, me envie mensagem pelo Discord ou por e-mail indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
Peço que isso seja feito até o dia 15/06.
- Corrigi a prova 2. Se você a fez, enviei por email com alguns comentários.
- As notas finais (pré-rec) estão na planilha na seção de notas.
- A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F.
Se você deseja fazê-la, me envie um email dizendo seu nome e O NOME DA DISCIPLINA no título, por favor.
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. - Se você deseja solicitar revisão de qualquer nota, me envie mensagem PELO DISCORD indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
Prefira fazer isso amanhã (10/05), pois as notas serão lançadas no dia 11/05. - Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.
[12/abr] Corrigi a prova 1. Se você a fez, enviei por email com alguns comentários. As notas e os critérios estão na planilha na seção de notas.
[12/abr] Disponibilizei uma versão corrigida da lista 5 (houve apenas uma remoção do item (d) da questão 11).
[29/mar] Com a manutenção dos calendários acadêmicos nesse período de antecipação de feriados, o cronograma de aulas e atendimentos está mantido. Veja mais no Discord.
[29/mar] Detalhes da prova 1 substitutiva na seção cronograma.
[25/mar] Atenção! Sobre o informe da reitoria, veja a seção de avisos no Discord.
[08/fev] Disponibilizei a solução de alguns exercícios da lista 1.
[29/jan] O cronograma foi alterado para seguir o calendário de reposições. Com isso, as provas tiveram Duas datas adiadas em uma semana.
[26/jan] Leia a seção sobre 🔥🔥🔥 como será a disciplina 🔥🔥🔥 sem falta!
[26/jan] Apenas para matriculados e alunos especiais: 🔥🔥🔥 grupo no Discord 🔥🔥🔥 e formulário de início de curso para alunos da graduação e para alunos da pós-graduação.
[26/jan] 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 servidor apenas se você está matriculado na
disciplina ou é aluno especial (e falou comigo).
O site sempre será atualizado com avisos, porém comunicados menores e
atendimentos serão pelo Discord.
Aliás, o servidor no Discord pode e deve ser utilizado em qualquer horário, para atendimento assíncrono.
As videoaulas com os conteúdos da disciplina já estão
disponibilizadas na seção Cronograma.
Os conteúdos foram distribuídos da forma como eles seriam dados em um
curso 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:
- Segundas-feiras, das 19h às 21h.
- Quartas-feiras, das 21h às 22h30.
Esses horários devem ser usados para tirar dúvidas do conteúdo e também para discutir a solução de exercícios.
Sugestão de organização dos estudos: assista aos vídeos com atenção, sem fazer anotações. Depois, leia os materiais de apoio enquanto faz anotações. Existem mais exemplos nesses materiais e detalhes que podem passar despercebidos nos vídeos.
Idealmente, siga 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.
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ê vai me entregar.
Meu único 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-o 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
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).
Preparei esse material de 🔥revisão🔥 que contém tudo que precisamos na disciplina. Também tenho vídeos com definição e exemplos de indução.
Outros materiais de apoio:
- 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 - 1/fev 🎥🎥 LIVE (aula síncrona) 🎥🎥
|
Aula 2 - 3/fev |
Aula 3 - 8/fev |
Aula 4 - 10/fev
|
15/fev (Feriado carnaval 🎉)
|
17/fev (Feriado carnaval 🎉)
|
Aula 5 - 22/fev |
Aula 6 - 24/fev
|
Aula 7 - 1/mar |
Aula 8 - 3/mar |
Aula 9 - 8/mar
|
Aula 10 - 10/mar
|
Aula 11 - 15/mar
|
Aula 12 - 17/mar
|
Aula 13 - 22/mar 🎥🎥 LIVE (aula síncrona) 🎥🎥 |
Aula 14 - 💥💥PROVA 1💥💥 - 24/mar
|
Aula 15 - 29/mar
|
Aula 16 - 31/mar
|
Aula 17 - 5/abr
|
Aula 18 - 7/abr
|
Aula 19 - 12/abr
|
Aula 20 - 14/abr
|
Aula 21 - 19/abr |
21/abr (Feriado Tiradentes 🦷)
|
Aula 22 - 27/abr (na terça-feira às 19h, por ser reposição)
|
Aula 23 - 29/abr 🎥🎥 LIVE (aula síncrona) 🎥🎥 (na quinta-feira às 21h, por ser reposição) |
💥💥PROVA 1 SUB💥💥 - 30/abr
|
Aula 24 - 💥💥PROVA 2💥💥 - 4/mai
|
RECUPERAÇÃO - 26/mai (quadrimestre seguinte)
|
👎 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
- Ao todo teremos 6 listas, cujos enunciados estão disponibilizados abaixo.
- Elas não valem nota, mas podem ser entregues até os dias das
avaliações e serão consideradas como um bônus.
- As listas 1 a 4 podem ser entregues até o horário de liberação da prova 1. Elas valerão até 1 ponto extra na nota da prova 1.
- As listas 5 e 6 podem ser entregues até o horário de liberação da prova 2. Elas valerão até 1 ponto extra na nota da prova 2.
- Soluções entregues depois desses prazos não serão consideradas.
- As soluções das listas deverão ser feitas à mão em papel ou algum dispositivo como um tablet ou mesa digitalizadora (capriche na letra!), escaneadas (caso feitas em papel) em um único arquivo PDF e entregues pelo Google Forms nos links disponibilizados abaixo.
- Certifique-se de que o resultado final está legível.
- Não entregue sua primeira solução! Passe a limpo antes.
- Procure atendimento sempre que tiver dúvidas nos exercícios.
- Nem todos são fáceis, mas eu não espero que você consiga fazer tudo sozinho.
- Também é recomendável que você me envie suas soluções antes, por mensagem privada no Discord, para que eu possa verificar como está a apresentação delas.
- Faça o maior número de exercícios que puder, sempre.
- Os exercícios destacados abaixo, após cada lista, representam um mínimo de cobertura do conteúdo.
- O bônus que você receberá será diretamente proporcional à quantidade desses exercícios que forem entregues.
- Finalmente:
- Lista 0 (revisão)
- Lista 1 (tempo de
execução, notação assintótica e corretude de algoritmos iterativos - Aulas 2, 3, 4)
Exercícios em destaque: 2, 3, 4 (itens ímpares), 9, 10, 16, 18, 20.
Soluções de alguns exercícios.
Entrega: AQUI - Lista 2 (recorrências e
corretude de algoritmos recursivos - Aulas 5, 6, 7, 8)
Exercícios em destaque: 2, 3 (a-j,n,q), 7, 9.
Entrega: AQUI - Lista 3 (ordenação - Aulas 4, 6, 9)
Exercícios em destaque: 1, 6, 7, 8.
Entrega: AQUI - Lista 4 (introdução a grafos - Aulas 10, 11, 12)
Exercícios em destaque: 1, 3, 5, 8.
Entrega: AQUI - Lista 5 (algoritmos gulosos e programação dinâmica - Aulas 15 a 20)
Exercícios em destaque: 2, 3, 4, 8, 11, 13.
Entrega: AQUI - Lista 6 (complexidade - Aulas 21 e 22)
Exercícios em destaque: 1, 3, 6, 8, 11.
Entrega: AQUI
- Lista 0 (revisão)
- Acompanhe aqui a entrega das listas.
🎓 Critérios de avaliação
- A avaliação da disciplina constituirá da nota de duas provas, denotadas P1 e P2.
- A prova 1 vale 55% da nota.
- A prova 2 vale 45% da nota.
- As provas serão enviadas 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 das provas englobará todos os temas vistos até a data das mesmas.
- Ainda sobre avaliação, leia a seção sobre as listas de exercícios.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.55 × P1 + 0.45 × P2 - 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 nenhuma prova for entregue
💯 Notas
- Acompanhe aqui a entrega das atividades.
- Acompanhe aqui as notas das atividades.
- Essas planilhas são atualizadas automaticamente, então 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 alguma 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.