Árvore binária
SISTEMAS DE INFORMAÇÃO
Árvore binária
 Conceito

Uma árvore binária, ou binary tree, é um tipo
de estrutura de dados, formados por Nós (ou
células), que satisfazem algumas condições.
Árvore binária
Árvore binária
 Árvore Binária T é um conjunto finito de elementos
denominados nós ou vértices, tal que:

T = 0 e a árvore é dita vazia ou

Existe um nó r, chamado raiz de T, e os nós
restantes podem ser divididos em dois
subconjuntos disjuntos, que são as sub-árvores
esquerda e direita de r, respectivamente e as
quais, por sua vez, também são árvores binárias.
Árvore binária
 Conceito

Uma árvore é composta por um nó raiz e suas
sub-árvores (esquerda e direita).

Cada nó pode conter diversas informações
representadas por uma estrutura.
Arvore T
Sub-Arvore
Sub-Arvore
RAIZ
Árvore binária
Termos





Nós são todos os itens guardados na árvore.
Raiz é o item do topo da árvore (neste caso, o
número 50).
Filhos são os itens logo abaixo da raiz, 30 e
90 e assim sequencialmente. Por exemplo, o
20 é filho do 30.
Parentes são os nós do mesmo nível. Por
exemplo, o 90 é parente do 30.
Folha é um nó que não tem filho, é o último
item da árvore. Por exemplo, 20, 40 e 100.
Árvore binária
 Vantagens


A árvore binária traz benefícios nas inserções,
remoções e principalmente nas buscas, pois
são inseridas em uma ordem previamente
definida.
Cada nó é composto por um núcleo (local que
armazena as informações) e por indicadores
esquerdo e direito, responsáveis por apontar
para as sub-árvores.
Árvore binária
Árvore binária
 Visualização da Árvore Binária usando
ponteiros
raiz
A
esq
dir
B
D
C
E
F
G
H
I
Árvore binária - Referências
 http://equipe.nce.ufrj.br/adriano/c/apostila/ar
vore.htm
Criptografia - Cifra de César
 Em criptografia, a Cifra de César é uma
das mais simples e conhecidas técnicas de
criptografia.


É um tipo de cifra de substituição em que
cada letra do texto é substituída por outra,
que se apresenta no alfabeto abaixo dela um
número fixo de vezes.
Por exemplo, com uma troca de 3 posições,
A seria substituído por D, B viraria E e assim
por diante.
Criptografia - Cifra de César
 A transformação pode ser representada
alinhando-se dois alfabetos;


o alfabeto normal
o alfabeto cifrado rotacionado à direita ou
esquerda com um número fixo de posições.

Por exemplo, aqui está uma cifra de César
usando uma rotação à esquerda de 3 posições
(o parâmetro de troca, 3 neste caso, é usado
como chave e deve ser transmitido por um
canal seguro).
Criptografia - Cifra de César

Para criptografar uma mensagem, simplesmente observe
cada letra da mensagem na linha "Normal" e escreva a letra
correspondente da linha "Cifrado". Para decriptografar, faça o
contrário.
Criptografia - Cifra de César
 Decifrando um código

Para decifrar um código é necessário saber
a chave a ser usada, a partir de então,
aplica-se o processo contrário.
Criptografia - Cifra de César
 Decifrando um código

Cifra de César pode ser facilmente decifrada
mesmo num cenário em que se tenha
apenas o texto cifrado.

Duas situações podem ser consideradas:


1) o interceptador conhece (ou adivinha) que algum
tipo de cifra de substituição simples foi usada, mas
não especificamente que é um código de César; e
2) o atacante sabe que a cifra de César foi usada,
mas não sabe o valor de troca.
Criptografia - Cifra de César

TRABALHO





Desenvolva um programa em C que receba um
número chave (indica a quantidade de posições) do
usuário. Seu programa deverá permitir a codificação
de uma mensagem , e ou a decodificação.
DICA: argc e argv.
Linha de comando:

Codificar “Unipac Araguari” 3 => xqlsdf dudjxdul

Decodificar “xqlsdf dudjxdul” 3 => Unipac Araguari
Data entrega: Quinta (dia 25/06) e sábado
(27/06/2009)
Valor 5 pts - Individual. (trabalhos iguais – 0 zero
para os dois)
Criptografia - Cifra de César
 Desafio (5pontos)

Desenvolva um programa que tente
decodificar um texto sem ter o conhecimento
da chave (simplesmente do texto).

Dica:



Algoritmo força bruta
Análise de frequencia
O aluno que fizer e apresentar,
individualmente 100% do trabalho poderá
retirar da prova 5 pontos, caso contrario, a
prova valerá o seu valor normal.
Criptografia - Cifra de César
 Avaliação

Data 02/07/2009

Material

Estruturas de dados
 Lista
 Pilha
 Fila
 Arvore binária
 Cifra de Cesar