Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

Lembra da arvore genealógica? É um conceito parecido.
A “arvore” é composta opor alguns elementos como a “Raiz” que é nosso elemento principal dela partem os galhos ou filhos esses galhos pode possuir outros galho, quando isso não acontece é uma folha ou nó terminal.

O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, em que cada elemento possui no máximo 2 galhos.

Aqui temos uma árvore binária:

Legenda:(se é que da pra ter alguma duvida)
Vermelho: Raiz
Azul: Galhos/Filhos
Verde: Folhas/nó terminal

Variaveis

Vamo lá pessoal, agora sobre variáveis.

Variável é toda e qualquer posição definida na memória do computador( a RAM). Toda variável inicia-se por letra podendo ou não estar acompanhada por outras letras ou números.

Ela está dividida em alguns tipo:

-Númerica: que guarda dados numéricos.
-Alfanumérica: que guarda dados alfanuméricos.
-Lógicas: que guarda dados lógicos.

Esqueminha relacionando os componentes de um pc

Mais alguns conceitos básicos

Unidade de entrada: é através desse dispositivo que o computador obtém dados e instruções externamente. Hoje, os computadores têm unidades de entrada capazes de obter informações em diversas mídias: papel, tarjas magnéticas, fitas, cd's, etc. Esta unidade traduz o que obtém externamente em uma representação que o computador possa processar.


Unidade de saída: é o dispositivo usado pelo computador para enviar os resultados do processamento das instruções recebidas para o meio exterior. Desde papel até o dvd.

Memória principal(memória cache): é o componente do computador que armazena as instruções e os dados usados em seu processamento. É o tipo de memória de acesso rápido, onde as instruções e os dados residem em tempo de execução, ou seja, no momento em que estão sendo processados.



Memória secundária: é um tipo de memória auxiliar - normalmente disco magnético - utilizado para guardar informações. Tem um acesso mais lento do que o da memória principal, porém, possui mais capacidade de armazenamento.



Unidade lógica e aritmética: é o componente que realiza as operações lógicas de comparação de grandezas e condições, além das operações aritméticas. É onde todas as operações são realizadas.

Unidade de controle: é o componente que controla o fluxo de informação e a execução das instruções, transferindo dados ente as unidades de entrada e saída e a memória. É onde as instruções a serem executadas são interpretadas pelo computador.

Unidade Central de Processamento(UCP): é formada pela unidade lógica e aritmética e a unidade de controle. A velocidade de um computador é medida, em geral, em MegaHertz, referindo-se ao ciclo interno de processamento da UCP. Tipicamente uma instrução já é executada hoje em poucos nanossegundos( 10 elevado a -9)

Artigo ED-02: Listas Lineares Sequenciais (Parte I)

Por Brunno Augusto
No artigo anterior introduzimos o estudo das estruturas de dados, dando algumas definições básicas. A partir de agora estudaremos uma a uma as estruturas citadas. Iniciemos o nosso estudo com as listas lineares sequenciais.
Uma lista linear é sequencial se, para cada nó da lista, seu sucessor está armazenado na posição seguinte da memória. A principal forma de se implementar uma lista linear sequencial é por meio da utilização de arrays (vetores). Um vetor é uma estrutura de armazenamento caracterizada por um nome, um tipo de dado que é capaz de armazenar e um tamanho, número de dados do mesmo tipo que pode armazenar. Antes de prosseguirmos neste artigo, duas observações devem ser feitas: Primeiro - A partir de agora far-se-á necessário implementarmos os algoritmos para mostrarmos o uso das estruturas de dados. Para tornar as soluções o mais genéricas possíveis, os algoritmos serão implementados em português estruturado e não em uma linguagem qualquer em particular. Segundo - Assumirei aqui que você leitor domina as noções mais elementares sobre algoritmos tais como declaração e uso de variáveis, estruturas de decisão e de repetição, entre outras. Feitas as considerações necessárias, prossigamos. A sintaxe de declaração de um vetor é dada como segue: declare nome_vetor : vetor [1..n] de tipo_vetor. Usaremos como padrão que palavras reservadas serão escritas em negrito. Vejamos agora os algoritmos que nos permitem realizar as operações mais básicas em uma lista linear sequencial. Nesse artigo implementaremos algoritmos de busca e nos demais os de inserção e exclusão.
Consideremos antes de mais nada que as listas podem se encontrar ordenadas ou desordenadas. É importante considerar isso, já que teremos mais de um algoritmo de busca e o emprego de um ou de outro, dependerá do fato de a lista está ou não ordenada.
Para qualquer tipo de lista temos o algoritmo de busca sequencial. Esse algoritmo atua da seguinte forma: ele sai em busca de um elemento vasculhando a lista do inicio até o final. Se chegar ao final e o último elemento não for o procurado, então ele não existe na lista. Percebemos que no pior caso, ou seja, quando o elemento a ser procurado é o último faremos n comparações, sendo n o número de elementos da lista. Por isso, dizemos que o algoritmo de busca sequencial é de ordem n O(n). Implementemos então o algoritmo de busca sequencial:

