Estruturas de Dados - Introdução (Dibio)

Prévia do material em texto

dibio@unb.br
Por que estamos aqui?
dibio@unb.br
Ensinar/aprender
"Education is the acquisition of the art of the 
utilisation of knowledge" (Alfred North 
Whitehead [1861-1947], The Aims of Education, 
1929: 16)
dibio@unb.br
Dados da disciplina
● Estruturas de Dados, Turma E, 2011/2
● Créditos (04-00-00-04)
● 04 aulas (horas)
● 04 ESTUDOS (horas)
● semanalmente (= 8 horas)
● Linguagem de Programação utilizada: C
dibio@unb.br
Assuntos 
● Computação e resolução de problemas 
algorítmicos. Conjuntos, dados compostos e 
abstração de dados. Estruturas básicas para 
representação de informações: listas, árvores, 
grafos, e suas generalizações. Ordenação e busca: 
Arquivos, Ordenação, Busca e Espalhamento 
(“Hashing”). 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. (POR QUE?)
dibio@unb.br
Estruturas de Dados
● Formas/métodos conceituais e concretos de 
organizar dados para armazenamento e 
manipulação EFICIENTES
● Empregos dessas estruturas de dados no projeto de 
algoritmos eficientes
dibio@unb.br
Requisitos para um bom 
software/programa
● Projeto claro, objetivo
● Fácil manutenção (comentários, modular)
● Confiável (sem erros)
● Fácil para usar (mnemônicos)
● Algoritmos rápidos
● ESTRUTURAS DE DADOS EFICIENTES
● ALGORITMOS EFICIENTES
dibio@unb.br
O que vocês aprenderão?
● Quais são algumas das estruturas de dados comuns
● Quais são algumas maneiras de implementá-las
● Como avaliar a eficiência das mesmas
● Como usá-las para resolver problemas 
interessantes
dibio@unb.br
Material/método indispensável
● Bons livros para ler e entender (ver referências e ir 
a BCE – UnB, ou web)
● Laboratório de programação em C (LINF, linux, 
gcc), praticar e aplicar em projetos
● Aulas e resolução de tarefas 
dibio@unb.br
Professor: Díbio
● CIC (sala ?, módulo 18 ICC)
● dibio at unb.br (correio eletrônico)
dibio@unb.br
Roteiro
● Apresentações e agenda do curso
● Como estudar?
● Papéis em nossa jornada de aprendizagem
● Horários de laboratório
● Afinal, o que é computação?
● O que seria computável?
● Métodos para resolução de problemas, 
computáveis...
● Dados simples, compostos
dibio@unb.br
Agenda do curso (onde? o quê? 
como? e agora?)
● Encontros: 
 2a. e 4a. Aula Expositiva/Provocações 
 LINF (Definir horário com
 atendimento) 
● Avaliação: Presença => 75% 
 Trabalhos Práticos (Prog.C) = 6 
 Provas Escritas = 3
dibio@unb.br
Agenda do curso (onde? o quê? 
quando? como? e agora?)
● Datas para lembrar: 
 
 Provas escritas (28/09) (16/11) (14/12) 
 
 
Trabalhos práticos (04/09) (25/09) (23/10) 
 (06/11) (27/11) (11/12) 
 obs: domingos 
dibio@unb.br
Algoritmo da nota final
Exames={Emaior, Emeio, Emenor} Trabalhos={T1, T2, T3, T4, T5, T6} 
 
 MEx = (1.25xEmaior + 1.0xEmeio + 0.75xEmenor)/3
 Mtr = (T1+T2+T3+T4+T5+T6)/6 
SE (MEx => 5.0 E Mtr => 5.0)
 ENTÃO 
Mfinal = 0.75xMex + 0.25xMtr
 SENÃO 
