Estrutura de Dados Não-Lineares

SERVIÇO PÚBLICO FEDERAL
INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE
DI RET O RI A DE EDUC AÇ ÃO E T ECNO L OG I A DA I NF O RM AÇ ÃO
Av. Sen. Salgado Filho, 1559, Natal/RN, 59015-000. Fone/FAX (084) 4005-2637
Curso: Tecnologia em Análise e Desenvolvimento de Sistemas
Disciplina: Estrutura de Dados Não-Lineares
Pré-Requsito(s): Estrutura de Dados Lineares
Carga-Horária: 60h(80h/a)
Número de créditos 4
EMENTA
Estrutura de dados não-lineares: árvores genéricas, árvores binárias, árvores binárias de pesquisa, árvores
balanceadas (AVL e rubro-negra). Filas de prioridade com Heaps.
Introdução a teoria dos grafos. Representação computacional de grafos. Algoritmos de busca em grafos,
problemas de menor caminho.
·
·
·
1.
2.
3.
4.
5.
6.
7.
8.
9.
·
·
·
·
·
·
·
PROGRAMA
Objetivos
Compreender conceitos utilizados no processo de desenvolvimento das estruturas de dados;
Desenvolver programas utilizando estruturas de dados;
Aplicar técnicas de pesquisa e classificação de dados.
Bases Científico-Tecnológicas (Conteúdos)
Árvores
1.1. Conceito, representação e terminologia.
1.2. Árvores genéricas
1.3. Árvores binárias
1.4. Árvores binárias de pesquisa
1.5. Algoritmos de caminhamento
Filas de Prioridade com Heaps
2.1. Conceito, implementação e aplicações
Árvores Balanceadas AVL
3.1. Conceito, balanceamento, inserção e remoção
Árvores Balanceadas rubro-negra
4.1. Conceito, balanceamento, inserção e remoção
Teoria dos grafos
5.1. Conceitos
5.2. Representação computacional
5.3. Coloração
5.4. Planaridade
Conectividade e distância
6.1. Grafo conexo, Grafo f-conexo, componentes conexas e fortemente conexas
6.2. Algoritmos para conexidade
6.3. Distância
Caminhos em Grafos
7.1. Caminhos e ciclos
7.2. Grafos de Eulerianos
7.3. Grafos Hamiltonianios
Busca em grafos
8.1. Algoritmo básico
8.2. Busca em profundidade
8.3. Busca em largura
Problemas do Menor Caminho
9.1. Carteiro chinês
9.2. Caixeiro viajante
9.3. Algoritmo de Floyd
9.4. Algoritmo de Dijkstra
Procedimentos Metodológicos
Aulas teóricas expositivas,
Aulas práticas em laboratório,
Desenvolvimento de projetos.
Recursos Didáticos
Quadro branco, computador, projetor multimídia.
Avaliação
Avaliações escritas e práticas
Trabalhos individuais e em grupo (listas de exercícios, estudos dirigidos, pesquisas)
Apresentação dos trabalhos desenvolvidos
Bibliografia Básica
1.
2.
3.
4.
5.
1.
BOAVENTURA NETTO, Paulo O. Grafos: teoria, modelos, algoritmos. 3ª Edição. Edgar Blucher LTDA, 2003. (10)
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de dados e algoritmos em Java. 4ª Edição. Bookman, 2007. (8)
CORMEN, Thomas H. Algoritmos: Teoria e Prática. Campus, 2002. (8)
McMILLAN, Michael. Data Structures and Algorithms using C#. Cambridge University Press, 2007. ISBN: 978-0521670159.
EBook: PREISS, Bruno R. Data Structures and Algorithms with Object-Oriented Design Patterns in C#.
http://www.brpreiss.com/books/opus6/
Bibliografia Complementar
GUIMARÃES, Ângelo M. Algoritmos e estruturas de dados. LTC, 1994. (7)
Software(s) de Apoio: