Algoritmo e Estrutura de Dados

Algoritmo e Estrutura de Dados

(Parte 1 de 10)

José Vasconcelos Luís Paulo Reis

Engenharia do Ambiente

Engenharia Civil

Engenharia Informática Engenharia da Qualidade

1º ANO Março 2002

Programação I Universidade Fernando Pessoa

1ALGORITMOS E A RESOLUÇÃO DE PROBLEMAS.........................................3
1.1. RESOLUÇÃO DE PROBLEMAS3
1.2. APROXIMAÇÃO DESCENDENTE (TOP-DOWN APPROACH)4
1.3. NOÇÃO FORMAL DE ALGORITMO6
1.4. CARACTERÍSTICAS DE UM ALGORITMO6
2. ESTRUTURAS DE DADOS7
2.1. ESTRUTURAS DE DADOS PRIMITIVAS8
2.1.1. Tipo de dados booleano8
2.1.2. Tipo de dados numérico8
2.1.3. Tipo de dados alfanumérico9
2.1.4. Representação dos dados9
2.2. ESTRUTURAS DE DADOS NÃO PRIMITIVAS12
2.2.1. Vectores12
2.2.2. Matrizes13
3. NOTAÇÃO ALGORÍTMICA14
3.1. PSEUDOCÓDIGO14
3.1.1. Instrução de atribuição15
3.1.2. Leitura e escrita de dados16
3.1.3. Estrutura condicional17
3.1.4. Instruções de repetição18
3.1.5. Operações e Expressões Aritméticas21
3.1.6. Operadores e operações relacionais21
3.1.7. Operadores e operações lógicas2
3.2. ALGORITMOS PROPOSTOS23
3.3. DIAGRAMAS DE FLUXO (FLUXOGRAMAS)30
3.3.1. Notação gráfica30
3.3.2. Fluxogramas vs. Estruturas de controlo30
3.3.3. Algoritmo em pseudocódigo / Fluxograma3

Programação I Universidade Fernando Pessoa

Algoritmos e a Resolução de Problemas

A programação de computadores é uma disciplina na área das ciências da computação e refere-se essencialmente ao estudo de estruturas de dados e a sua manipulação para a resolução de problemas em diversos domínios do conhecimento.

Um programa de computador envolve a definição de um algoritmo para a resolução de um problema. Um algoritmo é representado através de expressões simbólicas de modo a descrever e a encontrar a solução de problemas do mundo real.

Um algoritmo representa uma sequência finita e não ambígua de instruções elementares bem definidas, conducente à solução de um determinado problema, cada uma das quais pode ser executada mecanicamente numa quantidade finita de tempo.

As estruturas de dados representam de modo simbólico entidades e objectos do mundo real e definem a parte estática de um algoritmo. A manipulação das estruturas de dados através de declarações e instruções precisas de controlo definem a parte dinâmica de um algoritmo. Este conjunto de estruturas de dados e de controlo constituem formalmente um algoritmo para a resolução de problemas.

1.1. Resolução de Problemas

A resolução de um problema através de um algoritmo e consequente programa computacional refere-se ao processo de identificar e analisar um problema do mundo real e desenvolver a sua solução de modo eficiente. Este processo é constituído pelas seguintes fases: (1) identificação e compreensão do problema (e objectivos), (2) conceptualização da solução, (3) definição do algoritmo para a resolução do problema, e (4) implementação (codificação) da solução através de um programa computacional.

A tarefa de escrever um algoritmo pode ser simplificada através da decomposição e análise de subproblemas. O processo de estruturação na resolução de problemas reflecte-se num programa modular constituído por diferentes partes que definem a solução do problema (figura 1).

Problema / Objectivo ÞÞ Passos de Resolução

Figura 1: Abordagem para a resolução de problemas Definição de módulos

Subproblemas Sub-objectivos

Programação I Universidade Fernando Pessoa

