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.