Projeto e Análise de Algoritmos I (Turma A)

Novidades

• Aqui serão colocados avisos importantes. Consulte esta página regularmente.
• As notas do Exame e as Médias Finais estão disponíveis. As notas e médias finais são definitivas. Os Exames já foram cuidadosamente corrigidos e revisados. Alunos que queiram ver seus Exames corrigidos devem enviar email ao professor para marcar um horário no início do próximo semestre. [20180710]
• Os alunos para quem o Exame é obrigatório podem consultar a tabela de notas para verificarem a nota mínima que precisam obter no Exame para lograr aprovação na disciplina. [20180706]
• Haverá atendimento no dia 9/7, segunda-feira (isso mesmo, 9/7, mesmo sendo feriado!), dado pelo PED da disciplina na sala IC353 às 10:00hs. Os alunos que tomarão o Exame são incentivados a comparecer! [20180705]
• O Exame será ministrado no dia 10/7, às 10:00hs, na sala IC353. [20180629]
• As notas da Prova 3 e as Médias Semestrais estão disponíveis. Os alunos que desejarem ver suas Provas 3 corrigidas devem comparecer exclusivamente no horário de 10:30 às 11:30 na terça-feira, dia 03/7, à sala IC29 (sala do Prof. Rezende). [20180629]
• As notas do Teste 5 estão disponíveis. Os alunos que desejarem ver seus Testes corrigidos devem comparecer exclusivamente no horário de atentimento do PED (André) na quinta-feira, dia 14/6, às 13:00 na sala IC353. [20180613]
• A Unicamp acaba de determinar a suspensão de todas as atividades acadêmicas até quarta-feira, 30/05. Por essa razão, na terça-feira, 29/5, não teremos aula nem atendimento pelo PED. [20180528] 
• As notas do Teste 4 estão disponíveis. Os alunos que desejarem ver seus Testes corrigidos devem comparecer exclusivamente no horário de atentimento do PED (André) na terça-feira, dia 5/6, às 13:00 na sala IC351. [20180528] 
• Nova alteração de sala de aula para MC458-A: as aulas, os Testes e as Provas passam a ser na sala IC353 a partir de 24/5, [20180524] 
• As notas da Prova 2 estão disponíveis. Os alunos que desejarem ver suas Provas 2 corrigidas devem comparecer exclusivamente na aula de 24/5. [20180523]
• As notas do Teste 3 estão disponíveis. Os alunos que desejarem ver seus Testes corrigidos devem comparecer exclusivamente no horário de atentimento do PED (André) na terça-feira, dia 8/5, às 13:00 na sala PB06. [20180507]
• As notas da Prova 1 estão disponíveis. [20180422]
• As notas do Teste 2 estão disponíveis. Os alunos que desejarem ver seus Testes corrigidos devem comparecer exclusivamente no horário de atentimento do PED (André) na terça-feira, dia 24/4, às 13:00 na sala PB06. [20180422]
• As notas do Teste 1 estão disponíveis. Os alunos que desejarem ver seus Testes corrigidos devem comparecer exclusivamente no horário de atentimento do PED (André) na terça-feira, dia 10/4, às 13:00 na sala PB06. [20180406]
  
• Disponibilizada lista adicional de exercícios sobre indução forte. [20180314] 
• Procure conseguir um exemplar dos livros recomentados (Cormen [1] e Manber [2]) desde a primeira semana de aulas. [20180204] 

Docente 

• Prof. Pedro J. de Rezende [MC458 - Turmas A e B]
• Sala IC-29, http://www.ic.unicamp.br/~rezende, (19) 3521-5860,

Aulas Teóricas

• As aulas serão de 10h05 às 11h55 às terças e às quintas-feiras. A partir de 24/5 as aulas serão na sala IC353. Sejam pontuais para o início das aulas!
  
• Primeiro dia de aula: terça-feira, 27/02.

Monitor