Mfinal = (Menor valor entre MEx e Mtr)
dibio@unb.br
Referências Bibliográficas
● CORMEN, T. H. et al. Introduction to algorithms. 2nd ed. 
Cambridge: MIT Press, 2001.
● SEDGEWICK, R. Algorithms in C (Parts 1-4, Part 5), 2nd 
ed., Addison Wesley, EUA, 1997.
● RANGEL, J.; CERQUEIRA, R.& CELES, W. Estruturas 
de dados: uma introdução com técnica de programação 
em C, Elsevier Brasil, RJ, 2004.
● TENENBAUM,A.; LANGSAM, Y. & AUGENSTEIN, 
M. Estruturas de dados usando C, Makron Books, SP, 
1995.
● ZIVIANI, N. Projeto de Algoritmos: com implementações 
em Pascal e C, 2a. ed., Thompson, SP, 2007.
dibio@unb.br
Referências Bibliográficas
● DEITEL, Harvey M.; DEITEL, Paul J.. Como programar 
em C. 2. ed. Rio de Janeiro: LTC, c1994.
● KERNIGHAM, B. & RITCHIE,D. The C Programming 
Language, Prentice-Hall, EUA, 1988.
● SCHILDT, Herbert. C completo e total. São Paulo: 
Makron, 1991. 
dibio@unb.br
Referências Bibliográficas
● + notas de aula;
● material disponível na internet (obs: “links” 
disponibilizados no ambiente do curso (moodle));
● outros livros sobre o assunto disponíveis na BCE.
dibio@unb.br
Ferramentas para o laboratório
● Ambiente linux (ubuntu, redhat, slackware, ...)
● Editor de programas (gedit, kwrite, emacs, 
codeblocks)
● Compilador (gcc, versão 4.1 ou acima)
● Depurador (xgdb)
● Obs: todos os softwares são de domínio público, 
gratuitos, e cópias podem ser instaladas em 
computadores pessoais. 
 
dibio@unb.br
Inscrição no ambiente “moodle”
● Todos os alunos devem se cadastrar no ambiente 
“moodle” do -aprender- para acesso e entrega dos 
trabalhos, bem como de acompanhamento das 
atividades do curso.
● Como?
– 1) tenha um conta de correio eletrônico pessoal (e.g. 
www.hotmail.com, www.yahoo.com.br, 
www.gmail.com, e outros)
– 2) Acesse http://aprender.unb.br/
dibio@unb.br
Inscrição no ambiente “moodle”
– 3) Após o preenchimento da inscrição, acesse 
http://aprender.unb.br/ e faça as opções:
● Depto. de Ciência da Computação
● 116319 Estruturas de Dados – Turma E
● O sistema pedirá um código de acesso à disciplina, que é: 
ed-20112
●
● Fazer sua inscrição o quanto ANTES 
dibio@unb.br
Como estudar?
● Problemas contextualizados;
● Objetivo é resolvê-los, estabelecendo um processo 
contínuo (com sucessivos refinamentos) de 
aprendizagem;
● Questionamentos e uso de ferramentas (leitura, 
exercícios) reforçam caminhos;
● 1) Problematizar
● 2) Questionar e Praticar
● 3) Refinamentos
dibio@unb.br
Como aprender?
dibio@unb.br
Como aprender?
● Necessário ter: MOTIVAÇÃO
 CURIOSIDADE
