AEDS 3

Prévia do material em texto

MANIPULAÇÃO DE DADOS EM MEMÓRIA SECUNDÁRIA
Principais diferenças entre memória principal e memória secundária:
	Tipo
	MEMÓRIA PRINCIPAL
	MEMÓRIA SECUNDÁRIA
	Capacidade de Armazenamento
	Menor
	Maior
	Velocidade
	Maior
	Menor
	Tipo de Armazenamento
	Livre
	Arquivos
Tipos de memórias:
· Memória primária ou principal – memória de alta velocidade para armazenamento de programas e dados em uso pelo computador. São memórias com tempo de acesso muito baixo, mas com custo por byte relativamente alto. A memória RAM é o principal exemplo de memória primária. Na maioria das vezes são memórias voláteis (que se apagam quando a máquina é desligada).
· Memória secundária – memória utilizada para armazenar grandes volumes de dados que não são comportados na memória principal ou em que a relação custo/benefício não é vantajosa. É, portanto, significativamente mais lenta, mas também mais barata que a memória primária. Programas e dados que não estão em uso imediato pelo computador, mas que devem estar facilmente acessíveis também são armazenados em memória secundária. O disco rígido é o tipo de memória secundária mais usual nos dias de hoje.
· Memória terciária – memória utilizada para armazenar gigantescos volumes de dados, quando o tempo de acesso não é um fator crítico. Exemplos de memórias terciárias são as jukeboxes de CDs ou DVDs e os silos robotizados de fitas. A memória terciária também é utilizada para fins de cópias de segurança (backups).
Quando um determinado sistema requer o acesso e/ou a manipulação de um grande volume de dados, que não cabem na memória primária, ele deve usar uma memória secundária, como o disco rígido, para armazenamento desses dados.
Salvar dados em blocos e sequencialmente ganha tempo no processamento devido a forma como o disco rígido trabalha.
FLUXO DE ENTRADA E SAÍDA DE DADOS
· A escrita de dados em um arquivo do disco rígido é um fluxo de saída.
· A leitura de dados em um arquivo do disco rígido é um fluxo de entrada.
Observe que o fluxo é observado pela perspectiva do programa e ocorre de forma unilateral
ARQUIVOS COMO VETORES DE BYTES
Qualquer informação que desejamos escrever em um arquivo deve ser convertida em bytes. Um arquivo é apenas uma sequência de bytes, sendo o programa o responsável por entender o que essa sequência significa e como tratá-la.
Um “ponteiro” dentro do programa, define em qual posição será lido ou escrito um byte. Esse ponteiro segue sequencialmente.
Existem algumas regras para ler a sequência de bytes e entender o que ela significa. Essas regras variam de acordo com o sistema operacional e o sistema de codificação.
Normalmente o tamanho de cada arquivo é predefinido por padrão, aviso antecipado (a string tem 5 caracteres) ou final (Lucia\0). 
Strings têm identificadores que as antecedem explicando quantos caracteres tem, sendo aqueles acentuados contados como 2 caracteres. Outra possibilidade é ter um delimitador no final da string que diz quando ela acaba. 
A sequência de bytes de uma struct é chamada de registro em um arquivo.
ARQUIVOS DE DADOS ESTRUTURADOS
Arquivos de dados estruturados são arquivos que têm uma estrutura definida. Normalmente são conjuntos de entidades com a mesma estrutura definida.
· Uma entidade é uma coisa ou objeto do mundo real, que pode ser físico (ex.: pessoa, carro, produto, ...) ou abstrato (ex.: evento, cargo, matrícula, ...).
· Um atributo é uma propriedade que ajuda a descrever uma entidade. Por exemplo, se a entidade representar um funcionário, então os atributos podem ser: nome, data de nascimento, endereço, telefone e email; se a entidade representar um evento, então os atributos podem ser: descrição, data, horário, local e observações.
· Um registro é uma sequência de bytes em um arquivo que contém/representa uma entidade.
· Um campo é uma parte do registro, também na forma de uma sequência de bytes, que contém um atributo da entidade.
SERIALIZAÇÃO
Trata-se da transformação de uma entidade ou atributo em um registro ou campo.
· Existem alguns atributos que são considerados como falsos números. Isso acontece quando o número ou a sequência é dada para o propósito de identificação, sem ter qualquer relação com o seu subsequente ou antecessor. Como por exemplo o CPF, o RG, número telefônico, etc. Esse tipo de atributo é aconselhável guardar em formato string e não int, por ocupar menos espaço. 
· Caracteres podem ser substituídos por bytes, uma vez que cada número representa uma letra dentro da programação. Isso é util quando o objetivo é poupar espaço e o usuário só vai utilizar um char.
· O formato Char normalmente usa-se 2 bytes por caractere, mas quando se trata de string, cada caractere usa apenas 1 byte.
O espaço utilizado na serialização segue a tabela:
	Tipo
	Descrição
	Valores
	byte
	Número inteiro de 8 bits com sinal
	-128 a 127
	short
	Número inteiro de 16 bits com sinal
	-32.768 a +32.767
	int
	Número inteiro de 32 bits com sinal
	-2.147.483.648 a 2.147.483.647
	long
	Número inteiro de 64 bits com sinal
	-9.223.372.036.854.775.808 a +9.223.372.036.854.775.807
	float
	Número de ponto flutuante de 32 bits com sinal 
	±1,40129846e-45 a ±3,40282347e+38
	double
	Número de ponto flutuante de 64 bits com sinal 
	±4,94065645841246544e-324 a ±1,79769313486231570e+308
	char
	Caractere ASCII (1 byte) ou Unicode de 16 bits (2 bytes)
	Qualquer caractere
	boolean
	Variável lógica que indica falso ou verdadeiro (1 byte)
	true ou false
STRINGS DE TAMANHO FIXO
Algumas strings podem ter tamanhos pré determinados, como por exemplo o número de telefone, o cpf e atributos do tipo.
· Pode ser utilizado a estatística para determinar quantos caracteres é o provável de ser utilizado em algum atributo.
· Uma string de tamanho fixo sempre terá o mesmo tamanho.
STRING DE TAMANHO VARIÁVEL
As opções para utilizar strings de tamanho variável na serialização são:
· Utilizar 2 bytes com indicador de tamanho antes da string
	Ind de Tamanho
	C
	o
	n
	c
	e
	i
	ç
	ã
	o
	00
	0B
	43
	6F
	6E
	63
	65
	69
	C3
	A7
	C3
	A3
	6F
· Utilizar um delimitador no final da string
	C
	o
	n
	c
	e
	i
	ç
	ã
	o
	\n
	43
	6F
	6E
	63
	65
	69
	C3
	A7
	C3
	A3
	6F
	0A
	
