MC458 - Projeto e Análise de Algoritmos I
Instrutor: Joao Meidanis, meidanis at unicamp dot br
Terças, 21:00-23:00. Quintas, 19:00-21:00. Horário
Primeiro Semestre, 2024; Turma B
Visão Geral
Esta é a primeira disciplina de análise de algoritmos de seu curso de computação. Aqui estudaremos quatro grandes tópicos:
- Noções básicas de como estimar tempo de processamento e calcular somatórias;
- Como projetar algoritmos usando indução;
- Algoritmos básicos de ordenação, busca e correlatos;
- Algoritmos que usam programação dinâmica e algoritmos gulosos.
Atendimento e monitores
Para falar com o instrutor, é só marcar um horário através de email. Os monitores estarão disponíveis para tirar dúvidas e resolver exercícios em horários a definir.
Programa
| MC458B | Projeto e Análise de Algoritmos I | 2024 | 1o. Semestre | |
| PROGRAMAÇÃO PRELIMINAR | Última edição: 2024-03-11 | |||
| Dia | Data | Atividade | Referência | Exercícios |
| ter | 27/fev | |||
| qui | 29/fev | Introdução | Cormen | |
| ter | 05/mar | Conceitos de análise de algoritmos | Cormen | 1.2-2, 1.2-3, 1-1, 2.1-3, 2.1-4, 2.2-2, 2-1 |
| qui | 07/mar | Mergesort; Teste | Cormen | 2.2-3, 2.3-3, 2.3-5, 2.3-6, 2.3-7 |
| ter | 12/mar | Crescimento de funções | Cormen | 3.1-3, 3.1-4, 3-1a, 3-2, 3-3, 3-4 |
| qui | 14/mar | Ferramenta: diferenças finitas | Milne | p.135.5, p282.1 a 4, p290.1,2,3,6, p291.9,10,13 |
| ter | 19/mar | Ferramenta: recorrências; Teste | Cormen | 4.3-1, 4.3-2, 4.3-4, 4.3-5, 4-1, 4-3(b), 4-4 |
| qui | 21/mar | Ferramenta: Teorema Mestre | Cormen | 4.1-2, 4.1-5, 4.2-2, 4.2-4, 4.2-5 (N\A) |
| ter | 26/mar | Prova | ||
| qui | 28/mar | Feriado | ||
| ter | 02/abr | Entendendo indução | Ferreira | 2.1, 2.4, 2.7, 2.9 |
| qui | 04/abr | Polinômios | Manber | 2.12, 2.15, 2.18, 5.1 |
| ter | 09/abr | Função 1-1; Teste | Manber | 2.19, 2.21, 5.3 |
| qui | 11/abr | Viés de árvore binária | Manber | 5.5, 5.14, 5.15 |
| ter | 16/abr | Celebridade | Manber | 5.25(a), 5.4, 6.14, 6.21 |
| qui | 18/abr | Subcadeia máxima; Teste | Manber | 5.6, 5.12 |
| ter | 23/abr | Ordenação topológica | Manber | 6.24, 6.25, 7.5 |
| qui | 25/abr | Prova | ||
| ter | 30/abr | Ordenação; Heapsort | Cormen, Manber | 6.1-4, 6.1-5, 6.2-1, 6.2-2, 6.2-3, 6.34 |
| qui | 02/mai | Análise de Heapsort | Cormen, Manber | 6.2-4, 6.2-6, 6.4-3, 6.4-4, 6.4-5, 6.11, 6.29 |
| ter | 07/mai | Quicksort; Lower bound | Cormen | 7.2-2, 7.2-3, 8.1-1 |
| qui | 09/mai | Counting sort; Radix sort | Cormen | 8.2-1, 8.2-4, 8.3-3 |
| ter | 14/mai | Bucketsort; Máximo e mínimo; Teste | Cormen | 8.4-1, 8.4-2, 8-3(a), 9.1-1 |
| qui | 16/mai | Mediana e k-ésimo em tempo linear | Cormen | 9.3-3, 9.3-5, 9.3-7, 9.3-8, 9.3-9, 9-1 |
| ter | 21/mai | Exercícios | ||
| qui | 23/mai | Exercícios | ||
| ter | 28/mai | Subsequência mais longa; Teste | Cormen | 15.4-1, 15.4-2, 15.4-3, 15.4-4, 15.4-5, 15.4-6 |
| qui | 30/mai | Feriado | ||
| ter | 04/jun | Prova | Cormen | |
| qui | 06/jun | Mochila; Huffman | Cormen | 16.2-4, 16.2-5, 16.3-1 |
| ter | 11/jun | Produto de cadeias de matrizes | Cormen | 15.2-1, 15.2-2, 15.2-3 |
| qui | 13/jun | Árvore binária de busca ótima; Teste | Cormen | 15.5-1, 15.5-2, 15.5-3 |
| ter | 18/jun | Seleção de atividades | Cormen | 16.2-3 |
| qui | 20/jun | Coloração de intervalos; Teste | ||
| ter | 25/jun | Prova | ||
| qui | 27/jun | |||
| ter | 02/jul | Estudos | ||
| qui | 04/jul | Estudos | ||
| ter | 09/jul | Feriado | ||
| qui | 11/jul | Exame |
Avaliação
Haverá quatro Provas (P1, P2, P3 e P4) nas datas indicadas no programa. Cada Prova será em classe, nos horários normais de aula, sem exceção, terá duração de 100 minutos e receberá nota entre 0,0 e 10,0.
Haverá oito Testes (T1, T2, T3, T4, T5, T6, T7, T8), também em classe, na segunda metade da aula, aos quais serão atribuídas notas também entre 0,0 e 10,0. Excepcionalmente, em função de disrupções imprevisíveis no andamento do semestre, alguns testes poderão ser feitos remotamente.
Não serão ministrados provas ou testes antecipados nem substitutivos.
A Média dos Testes (MT) será a média aritmética
MT := (T1 + T2 + T3 + T4 + T5 + T6 + T7 + T8) / 8.
A Média das Provas (MP) será a média ponderada
MP := (1xP1 + 2xP2 + 2xP3 + 4xP4) / 9.
A Média Semestral (MS) será calculada da seguinte forma:
Se min { MT; MP } ≥ 5,0
então MS := (MT + 4 MP) / 5
senão MS := min { 4,9; (MT + 4 MP) / 5 }
A Média Final (MF) será calculada da seguinte forma:
Se 2,5 ≤ MS < 5,0onde E é a nota obtida pelo aluno no Exame Final.
então MF := (MS + E) / 2
senão MF := MS
Um aluno com 2,5 ≤ MS < 5,0 poderá tomar o Exame Final; se não o fizer, vamos adotar E = 0 na fórmula acima; alunos com MS < 2,5 ou com MS ≥ 5,0 não poderão fazer o Exame Final.
Serão aprovados os alunos que obtiverem Média Final (MF) maior que ou igual a 5,0; os demais serão reprovados.
Os testes serão realizados em sala de aula, na segunda metade da 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 aula.
Fraude
Qualquer tentativa de fraude neste curso implicará nota igual a zero para todos os envolvidos, com possível sanções adicionais, conforme julgado necessário pela administração da universidade.
Referências bibliográficas
B. Obama. Campanha na sede do Google. Mountain View, 2009. Conhecer algoritmos pode ajudar na hora de uma entrevista. Veja como uma pessoa que não é da área, com um pouco de conhecimento sobre bubble-sort, conseguiu angariar votos importantes para chegar à presidência de uma grande nação.
A. K. Agassi. Open: An Autobiography. Vintage Books, 2010. Andre Agassi odiava tênis e mesmo assim foi um dos maiores tenistas de todos os tempos. Se você detesta teoria, ainda assim pode se dar bem nesta matéria. Leia o livro para ver como ele fez.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms (3nd edition). The MIT Press, 2009.
W. E. Milne. Cálculo numérico (2a edição). Polígono, 1968.
J. Ferreira. Induzindo a um bom entendimento do Princípio da Indução Finita. VI Encontro Capixaba de Educação Matemática, 2002.
U. Manber. Using induction to design algorithms. Communications of the ACM, 31(11) 1300-1313, 1988.
U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
J. Kleinberg e E. Tardos. Algorithm design. Pearson/Addison-Wesley, 2006.
G. Brassard e P. Bratley. Algorithmics: theory and practice. Prentice-Hall, 1995.
A. Aho, J. Hopcroft e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975.
N. Ziviani. Projeto de Algoritmos (2a edição). Thomson, 2004.
J. Szwarcfiter e L. Markenson. Estruturas de Dados e seus Algoritmos. LTC Editora, 1994.