Introdução (Informal) à Programação
Pedro Barahona
DI/FCT/UNL
Introdução aos Computadores e à Programação
1º Semestre 2007/2008
Programa e Algoritmo
• Um programa é um conjunto de instruções que
aplicadas aos dados de entrada (input) e a outros
intermédios auxiliares produz um resultado (output).
input
Programa
output
• Um programa é a materialização para uma dada
máquina (computador e linguagem de programação)
de um algoritmo.
14 de Setembro de 2007
Introdução (Informal) à Programação
2
Níveis de Abstração
• Um programa pode ser entendido a vários níveis de
abstracção (detalhe).
• Quanto mais “inteligente/conhecedor” for o
interlocutor, a mais alto nível podem ser dadas as
instruções.
Saia da sala
Vá para Lisboa
Saia do Edifício
Dirija-se à portaria
Vá para a paragem de autocarro
Apanhe o autocarro
....
14 de Setembro de 2007
Introdução (Informal) à Programação
3
Níveis de Abstração
Nível Máquina e Nível “Humano”
• Um computador só executa instruções extremamente
simples. Por exemplo:
– Transferir palavras entre a memória e os registos
– Processar dados nos registos (p.ex. soma binária)
• Um programador humano raciocina a um nível mais
alto de abstração.
LDA 1005
CA+B
LDB 22345A91
ADD A,B
STA 1234FE88
14 de Setembro de 2007
Introdução (Informal) à Programação
4
Linguagens de Programação
• As linguagens de programação permitem a um utilizador
especificar um programa de uma forma semelhante ao
algoritmo.
• Um compilador/interpretador da linguagem deverá fazer a
tradução das intruções de alto nível para as de nível máquina
(por exemplo, manter os endereços de memória onde estão
guardadas as variáveis).
LDA 11A810A0
CA+B
LDB 22345A91
ADD A,B
STA 1234FE88
14 de Setembro de 2007
Introdução (Informal) à Programação
5
Linguagens de Programação (2)
• Existem vários tipos de linguagens de programação baseadas em
diferentes paradigmas (estilos) de programação.
– Linguagens imperativas:Fortran, Pascal, C, Octave/MATLAB
• Controle explícito da execução
– Linguagens Orientadas por Objectos: Smalltalk, C++, Java
• Controle implícito na manipulação dos dados
– Linguagens Funcionais: LISP, Scheme
• Baseadas na especificação de funções
– Linguagens Lógicas: Prolog
• Implementando a Lógica de Predicados
14 de Setembro de 2007
Introdução (Informal) à Programação
6
Programação Imperativa
• No paradigma de programação imperativa, o programador
especifica explicitamente o controle de execução, isto é, a
sequenciação das instruções base.
• Informalmente podemos considerar as seguintes instruções
base, na especificação de algoritmos:
– Afectação:
A Expressão
• A variável A toma o valor da Expressão
– Entrada:
Entra A
• A variável A toma um valor dado do exterior (teclado, ficheiro)
– Saída:
Sai A
• A variável A é passada para o exterior (monitor, ficheiro)
14 de Setembro de 2007
Introdução (Informal) à Programação
7
Controle de Execução
• A ordem pela qual as várias instruções são executadas é
controlada explicitamente por instruções de
– Sequência
– Execução Condicional
– Execução Repetida
• Sequência (“;”)
– Exemplo:
entra A ; % O valor de A é “entrado”. Seja A = 2
B  A + 3 ;
% A variável B toma o valor 2+3 = 5
C  B * 2 ;
% A variável C toma o valor 5*2 = 10
sai C ;
% O valor de C é passado para o exterior
14 de Setembro de 2007
Introdução (Informal) à Programação
8
Controle de Execução
• Execução condicional (“se”)
– Exemplo:
entra A ;
se A > 0 então
B  A
senão
B  - A
fim se;
sai B ;
14 de Setembro de 2007
% o valor de A é “entrado”
% à variável B é atribuído
% o valor absoluto
% da variável A
% o valor de B é comunicado
Introdução (Informal) à Programação
9
Controle de Execução
• Execução Repetida (“enquanto”)
– Exemplo:
entra A;
B  1;
enquanto A > 1 fazer
B  B * A;
A  A – 1;
fim enquanto;
sai B;
14 de Setembro de 2007
% o valor de A é “entrado”
% o valor de B é inicializado a 1
% à variável B é atribuído
% o factorial de A
% o valor de B é comunicado
Introdução (Informal) à Programação
10
Tipos de Dados Simples
• Às variáveis usadas têm sido atribuídos valores inteiros. No
entanto podem ser considerados outros valores nos algoritmos
(e programas).
• Os tipos de dados simples habituais são
– Booleanos (Verdade/Falso ou 1/0)
– Numéricos (Inteiros, Reais e Imaginários)
– Não numéricos (caracteres)
• Normalmente o contexto torna claro os tipos de dados
pretendidos para as variáveis, mas as linguagens de
programação típicas (não o Octave) requerem a declaração dos
tipos de dados das variáveis.
14 de Setembro de 2007
Introdução (Informal) à Programação
11
Estruturas de Dados
• Os dados simples podem ser agrupados em estruturas de dados
mais complexas.
• As estruturas mais vulgares correspondem a matrizes de
dimensão arbitrária.
• Um caso
(vectores).
importante são as
matrizes unidimensionais
• Como o nome indica (MATrix LABoratory), o sistema Octave
/MATLAB tem um suporte muito completo dos tipos de dados
matriz, permitindo a sua definição e as operações habituais.
14 de Setembro de 2007
Introdução (Informal) à Programação
12
Estruturas de Dados
• Exemplo 1:
1 2 3
A = [1 2 3 ; 4 5 6 ; 7 8 9]
A =
4 5 6
7 8 9
• Exemplo 2:
3 3 3
B = [3 3 3 ; 2 2 2 ; 1 1 0]
B =
2 2 2
1 1 0
• Exemplo 3:
4 5 6
C = A + B
C =
8 9 9
• Exemplo 4:
D = 30 36 42
D = [1 2 3] * A
14 de Setembro de 2007
6 7 8
Introdução (Informal) à Programação
13
Algoritmo 1 – Raízes da equação do 2º grau
entra A ;
entra B ;
% Ax2 + Bx + C = 0
entra C ;
Disc  B^2 – 4 * A * C;
se Disc < 0 então
sai ‘não há raízes reais’
senão
D  sqrt(Disc);
se D = 0 então
sai ‘ 2 raízes iguais’
R  -B/(2*A);
sai R
senão
R1  (-B + D)/(2*A); sai R1;
R2  (-B - D)/(2*A); sai R2;
fim se;
fim se;
14 de Setembro de 2007
Introdução (Informal) à Programação
14
Algoritmo 2 – Cálculo da Raiz Quadrada
X = sqrt(A)

