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.

 

 

Programa

  1. Apresentação do curso: programa, objetivos e bibliografia
  2. Tipos de dados abstratos
  3. Alocação dinâmica
  4. Noções de análise de complexidade de algoritmos
    • Medida de Tempo de execução;
    • Análise assintótica, notação O.
  5. Recursividade
  6. Listas
  7. Pilha e Fila
  8. Filas de prioridade e implementação por heap
  9. Árvores
  10. Métodos de ordenação
    • selectionsort, insertionsort, bubblesort, shellsort, quicksort, heapsort e mergesort
  11. Métodos de pesquisa
    • simples, binária, árvores binárias, digitais e AVL, e hashing

 

 

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 em linguagem C, Editora Campus, 2009.

 

 

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]

Lista 2 – Alocação Dinâmica

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]

Lista 3 – Limite Inferior

10

10T

24/03/2010

Quarta-feira

Aula 06 – Medida de Tempo de Execução de um Programa III [slides]

Lista 4 – Ordem de Complexidade

11

11T

30/03/2010

Terça-Feira

Aula 07 – Medidas de Tempo de Execução [slides]

Lista 5 – Função de Complexidade

12

12T

31/03/2010

Quarta-feira

Aula 08 – Recursividade [slides]

13

13T

06/04/2010

Terça-Feira

Aula 09 – Recursividade [slides]

Lista 6 – Recursividade

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]

Lista 7 – Listas implementadas por Arranjos

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]

Lista 8 – Listas implementadas por Encadeamento

19

19T

04/05/2010

Terça-Feira

Aula 13 – Pilha [slides]

Lista 9 – Pilha

20

20T

05/05/2010

Quarta-feira

Aula 14 – Fila [slides]

Lista 10 – Fila

21

21T

11/05/2010

Terça-Feira

Aula 15 – Árvore [slides]

Lista 11 – Árvores

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]

Lista 12 – Ordenação

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]

Lista 13 – Pesquisa

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 2 – Alocação Dinâmica

Lista 3 – Limite Inferior

Lista 4 – Ordem de Complexidade

Lista 5 – Função de Complexidade

Lista 6 – Recursividade

Lista 7 – Listas implementadas por Arranjos

Lista 8 – Listas implementadas por Encadeamento

Lista 9 – Pilha

Lista 10 – Fila

Lista 11 – Árvore

Lista 12 – Ordenação

Lista 13 – Pesquisa

 

 

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

Borland C

Dev C++

Moodle - http://www.decom.ufop.br/moodle/

Apostilas C:

Renato Cardoso Mesquita - DEE/UFMG

Camillo - PUCPR

GACLI - UNICAMP

MenottiDCC/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