SISTEMA DE CODIFICAÇÃO
Trata-se de uma tabela representativa do valor em bytes para cada símbolo. Alguns sistemas de codificação são:
· ASCII (1960) - American Standard Code for Information Interchange
Representação de 128 símbolos
65 = 0x41 = ‘A’
O 8º mais significativo era usando como bit de paridade.
Devido à falta de símbolos no sistema ASCII, foram criados sistemas complementares, que iniciavam a partir do 129. 
· Unicode - Sistema que abrange todas as línguas já criadas, inclusive línguas mortas e fictícias.
Mais de 100 mil símbolos
O unicode foi determinado como sistema de codificação universal, porém, existem 3 diferentes formatos:
· UTF-8 - Codificação Unicode de tamanho variável (1 a 4 bytes), que pode representar qualquer caractere (code point) do padrão. Padrão da internet e na Web.
· UTF-16 - Codificação de 2 ou 4 bytes, usada principalmente para escrita em idiomas de países asiáticos. (Quando usamos char, é utilizado essa codificação, por isso é usado 2 bytes).
· UTF-32 - Codificação de comprimento fixo 4 bytes.
A UTF-8 controla a quantidade de bytes através do primeiros bits, responsáveis por dizer quantos bytes serão utilizados.
1 Byte - Tabela ASCII
2 Bytes - Caracteres Latinos, hebraicos, gregos..
3 Bytes - Caracteres chineses, japoneses, coreanos…
4 Bytes - Outros caracteres e símbolos
REGISTROS
Os registros, assim como as entidades, podem ter tamanho fixo ou variável. A forma como isso é colocado em prática depende da programação.
Para trabalhar com registros de tamanho fixo temos as seguintes alternativas:
· Campo de tamanho fixo - Assim o espaço utilizado sempre será o mesmo. Como no caso dos números telefônicos e CPFs.
	ID
	NOME
	PREÇO
	1
	G
	E
	L
	A
	D
	E
	I
	R
	A
	2750,00
	2
	P
	I
	A
	‘ ‘
	‘ ‘
	 ‘ ‘
	 ‘ ‘
	 ‘ ‘
	 ‘ ‘
	395,00
	3
	V
	A
	S
	O
	‘ ‘
	‘ ‘
	‘ ‘
	‘ ‘
	 ‘ ‘
	400,004 Bytes
	9 Bytes
	4 Bytes
· Registros de tamanho fixo com campos de tamanho variável - Trata-se de um registro com tamanho máximo onde os campos preenchem os espaços vazios de outros campos de mesmo tipo.
	ID
	NOME
	PREÇO
	1
	L
	I
	V
	R
	O
	\
	A
	U
	T
	O
	R
	' '
	' '
	2750,00
	2
	E
	X
	E
	M
	P
	L
	O
	\
	A
	U
	T
	O
	R
	395,00
	3
	G
	O
	S
	T
	\
	M
	I
	A
	' '
	' '
	' '
	' '
	' '
	400,00
	4 Bytes
	9 Bytes
	4 Bytes
Para registros de tamanho variável temos as alternativas:
· A quantidade de campos sendo fixo e sempre na mesma ordem. Ex: Id, nome, e-mail; Id, nome, e-mail.
· Leitura/escrita dos campos em ordem pré determinada. 
· Indicador de tamanho do registro.
· Uso de delimitador de registro.
CABEÇALHO DE ARQUIVO
É o número utilizado para identificar quantos registros terão no arquivo.
	CABEÇALHO
	
	
	
	3
	1
	5
	L
	I
	V
	R
	O
	5
	A
	U
	T
	O
	R
	2750,00
	2
	
	7
	E
	X
	E
	M
	P
	L
	O
	5
	A
	U
	T
	O
	R
	395,00
	
	3
	4
	G
	O
	S
	T
	3
	M
	I
	A
	400,00
	
	
	
ACESSO AOS REGISTROS
Para encontrar um registro específico é necessário passar por um tipo de acesso. Esse acesso normalmente utiliza a chave de ordenação para encontrar um registro específico. A chave de ordenação pode ser qualquer coisa utilizada para ordenar os demais registros. 
IDENTIFICADORES
As chaves de ordenação podem ser divididas em dois tipos:
· Chaves candidatas 
São os meios de identificar determinado indivíduo ou objeto. Como CPF para pessoas, chassi para carros, nome do livro mais do autor para livros, ID e etc.
· Chaves Primárias
É a chave candidata escolhida.
Alguns problemas de chaves candidatas:
· Nome - Algumas pessoas tem o mesmo nome e algumas podem mudá-lo.
· E-mail - Pessoas trocam o e-mail.
· Telefone - São reutilizados
· CPF e CNPJ - Muito longos
Sendo assim, a melhor alternativa normalmente é utilizar identificadores(ID) próprios do sistema, pois não são longos, não podem ser reutilizados, não tem significado e são sequenciais.
O ID é uma informação interna do sistema, utilizado em buscas internas. Mas externamente o usuário utiliza atributos do objeto.
ARQUIVOS SEQUENCIAIS
Em arquivos sequenciais os registros são acessados de forma sequencial, na ordem em que foram armazenados.
· Normalmente usado quando há poucas ou nenhuma movimentação de registros
· O objetivo é o acesso rápido a um conjunto de registros.
· Não são bons para acesso aleatório.
Alguns tipos de chave de ordenação nos arquivos sequenciais são:
· Data de criação
· Chave primária - Atributo que serve para identificar de forma exclusiva. Como ID.
· Qualquer outra ordem
· Nenhuma ordem
Observações:
· O arquivo eventualmente precisará ser reordenado.
· Arquivos sequenciais são geralmente usados como arquivos temporários. Como por exemplo relatórios
IDs são números sequenciais, exclusivos, não significativos e não reusáveis;
IDs são usados nas relações internas entre as entidades e não devem precisar ser conhecidos ou memorizados pelos usuário; 
A busca por entidades deve continuar sendo feita por valores do mundo real (nomes, emails, placas, títulos, etc.).
Os metadados do arquivo, inclusive o último ID usado, podem ser mantidos no cabeçalho do próprio arquivo.
.
OPERAÇÕES EM ARQUIVOS SEQUENCIAIS - CRUD
O que é passado para fazer as operações:
· ID ⬅ arquivo.create(novo.objeto)
· Objeto ⬅ arquivo.read(ID/CPF/chaves)
· ok ⬅arquivo.update(objeto.atualizado)
· ok ⬅ arquivo.delete(ID/CPF/chaves)
Durante a exclusão do arquivo não faz sentido excluí-lo de fato, pois dessa forma teríamos que reformular todos os registros o que demanda muito tempo. A melhor forma de tratá-lo é colocando uma lápide (marca de exclusão) nele. Essa lápide pode ser usada para uma recuperação de dados ou usada para transcrever algum outro registro por cima. Os registros só são realmente apagados quando há uma reordenação.
Na tabela abaixo é utilizado um byte como lápide, onde o espaço em branco significa que o registro não foi apagado e o asterisco que o registro foi apagado. Nesse caso o registro de ID 3 foi apagado.
	/
	
	
	
	3
	' '
	1
	5
	L
	I
	V
	R
	O
	5
	A
	U
	T
	O
	R
	2750,00
	' '
	2
	7
	E
	X
	E
	M
	P
	L
	O
	5
	
	A
	U
	T
	O
	R
	395,00
	' * '
	3
	4
	G
	O
	S
	T
	3
	M
	I
	A
	400,00
	
	
	
	
	
	
	
	
	
	
