Curso: Ciência da Computação, DOURADOS, Integral (2017) - 3a Série
Professor: CLEBER VALGAS GOMES MIRA
Disciplina: Análise de Algoritmos
Carga Horária: 136 h Período Letivo: 02/2017 a 12/2017
Ementa:
Modelo de computação, crescimento de funções e notações. Somatórias e recorrências. Projeto de algoritmos por indução: paradigma incremental e divisão e conquista. Programação dinâmica e algoritmos gulosos. Análise de algoritmos de: ordenação, seleção, correspondência de cadeias, geometria computacional e grafos. Reduções e NP-Completude.
Objetivos:
Estudar técnicas de análise da complexidade de algoritmos, bem como paradigmas para o projeto de algoritmos eficientes.
Conteúdo:
Obs.: O material didático utilizado nessa disciplina será baseado nas transparências do Prof. Dr. Cid Carvalho de Souza e Cândida Nunes da Silva.
Metodologia:
As aulas serão ministradas em salas com o uso do datashow, giz e quadro negro. Serão efetuadas 4 provas e 1 seminário. As prováveis datas das provas são:
SUBSTITUTIVA 28/11
EXAME 05/12
Bibliografia:
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. Elsevier, 2002.
MANBER, U. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
AHO, A.; HOPCROFT, J.; ULLMAN, J. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Bibliografia Complementar:
BASE, S. Computer Algorithms. Addison-Wesley, 2000.
TERADA, R.; Desenvolvimento de Algoritmo e Estrutura de Dados. McGraw Hill, 1991.
BAZARRA, N. S.; JARVIS, J. J. Linear Programming and Network Flows. John Wley & Sons, 1977.
EVEN, S. Algorithmic Combinatories, Memilian Co., 1973
HOROWITZ, E.; SAHNIS, S. Fundamentals of Data Structures. Computer Science Press Inc., 1982.
KNUTH, D. E. The Art of Computer Programming. Addison-Wesley, 2005. Vols 1, 2 e 3.
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elements of the Theory of Computation. Prentice Hall, 1997.
NIJENHUIS, A.; WILF, H. S. Combinatorial Algorithms. Academic Press, 1978.
PAPADIMITRIOU, C. Computational Complexity. Addison-Wesley, Reading, 1994.
Critérios de Avaliação:
Serão efetuadas 4 provas. Além disso, a entrega de listas de exercícios resolvidas contribuirá com as notas das provas. Cada lista de exercícios resolvida vale até 1,0 ponto que será adicionada à nota final da prova. A nota da prova não pode ultrapassar o valor de 10.
A média final será computada pela fórmula :
MF = (P1 + P2 + P3 + P4 + S) / 5 onde
P1, P2, P3 e P4 são as notas das respectivas provas e S é o valor da nota de seminários; todos com valor entre 0 e 10.
A prova substitutiva substitui a prova com menor nota. A substitutiva tem valor entre 0 e 10,0 e o conteúdo é referente a toda a matéria.
A Nota Final (F) é calculada da seguinte maneira:
Caso o valor de MF do aluno for igual ou superior a 6,0, então a nota final é F = MF.
Caso o valor de MF do aluno for entre 3,0 e 6,0, o aluno terá direito a fazer o Exame Final (E) com valor entre 0 e 10 e a nota final será F = (MF + E)/2.
O aluno com nota de MF inferior a 3,0 é automaticamente reprovado.
O Exame Final cobrará o conteúdo de toda a matéria
Será aprovado o aluno cuja nota final F for igual ou superior a 5,0.