Skip to content. | Skip to navigation

Personal tools

Navigation

You are here: Home / CI056-2016-1

CI056-2016-1


CI056 - Algoritmos e Estruturas de Dados II

Universidade Federal do Paraná
Setor de Ciências Exatas
Departamento de Informática
Professor: David Menotti ( menottid@gmail.com )
Monitor: Leonardo Strozzi ( laps15@inf.ufpr.br )
2016-1

 

 

 

Novidades

  • A apresentação das provas/notas do exame final será realizada hoje, na sala 85 das 13h30 as 17h30 (14/07/2016 - 10h45)
  • Divulgado situação final da disicplina (13/07/2016 - 20h05)
  • Divulgado notas do exame final (13/07/2016 - 20h05)
  • Divulgado situação final (faltando exame final) da disicplina (22/06/2016 - 21h45)
  • Divulgado controle de frequência da disicplina (22/06/2016 - 21h45)
  • Divulgado notas da 3a. Prova, Trabalho Prático 3 e listas de exercícios 11 e 12  (22/06/2016 - 21h45)
  • Divulgado controle de frequência da disicplina (15/04/2016 - 20h10)
  • Divulgado notas da 2a. Prova, Trabalho Prático 2 e listas de exercícios 7, 8, 9 e 10 (13/05/2016 - 20h10)
  • Aulas na PC01 a partir de 06/05/2016 (12/05/2016 - 14h15)
  • Nova data para entrega de Trabalho 3 (12/05/2016 - 14h00)
  • Nova data para entrega de Trabalho 2 (04/05/2016 - 17h15)
  • Divulgado controle de frequência da disicplina (15/04/2016 - 21h00)
  • Divulgado notas da 1a. Prova, Trabalho Prático 1 e listas de exercícios 2, 3, 4, 5 e 6 (15/04/2016 - 21h00)
  • Disponível listas de exercícios (14/01/2016 - 16:00)
  • Disponível slides de todas as aulas (13/01/2016 - 18:20)
  • Disponível especificação do Trabalho 1 , Trabalho 2 e Trabalho 3 (12/01/2016 - 12:30)
  • Divulgado o cronograma tentativo para a disciplina com base em calendário acadêmico (08/01/2016 - 15:00)

 

 

 

Dados gerais

Carga horária: 4 aulas semanais - 4 teóricas / 60 horas de aula (semestral)
Pré-requisitos: CI055 - Algoritmos e Estruturas de Dados I
Cursos: Ciência da Computação, Informática Biomédica & Matemática Industrial

 

 

 

Horário de aulas

  • Turmas A - Quarta-feira das 15:30 as 17:30 - Sala PC01 (PA01 até 04/05/2016)
  • Turmas A - Sexta-feira das 15:30 as 17:30 - Sala PC01 (PA01 até 04/05/2016)

 

 

 

Horário de monitoria

  • Turmas A - Segunda-feira das 17h30 as 19:30 - Lab 1/2.
  • Turmas A - Quarta-feira das 17:30 as 19:30 - Lab 1/2.
  • Turmas A - Sexta-feira das 17:30 as 19:30 - Lab 1/2.

 

 

 

Objetivos

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 para o desenvolvimento de programas, utilizando tipos abstratos 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.

 

Ementa

  • Estilos de programação.
  • Refinamentos sucessivos.
  • Tipos abstratos de dados: listas, pilhas, filas.
  • Recursividade.
  • Ordenação interna.
  • Busca.
  • Análise de complexidade dos algoritmos.

 

 

 

Avaliação da Aprendizagem

Três provas: 60 pontos
Três trabalhos práticos: 30 pontos
Dez listas de exercícios: 10 pontos
Exame final: 100 pontos (média inferior a 70)

 

 

 

Cronograma tentativo (30 encontros)











Encontro - P/T - ---- Data ---- - Dia da semana - - Atividade -





1

1T

02/03/2016

Quarta-feira

Apresentação da disciplina [slides]
Teste Inicial para avaliar conhecimentos em Algoritmos e Estruturas de Dados I (2 pontos extra)

 

 

04/03/2016

Sexta-feira

Palestra de Newton Costa - A Matemática na Polônia
não haverá aula

2

2T

09/03/2016

Quarta-feira

Aula 01 – Tipos Abstratos de Dados [slides]
Lista 01 - Tipos Abstratos de Dados e Estruturas de Dados em C (não entregar - veja gabarito)

3

3T

11/03/2016

Sexta-feira

Aula 02 – Alocação Dinâmica [slides]
Lista 02 – Alocação Dinâmica (entrega para: 18/03/2016)

4

4T

16/03/2016

Quarta-feira

Aula 03 – Medida de Tempo de Execução de um Programa I [slides]

5

5T

16/03/2016

Quarta-feira
(sala PA02)
(17h30-19h)

Aula 04 – Medida de Tempo de Execução de um Programa I [slides]

6

6T

18/03/2016

Sexta-feira

Aula 05 – Medida de Tempo de Execução de um Programa II [slides]
Lista 03 – Limite Inferior (entrega para: 30/03/2016)

7

7T

23/03/2016

Quarta-feira

Aula 06 – Medida de Tempo de Execução de um Programa III [slides]
Lista 04 – Ordem de Complexidade (entrega para: 01/04/2016)

 

25/03/2016

Sexta-feira

Sexta Feira da Paixão - Feriado
não haverá aula

8

8T

30/03/2016

Quarta-feira

Aula 07 – Medida de Tempo de Execução de um Programa IV [slides]
Lista 05 – Função de Complexidade (entrega para: 06/04/2016)

9

9T

01/04/2016

Sexta-feira

Aula 08 – Recursividade [slides]

10

10T

