Nome da Atividade
ALGORITMOS E ESTRUTURAS DE DADOS II
CÓDIGO
22000299
Carga Horária
60 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CRÉDITOS
4
CARGA HORÁRIA TEÓRICA
2
CARGA HORÁRIA PRÁTICA
2
CARGA HORÁRIA OBRIGATÓRIA
4
FREQUÊNCIA APROVAÇÃO
75%
NOTA MÉDIA APROVAÇÃO
7
Ementa
Desenvolvimento e análise de algoritmos gulosos e baseados em programação dinâmica. Estruturas de dicionário em memória secundária. Tabelas Hash e suas aplicações. Tries e suas aplicações. Implementações e algoritmos de grafos.
Objectives
Objetivo Geral:
Apresentar técnicas avançadas de desenvolvimento e análise de algoritmos e estruturas de dados para manipulação de dados, inclusive em memória secundária.Conteúdo Programático
1. Análise e Desenvolvimento de Algoritmos
• Análise Amortizada
• Algoritmos Gulosos
• Programação Dinâmica
2. Estruturas de dicionário
• Tries e aplicações
• Tabelas Hash e aplicações
• Estruturas de dicionário em memória secundária (Árvores-B, Hash)
3. Grafos e algoritmos associados
• Propriedades e aplicações de grafos
• Estruturas de dados para grafos (matriz de adjacência, lista de adjacência)
• Algoritmos sobre grafos
– Busca em profundidade e amplitude
– Algoritmos de menores caminhos (Dijkstra)
– Algoritmos de árvores geradoras mínimas (Kruskal, Prim)
– Algoritmos de fluxo em grafos (Ford-Fulkerson)
– Algoritmos de detecção de ciclos e ordem topológica
• Análise Amortizada
• Algoritmos Gulosos
• Programação Dinâmica
2. Estruturas de dicionário
• Tries e aplicações
• Tabelas Hash e aplicações
• Estruturas de dicionário em memória secundária (Árvores-B, Hash)
3. Grafos e algoritmos associados
• Propriedades e aplicações de grafos
• Estruturas de dados para grafos (matriz de adjacência, lista de adjacência)
• Algoritmos sobre grafos
– Busca em profundidade e amplitude
– Algoritmos de menores caminhos (Dijkstra)
– Algoritmos de árvores geradoras mínimas (Kruskal, Prim)
– Algoritmos de fluxo em grafos (Ford-Fulkerson)
– Algoritmos de detecção de ciclos e ordem topológica
Bibliografia
Bibliografia Básica:
- LEISERSON, Charles, RIVEST, Ronald, CORMEN, Thomas. Algoritmos - Teoria e Prática. Editora Campus. ISBN 8535209263.
- SEDGEWICK, Robert. Algorithms in C, 3rd. edition, vol. 1, Addison Wesley Longman, 1998. ISBN 0201314525
- ROBERTS, Eric. Programming Abstractions in C: A Second Course in Computer Science. Addison-Wesley, 1997. ISBN 0201545411
Bibliografia Complementar:
- TENENBAUM, Aaron M., AUGENSTEIN, Moshe J., LANGSAM, Yediduyah. Estrutura de dados usando C. São Paulo: Pearson Makron Books, 2004. 883 p. ISBN 8534603480
- LORENZI, Fabiana, MATTOS, Patrícia Noll de, CARVALHO, Tanisi Pe- reira de. Estruturas de dados. São Paulo: Thomson, 2007. 175 p. ISBN 9788522105564
- EDELWEISS, Nina. Estruturas de dados. Porto Alegre: Bookman, 2009. 261 p. (Livros didáticos do Instituto de informática da UFRGS) ISBN 9788577803811
- SZWARCFITER, Jayme Luiz. Estruturas de dados e seus algorítmos. 2. ed. Rio de Janeiro: LTC, 1994. 320 p. ISBN 852l610149
Turmas Ofertadas
| Turma | Período | Vagas | Matriculados | Curso / Horários | Professores | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 | 2024 / 2 | 24 | 23 |
Ciência da Computação (Bacharelado) Engenharia de Computação (Bacharelado) Horários
|
GUILHERME TOMASCHEWSKI NETTO Professor responsável pela turma |
||||||
| M2 | 2024 / 2 | 26 | 26 |
Ciência da Computação (Bacharelado) Engenharia de Computação (Bacharelado) Horários
|
GUILHERME TOMASCHEWSKI NETTO Professor responsável pela turma |
||||||
| M3 | 2024 / 2 | 24 | 14 |
Ciência da Computação (Bacharelado) Engenharia de Computação (Bacharelado) Horários
|
BRENDA SALENAVE SANTANA Professor responsável pela turma |
Disciplinas Equivalentes
| Disciplina | Curso |
|---|---|
| ESTRUTURA DE DADOS II | Ciência da Computação (Bacharelado) |
| ESTRUTURAS DE DADOS II | Engenharia de Computação (Bacharelado) |