Aula3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Tecnologia e novas mídias
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTE
Aula 03
AULA 02
Á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, Tre e Trd, 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. 
Tre
Trd
T
Árvore binária - definição
Vídeo
https://www.youtube.com/watch?v=PgZflufXGUU
3s a 1:16s
3
https://www.youtube.com/watch?v=PgZflufXGUU
3s a 1:16s
3
 Possuem um número constante de sub-árvores em cada nó
 Limitação do número de ponteiros usados:
Algoritmos eficientes para o tratamento
 A forma de armazenar os nós surge naturalmente de sua definição:
 Ponteiro para o nó raiz (como nas listas lineares) 
 Ponteiros para os filhos: esq e
 dir 
Vantagens
© Archibald1221 | Dreamstime.com
4
ID 18168124
4
Aplicações que usam árvores binárias
Problemas de busca de dados armazenados na memória principal do computador: 
árvore binária de busca, 
árvores (quase) balanceadas como AVL, rubro-negra, etc. 
Problemas de busca de dados armazenados na memória secundárias principal do computador (disco rígido): e.g. B-árvores. 
5
© Archibald1221 | Dreamstime.com
ID 18168124
5
Aplicações que usam árvores binárias
Aplicações em Inteligência Artificial: árvores que representam o espaço de soluções, e.g. jogo de xadrez, resolução de problemas, etc. 
No processamento de cadeias de caracteres: árvore de sufixos. 
Na gramática formal: árvore de análise sintática.
Em problemas onde a meta é achar uma ordem que satisfaz certas restrições (e.g. testar a propriedade de uns-consecutivos numa matriz, reconhecer grafos intervalo, planaridade de grafo, etc.): árvore-PQ. 
6
 A busca nada mais é do que um percurso em uma árvore.
O percurso em uma árvore visitando cada nó uma única vez gera uma sequência linear de nós.
Assim, passa a ter sentido falar em sucessor e predecessor de um nó segundo um determinado percurso.
Há três maneiras recursivas de se percorrer árvores. binárias:
Percurso em pré-ordem
Percurso em pós-ordem
Percurso em ordem 
Percurso em árvores Binárias
© Archibald1221 | Dreamstime.com
7
  Neste caso a visita aos nós acontecem de cima para baixo da esquerda para a direita, Passando pelo nó raiz antes de visitar os nós a ela ligados. 
 Algoritmo básico:
Se árvore vazia  fim 
Visitar o nó raiz 
Percorrer em pré-ordem a sub-árvore esquerda 
Percorrer em pré-ordem a sub-árvore direita 
Percurso em pré-ordem
© Archibald1221 | Dreamstime.com
8
ID 18168124
8
Vídeo
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
3:24 4:41 
9
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
3:24 4:41 
9
Neste caso a visita aos nós acontecem de baixo para cima da esquerda para a direita.
Algoritmo básico:
Se árvore vazia  fim 
percorrer em ordem a sub-árvore esquerda 
visitar o nó raiz 
percorrer em ordem a sub-árvore direita 
Percurso em ordem
© Archibald1221 | Dreamstime.com
10
ID 18168124
10
Vídeo
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
5:18 -6:40
11
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
5:18 -6:40
11
Neste caso a visita aos nós acontecem da esquerda para a direita de baixo para cima, visitando por último a raiz.
Algoritmo básico:
 Se árvore vazia  fim 
 percorrer em pós-ordem a sub-árvore esquerda 
 percorrer em pós-ordem a sub-árvore direita 
 visitar o nó raiz 
