Wikiversidade

DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos e Estruturas de Dados

< DC-UFRPE‎ | Bacharelado em Ciência da Computação

Programa da Disciplina editar

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

  • 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

  1. Introdução ao Estudo de Algoritmos.
    1. Definição de Algoritmo
    2. Análise de Pior Caso, Caso Médio e Melhor Caso
    3. Análise Assintótica
    4. Estratégia Dividir-Para-Conquistar
    5. Algoritmos Recursivos
  2. Estruturas de Dados.
    1. Listas Ligadas: simples, duplas e circulares
    2. Alocação Dinâmica de Memória
    3. Pilhas e Filas: alocação estática e dinâmica
    4. Árvores Binárias de Busca
    5. Árvores AVL
    6. Tabelas Hash
    7. Heaps
    8. Conjuntos Disjuntos
  3. Ordenação.
    1. Mergesort
    2. Quicksort
    3. Heapsort
  4. Algoritmos em Grafos
    1. Busca em Largura
    2. Busca em Profundidade
    3. Árvore Geradora Mínima
    4. Busca de Caminho Mais Curto
    5. Enumeração Topológica. Componentes fortemente conexos
  5. Conceitos Básicos de NP-Completude.
    1. Problemas NP-Completos
    2. Redutibilidade
    3. Aplicações

Conteúdo programático período letivo 2019.1 editar

  1. Análise de Algoritmos.
    1. Análise do Pior Caso;
    2. Notação Assintótica;
  2. Estruturas de Dados.
    1. Lista ligadas: simples, duplas, circulares;
    2. Alocação dinâmica de memoria;
    3. Pilhas, Filas: alocação estática de dinâmica;
    4. Árvores: binárias;
      1. Construção recursiva de árvores;
      2. Passeio em árvores? préfixo, pósfixo e central;
    5. Grafos: orientados e não-orientados;
    6. Aplicações.
  3. Pesquisa de Dados.
    1. Sequencial e Binária;
    2. Árvores: busca (largura e profundidade), inserção e remoção; balanceamento;
    3. Grafos; busca, árvore geradora;
    4. Aplicações.
  4. Conceitos Básicos de NP-Completude.
    1. Problemas NP-Completos;
    2. Redutibilidade;
    3. Aplicações.
  5. Projeto de Desenvolvimento com Estruturas de Dados Avançadas.

Validação período letivo 2019.1 editar

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

  • 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

  • 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

Estrutura de Dados é obrigatório para Estrutura de Dados II e para aperfeiçoamento nas linguagens de programação ensinadas neste curso.

Índice editar

Obtida de "https://pt.wikiversity.org/w/index.php?title=DC-UFRPE/Bacharelado_em_Ciência_da_Computação/Algoritmos_e_Estruturas_de_Dados&oldid=148889"