---

MCTA003-17 - Análise de Algoritmos (2018 Q2)

Professora: Carla Negri Lintzmayer, Sala 508-2

Avisos importantes

[21/09] Planilha de notas atualizada com as notas da prova de recuperação.

― novos ↑ ―

[7/09] A prova de recuperação será no dia 21 de setembro às 10h na sala S306-1, bloco A. Estou disponível para tirar dúvidas por e-mail e, se necessário, podemos marcar um horário de atendimento presencial.
[28/08] Formulário obrigatório para os que vão fazer recuperação e formulário opcional e anônimo sobre a disciplina como um todo.
[22/08] Planilha de notas atualizada com as notas da prova 2. Portanto, a aula de amanhã (23/08) está mantida conforme o cronograma (para vista e discussão da prova). Presença não será cobrada nessa aula.
[19/08] Planilha de notas atualizada com as notas das listas 3 e 4 e com informações sobre as faltas. Detalhes das correções da lista 3 estão no Tidia.
[14/08] Mudança nas datas da prova 2 e da recuperação.
[20/07] Planilha de notas atualizada com as notas da lista 2. Detalhes das correções estão no Tidia.
[20/07] Planilha de notas atualizada com as notas da prova 1. Estarei disponível para tirar dúvidas sobre as notas em qualquer um dos meus horários de atendimento (não haverá vista de prova em sala de aula).
[19/07] Disponibilizado material sobre os algoritmos de Prim e Dijkstra e a prova de corretude do algoritmo de Kruskal.
[19/07] Entrega da lista 3 adiada para o dia 01/08.
[19/07] Não haverá horário de atendimento no dia 25/07. Esse horário foi transferido para o dia 30/07, às 18h.
[19/07] Não haverá horário de atendimento no dia 23/07. Esse horário foi transferido para o dia 27/07, às 13h.
[04/07] Horário extra de atendimento na sexta dia 06/07 e na segunda dia 09/07, na sala da professora.
[04/07] Disponibilizada planilha de notas parciais. Detalhes das correções estão no Tidia.
[22/06] Dica de aplicativo para escanear as listas de exercícios: CamScanner.
[18/06] Entrega da lista 1 adiada para o dia 26/06.
[18/06] O horário de atendimento do dia 25/06 está sendo transferido para o dia 26/06 (mesmo local e horário).
[27/05] Criada página do tidia.
[27/05] Página da disciplina no ar.

Conteúdo dessa página

• Dias, horários e local das aulas
• Dias, horários e local de atendimento
• Ementa da disciplina
• Recomendação
• Cronograma
• Listas de exercícios
• Critérios de avaliação
• Mecanismo de recuperação
• ATENÇÃO!
• Mecanismos de avaliação substitutivos
• Bibliografia e outros materiais

Dias, horários e local das aulas (voltar ao topo)

Terças-feiras, das 10h às 12h, na sala A-113-0.
Quintas-feiras, das 8h às 10h, na sala A-113-0.

Dias, horários e local de atendimento (voltar ao topo)

Segundas-feiras, das 13h às 14h, na sala 508-2 do bloco A.
Quartas-feiras, das 13h às 14h, na sala 508-2 do bloco A.

Ementa da disciplina (voltar ao topo)

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.

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).

Um bom material que contém os tópicos de matemática discreta mencionados acima (e muitos outros) é esta apostila, dos profs. Anamaria Gomide e Jorge Stolfi, da Unicamp.

Além disso, esse material do prof. Cid Carvalho de Souza, da Unicamp, contém vários exemplos de provas por indução.

Alguns outros tópicos podem ser encontrados em vídeos no Portal da Matemática da OBMEP.

O prof. Paulo Feofiloff, da USP, tem um texto bem curto que descreve o que é uma prova matemática .

Cronograma (voltar ao topo)