• Teremos um Monitor-PED (André H. C. de Moraes, e-mail: andre.moraes <at> students.ic.unicamp.br) para esta disciplina que fará atividades de exercícios e sessões de atendimento.
• As Aulas de Exercícios do André serão às quintas-feiras a partir de 15/03, de 13:00 às 13:50 na sala PB06.
  
• Os Horários de Atendimento do André serão às terças-feiras a partir de 13/03, de 13:00 às 13:50 na sala PB06.
  A partir de 24/5 as Aulas de Exercícios e Atendimento do André serão nas salas: 24/5=>IC353, 29/5=>IC351, 05/6=>IC351, 07/6=>IC353, 12/6=>IC353,14/6=>IC353, de 13:00 às 13:50.
• As Aulas de Exercícios e os Horários de Atendimento do Monitor-PED (Allan Sapucaia) da turma B de MC458 serão abertos também aos alunos da turma A, e serão:
• As Aulas de Exercícios do Allan serão às quintas-feiras a partir de 15/03, de 18:00 às 18:50 na sala IC-351.
• Os Horários de Atendimento do Allan serão às segundas-feiras a partir de 12/03, de 18:00 às 18:50 na sala IC-351.

Avaliação e Critérios para Aprovação

Haverá três Provas (P1, P2, P3) nas datas indicadas ao final deste documento. Cada Prova será em classe nos horários normais de aula, sem exceção, terá duração de 120 minutos e receberá nota entre 0,0 e 10,0.

Haverá cinco Testes (T1, T2, T3, T4, T5) aos quais serão atribuídas notas também entre 0,0 e 10,0.

Não serão ministrados provas ou testes antecipados nem substitutivos.

A Média dos Testes (MT) será a média ponderada MT := (T1 + T2 + T3 + 2xT4 + 2xT5) / 7.

A Média das Provas (MP) será a média ponderada MP := (2xP1 + 3xP2 + 5xP3) / 10.

Cálculo da Média Semestral (MS):

Se min { MT; MP } >= 5,0
então MS := (MT + 4 MP) / 5
senão MS := min { 4,9; (MT + 4 MP) / 5 }

Cálculo da Média Final (MF) e obrigatoriedade do Exame Final:

Se (MS >= 5,0) ou (MS < 2,5)
então MF := MS
senão se (2,5 <= MS < 5,0)
         então MF := (MS + E) / 2

onde E é a nota obtida pelo aluno no Exame Final. Um aluno com 2,5 <= MS < 5,0 é obrigado a tomar o Exame Final, se não o fizer, lhe será atribuído zero a E; alunos com MS < 2,5 não poderão fazer o Exame Final; e alunos com MS >= 6,0 não poderão fazer o Exame Final.

Será considerado aprovado o aluno que obtiver Média Final (MF) maior que ou igual a 5,0.
Será considerado reprovado o aluno que obtiver Média Final (MF) menor que 5,0.

Sobre os testes:

Os testes serão realizados em sala de aula e consistirão de um ou mais exercícios para serem feitos em dupla (excepcionalmente poderá haver uma tripla na classe) e entregues até o final da primeira parte da aula. A segunda parte da aula será dedicada a discussão sobre a resolução do(s) exercício(s) proposto(s) no Teste.

Aviso: Qualquer tentativa de cola ou fraude, detectada durante ou posteriormente a uma Prova ou Teste, acarretará nota zero naquela avaliação para todos os implicados, além das sansões regimentais previstas

Notas

Tabelas de notas estarão disponíveis aqui: Testes e Provas.

Exercícios

Listas de exercícios serão atribuídas ao longo do semestre. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e será assumido como parte da matéria coberta.

Como as listas não farão parte da avaliação, suas soluções não serão coletadas. Os alunos são encorajados a resolver todos os exercícios individualmente e, só posteriormente, realizar discussão em grupo. Quaisquer dificuldades devem ser prontamente discutidas com o PED nos horários de atendimento ou com o  Professor. Dúvidas não sanadas geram mais dúvidas.

