Ce Pesquisa

Relatório 1 - Pesquisa de Dados

Este relatório visa apresentar uma síntese da Apostila de Algoritmo Estruturado, Projeto de Algoritmos: Com implementação em Pascal e C – Capítulo 1 e Capítulo 5, abrangendo algoritmos sua estrutura e ordenação.

Um algoritmo pode ser visto como uma sequencia de ações executáveis para a obtenção de uma solução para um determinado tipo de problema. Para escrevermos um algoritmo deve-se definir uma sintaxe e uma semântica, para que seja permitido uma única interpretação das suas instruções.

A estrutura de um algoritmo consiste em: Nome_Do_Algoritmo, Declaração das variáveis, Declaração dos procedimentos, declaração das funções, início, corpo do algoritmo e fim.

As variáveis são unidades básicas de armazenamento das informações a nível da linguagem de programação. Os tipos de dados e variáveis utilizados dependerá da finalidade dos algoritmos. Exemplos de tipos de dados: Inteiro (qualquer numero inteiro, nulo, negativo ou positivo), Real (qualquer número real, negativo, nulo ou positivo), Caracter (Caracteres alfanuméricos) e Lógico ou boleano (armazena valores V e F, verdadeiro e falso, respectivamente).

Os comandos de entrada e saída são a troca de informações entre o nosso mundo e a máquina. Exemplos: Comando de Entrada de Dados (Leia (varivael_1, variável_2) e comando de saída de dados (Imprima(expressão_1, expressão_2).

Comandos de Controle de Fluxo possuem os seguintes mecanismos: Sequencia (delimitado pelos identificadores Inicio e Fim), Seleção (utilizado para tomar decisões de acordo com uma condição) e Repetição (utilizada para efetuar açoes repetidas vezes).

Tipos de dados são estruturas compostas por um conjunto de variáveis. Exemplos: Vetor (unidimensional de mesmo tipo e numero fixo de elementos), Matriz (Pode possuir n dimensões) e Registro (Conjunto de variáveis de diferentes tipos, agrupadas em uma só unidade).

Para a construção de programas extensos pode-se utilizar a modularização, que divide o programa em pequenas etapas tais como: módulos, rotinas, sub-rotinas ou sub-programas. Isso permite reaproveitar o código, evitando escrevê-lo diversas vezes em situações repetitivas. Os procedimentos são compostos de um cabeçalho que contém o nome do procedimento e seus parâmetros. Pode-se fazer referência ao procedimento de qualquer ponto do algoritmo, através do seu nome e parâmetros.

Os parâmetros podem ser de entrada( são passados por valor e não podem ser alterados pelo procedimento) ou de entrada/saída (são passados por referência).

Funções é semelhante ao procedimento e deve retornar um valor em seu nome obrigatoriamente. Deve-se declarar o seu tipo, no cabeçalho da função. Ex: NomeDaFunção [(paramentro)]: tipo_da_função.

Os algoritmos de pesquisa devem ser projetados para garantir a confiabilidade e eficiência exigidas pela importância das aplicações existentes. A pesquisa de dados pode ser efetuada em unidades de memória secundárias quanto na memória principal do computador.

Pesquisa sequencial compreende a busca realizada de um elemento numa sequencia, percorrendo a partir do seu início, efetuando comparações, até o elemento ser encontrado.

A pesquisa binária é utilizada em programas grandes em que há sequencia de tamanhos consideráveis.Neste caso o vetor de entrada tem que estar ordenado.

Algoritmos de Ordenação: Divide-se em 3 tipos:

1) Selection Sort: Seleciona o menor elemento da sequência considerada e coloca-o no inicio;

2) Bubble Sort: Consiste de comparações e trocas entre elementos consecutivos da sequência, enviando o maior elemento para a ultima posição;

3) Insertion Sort: Com o primeiro elemento da sequencia forma-se uma sequencia de tamanho 1 ordenada, cada elemento restante da sequencia original é inserido na sequencia, de modo que esta permaneça ordenada, quando um elemento é inserido a frente de outro, estes deverão ser deslocados de uma posição.

No capítulo 1 do livro Projeto de Algoritmos: com implementação em Pascal e C, foram descritos os tipos de dados e tipos abstratos de dados em que podemos denominar tipos simples de dados, os grupos de valores indivisíveis, como os tipos básicos integer, boolean, char, e real do Pascal. Enquanto que o tipo abstrato de dados podem ser considerados generalizações de tipos primitivos de dados. Esses tipos abstratos de dados podem ser usados para encapsular tipos de dados. O exemplo citado, no referido capítulo, é de uma lista de inteiros com as seguintes operações: 1. Faça a lista vazia; 2. Obter o primeiro elemento da lista, caso a lista esteja vazia então o retorno deve ser nulo; 3. Insira um elemento na lista.

Após a criação e análise de um programa devemos implementá-lo em um computador. É de suma importância analisar a medida do custo de execução.

A medida do custo de execução de um algoritmo depende principalmente do tamanho da entrada dos dados. Por isso é comum considerar-se o tempo de execução de um programa como uma função do tamanho da entrada. Entretanto, para alguns algoritmos, o custo de execução é uma função da entrada particular dos dados, não apenas do tamanho da entrada. Temos então que distinguir o melhor caso, pior caso e caso médio. O melhor caso é aquele com menor tempo de execução sobre todas as possíveis entradas de tamanho n. O pior caso é o maior tempo de execução sobre todas as entradas de tamanho n e o caso médio corresponde à mpedia dos tempos de execução de todas as entradas de tamanho n.

Temos como exemplo, o acesso dos registros de um arquivo. Cada registro contém uma chave única que é utilizada para recuperar registros do arquivo. Dada uma chave qualquer o problema consiste em localizar o registro que contenha esta chave. 0 algoritmo de pesquisa mais simples que existe é o que faz uma pesquisa seqüencial.

Este algoritmo examina os registros na ordem em que eles aparecem no arquivo, até que o registro procurado seja encontrado ou fique determinado que o mesmo não se encontra no arquivo.

0 melhor caso ocorre quando o registro procurado é o primeiro consultado. 0 pior caso ocorre quando o registro procurado é o último consultado ou não está presente no arquivo, sendo assim, é necessários realizar n comparações.

Um programa criado na linguagem de programação Pascal, começa com um cabeçalho, rótulos, constantes, tipos, variáveis, procedimentos e funções declarados nesta ordem. Segue a estrutura Pascal:

program cabeçalho do programa

label declaração