Projeto e Análise de Algoritmos I (Turmas A e B)

  Novidades

• Aqui serão colocados avisos importantes. Consulte esta página regularmente.
• Estão disponíveis as notas do Exame (E) e as Médias Finais (MF). Atenção: os alunos que desejarem rever seus Exames devem comparecer à sala do Professor (IC-29), exclusivamente, na segunda-feira, dia 07/01/2013 entre 10h00 e 10h30, ou na segunda-feira, dia 25/02/2013 entre 12h00 e 12h30. [20121217]
• Haverá um horário de atendimento no dia 10 de dezembro de 9h00 às 10h00 na sala do Professor (IC-29) para os alunos que tomarão o Exame da disciplina. [20121126]
• Estão disponíveis as notas da P2 e as Médias Semestrais. Atenção: os alunos que desejarem rever sua Prova 2 devem comparecer exclusivamente no dia 26/11 à sala do Professor (IC-29) entre 9h00 e 10h00. [20121120]
• Estão disponíveis as notas do Lab6. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente na segunda-feira, dia 12/11, à sala IC-322 entre 12h00 e 13h00. [20121111]
• O enunciado do Lab6 já está disponível. (A chave só é informada em classe!) [20121111]
• Estão disponíveis as notas do Lab5. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente na quarta-feira, dia 31/10, à sala IC-322 entre 12h00 e 13h00. [20121028]
• O enunciado do Lab5 já está disponível. (A chave só é informada em classe!) [20121022]
• O enunciado do Lab4 já está disponível. (A chave só é informada em classe!) [20121017]
• Estão disponíveis as notas do Lab4. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente na quarta-feira, dia 17/10, à sala IC-322 entre 12h00 e 13h00. [20121011] 
• Estão disponíveis as notas da P1. Atenção: os alunos que desejarem rever sua prova devem comparecer exclusivamente no dia 01/10 à sala de aulas CB-14 às 8h00. [20120930]
• Estão disponíveis as notas do Lab3. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente no dia 24/9 à sala IC-322 entre 12h30 e 13h30. Observe que o horário deste atendimento não é o mesmo dos anteriores! [20120922]
• O enunciado do Lab3 já está disponível. (A chave só é informada em classe!) [20120922]
• Os slides de todas as aulas que precedem a Prova 1 já estão disponíveis. Guie-se pelos slides, estude pelos livros-textos e faça (pelo menos) todos os exercícios e você estará preparado para a prova. [20120913]
• Os enunciados dos Labs passados estão disponíveis: Lab1, Lab2. (As chaves foram informadas em classe.) [20120910]
• Estão disponíveis as notas do Lab2. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente no dia 10/9 à sala IC-322 entre 18h00 e 19h00. [20120909]
• Estão disponíveis as notas do Lab1. Atenção: os alunos que desejarem conversar com o PED (Lucas) sobre esse Lab devem comparecer exclusivamente no dia 27/8 à sala IC-322 entre 18h00 e 19h00. [20120824]
• Adiante-se na leitura do Guia dos Labs e do Guia sobre Depuradores. [20120807]
• As aulas tóricas serão na sala CB-14 a partir de segunda-feira, dia 1 de agosto. [20120731] 
• Verifique as datas de laboratório no texto abaixo e marque em sua agenda. [20120731] 
• Procure conseguir um exemplar dos livros recomentados (Cormen [1] e Manber [2]) desde a primeira semana de aulas. [20120731] 

  Docente 

• Prof. Pedro J. de Rezende [MC458 - Turmas A e B]
• Sala IC-29, http://www.ic.unicamp.br/~rezende, (19) 3521-5860,
• Atendimento: (na sala IC-29) às segundas-feiras de 18h05 às 19h00.

Aulas Teóricas

• As aulas serão às segundas-feiras e quartas 08h10-09:50.
• Todas as aulas das quartas-feiras serão aulas teóricas, e as aulas das segundas-feiras alternar-se-ão entre teóricas e de laboratório conforme calendário abaixo.
• As aulas teóricas serão na sala CB-14.

