DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos e Estruturas de Dados
Programa da Disciplina
[editar | editar código-fonte]Nome: | ALGORITMOS E ESTRUTURAS DE DADOS |
Código: | 06214 |
Departamento: | Departamento de Computação (DC) |
Área: | Computação |
Carga-horária total: | 60 horas |
Créditos: | 4 |
Pré-requisitos: | INTRODUÇÃO À PROGRAMAÇÃO I (Cód. 14117)/ MATEMÁTICA DISCRETA I (Cód. 14203) |
Ementa
[editar | editar código-fonte]- Análise de Algoritmos: Notação O e Análise Assintótica. Algoritmos para pesquisa e ordenação em memória principal e secundária.
- Organização de arquivos.
- Técnicas de recuperação de informação. Listas lineares e suas generalizações: listas ordenadas, listas encadeadas, pilhas e filas.
- Aplicações de listas.
- Árvores e suas generalizações: árvores binárias, árvores de busca, árvores balanceadas (AVL), árvores B e B+
- Aplicações de árvores.
Conteúdo
[editar | editar código-fonte]- Introdução ao Estudo de Algoritmos.
- Definição de Algoritmo
- Análise de Pior Caso, Caso Médio e Melhor Caso
- Análise Assintótica
- Estratégia Dividir-Para-Conquistar
- Algoritmos Recursivos
- Estruturas de Dados.
- Listas Ligadas: simples, duplas e circulares
- Alocação Dinâmica de Memória
- Pilhas e Filas: alocação estática e dinâmica
- Árvores Binárias de Busca
- Árvores AVL
- Tabelas Hash
- Heaps
- Conjuntos Disjuntos
- Ordenação.
- Algoritmos em Grafos
- Busca em Largura
- Busca em Profundidade
- Árvore Geradora Mínima
- Busca de Caminho Mais Curto
- Enumeração Topológica. Componentes fortemente conexos
- Conceitos Básicos de NP-Completude.
- Problemas NP-Completos
- Redutibilidade
- Aplicações
Conteúdo programático período letivo 2019.1
[editar | editar código-fonte]- Análise de Algoritmos.
- Análise do Pior Caso;
- Notação Assintótica;
- Estruturas de Dados.
- Lista ligadas: simples, duplas, circulares;
- Alocação dinâmica de memoria;
- Pilhas, Filas: alocação estática de dinâmica;
- Árvores: binárias;
- Construção recursiva de árvores;
- Passeio em árvores? préfixo, pósfixo e central;
- Grafos: orientados e não-orientados;
- Aplicações.
- Pesquisa de Dados.
- Sequencial e Binária;
- Árvores: busca (largura e profundidade), inserção e remoção; balanceamento;
- Grafos; busca, árvore geradora;
- Aplicações.
- Conceitos Básicos de NP-Completude.
- Problemas NP-Completos;
- Redutibilidade;
- Aplicações.
- Projeto de Desenvolvimento com Estruturas de Dados Avançadas.
Validação período letivo 2019.1
[editar | editar código-fonte]A nota da VA1 e da VA2 são calculadas segundo a fórmula VAi = 0.5*Pi + 0.5*Ei (i = 1, 2), onde Pi é uma nota de atividades escritas (prova e lista de exercícios), e Ei é uma média de exercícios de programação que faremos ao longo do semestre. Ou seja, atividades escritas são 50% da nota, exercícios de programação são 50%.
Chamo esses exercícios de Exercícios Programa ou EP. Para a primeira VA, faremos 3 EP's, identificados como EP1, EP2 e EP3; para a segunda VA faremos dois EP's, identificados como EP4 e EP5. Então, E1 é a média aritmética EP1, EP2 e EP3, e E2 é a média aritmética EP4 e EP5. A nota da terceira VA é composta da média entre uma prova escrita e a média de todos os EP's; idem para a final.
Bibliografia Básica
[editar | editar código-fonte]- CORMEN, Thomas H. et. al. Algoritmos: Teoria e Prática. Editora Campus, 2002.
- FEOFILOFF, Paulo. Algoritmos em Linguagem C. Editora Campus/Elsevier, 2008-2009.
- ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 2. ed. rev. e ampl. São Paulo: Thomson, 2005.
- SEDGEWICK, Robert. and Flajolet, Philippe. An Introduction to the Analysis of Algorithms Wesley, 1996.
Bibliografia Complementar
[editar | editar código-fonte]- MANBER, U. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989.
- PATASHNIK, O.; GRAHAM, R. L.; KNUTH, D. E. Matemática Concreta: Fundamentos para a Ciência da Computação. Segunda edição. Rio de Janeiro: LTC, 1995. 475 p.
- BRASSARD, G; BRATLEY, P. Fundamentals of Algorithmics, Prentice Hall, 1996.
- DASGUPTA, S; PAPADIMITRIOU, C.; VAZIRANI, U.V. Algorithms, McGraw-Hill, 2006. Disponível eletronicamente em: http://www.cs.berkeley.edu/~vazirani/algorithms.html
- KLEINBERG, J; TARDOS, E. Algorithm Design, Addison-Wesley, 2005.
Obrigatório
[editar | editar código-fonte]Estrutura de Dados é obrigatório para Estrutura de Dados II e para aperfeiçoamento nas linguagens de programação ensinadas neste curso.