BCC202 – Estruturas de Dados I
Carga Horária: 90 Horas de Aula ou 108 Horas Aula (72h – Teórica / 36h –
Prática = 6 créditos)
Professor: (Teórica) David Menotti (menottid@gmail.com)
Professora: (Prática)
Emiliana Mara Lopes Simões (simoes.eml@gmail.com)
Monitor: Tiago Alves Silva (tiago.silva1230@gmail.com)
Monitor: Flávio Antunes Almeida (flavio_antunesalmeida@hotmail.com)
1º Semestre
de 2010
Novidades
Disponível notas e situação final
(08/07/2010 – 21:00)
Exame especial no PCA –
sala 210 as 8:20h (28/05/2010 – 12:30) – a freqüência será computada
amanhã
Disponível notas (05/07/2010
– 22:10)
Selecionado melhor TP3 (02/07/2010 –
16:25)
Selecionados melhores TP2
(02/07/2010 – 16:25)
Disponível notas, texto e gabarito
do primeiro teste (22/06/2010 – 04:40)
Disponível Trabalho Prático 6 (10/06/2010 – 17:00)
Correção no enunciado do 3º item do Trabalho Prático 5 (05/06/2010 – 12:30)
Notas atualizadas
(28/05/2010 – 12:30)
Não haverá aula 02/06/10 e
esta aula será reposta 07/06/10 (segunda-feira) as 19h (28/05/2010 – 12:30)
Selecionados melhores TP1
(28/05/2010 – 12:25)
Disponível Trabalho Prático 5 (28/05/2010 – 12:15)
Disponível Trabalho Prático 4 (13/05/2010 – 07:20)
Disponível notas (05/05/2010
– 19:20)
Disponível texto e gabarito
do primeiro teste (05/05/2010 – 19:15)
Disponível Trabalho Prático 3 - [dados]
(30/04/2010 – 20:00)
Disponível Trabalho Prático 2 (13/04/2010 – 23:00)
Disponível Trabalho Prático 1 (16/03/2010 – 22:30)
Divulgado o horário da monitoria
(16/03/2010 – 20:40)
Definido datas de testes e entrega
dos trabalhos práticos (09/03/2010 – 23:30)
Divulgado o cronograma tentativo
para a disciplina (09/03/2010 – 22:00)
Horário:
Terça-feira das 13:30
as 15:10, Pavilhão Central de Aulas - PCA
Turma 21 e 22 -
Sala 107 (PCA) - Teórica
Quarta-feira das 08:20
as 10:00, Pavilhão Central de Aulas – PCA
Turma 21 e 22 -
Sala 209 (PCA) - Teórica
Segunda, Terça e Quarta-feira
das 19:00 as 20:40, Instituto de Ciência Exatas e Biológicas
– ICEB
Turma 21 e 22 –
Sala COM30 (ICEB I) – Monitoria
(Tiago)
Quinta e Sexta-feira
das 19:00 as 20:40, Instituto de Ciência Exatas e
Biológicas – ICEB
Turma 21 e 22 –
Sala COM30 (ICEB I) – Monitoria
(Flávio)
Sexta-feira das 10:10
as 11:50, Instituto de Ciência Exatas e Biológicas – ICEB
Turma 21 e 22 –
Sala COM30 (ICEB I) – Monitoria
(Tiago)
Ementa
Tipos
abstratos de dados.
Alocação
dinâmica.
Noções de
complexidade de algoritmos.
Recursividade.
Estruturas de
dados: listas, filas, pilhas e árvores.
Métodos de
ordenação por comparação.
Métodos de
pesquisa em memória primária.
Objetivos
Objetivos Gerais
O aluno
deverá conhecer conceitos associados aos métodos de pesquisa e ordenação e de
estruturas de dados de interesse teórico e prático.
Deverá
também adquirir a capacidade de utilizar esses recursos pra desenvolvimento de
programas, utilizando conceitos de abstração de dados, modularização
e recursividade.
Deverá
ainda ser capaz de comparar estratégias de implementação
do ponto de vista da complexidade dos algoritmos envolvidos, usando a notação
O.
Bibliografia Básica
Ziviani N. e Botelho, F.C.
Projetos de Algoritmos com implementação em C e Pascal (ou em Java e C++), Editora Thomson,
2003 (2007).
Tenenbaum, A.M., Langsam, Y. e Augenstein,
M.J. Estruturas
de Dados Usando C, Makron Books/Pearson Education, 1995.
Tenenbaum, A.M., Langsam, Y. e Augenstein, M.J. Data Strcutures Using C, Prentice-Hall International Editions, 1995.
Bibliografia Complementar
Cormen, T.H., Leiserson, C.E. Rivest, R.L. e Stein, C. Introduction to Algorithms. McGraw-Hill e The Mit Press, 2001.
Cormen, T.H., Leiserson, C.E. Rivest, R.L. e Stein, C. Algoritmos: Teoria e Prática. Editora Campus, Tradução da 2a. edição americana, 2001.
Knuth,D.E. The Art of Computer Programming. Vol 1: Fundamental Algorithms. Addison-Wesley, 3a. edição, 1997.
Knuth,D.E. The Art of Computer Programming. Vol 3: Sorting and Searching. Addison-Wesley, 1973.
Bibliografia Auxiliar
Schildt, H. C Completo e
Total, Pearson/Makron Books, 3ª. Edição, 1997.
Mizrahi, V.V. Treinamento em Linguagem C, Pearson Prentice Hall, 2ª. edição, 2008.
Guimarães, A.M.
e Lages, N.A.C. Algoritmos e Estruturas de Dados,
LTC (Livros Técnicos e Científicos Editora LTDA), 21a
Tiragem, 1994.
Farrer, H. Becker, C.G.
Faria, E.C. Matos, H.F., Santos M.A., Maia, M.L. Algoritmos Estruturados, LTC (Livros Técnicos e
Científicos Editora LTDA) 3ª. Edição, 1999.
Farrer, H. Becker, C.G.
Faria, E.C. Campos-Filho, F.F. Matos, H.F., Santos M.A., Maia, M.L. Pascal
Estruturado, LTC (Livros Técnicos e Científicos Editora LTDA) 3ª. Edição,
1999.
Lopes, Anita, Garcia, Guto, Introdução
à Programação: 500 Algoritmos Resolvidos, Editora Campus, 2002.
Paulo Feofiloff,
Algoritmos
Avaliação da Aprendizagem
Três testes: 6
pontos
Seis trabalhos práticos: 3 pontos
Entrega de listas de exercícios, trabalhos
em aula prática/laboratório: 1 ponto
Exame especial: 10 pontos (substitui
a nota integral do semestre)
Cronograma
tentativo para 1º Semestre de 2010 (37 encontros – 37 teóricos)
|
Encontro |
P/T |
Data |
Dia Semana |
Atividade |
|
1 |
1T |
02/03/2010 |
Terça-Feira |
Dispensa para assistir as palestras de inauguração
do Mestrado em Ciência da Computação da UFOP |
|
2 |
2T |
03/03/2010 |
Quarta-feira |
Apresentação da Disciplina [slides] Teste
Inicial para avaliar conhecimentos em Introdução à Programação (0,2 pontos extra) |
|
3 |
3T |
09/03/2010 |
Terça-Feira |
Aula 01 – Tipos Abstratos de Dados [slides] Lista 1
- Tipos Abstratos de Dados e Estruturas de Dados em C |
|
4 |
4T |
10/03/2010 |
Quarta-feira |
Aula 02 – Alocação Dinâmica [slides] |
|
5 |
5T |
15/03/2010 |
Segunda-feira |
Reforço sobre algoritmos – presença não obrigatória |
|
6 |
6T |
16/03/2010 |
Terça-Feira |
Aula 03 – Medida de Tempo de Execução de um Programa
I [slides] |
|
7 |
7T |
17/03/2010 |
Quarta-feira |
Aula 04 – Medida de Tempo de Execução de um Programa
I [slides] |
|
8 |
8T |
22/03/2010 |
Segunda-feira |
Reforço sobre algoritmos – presença não obrigatória |
|
9 |
9T |
23/03/2010 |
Terça-Feira |
Aula 05 – Medida de Tempo de Execução de um Programa
II [slides] |
|
10 |
10T |
24/03/2010 |
Quarta-feira |
Aula 06 – Medida de Tempo de Execução de um Programa
III [slides] |
|
11 |
11T |
30/03/2010 |
Terça-Feira |
Aula 07 – Medidas de Tempo de Execução [slides] |
|
12 |
12T |
31/03/2010 |
Quarta-feira |
Aula 08 – Recursividade [slides] |
|
13 |
13T |
06/04/2010 |
Terça-Feira |
Aula 09 – Recursividade [slides] |
|
14 |
14T |
07/04/2010 |
Quarta-feira |
Revisão – Dúvidas Listas |
|
15 |
15T |
13/04/2010 |
Terça-Feira |
1o. Teste – 2,0 pontos |
|
16 |
16T |
14/04/2010 |
Quarta-feira |
Aula 10 – Listas Arranjos [slides] |
|
17 |
17T |
20/04/2010 |
Terça-Feira |
Aula 11 – Listas Encadeadas [slides] |
|
18 |
18T |
27/04/2010 |
Terça-Feira |
Aula 12 – Listas Encadeadas [slides] |
|
19 |
19T |
04/05/2010 |
Terça-Feira |
Aula 13 – Pilha [slides] |
|
20 |
20T |
05/05/2010 |
Quarta-feira |
Aula 14 – Fila [slides] |
|
21 |
21T |
11/05/2010 |
Terça-Feira |
Aula 15 – Árvore [slides] |
|
22 |
22T |
12/05/2010 |
Quarta-feira |
Aula
16 – Ordenação I – SelectSort, InsertSort, BubbleSort [slides] |
|
23 |
23T |
18/05/2010 |
Terça-Feira |
Aula 17 – Ordenação II – ShellSort [slides] |
|
24 |
24T |
19/05/2010 |
Quarta-feira |
Aula 18 – Ordenação III – QuickSort
[slides] |
|
25 |
25T |
25/05/2010 |
Terça-Feira |
Aula 18 – Ordenação III – QuickSort
[slides] Aula 19 – Ordenação IV – HeapSort [slides] |
|
26 |
26T |
26/05/2010 |
Quarta-feira |
Aula 19 – Ordenação IV – HeapSort [slides] |
|
27 |
27T |
01/06/2010 |
Terça-Feira |
2o. Teste – 2,0 pontos |
|
28 |
28T |
07/06/2010 |
Segunda-Feira |
Aula 20 – Ordenação V – MergeSort [slides] |
|
29 |
29T |
08/06/2010 |
Terça-Feira |
Aula 21 – Pesquisa I – Pesquisa Sequencial
& Binária [slides] |
|
30 |
30T |
09/06/2010 |
Quarta-feira |
Aula 27 – Pesquisa V – Hashing
[slides]
|
|
31 |
31T |
14/06/2010 |
Segunda-feira |
Conclusão de Aula 19 – Ordenação IV – HeapSort
[slides]
e Aula 27 – Pesquisa V – Hashing [slides] |
|
32 |
32T |
16/06/2010 |
Quarta-Feira |
Aula 22 – Pesquisa
II – Árvores Binária de Busca I [slides] |
|
33 |
33T |
22/06/2010 |
Terça-Feira |
Aula 23 – Pesquisa
II – Árvores Binária de Busca II [slides] |
|
34 |
34T |
23/06/2010 |
Quarta-feira |
Aula 23 – Pesquisa
II – Árvores Binária de Busca II [slides] |
|
35 |
35T |
29/06/2010 |
Terça-Feira |
Aula 24 – Pesquisa III – Árvores AVL I [slides] |
|
36 |
36T |
29/06/2010 |
Terça-feira |
Aula 25 – Pesquisa III – Árvores AVL II [slides] |
|
37 |
37T |
30/06/2010 |
Quarta-feira |
3o. Teste – 2,0 pontos |
|
38 |
38T |
06/07/2010 |
Terça-feira |
Aula 26 – Pesquisa IV – Árvores Digitais [slides] |
|
39 |
39T |
07/07/2010 |
Quarta-feira |
Exame Especial – 10 pontos |
Trabalhos Práticos
Trabalho Prático 1 – 0,5 pontos - entrega 05/04/2010 – Trabalhos
Selecionados – [ solução 1 (Andrey) / solução 2
(Samuel) ]
Trabalho Prático 2 – 0,5 pontos - entrega 26/04/2010 – Trabalhos
Selecionados – [ solução 1
(Lucas) / solução
2 (Rossiny) ]
Trabalho Prático 3 – 0,5 pontos - entrega 11/05/2010 – Trabalhos
Selecionados – [ solução 2 (Andrey)]
·
[dados]
Trabalho Prático 4 – 0,5 pontos - entrega 25/05/2010 – Trabalhos
Selecionados – [ solução 1 (???) / solução 2 (???) ]
Trabalho Prático 5 – 0,5 pontos - entrega 07/06/2010 – Trabalhos
Selecionados – [ solução 1 (???) / solução 2 (???) ]
Trabalho Prático 6 – 0,5 pontos - entrega 28/06/2010 – Trabalhos
Selecionados – [ solução 1 (???) / solução 2 (???) ]
Listas de exercícios (BCC202)
Lista 1 -
Tipos de Dados Abstratos e Estruturas de Dados em C [gabarito]
Lista
4 – Ordem de Complexidade
Lista
5 – Função de Complexidade
Lista
7 – Listas implementadas por Arranjos
Lista
8 – Listas implementadas por Encadeamento
Listas
de exercícios para fortalecimento de Introdução à Programação (BC201/CIC100)
1ª.
Lista de Exercícios – Entrada/Saída, Atribuição e Estrutura Seqüencial (35
exercícios, 7 para cada aluno) [solução]
[professor]
2ª.
Lista de Exercícios – Estrutura Condicional (44 exercícios, 11 para cada
aluno) [solução]
[professor]
3ª.a Lista de Exercícios – Estrutura de Repetição (100
exercícios, 20 para cada aluno) [solução]
[professor]
3ª.b Lista de Exercícios – Estrutura de Repetição (100
exercícios, 20 para cada aluno) [solução]
[professor]
4ª.
Lista de Exercícios – Estruturas de Dados Compostas Homogêneas Unidimensionais
– Vetores (35 exercícios, 7 para cada aluno) [solução]
[professor]
5ª. Lista
de Exercícios – Estruturas de Dados Compostas Homogêneas Multidimensionais –
Matrizes (30 exercícios, 6 para cada aluno) [solução]
[professor]
6ª.
Lista de Exercícios – Modularização – Funções e
Procedimentos (30 exercícios, 6 para cada aluno) [solução]
[professor]
Recursos
Softwares
Dev C++
Moodle - http://www.decom.ufop.br/
Apostilas C:
Renato
Cardoso Mesquita - DEE/UFMG
Camillo - PUCPR
GACLI
- UNICAMP
Menotti
– DCC/UFMG
Aprenda
Microsoft Visual C++ 5.0 em 24 horas (texto público, em inglês)
Apostilas e documentos para LATEX
Símbolos em Latex – 105 páginas de caracteres e símbolos especiais
A não
tão pequena introdução ao Latex – 132 páginas –
aprenda de tudo um pouco
Uma não tão
pequena introdução ao Latex – 132 páginas –
aprenda de tudo um pouco