2023 Q2
MCTA003-17 - Análise de Algoritmos - Diurno
Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br
🚨 Avisos importantes (fique atento sempre!)
[5/out] 🔥🔥🔥🔥🔥 As notas finais, pós-rec, estão disponíveis na planilha. Cheque seu e-mail para mais informações![20/set] ATENÇÃO!! A prova de recuperação acontecerá na sala S-212-0.
[25/ago] Avisos (semi-)finais:
- As notas das listas e da prova 2 estão disponíveis na seção de notas, bem como as médias e conceitos pré-recuperação.
- A vista de prova nesse quadrimestre poderá ser feita no dia 30 de agosto, entre 10h e 12h, na sala de aula (S-212-0), ou no dia 20 de setembro, entre 10h e 12h, na minha sala.
- Os que quiserem realizar a prova de recuperação (conceito final D ou F) devem enviar e-mail até o dia 20 de setembro, para que eu possa imprimir a quantidade certa de provas.
- Haverá plantão da monitoria no dia 18 de setembro, das 17h às 19h. No dia 20 de setembro, entre 10h e 12h, estarei disponível para atendimento na minha sala também.
- Enviarei e-mail na próxima semana comentando alguns detalhes sobre a solução da prova 2.
[20/ago] ATENÇÃO!! Havia um erro no horário do cronograma. A Prova 2 será às 8h da manhã e não às 10h!
[17/ago] A sétima entrega de exercícios, prevista para o dia 18/ago (amanhã), pode também ser entregue no dia 22/ago.
[15/ago] Haverá um atendimento no dia 22, após a aula (é aula de reposição, por isso na terça-feira!), das 10h às 12h.
[4/ago] Há um exemplo extra de programação dinâmica disponível no cronograma!!
[1/ago] Como não haverá aula nem atendimento no dia 9/ago, haverá um atendimento extra no dia 11/ago, no período da tarde: das 14h às 15h30, na sala da professora. O atendimento da manhã, no dia 11/ago, está mantido.
[31/jul] As notas da prova 1 estão disponíveis na seção de notas. A vista das provas poderá ser feita às sextas-feiras, das 10h às 12h, ou às quartas-feiras, das 8h às 10h, na sala da professora.
[21/jul] ATENÇÃO!!!! Conforme informe feito pela Reitoria, não haverá aula no dia 2/ago.
Por causa disso, precisei alterar todo o cronograma, "empurrando" todas aulas e também todas as entregas de listas.
Particularmente, a nova data da prova 2 é 24/ago (** por enquanto! **)
[21/jul] O atendimento da próxima quarta, dia 26/jul, será, excepcionalmente, das 13h às 14h apenas.
[19/jul] Aos alunos que requisitaram sub da P1 (por e-mail): verifiquem seus e-mails.
[19/jul] As notas da terceira entrega de exercícios está disponível na seção de notas.
[7/jul] As notas da segunda entrega de exercícios bem como uma contagem de faltas até o momento estão disponíveis na seção de notas.
[5/jul] Atenção! A terceira entrega de exercícios, prevista para o dia 7/jul, pode também ser feita no dia da prova, 12/jul.
[23/jun] As notas das listas de exercícios estão disponíveis na seção de notas. As listas serão/foram entregues na aula de hoje. Não se esqueça de pedir ajuda sobre o que errou!
[21/jun] A segunda entrega de exercícios, prevista para o dia 23/jun, pode também ser entregue no dia 28/jun, entre as 10h e as 10h30, na sala de aula, para o professor Maycon Sambinelli.
[21/jun] No dia 1/jul, dia da reposição, haverá atendimento entre 9h e 10h e entre 12h e 13h, na própria sala da aula (S-212-0).
[21/jun] Nos dias 28/jun e 30/jun não haverá atendimento da professora.
[21/jun] As listas corrigidas serão devolvidas aos alunos, para que possam aprender com os problemas. Até o final do quadrimestre, devem ser devolvidas à professora, pois são itens de avaliação.
[21/jun] Atenção! Modifiquei algumas coisas na parte de entregas das listas de exercícios. Confira!
[13/jun] Atenção! As entregas das listas que valem nota devem ser feitas durante os horários das aulas!
[7/jun] Horário de atendimentos dos monitores foram definidos.
[7/jun] Atenção para mudança da sala de aula! As aulas serão sempre na sala S-214-0 a partir de hoje.
[5/jun] Os horários de atendimento foram definidos.
[2/jun] Atenção! Devido à aula cancelada do dia 2/jun, precisei modificar algumas coisas no nosso cronograma.
Ponto 1: a data da Prova 1 foi adiada (estava prevista para o dia 7/jul e agora será no dia 12/jul).
Ponto 2: as datas de entrega das listas também foram modificadas (adiadas).
[1/jun] A aula de amanhã, 2/jun, foi cancelada (informe da reitoria via e-mail institucional).
Isso vai atrapalhar nosso cronograma, que será modificado em breve. Conversamos sobre isso na próxima aula, de quarta-feira.
[24/mai] Verifique a seção Recomendação!!!
[24/mai] Responda a esse formulário antes das aulas começarem para podermos definir os melhores horários de atendimento extra-classe.
[24/mai] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em avaliação.
📝 Dias, horários e locais das aulas
Quartas-feiras, das 10h às 12h, na sala S-214-0.
Sextas-feiras, das 8h às 10h, na sala S-214-0.
🙋 Dias, horários e locais dos atendimentos
Segundas-feiras, das 17h às 19h, na sala de atendimentos do 5º andar, torre 2.
Quartas-feiras, das 13h30 às 15h45, na sala 508-2.
Sextas-feiras, das 10h às 11h, na sala 508-2.
Nestes dias/horários, basta aparecer na sala!
🧐 Ementa da disciplina
MCTA003-17 - Análise de Algoritmos
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.
⚠ Revise, no mínimo, indução e recursão antes das aulas começarem!!!⚠
Veja a lista 0 de exercícios!
Outros materiais de apoio:
- Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
- Videoaulas de Fundamentos da matemática para computação, 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.
- Videoaulas de Algoritmos e Estruturas de Dados I, do prof. Mário San Felice, da UFSCar.
- 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).
📚 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 pequenas 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.
📆 Cronograma
- Sobre qualquer material feito por mim, participe do banco de informantes.
As aulas que já foram ministradas estão coloridas.
Aula 1 - 31/mai
|
Aula 2 - 2/jun
|
| Aula 3 - 7/jun |
9/jun (Feriado Corpus Christi)
|
| Aula 4 - 14/jun |
Aula 5 - 16/jun
|
| Aula 6 - 21/jun |
Aula 7 - 23/jun
|
| Aula 8 - 28/jun - Sem aula presencial e sem atendimento! |
| Aula 9 - 30/jun - Sem aula presencial e sem atendimento! |
Reposição - 1/jul (sábado) - 10h às 12h
|
Aula 10 - 5/jul
|
Aula 11 - 7/jul
|
Aula 12 - 12/jul
|
Aula 13 - 14/jul
|
Aula 14 - 19/jul
|
Aula 15 - 21/jul
|
| Aula 16 - 26/jul |
Aula 17 - 28/jul
|
2/ago - SEM AULA
|
Aula 18 - 4/ago
|
9/ago - SEM AULA
|
Aula 19 - 11/ago
|
Aula 20 - 16/ago
|
Aula 21 - 18/ago
|
Aula 22 - 22/ago (⚠ Em uma terça-feira, às 8h, por ser reposição de uma aula de sexta-feira!)
|
Aula 23 - 24/ago (⚠ Em uma quinta-feira, às 8h, por ser reposição de uma aula de sexta-feira!)
|
Aula 24 - RECUPERAÇÃO - 23/set (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
- Sobre gabaritos de listas de exercícios:
eu acredito que o objetivo de um exercício teórico não é a resolução do problema em si, mas sim praticar a resolução de problemas;
você precisa chegar nas soluções por conta própria (com algumas dicas da minha parte) ao invés de apenas ler um gabarito (que mostrará uma única solução possível);
por isso, eu não disponibilizo gabaritos das minhas listas;
a melhor forma para você saber se resolveu o exercício corretamente é me procurando em horários de atendimento e me mostrando a sua solução. - Sobre descrição de algoritmos nos exercícios: veja essa página.
- Ao todo teremos 6 listas, cujos enunciados estão disponibilizados abaixo.
- O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
- As soluções das listas deverão ser feitas à mão em papel
(capriche na letra!).
- Se algo te impossibilita de fazer as listas à mão, converse comigo antes de fazer em outro formato, pois caso contrário sua nota naquela lista será zero.
- 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 as listas, são os que valerão nota.
- Vale moral!!
Qualquer exercício extra que for feito pode ser entregue nos dias das provas para serem considerados como evidência do seu esforço.
Participar das aulas, dos atendimentos/monitorias, também vale moral.
Alunos com moral terão direito a pedir arredondamento de conceitos e notas ou abono de alguma falta ao final do curso.
Em nenhuma hipótese será feito o arredondamento de conceitos ou abono de faltas para alunos sem moral.
- Finalmente:
- Lista 0 (revisão, não vale nota e não precisa entregar)
- Lista 1
(tempo de execução, notação assintótica e corretude de algoritmos iterativos - Aulas 2, 3, 4)
Vocês podem ver as soluções de alguns exercícios neste documento ou então nestes vídeos:
- Lista 2
(recorrências e corretude de algoritmos recursivos - Aulas 5, 6, 7, 8)
Vocês podem ver as soluções de alguns exercícios nestes vídeos:
- Lista 3 (ordenação - Aulas 4, 6, 9)
- Lista 4 (introdução a grafos - Aulas 12, 13, 14)
- Lista 5 (algoritmos gulosos e programação dinâmica - Aulas 15 a 19)
- Lista 6 (complexidade - Aulas 20 a 22)
- As listas devem ser entregues durante os horários das aulas e os extras devem ser entregues no dia das provas!
- As listas corrigidas serão devolvidas aos alunos, para que possam aprender com os problemas. Até o final do quadrimestre, devem ser devolvidas à professora, pois são itens de avaliação.
- Datas das entregas:
- Até o dia 16/jun: exercícios 2(a), 4(b) e 4(c) da Lista 1.
- Até o dia 28/jun: exercícios 3, 11 e 18 da Lista 1.
As listas entregues no dia 28/jun deverão ser entregues entre as 10h e as 10h30, na sala de aula, para o professor Maycon Sambinelli. - Até o dia 7/jul (ou, para quem quiser, até 12/jul): exercícios 2(a), 2(l), 2(m), e 8 da Lista 2.
No exercício 8, não precisa provar invariante de laço, caso sua solução use laços. - Até o dia 12/jul: exercício 8 da Lista 3.
No exercício 8, não precisa fazer demonstração formal. - Até o dia 28/jul: exercícios 3 e 8 da Lista 4.
- Até o dia 11/ago: 5 e 7 da Lista 5.
- Até o dia 18/08 ou 22/08: 12 e 13 da Lista 5.
- Até o dia 24/08: 2, 4 e 6 da Lista 6.
🎓 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 43% da nota e 0 ≤ P1 ≤ 10.
- A prova 2 vale 42% da nota e 0 ≤ P2 ≤ 10.
- As listas valem 15% da nota e 0 ≤ L ≤ 10, com L = 10 × (soma das notas obtidas nos exercícios entregues) / (número de exercícios exigidos).
- O conteúdo das provas englobará todos os temas vistos até a data das mesmas.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.43 × P1 + 0.42 × P2 + 0.15 × L - Se você teve presença em 75% ou mais das aulas, 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
- Se você faltou em 25% ou mais das aulas, seu conceito final será O.
- Não esqueça do vale moral!
💯 Notas
Confira aqui as notas das listas de exercícios!
Confira aqui as notas de todas as atividades, inclusive contagem de faltas!
Lembre-se sempre que a intenção das listas de exercício é reforçar seu aprendizado.
Não deixe de procurar atendimento para entender o motivo de ter errado algum exercício!
💪 Mecanismo de recuperação
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e que enviarem e-mail confirmando interesse.
- 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
- Uma 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