2022 Q1
CCM-001 - Análise de Algoritmos e Estruturas de Dados (Pós)
COMPARTILHADA: MCTA003-17 - Análise de Algoritmos
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
🚨 Avisos importantes (fique atento sempre!)
📌 [20/06] Avisos finais:- Corrigi a prova de recuperação. Se você a fez, enviei no Moodle sua prova com 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 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 25/06.
- Corrigi a prova 2 e as listas 5 e 6. Alguns comentários foram enviados no Discord.
- 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.
A prova ficará disponível no Moodle na data e horário descritos no cronograma. - 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.
Faça isso até o final desta semana. - Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.
[02/05] As notas das listas 2, 3 e 4 estão disponíveis na seção de notas.
[22/04] A lista 6 está disponível.
[18/04] Corrigi a prova 1. Se você a fez, veja os comentários no seu PDF, que estão disponíveis no Moodle. As notas e os critérios estão na planilha na seção de notas. Veja também a mensagem no Discord. Em caso de problemas ou dúvidas, mande mensagem privada no Discord!
[07/04] Atenção! Haverá atendimento normalmente no dia 13/04 (geral e individual).
[06/04] A lista 5 está disponível.
[01/04] Hoje teremos um atendimento geral extra, das 16h às 17h30.
[27/03] A lista 4 está disponível.
[24/03] As listas 2 e 3 podem ser entregues até às 18h de hoje.
[16/03] Corrigi a lista 1 e enviei as anotações no Moodle. 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á.
[10/03] A partir de 14/03 teremos monitoria! Segundas-feiras, das 20h30 às 22h, e quintas-feiras, das 20h às 22h, pela Beatriz Favini.
[01/03] As listas 2 e 3 estão disponíveis.
[27/02] Os atendimentos gerais passarão a ter duração de 1h30 (das 16h às 17h30), seguidos ainda dos atendimentos individuais.
[25/02] O horário de atendimento geral de hoje começará às 15h15, para ter mais tempo de duração.
[18/02] Há uma nova versão da lista 1, com correções no enunciado do exercício 2 apenas.
[17/02] Atenção! Você deve marcar horário de atendimento individual com pelo menos 4 (quatro) horas de antecedência! Organize-se para não perder as oportunidades.
[05/fev] Leia a seção sobre 🔥🔥🔥 COMO SERÁ A DISCIPLINA 🔥🔥🔥 sem falta e com atenção!
[05/fev] Apenas para matriculados e alunos especiais (ou ouvintes que me enviaram e-mail): 🔥🔥🔥 servidor no Discord 🔥🔥🔥 e formulário de início de curso para alunos da graduação e para alunos da pós-graduação.
[05/fev] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova.
🙋 Como será a disciplina?
Nosso meio de comunicação principal será pelo servidor na
ferramenta Discord (baixe o aplicativo e crie uma conta).
Por favor, participe do servidor apenas se você está
matriculado na disciplina ou conversou comigo sobre ser ouvinte.
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.
Eu certamente responderei dentro de 24h, exceto talvez pelos finais de
semana.
Usaremos também o Moodle, mas apenas para entrega das atividades.
As videoaulas com os conteúdos da disciplina serão disponibilizadas
apenas aqui no site, 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.
Particularmente, o conteúdo da Parte I vai te auxiliar muito.
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.
Em vários dias, estarei online pela ferramenta Google Meet para atendimento:
- das 16 às
16h4017h30 comentarei o conteúdo da semana, resolverei algum exercício, darei dicas de exercícios e explicarei enunciados (o link fica disponível no Discord); - das 17h30 às 19h, farei atendimentos síncronos individuais: cada aluno terá até 10 minutos de atendimento, e a inscrição deve ser feita em link específico (disponível no Discord).
As datas exatas estão no cronograma.
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: veja o conteúdo no dia previsto e
tire dúvidas naquela mesma semana.
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 também 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.
- Você já tem acesso à playlist completa dos vídeos, porém tente seguir o cronograma: o conteúdo está bem distribuído.
- O conteúdo de cada aula será atualizado durante o quadrimestre.
Acesse aqui um calendário resumido das atividades.
Aula 1 - 16/fev
|
Aula 2 - 18/fev
|
| Aula 3 - 23/fev |
Aula 4 - 25/fev
|
02/mar (Feriado Carnaval)
|
Aula 5 - 04/mar
|
| 07/mar: Data de entrega da Lista 1. |
Aula 6 - 09/mar
|
Aula 7 - 11/mar
|
| Aula 8 - 16/mar |
Aula 9 - 18/mar
|
Aula 10 - 23/mar
|
| 24/mar: Data de entrega das Listas 2 e 3. |
Aula 11 - 25/mar
|
Aula 12 - 30/mar
|
Aula 13 - 01/abr
|
Aula 14 - 06/abr
|
Aula 15 - 08/abr
|
| 11/abr: Data de entrega da Lista 4. |
Aula 16 - 13/abr
|
15/abr (Feriado Sexta-Feira Santa)
|
Aula 17 - 20/abr
|
Aula 18 - 22/abr
|
Aula 19 - 27/abr
|
| Aula 20 - 29/abr |
| 02/mai: Data de entrega da Lista 5. |
Aula 21 - 04/mai
|
Aula 22 - 06/mai
|
| 12/mai: Data de entrega da Lista 6. |
Aula 23 - 12/mai (em uma quinta-feira, por ser reposição)
|
Aula 24 - 13/mai
|
RECUPERAÇÃO - 10/jun (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.
- Usaremos o Moodle para a entrega de todas as atividades da disciplina.
- 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 Moodle.
- 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.
- Faça o maior número de exercícios que puder, sempre.
- Os exercícios destacados abaixo, após cada lista, são os que serão corrigidos e valem nota.
- Finalmente:
- Lista 0 (revisão, não vale nota)
- Lista 1 - peso 4 (tempo de execução, notação assintótica e corretude de algoritmos iterativos - Aulas 2, 3, 4)
Exercícios: 2, 3 (algoritmo 3 apenas), 4 (letras c, h), 5 (letra a), 12 e 19.
Soluções de alguns exercícios.
Entrega até 12h do dia 07 de março, pelo Moodle - Lista 2 - peso 4 (recorrências e corretude de algoritmos recursivos - Aulas 5, 6, 7, 8)
Exercícios: 2, 3(letras a, e, n) e 9.
Entrega até12h18h do dia 24 de março, pelo Moodle - Lista 3 - peso 2 (ordenação - Aulas 4, 6, 9)
Exercícios: 5, 6, 9.
Entrega até12h18h do dia 24 de março, pelo Moodle - Lista 4 - peso 2 (introdução a grafos - Aulas 12, 13, 14)
Exercícios: 4 e 7.
Entrega até 12h do dia 11 de abril, pelo Moodle - Lista 5 - peso 4 (algoritmos gulosos e programação dinâmica - Aulas 15 a 19)
Exercícios: 3, 4, 11 e 13.
Entrega até 12h do dia 2 de maio, pelo Moodle - Lista 6 - peso 4 (complexidade - Aulas 20 a 22)
Exercícios: 2, 4, 6, 11.
Entrega até 20h do dia 12 de maio, pelo Moodle
- Lista 0 (revisão, não vale nota)
🎓 Critérios de avaliação
- A avaliação da disciplina constituirá da nota de duas provas, denotadas P1 e P2, e da média ponderada das notas das listas, denotada L.
- A prova 1 vale 40% da nota e 0 ≤ P1 ≤ 10.
- A prova 2 vale 40% da nota e 0 ≤ P2 ≤ 10.
- As listas valem 20% da nota e 0 ≤ L ≤ 10.
- O conteúdo das provas englobará todos os temas vistos até a data das mesmas.
- Os pesos de cada lista estão na seção sobre as listas de exercícios.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.4 × P1 + 0.4 × P2 + 0.2 × 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 nenhuma atividade for entregue
💯 Notas
Acompanhe aqui as notas das atividades.💪 Mecanismo de recuperação
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F.
- 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.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br