Listas de exercícios
(As listas serão indicadas nesta página à medida que cada tópico for sendo coberto. A relação abaixo é apenas tentativa e poderá sofrer alterações e acréscimos ao longo do semestre. Visite esta página regularmente.)

1. Lista 1a: [1] Capítulo 1: Exercícios: 1.2-2;

2. Lista 1b: [1] Capítulo 1: Problemas: 1-1;

3. Lista 2a: [1] Capítulo 2: Exercícios: 2.1-3, 2.1-4, 2.2-2, 2.2-3, 2.3-3, 2.3-5, 2.3-6, 2.3-7;

4. Lista 2b: [1] Capítulo 2: Problemas: 2-1;

5. Lista 3a: [1] Capítulo 3: Exercícios: 3.1-1, 3.1-2, 3.1-3, 3.1-4, 3.1-6, 3.1-7, 3.1-8, 3.2-3;

6. Lista 3b: [1] Capítulo 3: Problemas: 3-1, 3-2, 3-3, 3-4;

7. Lista 4a: [1] Capítulo 4: Exercícios: 4.1-2, 4.1-5, 4.2-2, 4.2-4, 4.2-5, 4.3-1, 4.3-2, 4.3-4, 4.3-5, 4.4-2;

8. Lista 4b: [1] Capítulo 4: Problemas: 4-1, 4-3 b., 4-4 a., c., d., e., f., h., i.;

9. Lista 5: [2] Capítulo 2: Exercícios: 2.1, 2.4, 2.7, 2.9, 2.12, 2.14, 2.15 (substituindo, no enunciado, o número 81 por 49), 2.18 (substituindo, no enunciado, a palavra cycle por circle), 2.19, 2.21; Lista adicional sobre indução forte.
   

10. Lista 6: [2] Capítulo 5: Exercícios: 5.6, 5.12, 5.14, 5.15, 5.25a.;

11. Lista 7: [2] Capítulo 6: Exercícios: 6.14, 6.22, 6.23, 6.24, 6.25, 6.29;

12. Lista 8: [1] Capítulo 9: Exercícios: 9.2-4, Problemas: 9-1a.,b,c;

13. Lista 9: [2] Capítulo 6: Exercícios: 6.11, 6.21, 6.34;

14. Lista 10: [1] Capítulo 6: Exercícios: 6.1-4, 6.1-5, 6.2-1, 6.2-2, 6.2-3, 6.2-4, 6.2-6, 6.4-3, 6.4-4, 6.4-5, 6.5-8;

15. Lista 11: [1] Capítulo 7: Exercícios: 7.2-2, 7.2-3;

16. Lista 12: [1] Capítulo 8: Exercícios: 8.1-1, 8.1-2, 8.2-1, 8.2-4, 8.3-3, 8.4-1, 8.4-2, Problemas: 8-3a, 8-6;

17. Lista 13: [1] Capítulo 9: Exercícios: 9.1-1;

18. Lista 14: [1] Capítulo 15: Exercícios: 15.2-1, 15.2-2, 15.2-3, 15.3-2, 15.3-3, 15.3-5, 15.4-1, 15.4-2, 15.4-3, 15.4-4, 15.4-5, 15.4-6, Problemas: 15-4, 15-6, 15-7;

19. Lista 15: [1] Capítulo 16: Exercícios: 16.1-1, 16.1-2, 16.1-3, 16.1-4, 16.3-1, 16.3-4, 16.3-7, 16.3-8, Problemas: 16-1, 16-4a.

Tópicos a serem cobertos

O programa da disciplina consiste dos seguintes tópicos:
(Legenda: M=Modelo, A=Análise, P=Projeto/Paradigma)

1. Conceitos de Análise de Algoritmos ([1] Cap 1., 2., 3.).

·          (M) Modelos Computacionais. Aula 1

·          (A) Classes de funções, crescimento e o conceito de assintossidade. Aula 1

·          (A) O que é análise de um algoritmo -- quota superior.

