MATA40 T03 2017 2 Aula01 Introdução

Prévia do material em texto

MATA40 – Estrutura de dados e 
Algoritmos I
Introdução
Turma 03
Semestre: 2017.2
Prof. Igo Amauri dos S. Luz
Objetivo
• Objetivo dessa aula:
• Contextualizar Estruturas de dados e Algoritmos nos
sistemas computacionais
2
Modelo básico de um 
Computador
3
Armazenamento de dados
• A memória do computador armazena somente valores zero e
um.
• Programas, textos, imagens, vídeos, são armazenados em
forma de zero e um.
• Representação binária.
• Organização da memória:
• Bits:
• Digito Binário
• Menor unidade – 0 ou 1.
• Byte:
• Conjunto de 8 bits
• Célula:
• Conjunto ordenado de bits, armazena uma parte da informação.
4
Armazenamento de dados
• Espaço de memória finito
• Além de elementos numéricos, pode-se presentar também
texto.
• Cada caractere tem um valor associado.
• Os programas são representados na memória em forma de
linguagem de máquina
• Programas são sequencias de instruções (Códigos numéricos).
5
Armazenamento de dados
6
#include <16f628a.h> 
//Adicionar as funções que configuram o microcontrolador
#use delay(clock=1000000) 
#define PINO_LED PIN_A3 //Pino que o LED está ligado 
void main()
{ 
while (1) //Loop infinito, por isso nunca acaba
{ 
output_bit( PINO_LED, true); // Liga o Led 
delay_ms(500); // Espera 1000ms = 1 Segundo 
output_bit( PINO_LED, false); // Desliga o Led 
delay_ms(500); // Espera 1000ms = 1 Segundo 
} //Fim loop infinito 
}
Compilação
• Um Compilador é responsável por transformar o código
fonte em linguagem de máquina.
• Transforma o programa desenvolvido em C em um conjunto
de instruções.
7
Compilação
• Programas compilados para uma determinada
“máquina” não deve ser executado em uma “máquina”
diferente.
• Computadores idênticos com sistemas operacionais
diferentes são considerados “máquinas” diferentes.
8
Ciclo de desenvolvimento
9
Debate
10
• Debate dos conceitos visto até o momento
Estrutura de Dados - Conceitos 
Básicos
11
• Variáveis correspondem a posições de memórias.
• Referenciar o seu identificador, significa ter acesso a uma
única posição de memória.
• Considere que se deseje calcular a média das notas de
10 alunos e determinar o número de alunos que tiveram
nota superior a média.
Estrutura de Dados - Conceitos 
Básicos
12
• Estruturas de dados tratam da forma de se ter acesso a
conjunto de dados agrupados.
• Uma estrutura de dados mantém os dados organizados
seguindo alguma lógica e disponibiliza operações para o
usuário manipular os dados.
• Dados representam as informações armazenadas e a
estrutura é quem administra os dados.
Estrutura de Dados - Conceitos 
Básicos
13
• Dado:
• Elemento que possui valor agregado;
• Possuem tipos específicos:
• Inteiro; String; Ponto flutuante, etc
• Estrutura:
• Elemento estrutural responsável por carregar informações
dentro de uma estrutura de software.
• Tipos de estrutura de dados:
• Vetores, Pilhas, Filas, Listas, Árvores, etc.
Algoritmos - Conceitos Básicos
14
• O que é um algoritmo?
“Um algoritmo pode ser definido como uma sequência de 
passos que visam a atingir um objetivo bem definido.”
André Forbellone
Algoritmos - Conceitos Básicos
15
• Um algoritmo pode ser definido como uma sequência de 
instruções para solucionar um determinado problema.
• Deve-se seguir uma ordem, portanto precisa ser utilizada 
a lógica.
• As instruções devem ser finitas e não ambígua.
• A partir de um estado inicial, após determinado tempo 
finito, é produzido um estado final.
• Uma solução em algoritmo pode ser traduzida para 
qualquer linguagem de programação.
Algoritmos - Conceitos Básicos
16
• Um algoritmo corresponde a uma descrição de um 
padrão de comportamento, expresso em termos de um 
conjunto finito de ações.
• Executando a operação a + b percebemos um padrão de 
comportamento, mesmo que a operação seja realizada para 
valores diferentes de a e b.
Algoritmos - Conceitos Básicos
17
• Exemplo de algoritmo no nosso dia-a-dia: Troca de 
lâmpada
• Pegar uma escada;
• Posicionar a escada embaixo da lâmpada;
• Buscar uma lâmpada nova;
• Subir na escada;
• Retirar a lâmpada velha;
• Colocar a lâmpada nova;
• Testar o funcionamento da lâmpada nova.
Algoritmos - Conceitos Básicos
18
• Mais algum exemplo?
Algoritmos - Conceitos Básicos
19
• Exemplos de algoritmos: 
• Instruções para o uso de medicamentos;
• Indicações de como montar um aparelho; 
• Uma receita de culinária.
Algoritmos - Conceitos Básicos
20
• Diferentes tipos de problemas resolvidos por algoritmos:
• Genoma Humano;
• Acesso à informações através da internet;
• Comercio eletrônico;
• Industria;
Algoritmos - Conceitos Básicos
21
• Um algoritmo pode ser dividido em três partes:
• Entrada de dados
• Processamento de dados
• Saída de dados
Algoritmos - Conceitos Básicos
22
• Um algoritmo pode ser dividido em três partes:
• Entrada de dados;
• Informações fornecidas para serem processadas.
• Processamento de dados;
• Procedimentos executados para a solução do problema.
• Conjunto de passos organizados de forma lógica
• Saída de dados.
• Resultado do processamento da entrada.
• Informações processadas, saída do sistema.
ProcessamentoEntrada Saída
Algoritmos - Conceitos Básicos
23
• Como solucionar o problema computacional de
ordenação?
• Dada uma sequência de entrada: 20, 05, 80, 03, 25.
Algoritmos - Conceitos Básicos
24
• Muitas aplicações utilizam a ordenação como uma etapa
intermediária de execução.
• Existem diferentes tipos de algoritmos de ordenação
disponíveis.
• O melhor algoritmo depende:
• Número de itens, grau de ordenação da entrada, da
arquitetura do computador, do dispositivo de
armazenamento utilizado, etc.
Algoritmos x Estrutura de 
Dados
25
• Estruturas de dados e algoritmos estão intimamente
ligados:
• não se pode estudar estruturas de dados sem considerar os
algoritmos associados a elas,
• assim como a escolha dos algoritmos em geral depende da
representação e da estrutura dos dados.
• Para resolver um problema é necessário escolher uma
abstração da realidade, em geral mediante a definição de
um conjunto de dados que representa a situação real.
• A seguir, deve ser escolhida a forma de representar esses
dados.
Algoritmos x Estrutura de 
Dados
26
• Programar é basicamente estruturar dados e construir
algoritmos.
• Programas são formulações concretas de algoritmos
abstratos, baseados em representações e estruturas
específicas de dados.
• Um computador só é capaz de executar programas em
linguagens de máquinas
• As linguagens de programação representam uma abstração
para facilitar a tarefa de programar um computador.
Debate
27
• Debate dos conceitos visto até o momento
Próxima Aula ...
• Revisão de Linguagem C:
• Estrutura básica de um programa em C;
• Comandos condicionais;
• Comandos de repetição;
• Funções;
• Ponteiros;
• Alocação dinâmica.
28
Bibliografia
• N.Ziviani. Projeto de Algoritmos com Implementações 
em Pascal e C – 3ª. Edição. Ed.Cengage Learning. 2004
• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Algoritmos 
– Teoria e Prática – 3a. Edição. Editora Elsevier Campus. 
2012
• J.L.Szwarcfiter, L.Markenzon. Estruturas de Dados e seus 
Algoritmos – 2ª. Edição. Editora LTC. 2004
29