Algoritmos e Estruturas de Dados II
Critérios de
correção para os trabalhos.
Os trabalhos tem a forma de ARTIGOS (pegue aqui um exemplo).
Artigos que incluírem o código do programa e mal dão alguma
explicação para o algoritmo geralmente recebem notas que não são
legais. :(
E aqui o
texto explicando o método para encontrar as funções para algoritmos
desconhecidos. Este não é um trabalho da nossa disciplina, está
aqui apenas para leitura!
Pegue aqui o segundo trabalho.
E aqui os casos de teste.
Objetivos
O cumprimento da disciplina busca dar ao aluno, ao
final do semestre, condições de:
- Conhecer estruturas de dados avançadas: filas de prioridades,
mapas e conjuntos;
- Conhecer grafos, suas formas de representação e seus algoritmos
mais importantes;
- Indicar as estruturas de dados que melhor se adaptam para a
solução de um determinado problema;
- Analisar e selecionar o algoritmo mais eficiente para a solução
de um determinado problema.
Ementa
Projeto e análise de algoritmos e estruturas de dados
avançadas: filas com prioridade, heaps, tabelas de hash, mapas,
dicionários, conjuntos e grafos. Discussão, análise e raciocínio
sobre a complexidade de algoritmos e implementações correspondentes.
Programa
- Revisão de complexidade
- Estruturas avançadas
- Filas de prioridade
- Tabelas de espalhamento (hashing)
- Conjuntos
- Aplicações: dicionários
- Aplicações: quadtrees
- Aplicações: codificação de Huffman
- Aplicações: árvores B
- Grafos
- Definições básicas
- Representação e implementação
- Grafos ponderados
- Caminhamentos: largura e profundidade
- Operações sobre grafos
- Detecção de Ciclos e Ordenação Topológica
- Detecção de Componentes
- Árvores de cobertura mínima
- Caminhos Mínimos: Dijkstra e Floyd
- Fluxos
- Caminho crítico
- Aplicações
Avaliação
G1 = ( P1 + 2 * P2 + 2 * MT)/5
Materiais
- Materiais da disciplina:
- Material para aulas práticas sobre heaps: aqui.
- Material para aulas práticas sobre grafos:
- A lista de exercícios sobre grafos está aqui.
- Uma micro-classe para grafos está aqui.
- Um programa que pode ser usado para testá-la está aqui.
- Fornecendo a entrada
2 4
3 4
5 4
2 6
4 8
geramos uma saída que pode ser lida pelo Graphviz e gera esta imagem.
- Um pouco de tudo:
- Uma série de aulas do
MIT (em inglês), sobre vários tópicos da disciplina e outros
assuntos.
- Um catálogo de cursos sobre algoritmos na Universidade
de Pittsburgh. Fonte de outros links!
- Um livro inteiro sobre recursão.
- Recursão, explicada em um material de
Stanford. Leia tudo!!
- Estruturas de dados e algoritmos na
McGill. Bem legal!!
- Design and Analysis na
Universidade de Kent.
- Algoritmos do Skiena.
- Aulas em
video na Universidade da California at Berkeley
-
What papers should everyone read?
- Siga no Twitter: CompSciFact
- Um Wikibook inteiro
sobre algoritmos.
- Um livro ótimo está aqui.
- Caso você tenha dificuldade ao escrever os trabalhos:
- Dicas sobre o uso de pseudo-código estão
aqui e aqui.
- Também temos o livro do Zobel na biblioteca. Use-o!!
- Um repositório de links existe na Iowa
State.
- Recomendamos os itens listados em Writing Texts and
Abstracts, especialmente as dicas de Schulzrinne e a
apresentação de Peyton-Jones.
- Uma análise muito legal do processo de construção de um heap
para o
heapsort .
- Grafos
- Vocabulário de grafos na Wikipedia.
- Uma introdução muito legal da USP.
- Algoritmos, grafos e labirintos.
- Uma apresentação sobre grafos feita pelo Paul
van Dooren (Univ. Católica de Louvain).
- Outra apresentação (em português) feita pelo Antonio
Loureiro (UFMG).
- Este livro é
muito bom! Leia com calma e cuidado!!
- Tutoriais sobre teoria dos grafos na Univ. do Tenessee
(Martin).
- Um livro inteiro on-line: Bondy &
Murty. Contém aplicações, mas este é um livro de Matemática,
não de Informática. Também é meio antigo, então pode não ser a
melhor escolha do mundo... procure livros mais interessantes no
catálogo da biblioteca!
Bibliografia:
Livros texto
- CORMEN, Thomas H. Algoritmos – teoria e prática. 3. ed.
Rio de Janeiro: Elsevier-Campus, 2012.
- ELLIS, H.; SAHNI, S.; RAJASEKARAN, S. Computer
algorithms. Silicon Press, 2007.
- GOODRICH, M. T.; TAMASSIA, R. 3. Estruturas de dados e
algoritmos em Java. Porto Alegre: Bookman, 2013.
Livros complementares
- AHO, A. V. Foundations of computer science. New York:
Computer Science Press, 1998.
- GERSTING, Judith L. Fundamentos matemáticos para ciência da
computação: um tratamento moderno de matemática discreta. 5.
ed. Rio de Janeiro: LTC, 2004.
- GIBBONS, Alan. Algorithmic graph theory. Cambridge (UK):
Cambridge Univ., 1985.
- LEVITIN, Anany. Introduction to the design and analysis
of algorithms. Boston: Addison- Wesley, 2003.
- WALLIS, W. D. A beginner's guide to graph theory.
Boston: Birkhäuser, 2000.