Ordenação

Ordenação
Por simplicidade, é assumido nessa apresentação que as tabelas que serão ordenadas estão sempre contidas em memória. A classe de algoritmos de ordenação que trabalham com essa restrição são denominados algoritmos de ordenação interna. Algoritmos de ordenação externa manipulam conjuntos de valores que podem estar contidos em arquivos maiores, armazenados em discos ou outros dispositivos de armazenamento externos à memória principal. Os algoritmos de ordenação interna (em memória) são convencionalmente baseados em estratégias de comparação (quicksort, heapsort) ou em estratégias de contagem (radixsort).

Ordenação por comparação
Um algoritmo básico de ordenação é o algoritmo de ordenação pelo menor valor, que pode ser sucintamente descrito como a seguir. Inicialmente, procure a entrada que apresenta o menor valor de chave na tabela. Uma vez que seja definido que entrada é essa, troque-a com a primeira entrada da tabela. Repita então o procedimento para o restante da tabela, excluindo os elementos que já estão na posição correta. Esse procedimento é descrito no Algoritmo que recebe como argumento a tabela a ser ordenada com base nos valores da chave de cada entrada. No procedimento, pos1 e pos2 são as posições da tabela sendo correntemente analisadas e min corresponde à posição que contém a chave com menor valor dentre as restantes na tabela. A variável sml contém o valor da menor chave encontr

Neste algoritmo, o laço de iteração mais externo indica o primeiro elemento na tabela não ordenada a ser analisado -- no início, esse é o primeiro elemento da tabela. As linhas de 4 a 8 são responsáveis por procurar, no restante da tabela, o elemento com menor valor de chave. Na linha 9, o procedimento auxiliar SWAP, descrito no Algoritmo abaixo inverte o conteúdo das duas entradas nas posições especificadas.



Este tipo de algoritmo de ordenação é razoável para manipular tabelas com um pequeno número de elementos, mas à medida que o tamanho da tabela cresce ele passa a se tornar inviável -- sua complexidade temporal é , conseqüência do duplo laço de iteração que varre a tabela até o final. Felizmente, há outros algoritmos de ordenação com melhores características.
Quicksort é baseado no princípio de ``dividir para conquistar:'' o conjunto de elementos a ser ordenado é dividido em dois subconjuntos (partições), que sendo menores irão requerer menor tempo total de processamento que o conjunto total, uma vez que o tempo de processamento para a ordenação não é linear com a quantidade de elementos. Em cada partição criada, o procedimento pode ser aplicado recursivamente, até um ponto onde o tamanho da partição seja pequeno o suficiente para que a ordenação seja realizada de forma direta por outro algoritmo.
Nesta descrição do procedimento QUICKSORT (figura abaixo) os argumentos determinam as posições inicial e final do segmento da tabela a ser ordenado, init e end, respectivamente.

O segredo deste algoritmo está na forma de realizar a partição -- um elemento é escolhido como pivô, ou separador de partições. Nesse procedimento, a posição do pivô resultante é estabelecida pela posição part. Todos os elementos em uma partição têm valores menores que o valor do pivô, enquanto todos os elementos de outra partição têm valores maiores que o valor do pivô. Os dois laços internos (iniciando nas linhas 6 e 8) fazem a busca pelo pivô tomando como ponto de partida o valor inicial. Um melhor desempenho poderia ser obtido obtendo-se o valor médio de três amostras como ponto de partida para o pivô -- por exemplo, entre os valores no início, meio e fim da tabela. Dessa forma, haveria melhores chances de obter como resultado partições de tamanhos mais balanceados, característica essencial para atingir um bom desempenho para esse algoritmo.
Quicksort é um algoritmo rápido em boa parte dos casos onde aplicado, com complexidade temporal média . Entretanto, no pior caso essa complexidade pode degradar para . Mesmo assim, implementações genéricas desse algoritmo são usualmente suportadas em muitos sistemas -- por exemplo, pela rotina qsort da biblioteca padrão da linguagem C.
Entre os principais atrativos de quicksort destacam-se o fato de que na maior parte dos casos sua execução é rápida e de que é possível implementar a rotina sem necessidade de espaço de memória adicional. Uma desvantagem de quicksort é que todos os elementos devem estar presentes na memória para poder iniciar o processo de ordenação. Isto inviabiliza seu uso para situações de ordenação on the fly, ou seja, onde o processo de ordenação ocorre à medida que elementos são definidos.

Tabelas e Busca

Tabelas
Tabela é uma das estruturas de dados de fundamental importância para o desenvolvimento de software de sistema. Um de seus usos principais é na construção de tabelas de símbolos, amplamente utilizadas em compiladores e montadores. Tabelas são também amplamente utilizadas em sistemas operacionais para a manutenção de informação de apoio à execução de programas, como as tabelas de processos e as tabelas de arquivos.
Uma tabela é um agregado de elementos armazenados na forma de pares chave,valor, de tal forma que é possível ter acesso a valor (que pode eventualmente ser uma estrutura complexa) a partir da chave Assim, deve ser possível obter o valor def a partir da especificação da chave





