1IntroducaoED

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

SEM0543 – Organização de Dados em 
Computadores
Introdução
Objetivo:
Prover o aluno de graduação com conceitos 
básicos de estruturas de dados e da teoria de 
bancos de dados.
2
Ementa
 Estruturas de Dados: lineares, árvores e grafos. 
 Estruturas de Dados: sistemas de arquivos e 
métodos de acesso. 
 Sistemas de bancos de dados. 
 Sistemas de gerenciamento de banco de dados: 
recuperação de falhas, controle de concorrência. 
Banco de dados orientado a objetos
3
Bibliografia
Algoritmo:
CORMEN, T.H.; LEISERSON, C. E. RIVEST, R. L. 
STEIN, C. Algoritmos: Teoria e Prática. 2ª edição, 
São Paulo: Campus, 2002. 
ZIVIANI, N. Projeto de Algoritmos: com 
implementações em Pascal e C., 2ed., Pioneira 
Thomson Learning, 2004.
Linguagens:
KERNIGHAN, B. W.; RITCHIE, D. M. C A Linguagem 
de Programação Padrão ANSI. 2ª edição, São 
Paulo: Campus, 1989.
4
Bibliografia (cont.)
Estrutura de Dados:
VELOSO, P. Estrutura de Dados. Editora Campus, 
1986. 
TENENBAUM, A. M.; LANGSAM, Y.; AUGENSTEIN, 
M. J.; Estruturas de Dados Usando C. São Paulo: 
Pearson Makron Books, 2004. 
WIRTH, N. Algoritmos e Estruturas de Dados, 
Prentice Hall, 1986. 
5
Bibliografia (cont.)
Banco de Dados:
DATE, C. J. Introdução a Sistemas de Banco de 
Dados. : Campus, 1990. 
ELMASRI, R; NAVATHE, S. B. Sistemas de Banco 
de Dados, 4ª edição, São Paulo: Pearson –
Addison Wesley, 2005.
SILBERSCHATZ, A.; KORTH, H. F.; SUDARSHAN, S. 
Sistema de Banco de Dados. 3ª edição, São 
Paulo: Makron Books, 1999.
6
Bibliografia (cont.)
Organização de Computadores:
HWANG, K. Advanced Computer Architecture: 
Paralelism, Scalability, Programmability.: 
McGraw-Hill, 1993. 
MONTEIRO, M. A. Introdução à Organização de 
Computadores. : Livros Técnicos e 
Científicos(LTC), 1995. 
TANEMBAUM, A. S. Organização Estruturada de 
Computadores. : Prentice-Hall, 1992. 
7
Recursos
Editor e compilador C e C++ gratuito:
DevC++ (Bloodshed): 
http://www.bloodshed.net/devcpp.html
SGBD de uso livre (acadêmico ou 
desenvolvimento):
MySQL: http://www.mysql.com/
Manual de Referência do MySQL:
http://dev.mysql.com/doc/
8
Planejamento Detalhado
Estruturas de Dados
Algoritmos, estruturas simples
Tipos de dados: primitivos e estruturados
Estruturas estáticas: arrays e matrizes
Estruturas dinâmicas: listas simplesmente e 
duplamente encadeadas
Árvores
Conceito geral: árvores binárias e n-árias
Árvore Binária de Busca (ABB), Operações
9
Planejamento Detalhado (cont.)
Estruturas de Dados
Árvores
Árvores-B. Operações
Grafos
Conceito geral e componentes básicos
Dígrafos. Formas de representação
Algoritmos para busca em grafos
10
Planejamento Detalhado (cont.)
Sistema de arquivos
Conceitos de arquivos e armazenamento 
secundário
Organização do sistema de arquivos
Métodos de acesso a arquivos
Indexação: chaves primárias e secundárias
Árvores B+
Hashing
11
Planejamento – Ementa (cont.)
Sistemas de Banco de Dados
Sistemas gerenciadores de bancos de dados
Modelo Entidade-Relacionamento
Mapeamento do ME-R para o Modelo Relacional
Teoria do Processamento de Transações
Controle de concorrência e Sistema de recuperação
Banco de dados Orientado a Objetos
12
Avaliação, ver “handout”
Datas:
Prova: P1 (26/09/2011)
Prova: P2 (21/11/2011) toda matéria ministrada
Prova SUB SOMENTE para alunos que não 
puderam por motivos justificados fazer alguma 
das provas P1 ou P2
Prova: SUB (28/11/2011) toda matéria ministrada
Média Final = (P1+P2)/2
T – Exercícios práticos e trabalhos de laboratório 
(programação)
Algoritmos
Alan Turing (1912-1954)
Published On Computable Numbers, with 
an Application to the 
Entscheidungsproblem (1936)
Introduziu o Problema da Parada
Modelo Formal de computação
(conhecido como “Máquina de 
Turing”)
15
Máquina de Turing
A Máquina de Turing é um dispositivo 
teórico, conhecido como máquina 
universal, que foi concebido pelo 
matemático britânico Alan Turing (1912-
1954), muitos anos antes de existirem os 
modernos computadores digitais (o artigo 
de referência foi publicado em 1936).
Máquina de Turing Simples
. . .
Fita Infinita: Γ*
Cabeça da Fita: lê o corrente quadrado da fita, 
escreve no corrente quadrado,
move um quadrado; esquerda ou direita
MT: como Autômato Finito, exceto:
transições incluem direções (esq./dir.)
escrita na fita
CF: controle finito
Máquina de Turing: descrição formal
. . .
CF
7-tuple: (Q, , Γ, δ, q0,B F)
Q: conjunto finito de estados
: alfabeto de entrada (sem símbolo branco B)
Γ: alfabeto da fita, inclue  and B
δ: função de transição: Q  Γ Q  Γ  {L, R}
q0: estado inicial, q0  Q
F: conjunto de estados finais
18
MT - Exemplo
A função yxyxf ),(
é computável
Turing Machine:
Cadeia de entrada: yx0 unária
Cadeida de saída:
0xy unária
yx,
São inteiros
19
 0
0q
1 1 1 1
x y
1 
Início
Estado inicial
0: delimitador que separa os dois números
20
 0
0q
1 1 1 1
x y
1 
 0
fq
1 1
yx 
 11
Início
Fim
Estado Final
Estado Inicial
21
 0
fq
1 1
yx 
 11
Fim
Estado final
0: zero ajuda quando utilizado resultado
em outras operações
22
0q
MT para a função
1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11
yxyxf ),(
23
Exemplo de execução:
11x
11y
 0
0q
1 1 1 1
Time 0
x y
Resultado Final
 0
4q
1 1 1 1
yx 
(2)
(2)
24
 0
0q
1 1
Time 0 
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11
1 1
25

0q

0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11
01 11 1
Time 1
26
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11
 0
0q
1 1 1 1
Time 2
27
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

1q
1 11 11
Time 3
28
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

1q
1 1 1 11
Time 4
29
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

1q
1 11 11
Time 5
30
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

2q
1 1 1 11
Time 6
31
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

3q
1 11 01
Time 7
32
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

3q
1 1 1 01
Time 8
33
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

3q
1 11 01
Time 9
34
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

3q
1 1 1 01
Time 10
35
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

3q
1 11 01
Time 11
36
0q 1q 2
q
3q
L, L,01
L,11
R,
R,10
R,11
4q
R,11

4q
1 1 1 01
HALT & accept
Time 12
Tese de Church-Turing
“ A capacidade de computação representada
pela Máquina de Turing é o limite máximo que
pode ser atingido por qualquer dispositivo de 
computação”
Computabilidade Complexidade
Decidibilidade
Indecidibilidade
Intratável
Tratável
Resumindo
Decidibilidade
Tratável: “Decidível 
em uma quantidade 
razoável de tempo 
e espaço”
Indecidibilidade
40
Exercícios – 1
1) Descreva sobre Máquina
de Turing
2) Descreva sobre complexidade de algoritmos e tratabilidade
3) Descreva sobre Criptografia
4) Descreva sobre as seguintes máquinas: autômatos finitos, máquina
de Mealy e Moore.
5) Interprete a Tese de Church-Turing explicando-a.
Tópico adicional: Análise de Algoritmo: Faça uma pesquisa 
bibliográfica e defina com exemplos as seguintes notações: 
big-Oh  O(f(n)); big-Omega  (f(n)) ; big-Theta  (f(n)); 
little-oh  o(f(n)); little-omega  (f(n))