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:
11x
11y
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))