Para criar arquivos quando não tem ordem específica, todo novo registro é colocado no fim do arquivo. Quando há ordem, é preciso uma reordenação.
01: algoritmo create(objeto)
02: mover o ponteiro para início do arquivo (cabeçalho)
03: ler quantos registros existem através do cabeçalho
04: atribuir objeto.ID ← últimoID + 1
05: mover o ponteiro para início do arquivo
06: escrever objeto.ID no cabeçalho (numero max de registros)
07: criar registro para o objeto
08: mover para o fim do arquivo
09: escrever registro
10: fim-algoritmo
read (de uma única entidade)
01: algoritmo read(ID)
02: mover o ponteiro para o primeiro registro (após o cabeçalho)
03: enquanto não atingir o fim do arquivo
04: ler próximo registro
05: se registro.lapide ≠ '*'
06: então extrair objeto do registro
07: se objeto.ID = ID
08: então retornar objeto e terminar
09: fim-se
10: fim-se
11: fim-enquanto
12: retornar objeto vazio // null
13: fim-algoritmo
read (de um conjunto de entidades)
01: algoritmo read(critérios)
02: criar conjunto vazio
03: mover o ponteiro para o primeiro registro (após o cabeçalho)
04: enquanto não atingir o fim do arquivo
05: ler próximo registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro
08: se registro atender aos critérios
09: então adicionar objeto ao conjunto
10: fim-se
11: fim-se
12: fim-enquanto
13: retornar conjunto 
14: fim-algoritmo
Upudate
Quando atualizamos um arquivo, devemos primeiro verificar se o espaço do registro cabe o novo arquivo atualizado. Caso caiba, não há problema. Se sobrar, deixamos os bytes de sobra como lixo sem alterar o tamanho do arquivo. Caso não caiba, marcamos o arquivo como excluído e criamos outro no final com o mesmo ID.
01: algoritmo update(novoObjeto)
02: mover para o primeiro registro do arquivo (após cabeçalho)
03: enquanto não atingir o fim do arquivo
04: pos ← posição do ponteiro
05: ler próximo registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro
08: se objeto.ID = novoObjeto.ID
09: então criar novoRegistro para novoObjeto
10: se novoRegistro.tamanho ⩽ registro.tamanho
11: então mover para pos
12: escrever novoRegistro mantendo ind.tam.
13: senão mover para pos
14: escrever lápide como excluído
15: mover para fim do arquivo
16: escrever novoRegistro
17: fim-se
18: retornar verdadeiro e terminar
19: fim-se
20: fim-se
21: fim-enquanto
22: retornar falso
23: fim-algoritmo
delete
01: algoritmo delete(ID)
02: mover o ponteiro para o primeiro registro (após o cabeçalho)
03: enquanto não atingir o fim do arquivo
04: pos ← posição do ponteiro
05: ler próximo registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro
08: se objeto.ID = ID
09: então mover para pos
10: escrever lápide como excluído
11: retornar verdadeiro e terminar
12: fim-se
13: fim-se
14: fim-enquanto
15: retornar falso
16: fim-algoritmo
 ORDENAÇÃO EXTERNA
· É o processo de ordenação de dados em arquivos.
· Adotado quando os dados são muito grandes para se trabalhar na memória principal.
· Prioriza o acesso sequencial aos arquivos.
INTERCALAÇÃO BALANCEADA
· É o algoritmo que ordena os registros por meio da intercalação de registros de várias fontes balanceadas (arquivos temporários com tamanho aproximado). Como se o arquivo fosse dividido em vários outrosarquivos de tamanho semelhante onde o algoritmo ordena esses arquivos na ordem apropriada.
A intercalação balanceada de M caminhos é um algoritmo de intercalação que opera com arquivos temporários. Os dados são extraídos do arquivo principal em blocos que podem ser ordenados em memória principal. Em seguida esses blocos são escritos nos arquivos temporários. Como geralmente haverá muito mais blocos do que arquivos temporários, cada arquivo temporário conterá uma fila desses blocos como, por exemplo:
Arquivo_temporário_1: B1 B4 B7 B10 ...
Arquivo_temporário_2: B2 B5 B8 B11 ...
Arquivo_temporário_3: B3 B6 B9 B12 ...
Para garantir uma boa distribuição dos blocos, eles são escritos alternadamente entre os arquivos temporários.
Em seguida, toma-se um bloco de cada arquivo temporário gerando um segmento ordenado maior. Serão, assim, gerados vários segmentos ordenados que serão distribuídos por um segundo conjunto de arquivos temporários, também de forma balanceada:
Arquivo_temporário_4: S1 S4 S7 S10 ...
Arquivo_temporário_5: S2 S5 S8 S11 ...
Arquivo_temporário_6: S3 S6 S9 S12 ...
Nesse exemplo, o segmento S1 será composto pela intercalação dos blocos B1, B2 e B3; o segmento S2 será composto pela intercalação dos blocos B4, B5 e B6; e assim em diante. 
O processo se repete, com a intercalação de um segmento de cada arquivo temporário, gerando segmentos ainda maiores e escritos em um novo conjunto de arquivos temporários (o primeiro conjunto pode ser reaproveitado neste momento). 
As intercalações de segmentos ordenados nos arquivos temporários só se acabam quando restar apenas um único segmento ordenado contendo todos os dados. Ex:
Considere a seguir as chaves de ordenação de um arquivo original.
	Arq Inteiro
	28
	5
	40
	12
	2
	7
	1
	35
	30
	38
	22
	19
	13
	4
	11
	29
	6
	27
	33
	31
	8
	3
	25
	42
	44
	20
	41
	34
	18
	14
	10
Neste exemplo considere que cada bloco contém 4 registros e existem apenas dois arquivos temporários. Cada bloco é ordenado em memória principal e logo em seguida jogado no arquivo temporário. 
	Arq Temp 1
	5
	12
	28
	40
	19
	22
	30
	38
	6
	27
	31
	33
	20
	34
	41
	44
	Arq Temp 2
	1
	2
	7
	35
	4
	11
	13
	29
	3
	8
	25
	42
	10
	14
	18
	
Os primeiros blocos do Arquivo Temporário 1 e Arquivo Temporário 2 são ordenados em memória principal e jogado em um terceiro arquivo temporário de bloco de tamanho 8. E isso também acontece com os demais blocos.
	Arq Temp 3
	1
	2
	5
	7
	12
	28
	35
	40
	3
	6
	8
	25
	27
	31
	33
	42
	Arq Temp 4
	4
	11
	13
	19
	22
	29
	30
	38
	10
	14
	18
	20
	34
	41
	44
	
O mesmo acontece até que reste apenas um único arquivo.
	Arq Temp 5
	1
	2
	4
	5
	7
	11
	12
	13
	19
	22
	28
	29
	30
	35
	38
	40
	Arq Temp 6
	3
	6
	8
	10
	14
	18
	20
	25
	27
	31
	33
	34
	41
	42
	44
	Arq Final
	1
	2
	3
	4
	5
	7
	8
	10
	11
	12
	13
	14
	18
	19
	20
	22
	25
	27
	28
	29
	30
	31
	33
	34
	35
	38
	40
	41
	42
	44
A análise de complexidade do algoritmo de intercalação balanceada é baseada na quantidade de vezes que o programa precisa entrar na memória secundária para ler todos os registros. O tempo de ordenação na memória principal é desconsiderado devido ao fato de que o seu tempo de demora é insignificante quando comparado com o tempo necessário para acessar a memória secundária.
Sendo assim, o que observamos é o número de vezes que será preciso ler todos os registros.
Cálculo de complexidade:
· N = numero total de registros
· b = tamanho do bloco ordenado em memória principal
· m = quantidade de destinos usados na intercalação
De acordo com o ex anterior:
Passadas = 1 + [log2 (31/4)]
Passadas = 1 + [log2 8]
Passadas = 1 + 3 = 4
<> OTIMIZAÇÃO DO ALGORITMO <>
INTERCALAÇÃO COM SEGMENTOS DE TAMANHO VARIÁVEL
Quando geramos os blocos ordenados na fase de distribuição, pode ser que eles estejam ordenados entre si. Por exemplo, considere que os seguintes blocos foram gerados na fase de distribuição:
Arquivo_temporário_1: B1 B4 B7 B10 ...
Arquivo_temporário_2: B2 B5 B8 B11 ...
Arquivo_temporário_3: B3 B6 B9 B12 ...
Nesse caso, se todas as chaves do bloco B4 forem maiores que as chaves do bloco B1, podemos considerar que há um único segmento maior contendo os registros de B1 e B4. Nesse caso, a primeira intercalação deveria considerar a seguinte distribuição:
Arquivo_temporário_1: (B1+B4) B7 B10 ...
Arquivo_temporário_2: B2 B5 B8 B11 ...
Arquivo_temporário_3: B3 B6 B9 B12 ...
Ou seja, os registros do segmento (B1+B4) seriam intercalados com os registros dos blocos B2 e B3; os registros dos blocos B7, B5 e B6 seriam intercalados em seguida; e assim em diante.
Como nem todos os segmentos possuem chaves ordenadas entre si, dizemos que eles têm tamanho variável.
Finalmente, esperamos, ao trabalharmos com segmentos maiores, que o número de intercalações para a ordenação completa do arquivo seja menor.
Como podemos ver no exemplo acima, no momento em que o algoritmo começa a criar novos arquivos temporários, é feito uma comparação entre o último número do bloco com o seu posterior, verificando o seu tamanho. Se o número posterior for maior, essa comparação continua com os próximos números até que essa afirmação já não seja verdadeira. A partir desse momento que a comparação com outro bloco começa.
INTERCALAÇÃO COM SELEÇÃO POR SUBSTITUIÇÃO
A intercalação por substituição é utilizada no estágio de distribuição. Para aumentar a probabilidade dos arquivos já estarem ordenados em sentido crescente, utilizamos o que chamamos de HEAP de mínimo. Como podemos ver, o Heap aparenta com uma árvore binária, mas nesse caso o filho esquerdo não tem qualquer relação com o direito, não importando se é maior ou menor que seus pais. A única importância em um heap de mínimo é os pais serem menores que os filhos.
Também utilizamos as seguintes operações para encontra os filhos e os pais, sendo i substituído pela posição em questão:
Exemplo de utilização do Reap de mínimo em um arquivo:
· O número do segmento equivale a qual arquivo temporário se refere.
· Primeiramente inserimos as chaves no heap (no exemplo é de tamanho 7, mas quanto maior for o heap, melhor).
· Mudamos de número de segmentos quando a próxima chave a ser inserida é menor que a da raiz do heap.
Para organizamos o heap, é feita a seguinte operação: (n-1)/2 
Sendo n igual ao número da última posição. No exemplo, teríamos: (6-1)/2 = 2,5. Arredondamos para menor, logo teríamos 2. Assim, descobriremos os últimos pais do heap. Começamos comparando o pai de posição 2 com o filho da esquerda e depois da direita. Caso haja filhos menores que o pai, fazemos a troca. Em seguida comparamos o pai de posição 1, com o mesmo processo, até chegarmos ao pai de posição 0.
Em seguida, comparamos a raiz com a próxima chave, tiramos Caso a próxima chave seja maior, pegamos a raiz do heap e colocamos no primeiro arquivo temporário.
Depois inserimos a próxima chave no heap, organizamos o heap novamente, fazemos a comparação entre chave e raiz e mandamos a raiz, caso ela seja menor e a próxima chave, para o mesmo arquivo temporário.
Observe que a organização do heap é feita de cima para baixo.
Até então, a inserção dos arquivos ocorreu de forma cíclica. Mas se observarmos, a próxima chave é menor do que a raiz. Dessa forma mudamos o número do segmento para 1. Para que a nossa inserção e organização do heap continue a fazer sentido, temos que afundar todas as chaves de segmentos maiores para o fundo do heap, para que assim possamos continuar com a inserção no arquivo temporário de número 1. observe o exemplo:
Assim, continuamos a inserção até que todas as chaves com o número de segmento igual a 0 sejam inseridas. 
Continuamos o processo até o seguinte momento:
Iniciamos agora a inserção do segundo arquivo como fizemos como o primeiro. 
A ideia é entender que o número de segmentos é sempre mais importante que o número da chave, sendo assim, se o número de segmento é maior do que o número de seguimento do próximo iten, não importa se o número da chave é menor, ele continua sendo maior.
Uma últimaquestão de importância é que, quando acaba todos os elementos do vetor, temos que começar o processo de esvaziamento do heap, que ocorre da seguinte maneira:
Esvaziamos na seguinte ordem: 6 - 5 - 2 - 4 - 3 - 1 - 0
ARQUIVO INDEXADO
Um arquivo indexado é um arquivo que possui um ou mais índices que permitem o acesso aleatório a um registro, dada uma determinada chave.
ex: (Índice secundário denso direto)
Nesse exemplo, o ID dos arquivos se encontra fora de ordem, e por isso criamos um índice com apenas o ID e as posições do arquivo. Se procurarmos o ID no Índice, de forma sequencial, encontraremos a posição do arquivo desejado. O índice pode conter qualquer tipo de chave.
TIPOS DE ÍNDICE
· Primario ou Secundario
· Direto ou Indireto
· Denso ou Esparso
ÍNDICE PRIMÁRIO
Segue a mesma ordem do arquivo de dados. Utilizado quando a massa de dados é tão grande que a melhor opção é fazer a busca no índice para depois ir para o arquivo de dados.
ÍNDICE SECUNDÁRIO 
Não segue a mesma ordem do arquivo de dados
ÍNDICE DIRETO
Aponta diretamente para o endereço do registro
ÍNDICE INDIRETO
Aponta para um índice direto, normalmente baseado na chave primária (que por sua vez aponta para o arquivo de dados). Podemos ter vários índices indiretos apontando para um único índice direto. 
ÍNDICE DENSO
Todos os registros estão no índice
ÍNDICE ESPARSO 
Nem todos os registros se encontram no índice.
OPERAÇÃO EM ARQUIVO INDEXADO
Os seguintes códigos são exemplos de operações com arquivos indexados
create
01: algoritmo create(objeto)
02: mover o ponteiro para início do arquivo (cabeçalho)
03: ler últimoID
04: objeto.ID ← últimoID + 1
05: mover o ponteiro para início do arquivo
06: escrever objeto.ID
07: criar registro para o objeto
08: mover para o fim do arquivo
09: pos ← posição do ponteiro
10: escrever registro
11: inserir o par (objeto.ID, pos) no índice
12: fim-algoritmo
read (de uma única entidade)
01: algoritmo read(ID)
02: pos ← buscar o ID no índice
03: se pos ≠ -1
04: então mover o ponteiro para pos
05: ler registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro
08: retornar objeto e terminar
09: fim-se
10: fim-se
11: retornar objeto vazio // null
12: fim-algoritmo
update
01: algoritmo update(novoObjeto)
02: pos ← buscar o ID no índice
03: se pos ≠ -1
04: então mover o ponteiro para pos
05: ler registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro // para algum teste do objeto
08: criar novoRegistro para novoObjeto
09: se novoRegistro.tamanho ⩽ registro.tamanho
10: então mover para pos
11: escrever novoRegistro mantendo ind.tam.
12: senão mover para pos
13: escrever lápide como excluído
14: mover para fim do arquivo
15: pos ← posição do ponteiro
16: escrever novoRegistro
17: atualizar o endereço para o ID no índice
18: retornar verdadeiro e terminar
19: fim-se
20: fim-se
21: fim-se
22: retornar falso
23: fim-algoritmo
delete
01: algoritmo delete(ID)
02: pos ← buscar o ID no índice
03: se pos ≠ -1
04: então mover o ponteiro para pos
05: ler registro
06: se registro.lapide ≠ '*'
07: então extrair objeto do registro // para algum teste do objeto
08: mover para pos
09: escrever lápide como excluído
10: remover o ID do índice
11: retornar verdadeiro e terminar
12: fim-se
13: fim-se
14: retornar falso
15: fim-algoritmo
RELACIONAMENTOS
Trata-se da relação de uma estrutura a outra
TIPOS DE RELACIONAMENTOS
· Um para um (1:1)
Liga uma entidade de um tipo, para uma entidade de outro tipo
Ex: 1 Pessoa : 1 CNH
· Um para muitos (1:N)
Liga uma entidade de um tipo, para varias outras entidades de outro tipo.
Ex: 1 Casa : N moradores
· Muitos para muitos (N:N)
Liga varias entidades de um tipo para varias outras entidades de outro tipo.
Ex: Ator N : N filmes // Filme N : N Atores
ÁRVORE B
É semelhante a Árvore Binária, porém, possibilita que os nodos da árvore tenham mais de uma chave. 
Nesse exemplo, caso buscássemos a chave de número 10:
1. 29 = 10? Se não, 10 < 29?
2. Se sim, 8 = 10? Se não, 10 < 8?
3. Se não, 8 < 10 < 15 ?
4. Se sim 10 = 10?
5. Se sim, chave encontrada.
A ideia da árvore B é carregar da memória secundária uma página inteira, guardando-a na memória principal para manipulação ou leitura. Assim que terminado o uso dessa página, a memória primária descarrega toda essa informação e busca outra página até que as operações acabem. Dessa forma, diminuímos a quantidade de acessos a memória secundária.
O que significa Ordem da Árvore B? Existem duas definições
· A Ordem de uma Árvore B é o mínimo de chaves que cabem dentro de cada nodo/página (menos a raiz). No exemplo acima, a ordem seria 2. (Todas as páginas têm no mínimo 2 chaves, exceto a raiz).
· A Ordem de uma Árvore B é o número máximo de filhos que uma página pode ter. No exemplo acima, a ordem seria 5. (Cada página pode ter até 5 filhos. Obs: São as bolinhas). <= Mais usual
As regras da Árvore B são:
1. Cada página, exceto a raiz, deve ter pelo menos 50% de ocupação para menos.
2. Cada página deve ter o número de filhos igual ao seu número de chaves + 1 (exceto folhas porque não tem filhos).
3. Todas as folhas estão sempre no mesmo nível, pois a árvore cresce pra cima
ESTRUTURA DA ÁRVORE B EM BYTES
N - Número de elementos ocupados na árvore, sendo o máximo igual ao número de filhos -1Pi
Ci - Chave do registro
Di - Dados (Ex, endereço do registro do arquivo)
Pi - Ponteiro para o enésimo filho (São os ponteiros que apontam para os filhos da página, contendo o endereço das páginas subsequentes). Quando trata-se de folha, os ponteiros são nulos, normalmente preenchidos por zeros.
Ex:
Obss: O ponteiro da raiz indica em qual endereço está a raiz.
As árvores, para serem eficientes, adotam paginas de tamanho fixo.
INSERÇÃO EM UMA ÁRVORE B
1. Localize a folha em que a chave deve ser inserida;
2. Se a chave couber na folha, inseri a chave e termine;
3. Se não couber,
1. Crie uma nova folha;
2. Mova a metade superior das chaves para essa nova folha;
3. Se a chave a ser inserida for menor que a primeira chave da segunda (nova) folha,
1. Insira a nova chave na folha antiga (da esquerda);
2. Promova a maior chave dessa folha antiga, com o ponteiro direito para a nova folha;
4. Senão,
1. Insira a nova chave na nova folha (da direita);
2. Promova a menor chave dessa nova folha, com o ponteiro direito para a nova folha;
4. Se a chave promovida não couber na página pai, repita o algoritmo a partir do passo 2 acima.
Passo 1
Passo 3.1
Passo 3.2
Passo 3.3.1
Passo 3.3.2
REMOÇÃO EM UMA ÁRVORE B
A remoção em uma árvore B está sujeita a três casos diferentes:
1. Se o elemento estiver em uma folha e a folha tiver mais de 50% de ocupação, basta removê-lo
2. Se o elemento não estiver em uma folha, trocá-lo pelo seu antecessor e deletá-lo
3. Se a folha for ficar com menos de 50% de ocupação, mas a página irmã puder ceder uma chave, faça a redistribuição de chaves e delete a chave correspondente.
4. Se a folha ficar com menos de 50% de ocupação e as páginas irmãs não puderem ceder uma chave, é necessário fazer a fusão de duas folhas.
A seguir, os passos completos de uma remoção em árvore B:
ETAPA 1 - Remoção da chave em uma folha
1. Localize a chave a ser removida.
2. Se ela estiver em uma folha,
1. Então remova a chave.
2. Senão remova a chave e coloque em seu lugar a sua chave antecessora (descendente de maior valor da sub-árvore esquerda, que está em uma folha).Trate a exclusão como se fosse dessa chave antecessora em uma folha.
ETAPA 2 - Cessão de chave de alguma folha adjacente
3. Se a folha tiver ficado com menos de 50% de ocupação,
1. Então veja se a folha adjacente direita (se existente) pode ceder uma chave.
1. Se puder, faça a rotação.
2. Se não puder, veja se a folha adjacente esquerda (se existente) pode ceder uma chave.
1. Se puder, faça a rotação.
ETAPA 3 - Fusão
4. Se a folha ainda estiver com menos de 50% de ocupação e nenhuma folha adjacente puder ceder uma chave,
1. Se existir uma folha adjacente direita, faça a fusão entre as folhas.
2. Se não existir, faça a fusão com a folha adjacente esquerda.
5. Na fusão, a chave que divide as duas folhas deve ser demovida (descer para a folha resultante da fusão).
ETAPA 4 - Propagação
6. Se, após a fusão, a página pai ficar com menos de 50 de ocupação, voltar à ETAPA 2 considerando essa página.
7. As fusões podem ser propagadas até a raiz se necessário. Se a raiz tiver só dois filhos que precisarem ser fundidos, então a árvore terá sua altura reduzida.
ÁRVORE B+
A árvore B+ é utilizada quando a busca a ser feita tem como objetivo retornar uma sequência de chaves, e não apenas uma.
Funcionamento da Árvore B+:
· Todas as chaves válidas estão armazenadas nas folhas
Isso significa que as chaves antecessoras em nível são utilizadas apenas como objeto de comparação para assim criar um caminho mais fácil para as chaves necessárias.
· Cada folha aponta para a próxima folha, permitindo assim, um acesso sequencial
· As folhas podem possuir uma estrutura diferente das páginas não folhas, por serem as únicas páginas a carregar dados.
Enquanto os nodos podem carregar apenas um número em sua estrutura para direcionar a busca, as páginas folhas podem conter toda a estrutura de dados necessária ou parte dela.
Observe que no fim de cada folha existe um ponteiro apontando para a próxima e que como os números dos nodos não são realmente válidos, eles são duplicados. Na árvore B+ as únicas comparações feitas são:
1. A página é uma folha?
1.1. Se sim, a chave é igual ao número da folha?
	1. Retorna as chaves pedidas sequencialmente.
1.2 Se não, a chave é igual ao número à direita?
1.2.1 Se não, o processo é repetido até encontrar o número correspondente ou retornar -1.
2. Se não, a chave é menor que o número da folha? Se sim, desce pela direita, se não pela esquerda.
3. O processo é repetido até encontrar uma página folha.
A chave a ser copiada é sempre a menor do filho direito.
Há a opção de substituir o 10 pelo 12
TABELA HASH
· Algoritmo cuja o custo do acesso é igual O(1). 
· A ideia é ir diretamente ao recurso desejado.
· É muitas vezes utilizado como um índice que contém apenas endereços. 
· É utilizado uma função de dispersão para definir a posição das chaves de forma aleatória.
· A posição da chave deve ser multiplicada pelo tamanho do índice para conseguirmos identificar até qual posição vai o registro daquele índice.
· A função de dispersão pode ser qualquer função, mas vale considerar que quanto mais disperso for seus resultados, melhor a funcionalidade da tabela.
· Para encontrarmos determinada chave no arquivo, basta fazer a função de dispersão e ir no endereço resultante. Por exemplo, se quero a chave 1 e a função de dispersão é h(x) = 2x, basta fazer 1x2=2 e logo ir ao endereço 2 da tabela.
· Ex de função de disperção - [ h(x)=x^2 ] Após feito isso, pegamos o meio do número como resposta. 40^2=1600. Pegamos o número 60 por exemplo.
COLISÕES
Quando dois registros são mandados para o mesmo endereço, nós chamamos isso de colisão. Quando dois registros colidem, temos duas alternativas, usamos o encadeamento interno ou o encadeamento externo.
· Encadeamento Interno
	É quando colocamos o endereço em colisão no mesmo índice que os demais. Assim, se uma determinada posição está cheia, procuramos a próxima dentro do índice. Existem algumas formas cuja busca é feita.
Sondagem Linear - É quando buscamos de forma sequencial. Assim, se a posição 2 está cheia, buscamos na 3, e assim por diante. Outra observação importante é usar a lápide para elementos apagados. Pois nesse tipo de sondagem, quando buscamos algum elemento que foi vítima de colisão e o próximo endereço está vazio, isso significaria que esta chave não existe. 
	h(k,i) = [h(k) +i] mod n
	i = número de endereços saltados
n = numero máximo da tabela.
Sondagem Quadrática - ocorre quando elevamos o número das tentativas de busca ao quadro e então somamos ao endereço original, usando assim o endereço endereço resultante. Como exemplo, se a posição 2 está cheia, fazemos , e se a posição 3 estiver cheia, fazemos .
	
	i = número de endereços saltados
n = número máximo da tabela 
Duplo Hash - Calculamos a distância até a próxima posição a ser sondada através de uma segunda função hash.
	
	i = número de endereços saltados
n = número máximo da tabela
h’(k) = segunda função hash
· Encadeamento Externo
É a utilização de duas tabelas para o tratamento de dados. Dessa forma, no caso de colisão, usamos outra tabela para enviar a chave.
Área de Extensão - Quando ocorre colisão, criamos uma área de extensão para onde mandamos o arquivo colidido. Neste tratamento de dados, é necessário criar um elemento no registro que indique o próximo endereço a ser buscado no caso de colisões.
Lista Encadeada - Fazemos duas tabelas, uma apenas com indicador de endereço, chamada cabeça. Essa tabela só é responsável por indicar o endereço de uma outra. A outra tabela, contém a chave, o endereço da chave e quando há colisões, o "próximo" indica onde o número colidido foi parar. Essa tabela não precisa ser de tamanho, e por isso torna-se mais eficiente que as demais.
Buckets
Os Buckets são úteis quando buscamos mais de um registro. Dessa forma, cada endereço da tabela terá não apenas uma chave e um endereço, mas vários outros. 
O tratamento de colisão quando o bucket estiver cheio, pode ser dado da mesma forma que é feito com a tabela hash comum, adicionando assim um campo com um indicador, por exemplo. Uma observação é que a possibilidade de usar registros já preenchidos pela metade ou como no caso do registro de endereço 8 da imagem, é mais eficiente do que o uso de registros completamente vazios.
HASH EXTENSÍVEL
Trata-se de uma forma eficaz de aumentar o tamanho do índice sem que seja necessário realocar todas as chaves. 
Neste exemplo, observe que no hash extensível é necessário o uso de um segundo índice que funciona como ponteiro.
A letra p representa o nível de profundidade. Onde o p representa a profundidade global e o p’ a profundidade local. A profundidade global também indica a quantidade máxima de bits utilizados para definir a posição dos ponteiros. No caso do exemplo, apenas dois. Sendo assim, só é possível utilizar 4 ponteiros, indo do número 00 ao número 11.
No próximo caso, quando queremos adicionar a chave 20 ao bucket 0, percebemos que não há espaço. 
Nesse caso, o código deve comparar a profundidade local com a profundidade global, caso sejam iguais, significa que precisaremos estender o nosso Índice.
Ao estender o índice, perceba que os ponteiros dos endereços de 3 bits, continuam apontando para os mesmos ponteiros dos endereços de 2 bits. Após isso, o algoritmo deve de imediato criar outro bucket, separando os ponteiros do bucket em que tentamos colocar outra chave.
Dessa forma, como podemos ver, só precisamos re-alocar os endereços cuja foram afetados. Uma vez que a função hash seja , ao invés de 4 ficar na posição 0, teremos 4 mod 6 que vai dar 4. As outras posições continuaram no mesmo lugar, pois mesmo que , o ponteiro 4 do índice continua apontando para o mesmo bucket.
ÍNDICE INVERTIDO OU LISTA INVERTIDA
Trata-se de um índice onde buscamos dados para encontrar chaves. Por isso o chamamos de índice invertido.
No Índice invertido, a primeira ação a ser tomada é criar um índice com todos os termos utilizados no banco de dados. Para que isso seja eficaz, é necessário inserir todos os termos do título, porexemplo, no índice no momento em que o dado é criado.
Antes de inserirmos um termo no índice, devemos averiguar se já existe o termo dentro do índice. Quando já existe, devemos apenas adicionar a chave do termo correspondente ao registro. Quando inserimos algum termo no índice, é necessário ordenar o índice outra vez.
O mesmo vale quando formos excluir algum registro. Nesse caso, precisamos observar se os termos do registro excluído continuam sendo usados por outros registros. Caso isso não ocorra, o mais recomendável é excluir esses termos.
Devemos também, excluir os termos desnecessários do índice. Os termos desnecessários são aqueles que se repetem tantas vezes que não ajudam na busca dos arquivos. 
COMPRESSÃO DE DADOS
COMPRESSÃO SEM PERDAS
• Remoção (recuperável) das redundâncias
• Aplicada a compressão de dados, textos, programas, ...
• Exemplos:
• Run-length
• Huffman
• Lempel-Ziv
COMPRESSÃO COM PERDAS
• Eliminação de detalhes
• Aplicada a compressão de imagens, áudio, vídeo, ...
• Exemplos:
• JPEG
• MP3
• MP4
TIPOS DE COMPRESSÕES
- REDUÇÃO DA QUANTIDADE DE SÍMBOLOS
• Um símbolo passa a representar um conjunto de outros símbolos
• Ex.:
• Ao invés de indexarmos cada letra, indexamos palavras
• Um pixel pode representar um conjunto de pixels
- REDUÇÃO DO TAMANHO DO SÍMBOLO
• Um símbolo pode ser representado com menos bits do que o usual
• Ex.:
• Podemos usar menos de 1 byte para representar uma letra
• Um pixel pode usar menos de 3 bytes
CODIFICAÇÃO ELIAS GAMMA
É uma codificação desenvolvida por Peter Elias para a redução de tamanho em bits dos números. Apesar de tudo, ela só é realmente útil quando usada para números muito pequenos, como de 0 a 11. Na tabela abaixo vemos a representação em binário e também em código elias gamma. 
Os primeiros zeros são utilizados para representar a potência de um número dois enquanto os restantes dos bits representam a quanto esse número dois potenciado será somado.
Para determinar o código de elias, podemos fazer os cálculos:
Encontramos log do do número na base dois e depois subtraímos o número por 2 elevado ao log do número na base dois (que no caso acima será dois, assim teremos ).
ENTROPIA
É uma forma de estimar com quantos bits é possível representar determinado símbolo. Dessa forma, podemos identificar qual codificação é eficiente ou não.
Para descobrir a entropia de cada símbolo, usamos a porcentagem de sua frequência substituindo-a por e depois multiplicamos pela quantidade de vezes que o símbolo aparece no arquivo. Abaixo vemos outro exemplo:
CODIFICAÇÃO DE HUFFMAN
É uma codificação extremamente eficiente que tem como intuito diminuir o tamanho em bits dos símbolos. Para isso Huffman criou uma fila de árvores.
Para isso ele primeiramente definiu a frequência ou a média da frequência que um determinado símbolo aparece e criou uma pilha que ordenava árvores cuja só existiam raízes com o valor da frequência de cada letra.
Logo em seguida ele pegou as duas árvores de menor valor e as fundiu em uma única árvore, onde a raiz era a soma de seus dois números.
Em seguida ele ordenou a raiz dessa nova árvore na pilha e refez o processo até que existisse apenas uma árvore.
No final da codificação teríamos:
Logo, para codificar utilizamos a tabela, substituindo os bits de cada símbolo pelo código gerado.
Para decodificar utilizamos a árvore, seguindo o caminho dado pelo código até encontrar a letra correspondente.
COMPRESSÃO BASEADA EM DICIONÁRIOS 
LZW
É uma codificação cujo o intuito é diminuir o tamanho em bits dos símbolos. Para isso utilizamos números para representar um determinado símbolo ou um conjunto de símbolos.
CODIFICAÇÃO
Para a codificação adicionamos os símbolos básicos e depois buscamos a maior sequência que se inicia com aquele símbolo, sempre adicionando ao dicionário um caractere a mais do que o existente. Observe também que o número dado ao conjunto é de acordo com aquele conjunto que já existia previamente e não como o novo conjunto criado. Deve-se fazer o dicionário à medida que codificamos a mensagem.
DECODIFICAÇÃO
Inicializamos o dicionário (com símbolos básicos).
• Decodificar o 1º índice, escrevê-lo na saída e armazená-lo em w.
• Colocar w? no dicionário.
• Repetir até o fim dos índices:
• Decodificar o primeiro símbolo s do próximo índice.
• Trocar o ? da última entrada no dicionário por s
• Decodificar o resto do índice, escrevê-lo na saída e armazená-lo em w.
• Colocar w ? no dicionário.
CRIPTOGRAFIA
Do grego: kryptós (escondido) + graphein (escrita)
Cifragem
É o processo de conversão de um texto claro para um código cifrado.
Decifragem
é o processo contrário, de recuperar o texto original a partir de um texto
cifrado.
TIPOS DE CIFRA
Cifras de substituição
Cada símbolo é substituído por outro símbolo
Cifra de César
Homenagem a Júlio César (100 a.C. - 44 a.C.) que usava um alfabeto assim
Cifra de Vigenère
Cifra polialfabética
Inventada por Giovan Batista Belsa em 1553, apesar de ter sido atribuída durante muito tempo a Blaise de Vigenère. Semelhante à Cifra de César, mas cada letra é deslocada um diferente número de posições, de acordo com uma senha.
Para codificarmos uma mensagem, precisamos utilizar a tabela acima e uma palavra qualquer como chave.
No exemplo a seguir, codificamos a frase “fim de semana” com a chave “caro”:
FIMDESEMANA
(FIM DE SEMANA)
CAROCAROCAR
(CARO)
HIDRGSUACNR
Primeiro, removemos os espaços. Depois, substituímos as letras pela palavra chave. Por último, buscamos na tabela em x a letra cifrada com caro e em y a letra original. Dessa forma, basta substituí-la pela letra correspondente. 
Cifras de transposição
Os símbolos são trocados de lugar
Cifra das colunas
A informação é escrita em uma matriz, linha a linha. Em seguida, as colunas são extraídas, na ordem dos valores dos caracteres da palavra chave.
Exemplo:
TIPOS DE CRIPTOGRAFIA
Criptografia simétrica – a mesma chave criptográfica é usada na cifragem e na decifragem.
Criptografia assimétrica – chaves diferentes são usadas na cifragem e na decifragem, mas, geralmente, o processo é bidirecional.
CRIPTOGRAFIA SIMÉTRICA
Cifras de Fluxo
Há muitos exemplos de comunicação em que os dados são transferidos na medida em que essa comunicação ocorre. Os dois exemplos mais simples disso são as ligações (por telefone ou videoconferência) e as aplicações de streaming (como Spotify e Netflix). Nesses casos, os dados vão sendo consumidos na medida em que vão chegando. E quando a comunicação ou transferência precisa ser criptografada, não dá para esperar chegar toda a informação, decifrá-la e, somente então, apresentá-la. Precisamos decifrar os dados na medida em que eles vão chegando. Na outra ponta da comunicação, isto é, no lado do emissor, os dados precisam ser cifrados na medida em que são enviados. Precisamos, portanto, de uma técnica de cifragem de fluxo.
A cifragem de fluxo é feita bit a bit (ou símbolo a símbolo).
Ex.: Substituição simples
• Cifra de chave simétrica que combina os bits de um fluxo de bits (bitstream) com os bits de uma chave (keystream)
• A encriptação geralmente é feita por meio de uma simples operação XOR:
One Time Pad
• Desenvolvido em 1917 por Gilbert Vernam nos laboratórios da Bell, para cifrar fluxos.
• A chave é uma string de bits aleatória do mesmo tamanho da mensagem a ser criptografada.
• É inquebrável (matematicamente comprovado), desde que a chave seja realmente aleatória, mantida em segredo e usada apenas uma vez.
C - Cifra
K - Key
M - Mensagem
• O OTP requer chaves muito longas, difíceis de serem gerenciadas e mantidas em sigilo.
• Os algoritmos usam, portanto, um gerador de chaves pseudoaleatórias usando uma chave semente de 64, 128, 256 ou mais bits.
Cifra de Blocos
A ideia por traz da cifra de blocos é juntar um tanto de símbolos, sejam eles caracteres, dígitos, bytes ou mesmo bits, e codificá-los de uma só vez. Geralmente os blocos são bem pequenos,variando de 64 a 512 bits. Assim, uma mensagem, arquivo ou conjunto de dados será composto por uma quantidade muito grande de blocos. Eles serão codificados um a um de forma independente. Bem, de forma independente se você quiser, porque existe uma técnica para se aumentar a segurança em que o bloco anterior é usado na cifragem do bloco seguinte.
O processo da cifragem de blocos pode ser bem simples. Por exemplo, podemos usar alguma cifra de transposição como a cifra de colunas. Na verdade, podemos fazer uma série de operações que combinem transposições, substituições, XORs e ainda outras operações. 
Se o mesmo bloco se repetir, os blocos cifrados serão iguais, facilitando a percepção de um padrão. Para evitar isso, existem algumas técnicas como a realimentação, em que o bloco anterior é usado na cifragem do bloco atual.
CRIPTOGRAFIA ASSIMÉTRICA
Nesse tipo de criptografia, cada pessoa ou entidade tem duas chaves — uma ele tornará pública, isto é, todo mundo ficará conhecendo a chave, e a outra será privada, isto é, apenas o seu dono deve conhecê-la. É por isso que a criptografia assimétrica também é chamada de criptografia de chave pública. Mas, enfim, se você quiser mandar uma mensagem para uma pessoa, precisa usar a chave pública dessa pessoa. E somente ela vai conseguir decifrar a mensagem usando a sua chave privada. 
Veja o exemplo da figura abaixo. Nela, Paulo quer mandar um documento sigiloso para Carolina. Para isso, Paulo deve cifrar o documento usando a chave pública da Carolina, pois, assim, somente ela vai conseguir decifrar o documento. E, se ela quiser responder de forma sigilosa para o Paulo, deverá usar a chave pública dele, para que ele possa decifrar usando a sua própria chave privada.
• Criação de um função unidirecional, facilmente computada, mas difícil de ser invertida.
• Exemplo:
• É fácil multiplicar dois números primos grandes, mas é difícil fatorar o resultado para descobrir os números originais (sem se ter pelo menos um deles).
• Um algoritmo assimétrico pode ser até 10.000 vezes mais lento do que um algoritmo simétrico.
O principal algoritmo de criptografia assimétrica que temos hoje é o RSA, criado por Ron Rivest, Adi Shamir e Leonard Adleman em 1977.
ASSINATURA DIGITAL
Uma assinatura digital é uma forma de a gente validar um documento ou uma mensagem usando a criptografia assimétrica. Só que dessa vez, a gente usa a criptografia numa direção oposta, isto é, ciframos algum documento com a nossa chave privada e todo mundo vai conseguir abrir esse documento com a nossa chave pública — ele não será um documento sigiloso. No entanto, se esse documento realmente puder ser aberto com a nossa chave pública, então ele só pode ter sido cifrado pela nossa chave privada (à qual apenas a gente tem acesso). Assim, garantimos a autoria. Ao mesmo tempo, se o documento puder ser aberto sem nenhuma dificuldade, então ele está íntegro, isto é, ninguém adulterou esse documento.
Na verdade, a assinatura digital não é usada para cifrar todo o documento, pois ele não precisa ser sigiloso mesmo. O que ciframos com a nossa chave privada é apenas um código hash desse documento, gerado por alguma função hash especial. Esse código hash cifrado é a nossa "assinatura digital" que garante a autenticidade (autoria e integridade) do documento.
Assim, quando alguém quiser testar a autenticidade do documento, ele gera o código hash novamente e compara com o código hash decifrado da assinatura digital (usando a nossa chave pública). Se forem iguais, então o documento é autêntico. 
CERTIFICADOS DIGITAIS
Para a gente saber qual é a chave pública de uma determinada entidade — como uma loja virtual ou um banco on-line — a gente precisa ter acesso à sua chave pública. Essa chave pública pode ser encontrada no certificado digital, que nada mais é que um documento que dá autenticidade à chave. Esse documento diz que chave é essa, quem é o seu proprietário e quem emitiu o certificado. Esse documento pode ser usado de diversas formas, mas ele também precisa ser instalado no site da empresa, para que possa ser acessado pelos usuários que navegam por esse site (usando o protocolo HTTPS).
Um certificado digital é um arquivo que contém a identidade de um indivíduo ou entidade e a sua
chave pública. O certificado digital é emitido por uma entidade certificadora, a partir de uma rede de confiança ( web of trust ) descentralizada.
Para esclarecer as coisas, observe o exemplo abaixo:
Assim que o cliente solicita uma conexão segura, o servidor/estabelecimento retorna um certificado digital com a sua chave pública. Logo, o cliente envia uma chave simétrica criptografada com a chave pública do servidor. Dessa forma, apenas o servidor poderá decodificar a chave enviada, pois ele é o dono da chave privada da mensagem. Assim, o servidor confirma o recebimento da chave simétrica, agora através de uma criptografia simétrica, e ambos utilizam dessa criptografia para manter a comunicação.
CASAMENTO DE PADRÕES
O casamento de padrões é uma busca por uma cadeia de símbolos em uma sequência maior.
• Ex.: busca de palavras em textos
Os algoritmos são identificados como:
• Pattern searching
• String searching
• String matching
O casamento de padrões não se limita à busca de texto.
• Exemplos:
busca de DNA, detecção de intrusão, correção ortográfica, detecção de plágio, casamento de voz, etc.
Casamento exato de padrões
• Força Bruta
• KMP
• Aho Corasick
• Boyer Moore
• Casamento aproximado de padrões
• Distância de Levenshtein
FORÇA BRUTA
A forma mais simples de casamento de padrões é a força bruta. Nesse caso, a gente testa a sequência de símbolos do padrão em TODAS as posições possíveis do documento. Obviamente, não é uma boa ideia fazermos a busca usando a força bruta, mas é importante conhecê-la para que a gente possa entender as vantagens das outras formas. No casamento por força bruta, o resultado de um teste do padrão em uma posição não é aproveitado em um teste posterior. Assim, não há nenhuma otimização nessa forma de busca.
ALGORITMO KMP
• Criado por Donald Knuth, James Morris e Vaughan
Pratt em 1977
• Baseado em uma variação de um diagrama de estados
Ao invés de voltar para o início da palavra, voltamos para o último prefixo.
ALGORITMO BOYER MOORE
• Criado por Robert S. Boyer e J. Strother Moore em 1977
• Comparação de caracteres do padrão são feitas da direita para a esquerda
• São feitos dois testes a cada passo:
• Deslocamento por caractere ruim
• Deslocamento por sufixo bom
• O deslocamento final será o maior dos dois
É importante destacar que quando o valor do caractere ruim e do sufixo bom são diferentes, devemos considerar o maior deles.
Caso o algoritmo queira continuar procurando padrões, vale lembrar que o deslocamento sera sempre de uma posição
Aho Corasick
É uma variação do algoritmo KMP que permite testar vários padrões em uma única busca.
No exemplo acima procuramos 4 termos ao mesmo tempo: he, she, his e hers. Para o funcionamento do algoritmo, organizamos em uma espécie de esqueleto. Nesse esqueleto perceba que se em qualquer momento o algoritmo chegar nos estados 2, 5, 7 e 9, significa que uma das palavras, respectivamente, foram encontradas: he, she, his e hers.
Abaixo podemos ver as transições que ocorrem quando há falha ou quando um termo é encontrado com sucesso. O algoritmo sempre funciona de forma que quando regredimos a alguma outra posição, tentamos avançar para a próxima logo em seguida ou regredir ainda mais.
Casamento Aproximado de Padrões
É algo que busca encontrar padrões aproximados e não necessariamente exatos. Observe abaixo algumas de suas aplicações.
Corretores ortográficos, Comparação de DNA, Filtragem de SPAM, OCR (optical character recognition).
Para compreendermos o casamento aproximado de padrões, precisaremos ter uma ideia básica sobre o que é programação dinâmica. A programação dinâmica é um método desolução de problemas por meio de sua decomposição em problemas menores.
Na programação dinâmica, salvamos o resultado de cada problema decomposto para que possamos usar em problemas futuros idênticos. Um exemplo que podemos citar é Fibonacci, onde o resultado é a soma do fibonacci dos dois antecessores do número requerido. 
Nesse exemplo podemos perceber que para o resultado de F(5) são feitos vários cálculos iguais.
Voltando para o casamento aproximado, usamos a seguinte equação:
A minha distância de edição de casaco para cascão é o valor da posição 6x6 do vetor, ou seja, 2.
Obss: Nos comparamos se as letras são iguais, e não os números. Ex: S = S ent C = 0;