Percurso em pós-ordem
© Archibald1221 | Dreamstime.com
12
ID 18168124
12
Vídeo
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
7:07 a 8:10
13
https://www.youtube.com/watch?v=z7XwVVYQRAA
Percorrendo uma árvore binária
7:07 a 8:10
13
Introdução a algoritmos
Uma sequência finita de passos (instruções) para resolver um determinado problema. Sempre que desenvolvemos um algoritmo estamos estabelecendo um padrão de comportamento que deverá ser seguido (uma norma de execução de ações) para alcançar o resultado de um problema.
14
© Viktor88 | Dreamstime.com
ID 41785517
Genericamente, pode-se ver um algoritmo como uma coleção de passos que orientam as ações para se chegar a um resultado; uma sequência finita de passos (instruções) para resolver um determinado problema. Sempre que desenvolvemos um algoritmo estamos estabelecendo um padrão de comportamento que deverá ser seguido (uma norma de execução de ações) para alcançar o resultado de um problema. Para o desenvolvimento de um algoritmo eficiente é necessário obedecermos algumas premissas básicas no momento de sua construção:
14
Introdução a algoritmos
Para o desenvolvimento de um algoritmo eficiente é necessário obedecermos algumas premissas básicas no momento de sua construção:
Definir ações simples e sem ambiguidade;
Organizar as ações de forma ordenada
Estabelecer as ações dentro de uma sequência finita de passos.
15
© Viktor88 | Dreamstime.com
ID 41785517
Genericamente, pode-se ver um algoritmo como uma coleção de passos que orientam as ações para se chegar a um resultado; uma sequência finita de passos (instruções) para resolver um determinado problema. Sempre que desenvolvemos um algoritmo estamos estabelecendo um padrão de comportamento que deverá ser seguido (uma norma de execução de ações) para alcançar o resultado de um problema. Para o desenvolvimento de um algoritmo eficiente é necessário obedecermos algumas premissas básicas no momento de sua construção:
15
Introdução a algoritmos
Um algoritmo é capaz de:
Ler e escrever dados;
Avaliar expressões algébricas, relacionais e lógicas;
Tomar decisões com base nos resultados das expressões avaliadas;
Repetir um conjunto de ações de acordo com uma condição;
16
© Viktor88 | Dreamstime.com
ID 41785517
16
Introdução a algoritmos
Partes constituintes de um algoritmo
17
Na parte de entrada, são fornecidas as informações necessárias para que o algoritmo possa ser executado. Estas informações podem ser fornecidas no momento em que o programa está sendo executado ou podem estar embutidas dentro do mesmo. As informações fornecidas são armazenadas como estruturas de dados, que é uma maneira de organizar dados e operar sobre eles.
Na parte do processamento são avaliadas todas as expressões algébricas, relacionais e lógicas, assim como todas as estruturas de controle existentes no algoritmo (condição e/ou repetição). Assim, um programa é a junção do algoritmo e de uma ou mais estruturas de dados.
Na parte de saída, todos os resultados do processamento (ou parte deles) são enviados para um ou mais dispositivos de saída, como: monitor, impressora, ou até mesmo a própria memória do computador.
17
Estrutura de dados
Pode-se organizar os dados dos tipos simples em tipos mais complexos, formando o que se denomina de estruturas compostas. Por exemplos: estruturas compostas homogêneas unidimensionais (vetores) e multidimensionais (matrizes) permitem a manipulação de um conjunto de dados de um mesmo tipo. 
Outro tipo de estruturação de
 dados é chamado
 Tipo de Dado Abstrato
18
© Madmaxer | Dreamstime.com
ID 17646487
18
Estrutura de dados - vetor
É uma variável composta por uma coleção de elementos individuais com as seguintes características: 
Ordenado: os elementos de um vetor são indexados de forma ordenada 
Homogêneo: Todo valor armazenado em um mesmo vetor deve ser do mesmo tipo (exemplo: valores inteiros, reais, etc.)
 Exemplo de vetor de inteiros com 4 elementos, cujo identificador (nome) é A: 
A=
19
10
8
5
1
Estrutura de dados - vetor
Para fazer referência a um determinado elemento do vetor usa-se um índice. Dependendo da linguagem, o índice j está associado ao j-ésimo ou (j+1)-ésimo elemento do vetor. Por exemplo, tem-se para o vetor acima: A[1] faz referência ao segundo elemento do vetor
(em muitas linguagens computacionais o contador começa em 0, então o primeiro elemento do vetor seria A[0] ) O valor de A[1] é igual a 8
A=
20
10
8
5
1
Estrutura de dados - matriz
Uma matriz é vetor de vetores. Para fazer referência a um determinado elemento da matriz usa-se dois índices: o primeiro índice representa a linha e o segundo índice representa a coluna. Seja matriz 
B=
O elemento B[0][0] é igual a 10.
O elemento B [1][2] é igual a 69.
21
10
34
55
84
13
90
69
73
28
4
91
52
Estrutura de dados: tipos de dados abstratos
Os tipos e estruturas de dados existem para serem usados pelo programa para acessar informações neles armazenadas, por meio de operações apropriadas. Do ponto de vista do programador, muitas vezes é conveniente pensar nas estruturas de dados em termos das operações que elas suportam, e não da maneira como 
elas são implementadas.
22
© Madmaxer | Dreamstime.com
Estrutura de dados: tipos de dados abstratos
 Uma estrutura de dados definida dessa forma é chamada de um Tipo Abstrato de Dados (TAD) TAD, portanto, estabelece o conceito de tipo de dado divorciado da sua representação, definido como um modelo matemático por meio de um par (v,o) em que v é um conjunto de valores o é um conjunto de operações sobre esses valores, por exemplo:
Ex.: tipo real v =  ; o = {+, -, *, /, =, , <=, >=}
23
Atividade – percorrendo árvores
24
© Get4net | Dreamstime.com
ID 18375701
24
1
Depósito
Matriz
3
Filial 1
6
Depósito
Ext 2
2
Depósito
Ext 1
4
Filial 1 Ext 1
5
Filial 2 Ext 1
7
Filial 2 Ext 2
1 – 3 – 2 – 4 – 5 – 6 – 7
Exercício de Percurso em “Pré-Ordem” (Raiz – TRE – TRD)
1
Depósito
Matriz
3
Filial 1
6
Depósito
Ext 2
2
Depósito
Ext 1
4
Filial 1 Ext 1
5
Filial 2 Ext 1
7
Filial 2 Ext 2
3 – 1 – 4 – 5 – 2 – 6 – 7
Exercício de Percurso em “Em ordem” (TER- raiz- TRD)
Tecnologia e novas mídias
VAMOS AOS PRÓXIMOS PASSOS?
AVANCE PARA FINALIZAR
A APRESENTAÇÃO.
AULA 03