·          (A) O que é análise de complexidade de um problema -- quota inferior.

·                  - Exemplos: busca em vetor ordenado, entrada/saída, quotas superiores, quota inferior e algoritmo ótimo.

·          (A) O que é análise de pior caso.

 

2. Ferramental Matemático para Análise de Algoritmos ([1] Cap 4. e [Notas de Aulas])

·          (A) Crescimento assintótico e classes de funções. [Classes de funções] Aula 2

·          (A) Resolução de recorrências. [Recorrências] Aula 2

·          (A) Métodos diversos. Aula 2 e Aula 3

·          (A) Teorema Master. Aula 3

 

3.  (P) Projeto de algoritmos por indução ([2] Cap 5., [Paper do Manber] e [Indução])

·         (P) [Manber] 2.7, 2.8, 2.10 - Revisão. Aula 4, Aula 5

·         (P) [Manber] 5.2, 5.3, 5.4, 5.5, 5.7, 5.8, 5.9, 6.5.1, 6.11.1, 6.11.2. Aula 6, Aula 7
Leitura: [2] 2.7, 2.8, 2.10, 5.2, 5.3, 5.4, 5.5, 5.7, 5.8, 5.9, 6.5.1, 6.11.1, 6.11.2
([2] 5.4, 6.11.1 não serão cobertos em classe, mas a leitura é um requisito. Em caso de dúvidas, procure o professor.)

4. Busca, ordenação e estatísticas de ordem (Ênfase em [M] Divisão e Conquista) ([2] Cap 6., e [1] Cap 6., 7., 8., 9.)

·          (P) Paradigma de Divisão e Conquista (mergesort, busca binária, mediana). Aula 8, Aula 12

·          (P) Busca binária (simples, variações, seqüências gaguejantes, n=a^b para n, a, b naturais). Aula 9 (lousa)

Teste 1 Aula 10
Prova 1 Aula 11

·          (P) Conquista pode preceder a divisão (quicksort).

·          (A) Análise de caso médio de quicksort.

·          (A) Quota inferior para busca em vetor ordenado, ordenação e determinação do máximo.

·          (M/A/P) Algoritmos lineares para ordenação.

·         (P) Seleção do mediano e do k-ésimo menor elemento via partição do quicksort.

·          (A) Algoritmo de pior caso linear para seleção do mediano e do k-ésimo menor elemento.

·          (P) Benefícios da escolha de estrutura de dados adequada para projeto de algoritmos eficientes (ordenação com várias estruturas de apoio).

      Leitura: [2] Cap 6 = 6.2, 6.4, 6.5, 6.11, [1] Cap 6; 7; 8; 9.1, 9.2, 9.3

5. [M] Programação Dinâmica ([1] Cap 15.)
Exemplos dentre:

·         (P) Programação de linha de montagem.

·         (P) Multiplicação de cadeias de matrizes.

·         (P) Mais longa subseqüência comum.

·         (P) Problema da mochila.

·         (P) Árvore binária de busca ótima.
Leitura: [1] Cap 15 = 15.2, 15.3, 15.4

6. [M] Algoritmos Gulosos ([1] Cap 16.)

·        (P) Problema de seleção de atividade.

·        (P) Códigos de Huffman.

·        (P) Outros exemplos.
Leitura: [1] Cap 16 = 16.1, 16.2, 16.3

Tópicos opcionais à escolha do docente:

·        (P) Problemas geométricos (para ilustrar os paradigmas de Divisão e Conquista e Guloso).

·        (P) Emparelhamento de cadeias de caracteres e biologia computacional (para ilustrar o paradigma de Programação Dinâmica).

·        (P) Reduções de Problemas. [Redução]

Slides das aulas

1. Introdução até Projeto de Algoritmos por Indução
2. Exemplos do Paradigma de Divisão e Conquista
3. Ordenação e Estatísticas de Ordem
4. Paradigma de Programação Dinâmica
5. Paradigma Guloso