|
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
|
| UNIDADE: INSTITUTO DE MATEMÁTICA E ESTATÍSTICA | ||
| DEPARTAMENTO: DEPTO. DE INFORMATICA E CIENCIAS DA COMPUTACAO | ||
| DISCIPLINA: Algoritmos e Estruturas de Dados II | ||
| CARGA HORÁRIA: 60 | CRÉDITOS: 4 | CÓDIGO: IME04-10823 |
| MODALIDADE DE ENSINO: Presencial | TIPO DE APROVAÇÃO: Nota e Frequência | |
| STATUS | CURSO(S) / HABILITAÇÃO(ÕES) / ÊNFASE(S) |
| Obrigatória | IME - Ciência da Computação (versão 1) IME - Informática e Tecn. Informação (versão 3) |
| TIPO DE AULA | CRÉDITO | CH SEMANAL | CH TOTAL |
| Teórica | 4 | 4 | 60 |
| TOTAL | 4 | 4 | 60 |
OBJETIVO(S):
Tornar acessíveis aos alunos a prática de análise e projeto de algoritmos computacionais eficientes, através da apresentação de técnicas básicas de construção de algoritmos e sua análise matemática. Apresentar também uma visão dos problemas sem soluções eficientes conhecidas e as técnicas aproximativas para contornar essa deficiência.
EMENTA:
Medidas de complexidade de algoritmos e de problemas. Técnicas básicas de construção de algoritmos: Recursão, Backtracking, Programação Dinâmica e Algoritmo Guloso, com exemplificação e análise de cada técnica. Teoria da intratabilidade de problemas. Classes P e NP. Método da Redução. Teorema da Satisfatibilidade. Problemas pseudo-polinomiais. Problemas NP-Completos. Algoritmos Randômicos e Aproximativos.
| PRÉ-REQUISITO 1: IME04-10820 Algoritmos e Estruturas de Dados I |
| DISCIPLINA(S) CORRESPONDENTE(S): IME04-05441 Organização de Dados (p/curso inf) |
BIBLIOGRAFIA: -T. H. Cormen, C. E. Leiserson, R.L.Rivest,C. Stein, "Algoritmos - Teoria e Prática", Ed. Campus, 2002.
-N. Ziviani, "Projeto de Algoritmos", 2a. edição, Ed. Thomson, 2004.
-E.Horowitiz, S.Sahni, S.Rajasekaran, "Computer Algorithms", Computer Science Press, 1998.
-C.H.Papadimiotriou "Computational Complexity", Addison Wesley, 1995.
-G.Ausiello et al "Complexity and Approximation", Springer 1999.