Aula	Data	Conteúdo
1	5/6	Apresentação, motivação e introdução ao curso / Insertion Sort
2	7/6	Análise do Insertion Sort / Tempo de execução / Notação assintótica
3	12/6	Introdução a divisão e conquista / Mergesort / Recorrências (Lista 1)
4	14/6	Solução de recorrências: substituição e iteração
5	19/6	Solução de recorrências: árvore de recursão e Teorema Mestre
6	21/6	Quicksort
7	26/6	Selection Sort / Heapsort (Lista 2)
8	28/6	Estruturas de dados
9	3/7	Buscas em grafos
10	5/7	Revisão / Resolução de Exercícios
11	10/7	Primeira prova
12	12/7	Introdução a algoritmos gulosos
13	17/7	Árvore geradora mínima / Algoritmo de Kruskal (Lista 3)
14	19/7	Compressão de dados e algoritmo de Huffman
15	24/7	Não haverá aula presencial / Material sobre os algoritmos de Prim e Dijkstra
16	26/7	Introdução a programação dinâmica
17	31/7	Algoritmos para alinhamento de sequências (Lista 4)
18	2/8	Caminhos mínimos / Algoritmo de Floyd-Warshall
19	7/8	Classes P e NP / Problemas e reduções
20	9/8	Classes NP-Completo e NP-Difícil / Abordagens para tratamento de problemas nessas classes
21	14/8	Revisão / Resolução de exercícios
22	16/8	Plantão de dúvidas
23	21/8	Segunda prova
24	23/8	Vista de prova
	18/9	Prova de recuperação (horário e local a definir)

Listas de exercícios (voltar ao topo)

• Ao todo teremos 4 listas, cujos enunciados serão disponibilizados aqui e no tidia, nas datas indicadas acima.
• As listas poderão ser feitas em dupla, mas ambos os alunos precisam escrever e entregar sua solução, indicando claramente no início da lista os nomes e RAs dos alunos da dupla (evite plágios). Apenas uma dessas duas soluções será corrigida.
• A correção de cada lista será feita da seguinte forma: um subconjunto de tamanho ao menos 1 de exercícios da lista será escolhido para correção; a nota da lista será a nota desse subconjunto de exercícios; o mesmo subconjunto de exercícios será considerado para todos os alunos; caso nenhum exercício do subconjunto tenha sido resolvido, será atribuída nota zero à lista.
• As soluções das listas de exercícios deverão ser entregues apenas pelo tidia (não serão aceitas soluções entregues por e-mail em hipótese alguma), dentro do prazo divulgado junto com os enunciados.
• Soluções entregues fora do prazo valerão 0.

Lista 1 (entrega até 23h55 de 25/06/201826/06/2018)

Lista 2 (entrega até 23h55 de 09/07/2018)

Lista 3 (entrega até 23h55 de 30/07/201801/08/2018) -- Solução

Lista 4 (entrega até 23h55 de 13/08/201815/08/2018) -- Solução

Critérios de avaliação (voltar ao topo)

• A avaliação da disciplina constituirá da nota de duas provas e da média simples das notas das listas de exercícios, respectivamente denotadas por P1, P2 e L.
• Prova 1 vale 35% da nota.
• Prova 2 vale 45% da nota.
• 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 0.0 ≤ 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
  

ATENÇÃO! (voltar ao topo)

• Não haverá listas de exercícios substitutivas.
• As provas serão realizados sem consulta a qualquer material.
• 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, plageiem ou não creditem devidamente autoria, aceitem autoria de material acadêmico sem participação na produção, e vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
• Qualquer tentativa de fraude nas provas ou nas listas de exercícios implicará em nota final MF = 0 (zero) para todos os envolvidos, sem prejuízo de outras sanções.

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.

Bibliografia e outros materiais (voltar ao topo)

• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
• Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
• Dasgupta, S.; Papadimitriou, C.; Vazirani, U.. Algorithms. Boston: McGraw-Hill. 2008.
• Kleinberg, J.; Tardos, E.. Algorithm design. Pearson/Addison-Wesley. 2006.
• Notas de aula do prof. Guilherme Mota, da UFABC.
• Site Geeks for Geeks, muito bom, com implementações em várias linguagens.

---