06/04/2016

Quarta-feira

Aula 09 – Recursividade [slides]
Lista 06 – Recursividade (entrega para: 13/04/2016)

11

11T

08/04/2016

Sexta-feira

Aula 10 – Listas Arranjos [slides]
Lista 07 – Listas implementadas por Arranjos (entrega para: 20/04/2016)

12

12T

13/04/2016

Quarta-feira

Revisão – dúvidas das listas de exercícios

13

13T

15/04/2016

Sexta-feira

1a. prova – 20 pontos

14

14T

20/04/2016

Quarta-feira

Aula 11 – Listas Encadeadas [slides]

 

 

22/04/2016

Sexta-feira

Recesso de feriado (Tiradentes)
não haverá aula

15

15T

27/04/2016

Quarta-feira

Aula 12 – Listas Encadeadas [slides]
Lista 08 – Listas implementadas por Encadeamento (entrega para: 04/05/2016)

16

16T

29/04/2016

Sexta-feira

Aula 13 – Pilha [slides]
Lista 09 – Pilha (entrega para: 06/05/2016)

17

17T

04/05/2016

Quarta-feira

Aula 14 – Fila [slides]
Lista 10 – Fila (entrega para: 11/05/2016)

18

18T

06/05/2016

Sexta-feira

Aula 15 – Árvore [slides]

19

19T

11/05/2016

Quarta-feira

Revisão – dúvidas das listas de exercícios

20

20T

13/05/2016

Sexta-feira

2a. prova20 pontos

21

21T

18/05/2016

Quarta-feira

Aula 16 – Ordenação I – SelectSort, InsertSort, BubbleSort [slides]

22

22T

20/05/2016

Sexta-feira

Aula 17 – Ordenação II – ShellSort [slides]

23

23T

25/05/2016

Quarta-feira

Aula 18 – Ordenação III – Quicksort [slides]

27/05/2016

Sexta-feira

Recesso de feriado (Corpus Christi)
não haverá aula

24

24T

01/06/2016

Quarta-feira

Aula 19 – Ordenação IV – HeapSort [slides]

25

25T

03/06/2016

Sexta-feira

Aula 20 – Ordenação V – MergeSort [slides]
Lista 11 – Ordenação (entrega para: 10/06/2015)

26

26T

08/06/2016

Quarta-feira

Aula 21 – Pesquisa I – Pesquisa Sequencial & Binária [slides]

27

27T

10/06/2016

Sexta-feira

Aula 22 – Pesquisa II – Árvores Binária de Busca [slides]

28

28T

15/06/2016

Quarta-feira

Aula 23 – Pesquisa II – Árvores Binária de Busca [slides]
Lista 12 – Pesquisa (entrega para: 22/06/2015)

29

29T

17/06/2016

Sexta-feira

Revisão – dúvidas das listas de exercícios

30

30T

22/06/2016

Quarta-feira

3a. prova20 pontos

 

 

24/06/2016

Sexta-feira

 

29/06/2016

Quarta-feira

01/07/2016

Sexta-feira






31

31T

13/07/2016

Quarta-feira

Exame final - sala PC01

32

32T

14/07/2016

Quinta-feira
(13h30-17h30))

Apresentação de notas - Sala 85/DInf






 

 

 

Referências Bibliográficas

 

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 Structures Using C, Prentice-Hall International Editions, 1995.
  • Cormen, T.H.; Leiserson, C.E.; Rivest, R.L. e Stein, C. Introduction to Algorithms. McGraw-Hill e The Mit Press, 3a. edição, 2009.
  • Cormen, T.H.; Leiserson, C.E.; Rivest, R.L. e Stein, C. Algoritmos: Teoria e Prática. Editora Campus, Tradução da 3a. edição americana, 2012.

 

Bibliografia Complementar

  • 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.
  • Celes, W.; Cerqueira, R.; e Rangel, J. L.; Introdução a Estrutura de Dados. Elsevier / Campus, 2004.
  • 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. e 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. e Maia, M.L. Pascal Estruturado, LTC (Livros Técnicos e Científicos Editora LTDA) 3ª. Edição, 1999.
  • Lopes, A. e Garcia, G. Introdução à Programação: 500 Algoritmos Resolvidos, Editora Campus, 2002.
  • Feofiloff, P. Algoritmos em linguagem C, Editora Campus, 2009.

 

 

 

Trabalhos Práticos

 

Listas de exercícios (CI056)

  • Lista 01 – Tipos de Dados Abstratos e Estruturas de Dados em C [gabarito]
  • Lista 02 – Alocação Dinâmica - divulgação: 14/01/2016, entrega: 16/03/2016
  • Lista 03 – Limite Inferior - divulgação: 14/01/2016, entrega: 30/03/2016
  • Lista 04 – Ordem de Complexidade - divulgação: 14/01/2016, entrega: 01/04/2016
  • Lista 05 – Função de Complexidade - divulgação: 14/01/2016, entrega: 06/04/2016
  • Lista 06 – Recursividade - divulgação: 14/01/2016, entrega: 13/04/2016
  • Lista 07 – Listas implementadas por Arranjos - divulgação: 14/01/2016, entrega: 20/04/2016
  • Lista 08 – Listas implementadas por Encadeamento - divulgação: 14/01/2016, entrega: 04/05/2016
  • Lista 09 – Pilha - divulgação: 14/01/2016, entrega: 06/05/2016
  • Lista 10 – Fila - divulgação: 14/01/2016, entrega: 11/05/2016
  • Lista 11 – Ordenação - divulgação: 14/01/2016, entrega: 10/06/2016
  • Lista 12 – Pesquisa - divulgação: 14/01/2016, entrega: 22/06/2016

 

 

 

Recursos