Análise de Algoritmos
​
​
Avaliação
Avaliações: 2 provas, prova substitutiva e exame.
Datas das Avaliações
-
P1:
-
P2:
-
Substitutiva:
-
Exame:
Média:
MC=(P1+ P2)/2
Sendo P1 a nota da primeira prova e P2 a nota da segunda prova
Para os alunos que necessitem de exame a média final pós exame será:
MF=(MC+E)/2
Sendo E a nota no exame.
Prova substitutiva destinada a alunos ausentes em uma das provas anteriores (com atestado)
A avaliação de recuperação (exame) abrange todo o conteúdo do quadrimestre e é destinada a alunos que tenham obtido conceito final D ou F (conforme Resolução Consepe 182).
PARA Provas, SUB e REC - LEVAR RG E CARTEIRINHA DE UFABC.
Tabela de conversão
Média final Conceito
0 ≤ MF<4,4 F
4,4 ≤ MF<5,1 D
5,1 ≤ MF<6,8 C
6,8 ≤ MF<8,3 B
8,3 ≤ MF ≤10 A
​
Bibliografia
​
-
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C. Introduction to Algorithms, 3a edição, MIT Press, 2009. Obs: Soluções para alguns problemas.
-
ZIVIANI, N. Projeto de Algoritmos: com implementações em Java e C++, 1a edição, Cengage Learning, 2009.
-
GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
Material didático, cronograma e exercícios sugeridos:
Semana 1: Análise assintótica - slides . Exercícios envolvendo notação O e Theta (lousa).
Semana 2: Análise de algotimos Busca Binária Recursiva (lousa), Mergesort - slides , Heapsort (lousa).
Semana 3: Heapsort (lousa), Recorrências - Método da Substituição (lousa).
Semana 4: Recorrências - Método árvore de recorrência (iteração) e Metodo Master (Mestre). (lousa)
Semana 5: Prova 1
Semana 6: QuickSort : análise de melhor caso e pior caso. QuickSort Aleatorizado: análise do caso médio. Algoritmos de ordenação baseados em comparação: limitante inferior para a complexidade. Counting Sort. Radix sort (lousa)
Semana 7: Programação Dinâmica (lousa)
Semana 8: Algoritmos gulosos (lousa). Classes de complexidade: P, NP, NPC (lousa). Redução entre problemas (lousa).
Semana 9: Provas de que problemas SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER são NP-completos (lousa).
Semanas 10-12: Revisão, Prova 2, Provas Substitutivas e Exame.
​