algoritmo busca_seq
declare
lista : vetor [1..n] de literal
chave : literal
i : numerico
achou : logico
inicio
leia chave
i <- 1 achou <- falso
enquanto (não achou) e (i<=n) faça
se lista[i] = chave então
escreva i
achou <- verdadeiro
senão
i <- i+1
fim se
fim enquanto
se não achou então
escreva "não encontrado"
fim se
fim algoritmo



Façamos uma breve análise do algoritmo acima. Nós definimos duas condições de parada, ou quando ele encontrar o elemento que busca, ou quando chegar ao fim da lista. Caso ele chegue ao final da lista e não tenha encontrado o elemento que busca, é exibida uma mensagem, se pelo contrário, for encontrado o elemento, então é exibida a sua posição na lista. É um algoritmo simples de se entender e de se implementar, podendo ser utilizado em qualquer tipo de lista. Quando porém a lista se apresenta ordenada, e nós queremos executar uma busca mais eficiente, nós podemos utilizar o algoritmo de busca binária. Vejamos no que consiste a busca binária: Estando a lista ordenada, temos que o primeiro elemento é o menor e que o último é o maior (considerando uma ordenação crescente que é a mais comum), desse modo, quando buscamos por um elemento podemos executar os seguintes passos. Procuramos o elemento médio da lista; Comparamos o valor procurado com esse e três situações podem ocorrer. O elemento procurado ser ele, desse modo encerra-se a execução do programa, o elemento procurado ser maior que ele, desse modo só no interessa procurar na metade do meio para o final da lista, ou o elemento ser menor que ele, desse modo, só nos interessa procurarmos na metade do meio para o inicio da lista. Uma vez em alguma dessas metades, repetimos os procedimentos anteriores, achando o meio da lista, comparando o elemento procurado com esse, e buscando em alguma das metades desse pedaço de lista. Para mostrarmos o que descrevemos acima de modo mais concreto, implementemos o algoritmo de busca binária, útil apenas quando a lista se encontra ordenada.



algoritmo buca_bin
declare
lista : vetor [1..n] de literal
chave : literal
ini, meio, fin : numerico
achou : lógico
inicio
leia chave
ini <- 1 fin <- n achou <- falso
enquanto (não achou) e (ini<=fin) faça
meio <- (ini+fin)/2 se chave = lista[meio]então
escreva meio
achou <- verdadeiro
senão
se chave < lista[meio] então
fin <- (meio-1)
senão
ini <- (meio+1) fim se
fim se
fim enquanto
se não achou então
escreva "elemento não encontrado"
fim se
fim algoritmo

Com base no algoritmo de busca binária, temos que a sua ordem é de log2N com N = tamanho da lista, ou seja, a busca binária no pior caso realizará log2N buscas. Para mais claramente vermos a eficiência da busca binária, consideremos uma lista com 10000 registros. A busca binária realizaria no pior caso 14 comparações enquanto que a busca sequencial realizaria em média 5000 comparações.
Bom, por hora ficamos aqui, até o próximo artigo então.