This template has a responsive menu toggling system. The menu will appear collapsed on smaller screens, and will appear non-collapsed on larger screens. When toggled using one of the buttons below, the menu will appear/disappear. On small screens, the page content will be pushed off canvas.
MC458 - Análise de Algoritmos I
Instrutor: Joao Meidanis
Segundas-feiras, 19:00-21:00, sala PB16
Quartas-feiras, 21:00-23:00, sala PB16
Segundo Semestre, 2018
Geralzona
Esta é a primeira disicplina de análise de algoritmos de seu curso de computação. Aqui estudaremos quatro grande 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.
Monitores
Haverá dois monitores para nos auxiliar nesta disciplina:
- Jadder Bismarck de Sousa Cruz
- Heitor Boschirolli Comel (heitor ponto boschirolli no gmail)
Atendimento
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 nos seguintes horários:
2as. a 5as., 18:00-18:50, sala PB01 (nova sala)
Programa e Cronograma
| MC458A | Projeto e Análise de Algoritmos I | ||
| Segundo Semestre, 2018 | Instrutor: João Meidanis | ||
| CRONOGRAMA INICIAL | |||
| S/Q | Data | Tópico | Exercícios/Eventos |
| seg | 30/07 | Exercícios Cormen: N.N-N | |
| qua | 01/08 | Introdução | Problemas Cormen: N-N |
| seg | 06/08 | SECOMP | Exercícios Manber: N.N |
| qua | 08/08 | SECOMP | Exercícios Milne: Página.N |
| seg | 13/08 | Conceitos de análise de algoritmos | 1.2-2, 1.2-3, 1-1, 2.1-3, 2.1-4, 2.2-2, 2-1 |
| qua | 15/08 | Crescimento de funções | 2.2-3, 2.3-3, 2.3-5, 2.3-6, 2.3-7 / Teste |
| seg | 20/08 | Ferramentas: somatórias | 3.1-3, 3.1-4, 3-1a, 3-2, 3-3, 3-4, p135.5 |
| qua | 22/08 | Ferramentas: diferenças finitas | p282.1 a 4, p290.1 a 3 e 6, p291.9,10,13 |
| seg | 27/08 | Ferramentas: recorrências | 4.1-2, 4.1-5, 4.2-2, 4.2-4, 4.2-5 / Teste |
| qua | 29/08 | Ferramentas: Teorema Mestre | 4.3-1, 4.3-2, 4.3-4, 4.3-5, 4-1, 4-3b, 4-4 |
| seg | 03/09 | Prova | |
| qua | 05/09 | Proj.Alg.Induc.: entendendo indução | 2.1, 2.4, 2.7*, 2.9 |
| seg | 10/09 | Proj.Alg.Induc.: polinômios, top.sort | 2.12, 2.4, 2.15, 2.18 |
| qua | 12/09 | Proj.Alg.Induc.: função 1-1 | 2.19, 2.21 / Teste |
| seg | 17/09 | Proj.Alg.Induc.: celebridade | 5.6, 5.12, 5.14*, 5.15* |
| qua | 19/09 | Proj.Alg.Induc.: matching | 5.25a, 6.14*, 6.21 |
| seg | 24/09 | Proj.Alg.Induc.: viés de árv.bin. | 6.22, 6.23 / Teste |
| qua | 26/09 | Proj.Alg.Induc.: par mais próximo | 6.24, 6.25 |
| seg | 01/10 | Prova | Limite:Desistência em Disciplinas |
| qua | 03/10 | Ordenação: mergesort, heapsort | 6.1-4, 6.1-5, 6.2-1, 6.2-2, 6.2-3, 6.34** |
| seg | 08/10 | Ordenação: heapsort | 6.2-4, 6.2-6, 6.4-3, 6.4-4, 6.4-5, 6.29 |
| qua | 10/10 | Ordenação: quicksort | 6.11*, 7.2-2, 7.2-3 / Teste |
| seg | 15/10 | Ordenação: lower bound, counting sort | 8.1-1, 8.2-1, 8.2-4, 8.3-3, 8.4-1, 8.4-2 |
| qua | 17/10 | Ordenação: radixsort, bucketsort | Limite:Trancamento de matrícula |
| seg | 22/10 | Busca binária | 8-3a, 8.6, 9.1-1, 9.3-3 / Teste |
| qua | 24/10 | Mediana e k-ésimo linear | 9.3-3, 9.3-5, 9.3-7, 9.3-8, 9.3-9, 9-1 |
| seg | 29/10 | Prova | |
| qua | 31/10 | Exercícios | |
| seg | 05/11 | Prog.Din.: subseq. mais longa, mochila | 15.4-1, 15.4-2, 15.4-3, 15.4-4 |
| qua | 07/11 | Prog.Din.: mult.cadeias matrizes | 15.4-5, 15.4-6, 16.2-3, 15.2-1 |
| seg | 12/11 | Prog.Din.: árv.bin.busca ótima | 15.2-2, 15.2-3 / Teste |
| qua | 14/11 | Alg.Gulosos: seleção de ativ. | 15.5-1, 15.5-2, 15.5-3 |
| seg | 19/11 | Não haverá atividades | |
| qua | 21/11 | Alg.Gulosos: cód. de Huffman | 16.2-4, 16.2-5, 16.3-1 / Teste |
| seg | 26/11 | Alg.Gulosos: coloração de intervalos | 16.3-2, 16.3-4, 16.3-7, 16.3-8, 16.1-3 |
| qua | 28/11 | Prova | |
| seg | 03/12 | Semana de estudos | |
| qua | 05/12 | Semana de estudos | |
| seg | 10/12 | Exame | |
| qua | 12/12 |
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. 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.
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 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 é obrigado a tomar o Exame Final; se não o fizer, ser-lhe-á atribuída nota zero a E; alunos com MS < 2,5 não poderão fazer o Exame Final; e alunos com MS ≥ 5,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.
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.
Referências
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 (2nd edition). The MIT Press, 2001.
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.