Programa da Disciplina

Nome:	Demografia
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

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

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
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
Ordenação.
1. Mergesort
2. Quicksort
3. Heapsort
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
Conceitos Básicos de NP-Completude.
1. Problemas NP-Completos
2. Redutibilidade
3. Aplicações

Conteúdo programático período letivo 2019.1

Análise de Algoritmos.
1. Análise do Pior Caso;
2. Notação Assintótica;
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.
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.
Conceitos Básicos de NP-Completude.
1. Problemas NP-Completos;
2. Redutibilidade;
3. Aplicações.
Projeto de Desenvolvimento com Estruturas de Dados Avançadas.

Validação período letivo 2019.1

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

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

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

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

Utilizador:Ricardosdag/Demografia

Índice