ALGORITMOS E ESTRUTURA DE DADOS II

Prévia do material em texto

Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
VIGÊNCIA: 2004/1 - 2021/1
PROGRAMA DA DISCIPLINA
DISCIPLINA:
ALGORITMOS E ESTRUTURA DE DADOS II
CODCRED CARGA HORÁRIA MÓDULO
46172-04 60 60
EMENTA:
Matrizes esparsas. Registros. Arquivos. Listas lineares. Árvores. Grafos. Algoritmos de manipulação
destas estruturas. Linguagem de programação para implementação destes algoritmos. Ordenação e
pesquisa em tabelas.
OBJETIVOS:
O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:
1. Definir as noções de classes e objetos e projeto de programas e estruturas de dados orientadas
à objetos.
2. Definir e diferenciar as estruturas de dados genéricas fundamentais, tais como filas, pilhas, listas
encadeadas, árvores e grafos.
3. Manipular estruturas de dados através do emprego de algoritmos.
4. Selecionar e construir estruturas de dados adequadas para aplicações específicas, bem como
modelar estas aplicações utilizando a noção de orientação à objetos.
5. Comparar estruturas de dados através da adequação ao problema.
CONTEÚDO:
Nº DA UNIDADE: 0l
CONTEÚDO: Conceitos Básicos
1.1. Algoritmos
1.2. Tipos abstratos de dados X Classes e Objetos
1.3. Representação física de relações lógicas: contiguidade física, encadeamento
1.4. Projeto Orientadados à Objetos
1.4.1. Conceitos Básicos
1.4.2. Exemplos
1.4.3. Estudos de Casos
Nº DA UNIDADE: 02
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica
Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
CONTEÚDO: Listas Lineares
2.1. Listas
2.1.1.Definição e exemplos
2.1.2. Listas contíguas
2.1.3. Listas encadeadas
2.1.4. Aplicações de listas
2.2. Pilha
2.2.1. Definição e exemplos
2.2.2. Pilhas contíguas
2.2.3. Pilhas encadeadas
2.2.4. Aplicações de pilhas
2.3. Fila
2.3.1. Definição e exemplos
2.3.2. Filas contíguas
2.3.3. Filas encadeadas
2.3.4. Aplicações de filas
2.4. Outras estruturas com disciplina de acesso
Nº DA UNIDADE: 03
CONTEÚDO: Árvores 
3.1.Introdução: conceitos, terminologia básica, aplicações
3.2.Tipos de árvores: geral e binária
3.3.Formas de representação de árvores binárias
3.4.Caminhamentos
3.5.Implementação de algoritmos de manipulação e transformação de árvores
3.6.Aplicações de árvores
Nº DA UNIDADE: 04
CONTEÚDO: Grafos
4.1. Introdução: conceitos, terminologia básica, classificação, propriedades, aplicações
4.2. Representações
4.3. Caminhamentos
4.4. Algoritmos sobre grafos
4.5. Aplicações de grafos
PROCEDIMENTOS E CRITÉRIOS DE AVALIAÇÃO:
Avaliação da disciplina será feita mediante trabalhos, exercícios, projetos, ou/e provas.
BIBLIOGRAFIA BÁSICA:
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica
Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
1.WEISS, MARK ALLEN. Data structures & algorithm analysis in C++. Reading, MA.
Addison-Wesley. 1999.
2.GOODRICH, MICHAEL T.; TAMASSIA, ROBERTO. Data Structure and Algorithms in Java. Wiley
and son. 1997.
BIBLIOGRAFIA COMPLEMENTAR:
3.AHO, A. V.; ULLMAN, J. D. Foundations of Computer Science. New York : Computer Science
Press, 1998.
4.CORMEN, T.; LEISERSON, C.; RIVEST, R. Introduction to Algorithms. Cambridge: MIT Press,
2001.
5.ADAMSON, I.T. Data Structures and algorithms: a first course. London: Springer, 1996
6.AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D. Data Structures and Algorithms. Cambridge:
Addison-Wesley, 1987.
7.TANEMBAUM, A. M., AUGENSTEIN, M.J. Data structures using Pascal. New Jersey : Prentice-Hall,
1986.
8.TANEMBAUM, A. M.; LANGSAM, Y; AUGENSTEIN, M.J., Estruturas de Dados Usando C. Makron
Books, 1995.
9.VELOSO, PAULO ET ALLI. Estruturas de Dados. Rio de Janeiro: Editora Campus, 1996.
10.WIRTH, N. Algoritmos e estruturas de dados. Rio de Janeiro: Prentice Hall. 1999.
11.ZIVIANI, Nivio. Projeto de algoritmos com implementação em Pascal. São Paulo : Ed. Pioneira,
1999.
•SOFTWARE DE APOIO:
1.Compiladores Borland C++ e g++
2.Ambientes de Programação Java
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica