ESTRUTURA DE DADOS I AULA I

Prévia do material em texto

ESTRUTURA DE 
DADOS I
AULA I
PROF. ME. HÉLIO ESPERIDIÃO
O que é um 
dado?
Dado pode ser definido como a 
matéria-prima originalmente 
obtida de uma ou mais fontes 
(etapa de coleta).
o que é a informação
A Informação é o resultado do processamento.
Isto é, o dado processado ou "acabado”.
Obtendo a informação
Dados Processamento Informação
Exemplo de Processamento
14/02/2019 5
Área S do 
circuloBase,Altura
2
.ab
s =
Modelo 
Matemático
Implementação (Padrão de bits/rotinas)
Processamento de Dados:
O esquema. 
ProcessamentoEntrada Saída
Dispositivo
de Entrada
Dispositivo
de Saída
Memória
CPU
Definindo Abstração
14/02/2019 7
Abstração
Quando a matéria-prima usada num processo é abstrata, isto é, apresenta-se sob a forma de 
valores, quantidades ou símbolos, então falamos em processamento de dados. Quando o 
processamento é realizado por um computador, entrada refere-se aos dados colhidos do mundo 
real externo ao computador, e processo refere-se a uma série finita de operações que são 
realizadas a partir destes dados, a fim de transformá-los em alguma informação desejada 
(saída).
Importante
Nem todo tipo de dado abstrato pode ser implementado em toda sua generalidade.
Observe o conjunto Z
Z = {...,-3,-2,-1,0,1,2,3,...}
O conjunto Z deve ser finito.
14/02/2019 9
Conceito de Estrutura de Dados
Uma estrutura de dados é um modo de armazenar os dados no computador para que os dados
sejam usados com eficiência.
Normalmente devem ser escolhidas cuidadosamente; Uma estrutura de dados bem
desenvolvida permite que uma variedade de operações críticas sejam implementadas por uma
linguagem de programação com os tipos de dados e referências e as operações advindas dos
mesmos.
Objetivo da 
Estrutura de 
Dados
Teórico: Identificar e desenvolver modelos matemáticos, 
determinando que classes de problemas podem ser resolvidos 
como uso deles;
Prático: Criar representações concretas dos objetos e 
desenvolver rotinas capazes de atuar sobre estas 
representações, de acordo com modelo considerado.
REPRESENTAÇÃO DE DADOS
✓ O matemático inglês George Boole (1815-1864) publicou em 1854 os 
princípios da lógica booleana.
✓ Segundo Boole tudo poderia ser representado utilizando apenas os 
números 0 e 1.
010000111010101011
110110101010110101
010110101010101101
George Boole
Bit
ü Simplificação de “dígito binário”(BInary digiT em 
inglês)
ü É a menor unidade de informação que pode ser 
armazenada ou transmitida.
ü Um bit pode assumir somente 2 valores, por 
exemplo: 0 ou 1, verdadeiro ou falso.
Byte
✓ Um byte nada tem de especial, é apenas um 
número binário de oito algarismos
0 1 0 1 0 1 1 1
Bytes
✓ 1 Byte é representado por uma cadeia de 8 bits
1 byte = 8 bits
1024 bytes = 1 K byte
1.048.576 bytes = 1 Mega byte
Noção de tamanho
Bit 20 0 ou 1
Byte 23 8 bits
Kilo 1 Kbyte 210 1024 Bytes 
Mega 1 Mbyte 220 1 024 kB
Giga 1 Gbyte 230 1 024 MB
Tera 1 Tbyte 240 1 024 GB
peta 1 Pbyte 250 1 024 TB
Exa 1 Ebyte 260 1 024 PB
Zetta 1 Zbyte 270 1 024 EB
Yotta 1 Ybyte 280 1 024 ZB
Decimais para Binários
7 2
31 2
11
= 111
Quantos Bits são Necessários para representar o numero 7?
Binários para Decimais 
2 2 2
012
+ +1 x 1 x 1 x
4 + 2 + 1 =7
= 7
Número binário: 111
Tipos de dados
Tipo descrição Bits
byte Inteiro sem sinal 8 0 a 255
sbyte inteiro com sinal com 
sinal
8 -128 a 127
int inteiro com sinal com 
sinal
32 -2,147,483,648 to 2,147,483,647
uint Inteiro sem sinal 32 0 a 4294967295
short inteiro com sinal com 
sinal
16 -32.768 a 32.767
long inteiro com sinal com 
sinal
64 -922337203685477508 to 
922337203685477507
ulong Inteiro sem sinal 64 0 a 18446744073709551615
Importância da escolha 
correta do tipo de dados
Economia de memória.
Economia de processador.
Economia de Disco.
Qual o resultado da economia?
Conceito de Ponteiros
Um ponteiro é uma variável que representa a 
localização de um item de dados na memória ou seja ele 
aponta para um endereço de memória na qual existe um dado 
para ser processado. Os ponteiros são usados para otimizar e 
aumentar performance de memória em uma aplicação.
14/02/2019 21
Armazenamento da informação na 
memória RAM
14/02/2019 22
RAM
0012F588
num = 80
x = 123.89
0012F580 Variável 
inteira (int)
Variável 
dupla 
precisão 
(double)
Ponteiro
*p
*j
Aplicações da Estrutura de Dados
Desenvolvimento de Banco de dados;
Software GIS (Sistema Geográfico de informções);
Geradores automáticos de programas;
Software de reconhecimento de padrões;
Sistemas de Computação Gráfica;
Sistema de IA (Inteligência Artificial);
Criação de Compiladores;
Expressões Regulares;
Processamento de Imagens Digitais
14/02/2019 23
É uma sequência de operações bem definidas que, quando executadas por um 
computador, sempre termina num determinado período de tempo, produzindo 
uma solução ou indicando que a solução não pode ser obtida.
◼ Procedimento passo a passo para obtenção de um fim
Algoritmo
Complexidade de Algoritmos
A Complexidade de um Algoritmo consiste na quantidade de “trabalho”
necessária para a sua execução.
Complexidade 
de Algoritmos
Um algoritmo serve 
para resolver um 
determinado 
problema. 
Todos os problemas 
têm sempre uma 
entrada de dados 
(N)
O tamanho desse N 
afeta diretamente o 
tempo de resposta 
de um algoritmo
A complexidade de um algoritmo pode ser dividido em:
◦ Complexidade Espacial: Quantidade de recursos utilizados para resolver 
o problema; 
◦ Complexidade Temporal: Quantidade de Tempo utilizado. 
Em ambos os casos, a complexidade é medida de acordo com o 
tamanho dos dados de entrada (N)
Complexidade de Algoritmos
Operações primitivas
De modo geral, são as computações básicas realizadas por um algoritmo:
◦ Atribuição de valor para uma variável
◦ Comparação entre valores
◦ Cálculo aritmético
◦ Chamada de função
Sua definição exata não é importante.
Apesar de serem obviamente diferentes, são contabilizadas como tempo 
unitário
28
Complexidade 
Espacial
Q UA N TO S R EC URS O S D E 
M E M Ó R I A S ÃO N EC ES S Á R I OS 
PA R A E X EC U TA R O 
P R O GR A MA A BA I XO :
29
Complexidade 
Espacial
Double: 64 bits
◦ 6*64bits = 384 bits
Int: 32 bits
◦ 1*32bits = 32bits
Total de Recursos:
◦ 416bits
◦ 52Bytes.
30
Complexidade de Algoritmos
Existem três escalas de complexidade:
◦ Melhor Caso
◦ Pior Caso
Nas três escalas, a função f(N) retorna a complexidade de 
um algoritmo com entrada de N elementos
Complexidade 
de Algoritmos 
– Melhor Caso
Definido pela letra grega Ω (Ômega)
É o menor tempo de execução em uma entrada de tamanho N
É pouco usado, por ter aplicação em poucos casos.
Ex.:
◦ Se tivermos uma lista de N números e quisermos encontrar 
algum deles assume-se que a complexidade no melhor caso 
é f(N) = Ω (1), pois assume-se que o número estaria logo na 
cabeça da lista. 
Melhor caso
Encontrar o número 35
• Se tivermos uma lista de N 
números e quisermos encontrar 
algum deles assume-se que a 
complexidade no melhor caso é 
f(N) = Ω (1), pois assume-se que o 
número estaria logo na cabeça da 
lista. 
33
35 23 20 10 22 10 15 22 1 3
Complexidade 
de Algoritmos 
–
Pior Caso
Será o caso utilizado durante esse curso
Representado pela letra grega O (O maiúsculo. Trata-se da 
letra grega ômicron maiúscula) 
É o método mais fácil de se obter. Baseia-se no maior tempo 
de execução sobre todas as entradas de tamanho N
Ex.:
◦ Se tivermos uma lista de N números e quisermos encontrar 
algum deles, assume-se que a complexidade no pior caso é 
O (N), pois assume-se que o número estaria, no pior caso, 
no final da lista. Outros casos adiante
Complexidade de 
Algoritmos –
Pior Caso
• Se tivermos uma lista de N números e quisermos encontrar algum deles, assume-se que a complexidade 
no pior caso é O (N), pois assume-se que o número estaria, no pior caso, no final da lista. 
35 23 20 10 22 10 15 22 1 3
Complexidade 
de Algoritmos
Mas como saber qual é a complexidadede um determinado 
algoritmo implementado?
Para resolver esse problema, dividiu-se os algoritmos em 
“Classes de Problemas”, de acordo com o parâmetro que afeta 
o algoritmo de forma mais significativa
Classes de 
Algoritmos
São elas:
1. Complexidade Constante
2. Complexidade Linear
3. Complexidade Quadrática
4. Complexidade Cúbica
5. Complexidade Exponencial
Complexidade Constante
São os algoritmos de complexidade O(1)
Independe do tamanho N de entradas
É o único em que as instruções dos algoritmos são executadas num 
tamanho fixo de vezes
Ex.:
int RetornaPrimeiro(List: t){
return t[0];
}
Complexidade Linear
São os algoritmos de complexidade O(N)
Uma operação é realizada em cada elemento 
de entrada, ex.: pesquisa de elementos em 
uma lista
Procedure Busca(Lista, x)
i:=0;
while Lista.Elemento[i] <> x do
if i >= Lista.MaxTam then
pos := -1
else
pos := i;
i := i+1;
End;
Retorna i
Complexidade Quadrática
São os algoritmos de complexidade O(N²)
Itens são processados aos pares, geralmente com um loop dentro do outro
Ex.:
Procedure SomaMatriz(Mat1, Mat2);
Var i, j: integer, MatRes;
Begin
for i:=1 to n do
for j:=1 to n do
MatRes[i,j] := Mat1[i, j] + Mat2[i,j];
Complexidade Cúbica
São os algoritmos de complexidade O(N³)
Itens são processados três a três, geralmente com um loop dentro do 
outros dois
Ex.:
Procedure SomaElementos_Vetor_Indices_Matriz
(mat: Matriz, vet: Vetor);
Var i, j: integer;
Begin
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do 
mat[i, j] := mat[i, j] + vet[k];
Complexidade Exponencial
São os algoritmos de complexidade O(2N)
Utilização de “Força Bruta” para resolvê-los (abordagem simples para 
resolver um determinado problema, geralmente baseada diretamente 
no enunciado do problema e nas definições dos conceitos envolvidos)
Geralmente não são úteis sob o ponto de vista prático
◼Bubble sort
Métodos simples de Ordenação de 
dados
Bubble sort
O bubble sort, ou ordenação por flutuação (literalmente 
"por bolha"), é um algoritmo simples. 
A ideia é percorrer o vetor diversas vezes até que ele esteja 
ordenado, a cada passagem o maior elemento é deslocado 
(flutua) para o final do vetor
44
Bubble sort
Essa movimentação lembra a forma como as 
bolhas em um tanque de água procuram seu 
próprio nível, e disso vem o nome do algoritmo.
45