U * L = A

L = A / U
Assumindo Li  X  Ui, o intervalo [Li, Ui] pode ir sendo
reduzido até convergir no valor de X = sqrt(A).
L1 A
U1
L1 L2
L3
14 de Setembro de 2007
U2
U1
Li = 2 / Ui
U3
Introdução (Informal) à Programação
15
Algoritmo 2 – Cálculo da Raiz Quadrada
Z = sqrt(X)  X * X = 2
entra X ;
entra P ;
% P: precisão pretendida

L= 2/U
i
Li
Ui
1
0.04000
50.00000
2
0.07994
25.02000
U  10000000 ;
L  X / U ;
enquanto U-L >= P fazer
U  (U + L)/2;
L  X / U;
fim enquanto;
Sai U ;
3
0.15936
12.54997
4
0.31473
6.35467
5
0.59975
3.33470
6
1.01666
1.96723
7
1.34053
1.49194
8
1.41219
1.41624
% U  sqrt(X)
9
1.41421
1.41422
14 de Setembro de 2007
Introdução (Informal) à Programação
16
Algoritmo 3 – Maior Divisor Comum”
A
56
B
182
X
182
126
70
56
42
28
14
Y
56
56
56
14
14
14
14
14 de Setembro de 2007
-
=
=
=
=
=
=
=
C
126
70
14
42
28
14
0
C  X – Y
novo X  max(Y,C)
novo Y  min(Y,C)
Introdução (Informal) à Programação
17
Algoritmo 3 – Maior Divisor Comum”
entra A ; entra B ;
Se A > B então
X  A; Y  B;
senão
X  B; Y  A;
fim se
D  A - B
enquanto D > 0 fazer
se D > Y então
X  D;
senão
X  Y; Y  D;
fim se
D  X-Y;
fim enquanto
sai X
14 de Setembro de 2007
A
56
B
182
X
182
126
70
56
42
28
14
Y
56
56
56
14
14
14
14
Introdução (Informal) à Programação
-
=
=
=
=
=
=
=
C
126
70
14
42
28
14
0
18