MC202D - Estruturas de Dados

Professor

Ricardo da Silva Torres <rtorres@ic.unicamp.br>

Monitor

Cristiano Dalmaschio Ferreira <crferreira@gmail.com>

Primeiro Semestre de 2006

Ementa

Estruturas básicas para representação de informações: listas, árvores, grafos, e suas generalizações. Algoritmos para construção, consulta, e manipulação de tais estruturas. Desenvolvimento implementação e testes de programas usando tais estruturas em aplicações específicas.

Programa

• Representação de matrizes por linearização de índices; acesso por linhas e colunas.
• Estruturas ligadas: nó, apontador, variável apontadora, alocação dinâmica de memória.
• Listas ligadas simples: operações básicas.
• Comparação de listas ligadas com vetores.
• Algoritmos gerais para listas simples: enumeração, inversão, cópia, concatenação.
• Pilhas, filas, e aplicações (inclusive eliminação de recursão).
• Intercalação (merge) de listas e mergesort; análise informal.
• Variações: listas circulares, duplamente ligadas, com cabeça. Lista livre.
• Árvores binárias: representação e percurso (recursivo).
• Aplicação: árvore de busca (com inserção e remoção).
• Fila de prioridade (heap) implementação com vetor e heapsort.
• Árvores gerais: definição, representação por listas, percursos.
• Listas generalizadas e uso para representar estruturas ligadas em geral.
• Introdução ao espalhamento (hashing): conceito, implementação com listas ligadas.
• Grafos: conceito, representação por matrizes e listas ligadas.
• Percurso de grafos em largura e profundidade.

Horários

Turma D

Dia	Hora	Sala
Terça	21-23	CB06
Quinta	19-21	CB06
Sábado	08-10	LM03

Atendimento:

Os horários e locais para atendimento serão definidos oportunamente e divulgados na página da disciplina.

Avaliação

A avaliação será feita através da realização de provas teóricas, resolução de listas de exercícios e realização de atividades de laboratório (implementação de programas ao longo do semestre).

Parte Teórica

Provas Teóricas

Serão realizadas duas provas teóricas $P_1$ e $P_2$.

Datas

$M_{ProvaTeorica}$

Turmas D	$P_1$: 27 de abril
	$P_2$: 20 de junho

$M_{ProvaTeorica} = \frac{4P_1 + 6P_2}{10}$

Fraude:

A ocorrência de fraude em provas teóricas implicará a atribuição de nota zero à nota $M_{ProvaTeorica}$, ou seja, $M_{ProvaTeorica} = 0$.

Listas de Exercícios

Os alunos receberão listas de exercícios ao longo do semeste que deverão ser respondidas e entregues ao professor. Uma nota será atribuída para cada lista de exercício.
A nota referente às listas de exercícios $M_{Listas}$será a média aritmética das notas obtidas em todas as listas, excetuando-se as 3 menores.

Fraude:

A ocorrência de fraude na resolução de listas de exercícios implicará a atribuição de nota zero à nota $M_{Listas}$, ou seja, $M_{Listas = 0}$.

Nota da Parte Teórica ($M_{Teorica}$)

A média da parte teórica do curso $M_{ProvaTeorica}$ será calculada da seguinte forma:
$M_{Teorica}= \frac{2*M_{ProvaTeorica}+M_{Listas}}{3}$

Atividades de Laboratório

Serão propostos vários programas para serem desenvolvidos em laboratório em uma ou duas semanas. A avaliação dos programas poder levar em conta os seguintes itens: (i) correção; (ii) clareza do código e comentários e (iii) eficiência: tempo e espaço.
Os laboratórios terão peso 1 ou 2, conforme sua complexidade. Desta forma, a nota dos laboratórios $M_{Lab}$será a média ponderada de todos os laboratórios.

Fraude:

A ocorrência de fraude em provas práticas ou programas implicará a atribuição de nota zero à nota da atividade fraudada. Além disso, a nota dos laboratórios $M_{Lab}$ será substituída pelo mínimo entre 4,9 e a nota $M_{Lab}$previamente obtida.

Linguagem de Programação:

A resolução de provas e listas de exercícios bem como a implementação de programas deverá utilizar a linguagem C.

Ambientes recomendados para o desenvolvimento dos programas:

GNU/Linux ou DevC++ 4/Windows.

Média parcial

	$M_{Teorica}\lt5$ ou $M_{Lab}\lt5$
$M_{Parcial}=\frac{7M_{Teorica}+3M_{Lab}}{10}$	$M_{Parcial}=min\{M_{Teorica}, M_{Lab}\}$

Exame

Poderão fazer exame teórico os alunos com $M_{Parcial}\lt 5$ e que tiverem freqüência maior ou igual a 75%. O exame será realizado no dia 11 de julho.

Média final

$M_{Parcial}\lt= 5$	$M_{Parcial}\lt 5$
$M_{Final}= M_{Parcial}$	$M_{Final} = \frac{Exame+ M_{Parcial}}{2}$

Referências

1

A. V. Aho, J. E. Hopcroft, and Ullman.
Data Structures and Algorithms.
Addison Wesley, 1983.

2

E. Horowitz, S. Sahni, and S. Anderson-Freed.
Fundamentals of Data Structures in C.
Computer Science Press, 1993.

3

B. W. Kernighan and D. M. Ritchie.
C: A Linguagem de Programação.
Campus, 1986.

4

T. Kowaltowski and C. L. Lucchesi.
Estruturas de dados e técnicas de programação.
Instituto de Computação - Unicamp.

5

F. K. Miyazawa.
Notas de Aula de Algoritmos e Programação de Computadores, 2001.
Com a colaboração de Cid C. de Souza e Tomasz Kowaltowski, Disponivel na xerox do Instituto de Artes.

6

E. S. Roberts.
The Art and Science of C : A Library Based Introduction to Computer Science.
Addison Wesley, 1995.

7

R. Sedgewick.
Algorithms in C.
Addison-Weley, 1990.

8

A. M. Tanembaum.
Estruturas de Dados Usando C.
Makron Books, 1995.

9

N. Ziviani.
Projeto de Algoritmos com Implementações em Pascal e C.
Pioneira Thompson Learning, São Paulo, Brazil, 2004.