EXA 806 – ESTRUTURA DE DADOS
Professor
João B. Rocha-Junior
Carga Horária
30 horas / (T:30; P:00; E:00)
Pré-requisitos
EXA 801 – Algoritmos e Programação I
MI - Algoritmos
Ementa
Tipos abstratos de dados; independência entre especificação e implementação. Estruturas de dados básicas: tabelas, listas simples e encadeadas, pilhas, filas. Filas com prioridades. Árvores: terminologia e implementação. Árvores binárias, balanceamento de árvores binárias, árvores B. Conjuntos: conceituação, implementação, métodos de representação. Métodos de busca e ordenação. Hashing. Grafos orientados e não orientados.
Objetivos, Habilidades e Competências (geral)
Conhecer o funcionamento das principais estruturas de dados, sabendo quando cada uma deve ser aplicada em um problema do mundo real.
Objetivos, Habilidades e Competências (específicos)
Conhecer estruturas de dados básicas como lista, fila e pilha;
Conhecer estruturas de dados avançadas avançadas como árvores e hash;
Conhecer principais métodos de busca e ordenação;
Saber computar a complexidade de algoritmos básicos;
Conhecer o funcionamento de grafos e saber desenvolver algoritmos de busca em grafos orientados e não orientados.
Conteúdo Programático
Complexidade de algoritmos
Alocação de memória
Estruturas de dados básicas
Array (tabelas)
Listas simples e encadeadas
Fila
Pilha
Algoritmos de busca
Busca linear
Busca binária
Estruturas de dados avançadas
Fila com prioridade
Heap
Métodos de ordenação
SelectionSort
BubbleSort
InsertionSort
MergeSort
HeapSort
QuickSort
Árvores
Terminologia e implementação
Árvores binárias
Árvore binária balanceada (AVL)
Árvores B
Hashing
Terminologia e implementação
Tabelas Hash
Conjunto
Grafos
Terminologia e implementação
Grafos orientados e não orientados
Busca em profundidade
Metodologia
A metodologia deste módulo será de Aulas Expositivas, mas haverá integração com os módulos do Estudo Integrado de Programação, Estrutura de Dados, Projeto de Sistemas, e Matemática Discreta. As Aulas Expositivas serão aulas dialogadas com o objetivo de introduzir assuntos que serão tratados mais detalhadamente nos problemas do Estudo Integrado de Programação.
Material Utilizado
Salas tradicionais de aula, com quadro negro ou branco, kit para escrever nos quadros, computador e projetor multimídia.
Avaliação
O módulo será dividido em três unidades, para que o estudante possa refletir sobre sua situação em diferentes momentos do curso e, caso necessário, realizar correções de rumo no processo de aprendizagem.
Medidas da Unidade
A medida das duas primeiras unidades será extraída através de uma prova escrita, enquanto que a terceira unidade será um projeto individual.
Média Parcial
A média parcial será a média aritmética das medidas de cada unidade. Obtendo média igual ou superior a 7,0 (sete), o estudante pode ser aprovado, caso cumpra os requisitos de frequência.
Prova Final
Não obtendo média parcial suficiente na avaliação do módulo, o estudante poderá fazer prova final, e a média final será calculada de acordo com o sistema de avaliação vigente na UEFS.
Aprovação no módulo
Para ser aprovado no módulo, o estudante precisa cumprir os seguintes requisitos: Ter frequência igual ou superior a 75% da carga horária efetiva ministrada no módulo, caso contrário haverá reprovação por frequência; Ser aprovado na avaliação do módulo, caso contrário haverá reprovação por nota.
Referências
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest e Clifford Stein. Algoritmos: Teória e Prática. Segunda Edição. Ed. Campus, 2001.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest e Clifford Stein. Introduction to Algorithms. Third Edition. MIT PRESS, 2009.
Robert Lafore. Data Structures & Algorithms in Java. SAMS. Second Edition, 2003.
Mark A. Weiss. Data Structures And Algorithm Analysis in Java. Person. Third Edition, 2012.
Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers. How to Think Like a Computer Scientist: Learning with Python 3, 2012.
Dionysis Zindros. A Gentle Introduction to Algorithm Complexity.