● RESOLVER PROBLEMAS (PENSAR 
ATIVAMENTE), transformando informação em 
conhecimento próprio
● FASES: Apreende, Conceitualiza, Aplica
● SEJA PRÓ-ATIVO(A) e CRIATIVO(A)!
dibio@unb.br
Ensinar/aprender
"My intention is not, however, to [simply] impart 
information, but to throw the burden of study upon 
you. If I succeed in teaching you to observe, my 
aim will be attained." Louis Aggasiz [1807-1873], 
Swiss-American Scientist.
dibio@unb.br
Ao estudar...
● O importante é interpretação e análise, pois o 
objetivo é ficar apto a resolver problemas.
● Perguntem-se, estabeleçam conexões, leiam muito 
e tentem resolver exercícios frequentemente.
● Não deixem assuntos, dúvidas se acumularem.
● ORGANIZAÇÃO + CRIATIVIDADE
dibio@unb.br
Um processo de aprendizagem 
proposto
Problematizar (Aulas)
Questionar e Praticar (Leitura e Exercícios)
Refinamentos (Realimentação e Avaliação)
dibio@unb.br
Papéis (funções) no processo de 
aprendizagem
● Professor = Orientador (Propõe problemas, indica 
caminhos, realimenta, avalia)
● Estudante = Ativo participante (não somente 
ouvinte), busca soluções, lê e pratica fora da sala 
de aula, dispõe-se a resolver problemas 
independentemente.
dibio@unb.br
Afinal, o que é computação?
● Máquinas para computar
● O imaginário e o computador
● Esquema e componentes típicos de um 
computadordibio@unb.br
“Yes, I share your concern: how to program well —though a 
teachable topic— is hardly taught. The situation is similar 
to that in mathematics, where the explicit curriculum is 
confined to mathematical results; how to do mathematics 
is something the student must absorb by osmosis, so to 
speak. One reason for preferring symbol-manipulating, 
calculating arguments is that their design is much better 
teachable than the design of verbal/pictorial arguments. 
Large-scale introduction of courses on such calculational 
methodology, however, would encounter unsurmountable 
political problems.” Edsger Dijkstra (2000)
dibio@unb.br
O imaginário e o computador
dibio@unb.br
O imaginário e o computador
dibio@unb.br
Na verdade, sistema típico...
dibio@unb.br
Memória, endereços, instruções
dibio@unb.br
Exemplos
● Estão em toda parte (automóveis, celulares, 
aparelhos de tevê, eletrodomésticos, trânsito, 
telecomunicações, bancos, bolsas de valores, 
hospitais, fábricas, escolas, corpo 
humano(próteses eletrônicas), aviões, espaço, etc)
dibio@unb.br
Processo computacional
Entrada
Saída
Algoritmo (sequência precisa de atividades
a serem executadas, e que transformam o conjunto de entrada 
na saída desejada)
dibio@unb.br
O que seria computável?
● Processos com algoritmos conhecidos, os quais 
param (terminam) em tempo finito.
● Buscamos então descobrir, estudar, analisar 
ALGORITMOS, para resolver problemas, e 
depois transferir as soluções (algoritmos) para que 
o computador faça de maneira diligente e 
repetitiva
dibio@unb.br
Métodos para resolução de 
problemas, computáveis...
● ESTRUTURAR (expressões, instruções, 
procedimentos (funções) independentes)
● “Dividir e conquistar”, refinamentos sucessivos a 
partir do ciclo (entrada, solução, saída) buscando 
com que partes (procedimentos) repetitivas sejam 
identificadas e isoladas;
● O mesmo conjunto de instruções, na mesma 
ordem, deve produzir sempre a mesma saída a 
partir de entradas iguais. 
dibio@unb.br
Dados simples
● Dados numéricos (e.g. inteiro, real)
● Dados simbólicos (e.g. caracteres)
dibio@unb.br
Dados Compostos
● Homogêneos (e.g. vetor, matriz, cadeia de 
caracteres (“string”))
● Não necessariamente homogêneo (e.g. Estrutura)
● Conjuntos, formas de inclusão, acesso, 
organização, algoritmos eficientes para uso em 
conjuntos e organizações diversas. (e.g. 
Sequências, prioridade, hierárquicos, fluxos) 
dibio@unb.br
Problemas a lidar
● Como compactar imagens? Dados heterogêneos
● Como acessar, processar esses dados?
● Como organizar prioridade em acesso, processos, 
fluxos?
● Como comparar grande quantidade de dados?
● Como representar e processar jogos, estratégias, 
processos em automação?
dibio@unb.br
Aprender
"The important thing is not to stop questioning. 
Curiosity has its own reason for existing. One 
cannot help but be in awe when he [or she!] 
contemplates the mysteries of eternity, of life, of 
the marvelous structures of reality. It is enough if 
one tries merely to comprehend a little of this 
mystery every day. Never lose a holy curiosity." 
(Albert Einstein [1879-1955]) 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40