Aulas de Laboratório

• As aulas de laboratório serão às segundas-feiras 08h00-09h50 nos seguintes dias:
  • 20/08
  • 03/09
  • 17/09
  • 08/10
  • 22/10
  • 05/11
    
• A Turma A terá as aulas de laboratório na sala CC-02 e a Turma B na sala CC-03.
• Nas demais segunda-feiras, as aulas serão teóricas (na sala CB-14).

Monitor

• Teremos um Monitor-PED (Lucas Oliveira, e-mail: oliveiralukas at yahoo dot com dot br) para esta disciplina que acompanhará as atividades de laboratório.

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

Haverá duas provas (P1, P2) 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á seis trabalhos de laboratório (L1, L2, L3, L4, L5, L6) aos quais serão atribuídas notas também entre 0,0 e 10,0.

Não serão ministradas provas antecipadas nem substitutivas e os laboratórios deverão ser realizados na sala de laboratório, em dia e horário designados. Sem exceção.

A Média dos Laboratórios (ML) será a média aritmética das notas dos trabalhos de laboratório, i.e., ML := (L1 + L2 + L3 + L4 + L5 + L6) / 6.

A Média das Provas (MP) será a média ponderada de P1 e P2 com pesos iguais a 1 e 2, respectivamente, i.e., MP := (P1 + 2 P2) / 3.

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

Se min {ML, MP} >= 5,0
então MS := (ML + 2 MP) / 3

senão se ML < MP
         então MS := (3 ML + 2 MP) / 5
         senão MS := (   ML + 4 MP) / 5

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

Se (MS >= 6,0 e {o aluno não fizer Exame}) ou (MS < 2,5)
então MF := MS
senão se (MS >= 6,0 e {o aluno fizer o Exame}) ou (2,5 <= MS < 6,0)
         então MF := (MS + E) / 2

onde E é a nota obtida pelo aluno no Exame Final. Alunos com 2,5 <= MS < 6,0 são obrigados a tomar o Exame Final, se não, 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 só poderão fazer o Exame Final se comunicarem ao professor, por escrito, até dia 22/11, sua decisão de tomá-lo.

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.

Gráfico mostrando a superfície MS(ML,MP) e o plano MS=6,0.

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

Notas

Tabelas de notas que estão disponíveis: Notas dos Labs, Notas das Provas e Médias.

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 Professor nos horários de atendimentos. 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 assiduamente.)

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;

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.

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

·          (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 aula])

·          (A) Crescimento assintótico e classes de funções.

·          (A) Resolução de recorrências.

·          (A) Métodos diversos.

·          (A) Teorema Master.

 

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

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

·         (P) [Manber] 5.2, 5.3, 5.4, 5.5, 5.7, 5.8, 5.9, 6.11.1, 6.11.2.
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 nos horários de atendimento.)

 

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) Busca binária (simples, variações, seqüências gaguejantes, n=a^b para n, a, b naturais).

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

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

·         (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. [Notas de aula]

Slides das aulas

Nunca estude apenas pelas suas anotações ou pelos slides das aulas. Compareça às aulas, guie-se por suas anotações, mas estude pelos livros indicados.

Referências Bibliográficas

1. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002). Há cópias do livro [1] na "Reserva" da Biblioteca do IMECC.

2. U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

3. J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, (2005).
4. G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall.
5. A. Aho, J. Hopcroft, e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley (1974).
6. N. Ziviani Projeto de Algoritmos com Implementações em Pascal e C, Pioneira Thomson Learning, 2ª. edição, (2004).
7. J. Szwarcfiter, Algoritmos em Grafos, Editora Campus (1987).
8. J. Szwarcfiter e L. Markenson, Estruturas de Dados e seus Algoritmos, LTC Editora (1994).

Datas importantes