A aproximação descendente (top-down) para a resolução de problemas do mundo real permite raciocinar e estruturar a solução de um problema em linguagem natural (ex.: Português). Este tipo de abordagem facilita o processo de compreensão do problema, assim como a conceptualização do problema/objectivo em subproblemas/sub-objectivos e respectiva solução.

Os próximos exemplos (1 e 2) ilustram dois problemas simples e a notação

Exemplo 1: Substituir uma lâmpada fundida de um candeeiro.

Algoritmo Mudança de Lâmpada

1Seleccione uma nova lâmpada
2Remova a Lâmpada fundida
3Insira uma nova lâmpada
1.1Seleccione uma lâmpada da mesma potência da fundida
2.1Posicione a escada em baixo do candeeiro
2.2Suba a escada até que possa atingir a lâmpada

Passo Descrição

2.3 Rode a lâmpada no sentido contrário ao dos ponteiros do relógio até que se solte

3.1Coloque a nova lâmpada no orifício correspondente

3.2 Rode a lâmpada no sentido dos ponteiros do relógio até que fique presa

3.3Desça da escada

Definição mais precisa para o passo 1.1

Seleccione uma lâmpada candidata à substituição Se a lâmpada não é da mesma potência da antiga, então repita até encontrar uma correcta:

Pouse a lâmpada seleccionada Seleccione uma nova lâmpada

Programação I Universidade Fernando Pessoa

descrições mais precisas e detalhadas, do tipo: Repitaaté ...

· Por exemplo, para os passos 2.2, 2.3, 3.2 e 3.3 poderiam também derivadas • Aumento do detalhe do algoritmo pode continuar quase indefinidamente.

• Grau de detalhe depende das necessidades do agente que vai executar o algoritmo.

Exemplo 2: Encontrar o número de telefone que corresponde a um dado nome numa lista telefónica.

Algoritmo Lista-Telefónica

1Encontre a página da lista que contém o último apelido do nome
2Encontre na página determinada no passo 1, o nome procurado

Passo Descrição

Aumentando o detalhe, obtemos instruções elementares não ambíguas:

1.1 Coloque o marcador D (dedo) ao acaso na lista 1.2 Abra a lista

1.3 Último apelido está contido numa das páginas (esquerda ou direita)? Se sim, siga para o passo 2

1.4 Último apelido precede a página esquerda? Se sim, coloque o marcador atrás da página esquerda; se não, coloque o marcador à frente da página direita.

1.5 Vá para 1.2 (retome a sequência de instruções no passo 1.2)

Eliminando formulações mal definidas (ex.: coloque o marcador atrás):

1.1.1 Torne A igual ao apelido do nome a seleccionar (atribuição à variável A)

1.1.2 Escolha uma posição n ao acaso no intervalo [1,N] (n representa o número de páginas útil da lista) 1.1.3 Torne D igual a n (atribua à variável D o valor n) 1.2 Abra a lista no local seleccionado pelo marcador D

1.3 A está contido numa das páginas (esquerda ou direita)? Se sim, siga para o passo 2.

1.4 A precede o primeiro apelido da página esquerda? Se sim, faça n igual a (n+1)/2 (actualização do valor de n); se não, faça n igual a (N+n)/2.

1.5 Vá para 1.2 (retome a sequência de instruções no passo 1.2)

Programação I Universidade Fernando Pessoa

1.3. Noção formal de algoritmo

Um algoritmo é um processo discreto (sequência de acções indivisíveis) e determinístico (para cada passo da sequência e para cada conjunto válido de dados, corresponde uma e uma só acção) que termina quaisquer que sejam os dados iniciais (pertencentes a conjuntos pré-definidos).

Um algoritmo é constituído por um conjunto de expressões simbólicas que representam acções (escolher, atribuir, etc.), testes de condições (estruturas condicionais) e estruturas de controlo (ciclos e saltos na estrutura sequencial do algoritmo) de modo a especificar o problema e respectiva solução.

1.4. Características de um Algoritmo

(Parte 1 de 10)

Comentários