608670_AED (1) - Apresentação

Prévia do material em texto

1
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Objetivos da Disciplina
Dar condições ao aluno de utilizar recursividade para a solução de problemas
computacionais. Dar condições ao aluno de utilizar técnicas simples de análise de
algoritmos. Possibilitar ao aluno conceituar e desenvolver a habilidade de projetar e
implementar estruturas de dados (filas, listas, pilhas e árvores) em memória principal.
Possibilitar ao aluno conceituar e desenvolver a habilidade de implementar métodos de
ordenação e pesquisa em memória principal, bem como selecionar o melhor método e
estrutura para determinadas aplicações.
Ementa
Apontadores. Classes como mecanismo para implementação de tipos abstratos de dados.
Estruturas de dados estáticas e dinâmicas. Introdução à análise de algoritmos. Árvores e
tabelas de pesquisa em memória principal.
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade I – Revisão Geral de Algoritmos e outros Aprofundamentos
• Algoritmos – Conceito
• Estrutura Seqüencial
• Estrutura Condicional
• Estruturas de Repetição
• Funções e Procedimentos
• Vetores e Matrizes
• Recursividade
2
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade II – Introdução à Análise de Algoritmos
• Técnicas para Análise de Algoritmos
• Medidas de Tempo de Execução
• Análise do Pior Caso, Caso Médio e Melhor Caso
• Comportamento Assintótico de Funções
• Classes de Comportamento Assintótico
• Considerações sobre Análise de Algoritmos Recursivos
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade III – Tipos Abstratos de Dados (TAD)
• Conceitos Básicos
• TAD na Programação
• Implementação de TAD – Estruturas e Classes
• Exemplos em C# – Uso de Tipos Abstratos de Dados
3
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade IV – Introdução à Programação Orientada por Objetos
• Classes e Objetos
• Atributos/Propriedades/Métodos de Classe
• Mecanismos de Visibilidade - Encapsulamento
• Herança e Polimorfismo
• Sobrecarga
• Exemplos em C#
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade V – Estruturas de Dados Fundamentais
• Listas
• Listas Simplesmente Encadeadas
• Listas Duplamente Encadeadas
• Listas Circulares
• Operações em Listas
• Filas
• Operações em Filas
• Pilhas
• Operações em Pilhas
4
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade VI – Classes Genéricas do C# e outras Implementações
• Introdução
• Classe ArrayList
• Classe List
• Classe Queue
• Classe Stack
• Classe SortedList
• Outras Classes...
• Estudos Práticos e Implementações em C#
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade VII – Algoritmos de Pesquisa em Memória Primária
• Algoritmo de Pesquisa Sequencial
• Algoritmo de Pesquisa Binária
• Implementação de Algoritmos de Pesquisa em C#
• Considerações sobre Complexidade de Algoritmos em Algoritmos de Pesquisa 
Sequencial e Binária
5
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade VIII – Tabelas Hashing
• Conceitos Preliminares
• Funções Hashing
• Tratamento de Colisões
• Tabela Hashing implementada com Endereçamento Aberto
• Tentativa Linear
• Tentativa Quadrática
• Tabela Hashing implementada como Lista
• A Classe HashTable do C#
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade IX – Estruturas de Dados do Tipo Árvore
• Árvore Binária
• Conceitos Preliminares
• Nó de uma Árvore e Grau de uma Árvore
• Nó Raiz/Nó Pai/Nó Filho/Nó Irmão/Nó Folha
• Nó Ancestral/Nó Descendente
• Nível e Altura de uma Árvore
• Árvore Estritamente Binária/Árvore Completa/Árvore Cheia
• Consultas em uma Árvore Binária
• Implementação de Árvores Binárias em C#
• Árvore AVL
• Balanceamento
• Rotações em Árvore AVL
6
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Unidades de Ensino
Unidade X – Introdução aos Métodos de Ordenação em Memória Primária 
• Introdução
• Métodos de Ordenação em Memória Primária
• Bubble Sort
• Heap Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Selection Sort
• Considerações sobre Complexidade de Algoritmos em Algoritmos de Ordenação
• Exemplos em C#
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Atividades e Distribuição de Pontos
Unidade I
Avaliação I 15 Pontos 25 Pontos
Avaliação II 15 Pontos
Lista de Exercícios 10 Pontos 15 Pontos
Unidade II
Avaliação III 15 Pontos 25 Pontos
Avaliação IV 15 Pontos
Lista de Exercícios 10 Pontos 15 Pontos
Trabalhos Práticos 10 Pontos
Trabalho Interdisciplinar 10 Pontos
Reavaliação (Novos Critérios)
7
Pontifícia Universidade Católica de Minas Gerais
Curso de Sistemas de Informação
Algoritmos e Estruturas de Dados
Apresentação da Disciplina
Bibliografia
• ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos – Estruturas de Dados: Algoritmos, Análise da
Complexidade e Implementações em Java e C/C++
• ZIVIANE, Nivio – Projeto de Algoritmos: com implementações em Java e C++
• FARRER, Harry et al. Programação Estruturada de Computadores – Algoritmos Estruturados. Rio de Janeiro:
Guanabara Dois, 1985. 260p.
• MANZANO, José Augusto N. G.; OLIVEIRA, Jayr F. – Algoritmos: Lógica para Desenvolvimento de Programação
• SZWARCFITER, Jayme Luiz; MARKENZON, Lilian – Estruturas de dados e seus Algoritmos
• CORMEN, Thomas H. et al. – Algoritmos: Teoria e Prática
• VILLAS, Marcos Vianna; VILLASBOAS, Luiz Felipe P. Programação – Conceitos, Técnicas e Linguagens. Rio de Janeiro:
Campus, 1988. 196p.
• PREISS, Bruno – Estruturas de dados e algoritmos. Rio de Janeiro: Campus, 2001. 584p.
• GUIMARÃES, Ângelo de M. & LAGES, Newton A. de C. – Algoritmos e Estruturas de Dados. RJ. LTC, 1985. 216p.