Em uma tabela de símbolos, a chave é usualmente o nome de uma variável e o valor é o conjunto de informações sobre a variável, tais como o seu tipo, endereço de memória e local de definição. Já em uma tabela de arquivos, a chave pode ser um identificador inteiro (por exemplo, o terceiro arquivo aberto pelo processo) e o valor o conjunto de informaçòes sobre o arquivo, tais como a posição corrente no arquivo.
Sob o ponto de vista funcional, a operação essencial associada a uma tabela é a busca de um valor a partir da especificação de uma chave:

GETVALUE(tabela,chave)
retorna o valor correspondente à chave especificada, se esta estiver presente na tabela; caso contrário, retorna uma indicação (por exemplo, um valor nulo) de que a chave não existe na tabela indicada.
Caso a tabela seja estática, ou seja, tenha um conteúdo que é determinado no momento da construção da tabela e não é alterado durante seu processamento, essa é a única operação definida para a manipulação da estrutura de dados, pois tais tabelas são utilizadas exclusivamente para consultas. Exemplos de tabelas desse tipo são as tabelas que descrevem as instruções de um processador, usadas em montadores.
Para a manipulação de tabelas que podem ter seu conteúdo construído e modificado ao longo da execução de um programa faz-se necessário definir outras operações, tais como:
INSERT(tabela,chave,valor)
é o procedimento para inserir uma nova informação na tabela;
REMOVE(tabela,chave)
é o procedimento para retirar da tabela o elemento que tem a chave especificada.


Busca
A operação GETVALUE, apresentada como a operação essencial na manipulação de uma tabela, é a implementação de um procedimento de busca, essencial para qualquer estrutura de dados. Embora detalhes desse procedimento sejam específicos de cada estrutura de dados, alguns princípios são comuns.
Em geral, estruturas cujo conteúdo são mantidos sem ordem serão mais simples de criar, porém demandarão mais tempo de busca. Na seqüência serão apresentados os dois mecanismos básicos de busca no contexto de tabelas, a busca linear e a busca binária. Os dois procedimentos poderiam ser utilizados para a implementação de GETVALUE, mas a busca binária demanda que as entradas na tabela sejam mantidas em ordem pelo valor da chave.



Busca linear
No caso da implementação mais simples de uma tabela, as suas entradas poderiam estar em qualquer ordem -- por exemplo, a ordem em que foram criadas. Neste caso, a operação de busca por um valor tem que ser exaustiva, ou seja, eventualmente todas as entradas deverão ser pesquisadas a fim de determinar se a chave está ou não presente na tabela.
Este procedimento de busca linear está descrito de forma simplificada no Algoritmo. Neste algoritmo, os argumentos de entrada são a tabela onde a busca será realizada e a chave de busca.






Esse algoritmo começa a analisar a tabela a partir da primeira posição, podendo potencialmente analisar todas as posições da tabela -- a máxima quantidade de posições analisáveis está restrita ao número de elementos na tabela. A chave associada a cada entrada da tabela é comparada com a chave de busca. Caso as duas chaves sejam iguais, a entrada foi encontrada e o algoritmo encerra retornando o valor associado à chave para essa entrada. Caso a busca chegue ao final da tabela sem que a chave especificada tenha sido encontrada, o algoritmo encerra retornando o valor especial NIL.
O atrativo desse procedimento é a simplicidade. Porém, seu uso está restrito a tabelas pequenas, pois para tabelas grandes ele é muito ineficiente. O tempo de pesquisa cresce linearmente com o número de entradas na tabela, ou seja, o algoritmo apresenta complexidade temporal .

Busca binária

Um mecanismo mais eficiente de busca é análogo àquele utilizado ao procurar uma palavra no dicionário. Faz-se uma estimativa da posição aproximada da palavra e abre-se na página estimada. Se a palavra não foi encontrada nessa página, pelo menos sabe-se em que direção buscar, se mais adiante ou mais atrás no dicionário. O processo de estimar a nova página de busca repete-se até que a página com a palavra desejada seja encontrada. Esse mecanismo de busca só é possível porque as palavras estão ordenadas no dicionário. Se o dicionário mantivesse as palavras sem nenhuma ordem, apenas a busca linear seria possível. Da mesma forma, a busca em uma tabela pode ser melhorada se seu conteúdo estiver ordenado.
O algoritmo de busca binária utiliza exatamente esse princípio. No caso, a estimativa que é feita para a posição a ser buscada é a posição mediana do restante da tabela que falta para ser analisado. No início, o restante é a tabela toda; assim, a primeira posição analisada é a entrada no meio da tabela. Se não for a entrada buscada, analisa-se a metade que resta, ou a inferior (se a chave encontrada tem valor maior que a que se busca) ou a superior (em caso contrário). O procedimento assim se repete, até que se encontre a chave buscada ou que a busca se esgote sem encontrar essa chave.
O Algoritmo descreve essa forma de busca. Os dois argumentos são, como para o algoritmo de busca linear, a tabela e a chave de busca. Também como no caso anterior, o valor retornado é o valor associado à chave na tabela ou NIL se a chave não for encontrada. As variáveis bot, mid e top referem-se a posições na tabela -- respectivamente o início, o meio e o fim da área da tabela ainda por ser pesquisada.








