CI056 - Algoritmos e Estruturas de Dados II
Departamento de Informática
Universidade Federal do Paraná
Carga Horária: 60 horas
Prof. Hélio Pedrini
Objetivos
Apresentar e analisar algoritmos e estruturas de dados avançadas para uso eficiente do computador na resolução de problemas. Diversos aspectos teóricos e práticos são abordados, buscando-se a construção de estruturas modulares e reutilizáveis. Os algoritmos são descritos através de uma linguagem simples, com ênfase no método utilizado para solucionar o problema, facilitando sua implementação em linguagens de programação tais como Pascal, C, C++ ou Java.
Ementa
Análise de Algoritmos. Recursividade. Tipos Abstratos de Dados: listas, pilhas, filas. Algoritmos de Ordenação. Pesquisa em Memória Primaria. Pesquisa em Memória Secundária.
Programa
- Introdução
- Algoritmos, estruturas de dados e programas
- Análise de algoritmos (comportamento assintótico de funções, notação assintótica, classes de problemas com diferentes funções de complexidade)
- Recursividade
- Definições
- Recorrências
- Algoritmos recursivos
- Aplicações
- Estruturas de Dados Elementares
- Definições e exemplos
- Tipos abstratos de dados
- Vetores e listas (vetores unidimensionais e multidimensionais, listas ligadas, listas circulares)
- Pilhas e filas
- Aplicações
- Pesquisa em Memória Primária e Secundária
- Pesquisa seqüencial
- Pesquisa binária
- Tabelas de dispersão (funções de dispersão, tratamento de colisões)
- Ordenação
- Definições
- Ordenação interna (bolha, seleção, inserção, mergesort, shellsort, heapsort, quicksort, radix)
- Ordenação externa
- Comparação entre algoritmos de ordenação
Bibliografia
- Básica
- A.M. Tenenbaum, Y. Langsam, M.J. Augenstein. Estruturas de Dados Usando C. Makron Books do Brasil Editora Ltda, São Paulo, SP, 1995.
- N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. Livraria Pioneira Editora, São Paulo, SP, 1994.
- J.L. Szwarcfiter, L. Markenzon. Estruturas de Dados e seus Algoritmos. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
- Complementar
- T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1996.
- R. Sedgewick. Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.
- A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.
- P.A.S. Veloso, C.S. Santos, P.A. Azeredo, A.L. Furtado. Estruturas de Dados. Editora Campus, Rio de Janeiro, RJ, 1986.
- N. Wirth. Algorithms and Data Structures. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).
Critérios de Avaliação
- Listas de Exercícios
- Provas (70% da nota)
- Prova 1: 25 de abril de 2008
- Prova 2: 20 de junho de 2008
- Final: 02 de julho de 2008
- Trabalhos (30% da nota)
- Trabalho 1: 23 de abril de 2008
- Trabalho 2: 18 de junho de 2008
Notas e Frequências