ALGORITMOS E ESTRUTURAS DE DADOS III

Nome da Atividade

CÓDIGO

1110186

Carga Horária

68 horas

Tipo de Atividade

DISCIPLINA

Periodicidade

Semestral

Unidade responsável

Centro de Desenvolvimento Tecnológico

CRÉDITOS

CARGA HORÁRIA TEÓRICA

CARGA HORÁRIA PRÁTICA

CARGA HORÁRIA OBRIGATÓRIA

FREQUÊNCIA APROVAÇÃO

75%

NOTA MÉDIA APROVAÇÃO

Ementa

Algoritmos probabilísticos e análise probabilística. Técnicas de otimização e aproximação de soluções. Classes de complexidade. Aplicações selecionadas.

Objectives

Objetivo Geral:

Apresentar técnicas avançadas de análise e desenvolvimento de algoritmos.

Conteúdo Programático

1. Algoritmos Probabilísticos
• Algoritmos Numéricos
• Algoritmos Monte Carlo
• Algoritmos Las Vegas
2. Análise probabilística de algoritmos
3. Programação Linear
4. Algoritmos aproximativos
5. Classes de complexidade
• As classes P e NP
• NP-Completeza
• Introdução à teoria dos números
• Algoritmos para teste de primalidade
• Algoritmos para fatorização de inteiros
• Sistemas criptográficos de chave privada única
• Sistemas criptográficos de chave pública

Bibliografia

Bibliografia Básica:

LEISERSON, Charles, RIVEST, Ronald, CORMEN, Thomas. Algoritmos - Teoria e Prática. Editora Campus, 2002. 936 p.
SEDGEWICK, Robert. Algorithms in C, 3rd. edition, vol. 1, Addison Wesley Longman, 1998.
ROBERTS, Eric. Programming Abstractions in C: A Second Course in Computer Science. Addison-Wesley, 1997.

Bibliografia Complementar:

TENENBAUM, Aaron M., AUGENSTEIN, Moshe J., LANGSAM, Yediduyah. Estrutura de dados usando C. São Paulo: Pearson Makron Books, 2004. 883 p.
LORENZI, Fabiana, MATTOS, Patrícia Noll de, CARVALHO, Tanisi Pereira de. Estruturas de dados. São Paulo: Thomson, 2007. 175 p.
EDELWEISS, Nina. Estruturas de dados. Porto Alegre: Bookman, 2009. 261 p. (Livros didáticos do Instituto de informática da UFRGS)
SZWARCFITER, Jayme Luiz. Estruturas de dados e seus algorítmos. 2. ed. Rio de Janeiro: LTC, 1994. 320 p.