Uma diferença entre os dois algoritmos de busca apresentados é que neste assume-se que a tabela está ordenada. A manutenção da ordem em uma tabela dá-se através de procedimentos auxiliares de ordenação, uma das áreas relevantes de estudos em estruturas de dados.
As situações especiais que podem ocorrer nesse processamento de busca incluem o tratamento de mais de uma entrada na tabela com a mesma chave e a situação na qual nenhuma entrada é encontrada para a chave. Tais situações devem ser tratadas, em princípio, pela aplicação, que saberá qual ação deve ser tomada em cada um desses casos.

Tipo de dado

Origem: Wikipédia

Em ciência da computação tipos de variáveis ou dados é uma combinação de valores e de operações que uma variável pode executar, o que pode variar conforme o sistema operacional e a linguagem de computador. São utilizados para indicar ao compilador ou interpretador as conversões necessárias para obter os valores em memória durante a construção do programa. Por outro lado, ajudam também o programador a detectar eventuais erros (maioritariamente sintáticos).
Dependendo da linguagem de programação, o tipo de um dado é verificado diferentemente, de acordo com a análise léxica, sintática e semântica do compilador ou interpretador da linguagem. Os tipos têm geralmente associações com valores na memória ou com objetos (para uma linguagem orientada a objeto) ou variáveis.
Tipo estático e dinâmico
A verificação do tipo de um dado é feita de forma estática em tempo de compilação ou de forma dinâmica em tempo de execução. Em C, C++, Java e Haskell os tipos são estáticos, em Scheme, Lisp, Smalltalk, Perl, PHP, Visual Basic, Ruby e Python são dinâmicos.
Em C uma definição estática do tipo de uma variáveis ficaria assim:

printf("O tipo char ocupa %d bytes\n", sizeof(char));

Tipo forte e fraco

Linguagens implementadas com tipos de dados fortes, tais como Java e Pascal, exigem que o tipo de dado de um valor seja do mesmo tipo da variável ao qual este valor será atribuído. Exemplo:(Sintaxe genérica)1. Declarar Variáveis2. TEXTO nome3. INTEIRO idade4.5. Atribuições6. nome = "Fulano"7. idade = "13"
Ocorrerá um erro ao compilar a linha 7, pois o valor "13" precisa ser convertido para o tipo de dado INTEIRO.
Em linguagens com tipos de dados fracos, tais como PHP e VBScript, a conversão não se faz necessária, sendo realizada implicitamente pelo compilador ou interpretador.



.

Estrutura de dados

Origem: Wikipédia


Estruturas de dados e algoritmos são temas fundamentais da ciência da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados de forma coerente, caracterizam uma forma, uma estrutura de dados. São a organização e os métodos que manipulam esta determinada estrutura que lhes conferem singularidade. As estruturas de dados são chamadas tipos de dados compostos que dividem-se em dois: homogêneos e heterogêneos . As estruturas homogêneas são conjuntos de dados formados pelo mesmo tipo de dado primitivo. As estruturas heterogêneas são conjuntos de dados formados por tipos de dados primitivos diferentes em uma mesma estrutura. A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução bastante trivial. O estudo das estruturas de dados está em constante desenvolvimento , mas apesar disso, existem certas estruturas clássicas que se comportam como padrões.


Lista
Uma Lista é uma estrutura de dados linear. Uma lista ligada é linear e dinâmica, composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula.
A principal diferença entre as listas e os vetores é que as listas implementam alocação dinâmica de memória.


Pilha
As pilhas são estruturas baseadas no princípio LIFO (last in, first out), onde os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.


Fila
As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila.
A operação ENQUEUE sempre pode ser executada, uma vez que teoricamente uma fila não tem limite. A operação DEQUEUE só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.


Árvores
Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:
uma estrutura (uma árvore);
um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)
Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.


Árvores binárias
Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos. São muito utilizadas como estruturas de buscas, como árvores de busca binária e árvores AVL.
Uma árvore binária é uma estrutura de dados.

Estrutura elementar de dados

Estruturação elementar de dados: vetores e matrizes, registros, apontadores.
Estruturas elementares; pilhas, filas, filas duplas
Recursão e retrocesso
Árvores binárias: representação e percursos
Árvores generalizadas: representação e percursos
Aplicações de árvores: busca, filas de prioridade, árvores balanceadas, árvores B
Listas generalizadas
Espalhamento (hashing)
Tipo abstrato de dados
Alguns problemas clássicos:
Ordenação de vetores
Busca de cadeias
Gerenciamento de memória
Algoritmos em grafos




Mensagem da semana:

"Um novo mundo é possivel, um mundo de alternativas e possibilidades"
Boaventura Souza Santos

Tipos de dados

Tipos de dados
A organização de uma estrutura de dados é construída a partir de alguns blocos básicos, presentes na maior parte das linguagens de programação de alto nível. A partir desses blocos elementares (os tipos escalares) e de operadores das linguagens de programação, construções mais complexas podem ser definidas, tais como arranjos e estruturas.