Estruturas de Dados I

Segundo trimestre de 2008

Horário alfa: 2a (19-21), 4a (21-23)

Sala: S 305, L 506 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

Novidades:

03/09 -- Notas finais disponíveis
28/08 -- Notas parciais disponíveis
19/08 -- Exemplos de questões que poderiam compor a prova disponíveis
16/08 -- Slides da última aula estão disponíveis (procure nesta página por "slides")
11/08 -- *** Lista de exercícios 8 (processamento de cadeias) disponível ***
11/08 -- Nova referência recomendada sobre casamento de cadeias (página web, por Christian Charras e Thierry Lecroq)
07/08 -- Notas de alguns exercícios disponíveis
27/07 -- *** Lista de exercícios 7 (busca digital) disponível ***
25/07 -- *** Lista de exercícios 6 (árvores B) disponível ***
25/07 -- Dentro do exercício 4 há mais um link de referência para consulta
25/07 -- *** Lista de exercícios 5 (árvores AVL e B) disponível ***
22/07 -- Exercício 4 teve o prazo adiado
21/07 -- *** Lista de exercícios 4 (árvores) disponível ***
18/07 -- Local da monitoria atualizado
18/07 -- Breve guia para desenvolvimento em C/Unix
18/07 -- Especificação PARCIAL dos trabalhos disponível
17/07 -- Seção sobre o trabalho adicionada
17/07 -- Duas indicações de livros (Dasgupta&Papadimitriou&Vazirani; Mehlhorn&Sanders)
08/07 -- Notas da P1 disponíveis
30/06 -- Prova adiada para segunda, 07/07
26/06 -- *** Lista de exercícios 3 (ordenação) disponível ***
26/06 -- Alguns exemplos de questões de prova
22/06 -- Link para o dicionário de algoritmos e estruturas de dados do NIST
21/06 -- Segunda lista de exercícios (heaps)
19/06 -- Lista de exercícios entregues
14/06 -- Horário de monitoria definido
06/06 -- Primeira lista de exercícios (linguagem C)
06/06 -- Cronograma modificado (não houve aula no dia 04/06, e a ordem dos tópicos foi alterada)

Ementa

Introdução à linguagem de programação C++. Estruturas lineares. Algoritmos de ordenação em estruturas lineares. Algoritmos de busca em estruturas lineares. Árvores.

Dinâmica do curso

A primeira aula começa com questões administrativas e segue com noções de programação em C.

Nas outras aulas, recomendo fortemente que o aluno leia algum dos textos de referência sobre o assunto a ser tratado!

Cópias em provas ou trabalhos resultam em conceito F na disciplina.

Avaliação

A avaliação tem quatro componentes:

• Duas provas (P1 e P2)
• Um trabalho (T)
• Exercícios (E)

A nota final é a média dos quatro componentes: (P1+P2+T+E)/4

O conceito final será dado de acordo com a tabela mostrada no primeiro dia de aula.

Notas

Exercícios / mini-trabalhos

• 1 - Linguagem C Prazo: 16/06
• 2 - Heaps Prazo: 08/07
• 3 - Ordenação de vetores Prazo: 14/07
• 4 - Árvores (binárias de busca e AVL) Prazo: 04/08 11/08
• 5 - Árvores, II (AVL e B) Prazo: 11/08
• 6 - Árvores III (só B) Prazo: 11/08
• 7 - Busca digital Prazo: 13/08
• 8 - Processamento de Cadeias Prazo: 27/08

Veja alguns exemplos de questões que poderiam compor a prova. É interessante fazer como exercício, claro.

Agora há também exemplos de questões para a segunda prova.

Exercícios entregues

Veja a tabela com os exercícios entregues.

Programa

Trabalhos

Monitoria

Ferramentas

Aqui está um breve projeto-de-texto (versão -1), ainda desconexo e estranho, que pode servir de guia para o desenvolvimento de programas em C/Unix, para quem acostumou-se com o mundo Java.

Usem os compiladores e ambientes que preferirem, desde que os programas sejam limitados à linguagem C padrão! Eu compilarei os programas usando o GCC em Linux.

Sugestão de ferramentas em ambiente Linux ou Unix:

• GCC, o compilador C do projeto GNU;
• GDB, o depurador do projeto GNU;
• Valgrind, para detectar erros de acesso à memória;
• Emacs, um editor de textos absurdamente customizável (a linguagem de customização é um tipo de Lisp). O Emacs já vem com configurações prontas para trabalhar com C. Se você decidir usar o Emacs, use também o ECB (Emacs Code Browser);
• vim, para quem acha que o Emacs tem features demais;
• Há também o Eclipse e o NetBeans para Linux, mas não os uso, por isso não posso ajudar muito com eles.

Bibliografia

Os três primeiros livros (Cormen et al, Ziviani, Szwarcfiter&Markenzon) são as referências principais para a matéria.

• Cormen, Leiserson, Rivest & Stein. Algoritmos: teoria e prática (Introduction to Algorithms). Excelente livro; há dois exemplares na biblioteca.
• Ziviani, N. Projeto de Algoritmos.
• Szwarcfiter, J. & Markenzon, L. Estruturas de Dados e seus Algoritmos.
• Manber, U. Algorithms: a creative approach. O autor trabalhou no Yahoo!, e hoje é Vice-Presidente de Engenharia do Google. Este livro é especial porque mostra uma abordagem diferente para o desenvolvimento de algoritmos, usando indução (e recursão).
• Mehlhorn, K.; Sanders, P. Algorithms and Data Structures. Um livro muito bom. Claro, preciso e bem organizado.
• Dasgupta, S.; Papadimitriou, C. H; Vazirani, U. V. Algorithms. Muito bom livro sobre projeto de algoritmos. Os autores são muito conhecidos e costumam produzir material de excelente qualidade. O livro está disponível em PDF nesta página.

Linguagem C:

• Kernigham & Ritchie. C: a linguagem de programação. Ótima introdução à linguagem C (escrito pelos criadores da linguagem).
• Harbison, S & Steele. L. C: manual de referência. Não é um tutorial; é a melhor referência que conheço para a linguagem C.

Veja também

• Exact String Matching Algorithms por Christian Charras e Thierry Lecroq. Com descrição clara, implementação em C e visualização do funcionamento.
• Wirth, N. Algorithms + Data Structures = Programs.
• Knuth, D. The Art of Computer Programming (v.1 & v. 3).
• Aho, Hopcroft & Ullman Data Structures and Algorithms. Muito bom livro, apesar de antigo. Não cobre toda a matéria (por exemplo, árvores AVL são deixadas como exercício para o leitor!)
• Goodrich, M. & Tamassia, R. Estruturas de dados e Algoritmos em Java. Bom livro, com exemplos em Java.
• Dictionary of Algorithms and Data Structures do NIST
• Johnson, D. A Theoretician's Guide to the Experimental Analysis of Algorithms. Não é o foco do curso, mas este é um texto muito interessante sobre como analisar (experimentalmente) o desempenho de um algoritmo. O autor é David Johnson, co-autor do conhecido livro sobre NP-completude ("Computers and Intractability: A Guide to the Theory of NP-Completeness", ou o "Garey&Johnson")