Algoritmos
2001/2002
Sistemas de Informação para a Gestão
Diurno e Nocturno
1ºano
1ª semestre
Computadores e Linguagens de
Programação
Estrutura e funcionamento de um computador
Algoritmos e Lógica da Programação
 [AAZ95]
Azul, Artur Augusto, Técnicas e Linguagens de Programação,
Porto Editora 1995 (pgs 8 - 73)
António Tavares, 2001/2002
Acetato 1
1. Suporte físico à Programação
Compreender
O que é um programa e uma linguagem de programação
Como um programa se articula com um computador
Ter algumas noções básicas acerca da estrutura e do funcionamento de
um computador, as quais, apesar da evolução tecnologica, mantêm-se
inalteradas à mais de 30 anos
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 2
1.1. Estrutura e funcionamento de um computador
Esquema básico de um computador
Unidade Central de
Processamento
(CPU)
Dispositivos
de Input
Dispositivos
de Output
Memória Primária
Memória Secundária
Computador – máquina ou cnjunto de dispositivos electrónicos capazes
de processar informação
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 3
Componentes fundamentais
CPU (Central Processing Unit) – é a componente que realiza a parte
fundamental do trabalho do computador, e que consiste em processar
electronicamente dados ou informação
Esquema básico
de um microprocessador
Unidade de aquisição e de
interface com a memória primária
Unidade
Lógico
Aritmética
(ALU)
Unidade de
Controlo
Registos (Registers)
Memória
Primária
Na memória primária ou
central é armazenada
informação codificada, que vai
ser chamada ao processador,
para este realizar as
operações ou instruções
contidas nessa informação
A unidade de controlo envia aos outros componentes
sinais de activação e sincronização das operações
Os registos são pequenos circuitos de armazenamento
temporário de instruções e dados
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 4
Componentes fundamentais
Estrutura Simplificada de
uma Memória (RAM)
endereços
células
N
9
8
7
6
5
4
3
2
1
0
 O processador apenas entende os sinais
eléctricos que percorrem os circuitos que
o constituem
 Os computadores funcionam com o
sistema de informação bimário (zeros
e ums)
 BIT – inidade minima de informação com
que lida um SI (pode ser 0 ou 1)
 Byte – agrupamento de 8 bits
 Todos os dados e instruções que
circulam entre o processador e a
memória estão sobre a forma de bits e
têm significado quando resultam do
agrupamento de bits (bytes)
 Um programa é armazenado em
memória sobre a forma de uma
sequência de instruções (bytes) podendo
ser directamente executado pelo
processador – PROGRAMA OBJECTO
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 5
Execução de um programa
Informação que entra para um sistema informático

Instruções de programas

Dados manipulados por esses programas

Instruções e dados são armazenados temporáriamente na RAM e
codificadas e executadas no processador

Cada instrução é executada através de um ciclo de instrução
Ciclo de Instrução – processo que consiste em fazer com que cada instrução
passe da memória para o processador, para aí poder ser executada
1. Em cada instante, o processador contém num registo próprio (Instruction Pointer-IP
ou Program Counter-PC) o endereço ou posição de memória onde se encontra a
próxima instrução a ser executada
2. A unidade de controlo envia um sinal à memória pedindo o conteúdo da instrução
que está no endereço dado por IP
3. A instrução pedida é devolvida para um outro registo do processador (Instruction
Register – IR) para então ser descodificada e executada pelo
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 6
1.2. Níveis de um Sistema Informático
O Computador é um sistema que integra e articula dois tipos fundamentais de
componentes:
Físicos - Hardware (compon. mecânicos, electrónicos e electromecânicos)
Lógicos - Software (programas = conjunto de instruções codificadas)
O SW permite que a máquina física (o HW) deixe de ser apenas um
emaranhado de circuitos e passe a ser um um utensílio que pode realizar
tarefas complexas manuseável por pessoas
O SW permite criar uma abstracção do HW (uma Máquina Virtual)
O SW é ele próprio organizado em camadas, em que, camadas de
nível superior são abtracções de camadas de nível inferior
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 7
Tipos e camadas de Software
Utilizador
Software de
Aplicação
Software de
Sistema
Programas de
Aplicação
Programador
Software de
Programação
Interface de Comandos (Shell)
Núcleo (Kernel)
Hardware - Máquina
Sistema Operativo – actua como interface entre o HW e o utilizador ou os seus
programas de aplicação
Programas de aplicação - Processador de Texto; Folha de Cálculo; etc.
Sobrepõem-se ao sistema operativo
Um Sistema Informático pode ser visto como uma sucessão de máquinas virtuais
as quais são criadsa usando linguagens de programação
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 8
2. Linguagens de Programação
Linguagem de Programação - é um sistemna de escrita formal para enunciar a
execução de operações em computador
– tem uma terminologia ou um conjunto de termos, palavras e sinais, que
assumem determinados significados (sintaxe)
– ou conjunto de regras que estipulam o uso correcto dos termos, para
construir significados válidos (semântica)
Programa - é um conjunto de frases que utilizam os termos e as regras de uma
determinada linguagem de programação, com vista a concretizar determinados
objectivos
Algoritmo – forma ou fórmula para resolução de um determinado problema,
mediante o estabelecimento de determinadas regras e procedimentos.
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 9
2.1. Da Linguagem Natural à Linguagem Máquina
Linguagem Natural
Linguagens de Programação
de “Baixo nível”
(Assembly)
Programa-fonte
Assemblador
Programa
tradutor
Programa-objecto
ou executável
Linguagem máquina ou código-máquina
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 10
2.1. Da Linguagem Natural à Linguagem Máquina
Linguagem Natural
Linguagens de Programação
de “Baixo nível”
(Assembly)
Programa-fonte
Assemblador
Programa-objecto
ou executável
de “Alto Nível”
(Pascal, C, C++, Java, ...)
Programa-fonte
Programas
tradutores
Compilador
Interpretador
Programa-objecto
ou executável
Linguagem máquina ou código-máquina
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 11
2.1. Da Linguagem Natural à Linguagem Máquina
Linguagem Natural
Linguagens de Programação
de “Baixo nível”
(Assembly)
Programa-fonte
Assemblador
de “Alto Nível”
(Pascal, C, C++, Java, ...)
Compilador
Ou tradutor
Programa-fonte
Programas
tradutores
Programa-objecto
ou executável
Linguagem máquina ou código-máquina
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 12
2.1. Da Linguagem Natural à Linguagem Máquina
Linguagem Natural
Linguagens de Programação
de “Baixo nível”
(Assembly)
de “Alto Nível”
(Pascal, C, C++, Java, ...)
Programa-fonte
Programa-fonte
Linker - liga programas objecto - Reutilização
Programa
tradutor
Assemblador
Programa-objecto
Linker
Programa-objecto
Compilador
Programa
tradutor
Programa-objecto
Linguagem máquina
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 13
2.2. Ambientes de programação
Tipos de Ficheiros:
 Ficheiro de texto simples (ASCII) – informação em formato de caracteres =>
programa em código fonte
 Ficheiro binário – informação em formato binário => programa executável
(em formato binário directamente executável)
Ambiente de programação – apoia o programador nas tarefas habituais, desde
a escrita à complicação dos programas, passando pela detecção e correcção
dos erros que os programas possam conter. Ferramentas típicas:
– Editores
– Compiladores
– Depuradores (debbugers)
– Verificadores
– Geradores de dados para testes
– Linkers (ligadores)
– .....
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 14
2.3. A evolução das Linguagens de Programação
 Alguns aspectos que deram origem a evoluções das linguagens de
programação
– autonomia do código fonte
– satisfação de necessidades sectoriais (ex. matemática)
– maior estruturação na abordagem dos problemas
– melhor manutenção
– maior expressividade (Inteligência Artificial)
– geração de código
– reutilização de código
– maior aproximação entre a linguagem natural e as linguagens de
programação
– .......
 As linguagens foram sendo classificadas em gerações em função das
características que ofereciam, considerando-se que linguagens com
caracrterísticas semelhantes pertencem à mesma geração
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 15
2.3. A evolução das Linguagens de Programação
Complexidade do SW
Linguagens Orientadas
por Objectos
Linguagens estruturadas,
4GL
Primeiras linguagens
Linguagens máquina,
assembly
1960
António Tavares, 2001/2002
1970
1980
1990
01 – Computadores e Linguagens de Programação
2000
Acetato 16
2.3. A evolução das Linguagens de Programação
 Ling. 1ª geração
– Dependentes da máquina, ao mais baixo nível de abstracção.
– Codificação em Assembly
 Ling. 2ª geração
– Oferecem algum nível de abstracção e Introduzem as Bibliotecas de Software
 Ling. 3ª geração (Linguagens Estruturadas)
– Ricas em capacidades procedimentais e estrutuas de dados. Dividem-se em:
• General Purpose High Order Languages (Pascal, C, ...)
• Object Oriented Languages
 Ling. 4ª geração
– Sintaxe distinta para controlo e representação de estruturas de dados
– O seu elevado nível de abtracção elimina a necessidade de especificação
algoritmica exaustivamente detalhada
– Combinam características procedimentais com não-procedimentais
– Query Languages e Geradores de Aplicações.
 Ling. 5ª geração
– Linguagens não-procedimentais que permitem a declaração do problema a resolver
possuindo a própria linguagem mecanismos para a sua resolução
– Linguagens declarativas (Prolog)
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 17
2.3. A evolução das Linguagens de Programação
Fortran
Cobol
Primeiras Linguagens
Algol
Linguagens Estruturadas
Simula
Pascal
C
Linguagens percursoras
OO
Smalltalk
Linguagens
OO
Objective C
Módula-2
C ++
Ada
Eiffel
OO Pascal
Actor
Java
António Tavares, 2001/2002
C#
01 – Computadores e Linguagens de Programação
Acetato 18
2.4. Paradigmas de Linguagens de Programação
 Paradigma de programação
– define um modelo ou norma a seguir pelas linguagens de programação baseadas
no paradigma
 Programação procedimental, sequencial, imperativa ou estrutural
– O programa é uma sequência de comandos ou instruções que o programador
fornece ao computador e que este executa sequencialmente
 Programação declarativa
– O programador declara o conhecimento que o computador deve ter necessário à
resolução do problema e como este deve proceder para atingir a solução
 Programação funcional
– Os programas baseiam-se em principios matemáticos (funções e conjuntos)
 Programação OO
– Surge como uma evolução da programação estruturada e modular
– Os programas são substituidos por objectos que encapsulam dados e instruções
 .....
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 19
3. A Lógica da Programação
 Enfoque: Programação Estruturada
 Os Algoritmos
– permitem-nos partir dos problemas e obter os programas
– são a forma de lidar com a complexidade natural da actividade de
programação
– São a fase intermédia entre a compreensão do problema e a escrita do
programa numa linguagem de programação
 Algoritmo
– é uma sequência ordenada e precisa de passos, acções ou operações,
que conduzem à solução de um dado problema
– a sua formulação consiste na descrição de forma ordenada, com clareza e
rigor, das operações que se pretendem realizar em computador para
resolver um problema ou atingir determinados objectivos
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 20
3.1. Fases tipicas na elaboração de um programa
Análise do Problema
Tradução do programa-fonte
para código-máquina
Detecção de
erros de escrita
sim
não
Testes de verificação lógica
Detecção de
erros de lógica
Revisão do algoritmo
Tradução do algoritmo num
programa-fonte
Revisão do Texto
Formulação de um Algoritmo
sim
não
Programa Terminado
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 21
3.2. Entidades fundamentais da lógica de programação
 Nos algoritmos destinados a programas de computador, tem de se recorrer a
diversas estruturas de representação das acções ou operações a realizar
 Entidades fundamentais:
– Dados
– Instruções básicas
– Estruturas de controlo
– Condições ou expressões lógicas
– Subprogramas
 Um programa executa sequencialmente um conjunto de instruções básicas sobre dados
 São no entanto necessárias situações em que:
– Uma instrução tenha de ser repetida várias vezes
– Decidir sobre se deve ou não executar determinada instrução em função de uma determinada
condição
– Seleccionar a acção a realizar de entre um conjunto de alternativas
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 22
3.3. Exemplo:

Problema:
– É dado o preço de um terreno de forma rectangular, bem como as
medidas de dois dos lados adjacentes
– Pretendemos saber se o seu preço por metro quadrado está acima ou
abaixo da média dos preços praticados na zona (que nos é dado)

Formulação do algoritmo:
Táctica : decompor o problema em problemas mais simples
1. Temos de saber: o preço do terreno; a medida do lado A (em metros); a
medida do lado B (em metros); o preço médio por metro quadrado
2. Calcular a área do terreno: área = lado A x lado B
3. Calcular o preço por m2: preço por m2 = preço do terreno / área
4. Comparar os preços por m2
SE preço por m2 > preço médio ENTÃO o preço está acima da média
SE preço por m2 < preço médio ENTÃO o preço está abaixo ao da média
SENÃO o preço está abaixo da média
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 23
3.4. Formas de representar algoritmos
Existem essencialmente duas para a programação estruturada:
Fluxogramas – descrição gráfica
Pseudocódigo – descrição textual que se aproxima da linguagem
natural
Os Fluxogramas estão em desuso, pelo que vamos optar nesta
disciplina, em exclusivo, pela utilização do Pseudocódigo, e fazer um
paralelo constante entre o pseudocódigo e as linguagens de
programação que vamos utilizar.
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 24
Fluxogramas
Simbolos
Significado
Exemplo
Processamento em
geral
x x+1
Leitura/Escrita
de dados
Escreve x
Inicio/Fim
de Processamento
Inicio
Linha de Fluxo
Conector de Fluxos
Decisão condicional
X>5
Escolha múltipla
Caso x
Subprograma
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Rotina x
Acetato 25
Fluxogramas
Inicio
Ler valor 1
Ler valor 2
Valor 1 > Valor2
Não
Valor 1 > Valor2
Não
Sim
Escrever
Valor 1 é maior
Escrever
Valor 2 é maior
Escrever
Valores iguais
Fim
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 26
Pseudocódigo
Código de escrita que :
– utiliza uma combinação de termos convencionais para indicar as
instruções do programa
– os termos utilizados são usualmente um misto de palavras da
nossa linguagem natural com palavras e notações típicas das
linguagens de programação.
Características:
– Não tem um notação standard
– Tem maior proximidade com as linguagens de programação
permitindo diminuir o esforço gasto no desenvolvimento/codificação
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 27
Pseudocódigo
Início
Escrever (“Introduza dois valores”)
Ler (valor1)
Ler (valor2)
SE valor 1 > valor ENTÃO
Escrevrer (valor 1, “é maior”)
SENÃO
SE valor 1 < valor 2 ENTÃO
Escrever (valor 2, “é maior”)
SENÃO
Escrever (“valores iguais”)
Fim
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 28
3.5. Ciclo de obtenção do produto final
Ciclo: Formulação, Codificação, Compilação, Depuração
Situação/Problema
Programa Terminado
Formulação de um
algoritmo como solução
do problema
Diagramas
Fluxogramas
Pseudocódigo
Verificação e
depuração do
programa
Escrita de um programa tradução do algoritmo em
linguagem de programação
Linguagens de programação
António Tavares, 2001/2002
Programa em
código-máquina
Tradução do
programa-fonte em
linguagem-máquina
Compiladores
Interpretadores
01 – Computadores e Linguagens de Programação
Acetato 29
3.6. A abordagem Estruturada

Linguagens de Programação Estruturadas => Abordagem Estruturada

Abordagem Estruturada - abordagem sistemática da construção de SW
que os princípios como:
1. a separação das definições de dados e de programa
2. aconcepção descendente ou “Top-Down”
3. e refinamento progressivo
=> A separação das definições de dados e de programa
– Os programas surgem com duas partes principais bem diferenciadas:
– Parte declarativa: declaram-se os tipos de dados e variáveis a utilizar no corpo
das instruções do programa
– Parte operativa: o corpo de instruções com que se pretende concretizar as
operações e atingir os objectivos pretendidos
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 30
3.6. A abordagem Estruturada
=> A concepção descendente ou “Top-Down”
– É um método de abordagem dos problemas que se decompondo o problema
original em problemas particulares, em níveis sucessivamente mais concretos
até ao pormenor desejado
=> Refinamento Progressivo
– É um complemento lógico da abordagem descendente
– Consiste em ir concretizando, cada vez com mais detalhe, com maior
exactidãoe perfeição, os passos sucessivos do projecto em questão
– Muito útil no desenvolvimento de pseudocódigo

Abordagem Modular – apresenta semelhanças com a abordagem
estruturada, consistindo na decomposição de um problema complexo nos
seus componentes, aos quais se chamam módulos
– Os módulos são unidades com alguma autonomia, mas também
relacionáveis entre si, pois podem-se integrar (ligar) num todo
– Reutilização de bibliotecas de módulos
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 31
4. Componentes fundamentais de um programa
Estruturação e componentes fundamentais de um programa
“A estruturação de programas subdivide-se na estruturação das suas acções e na estruturação dos
seus dados.A escolha destas estruturas é o problema fundamental da programação estruturada.
Da escolha criteriosa destas estruturas depende que o programa seja eficaz, compreensível,
robusto, modular e versátil.
A sintaxe de uma linguagem define determinados construtores, de entre os quais os mais
importantes são as expressões e os comandos
Uma expressão é uma fórmula ou regra de computação que especifica um valor ou um resultado.
Uma espressão consiste em operandos e operadores.
Os operandos são constantes, variáveis, ou valores gerados por funções.
Os operadores são usualmente classificados em monádicos ou unários (operam sobre um único
operador) e diádicos (operam sobre dois operadores).
Um comando é uma formula que especifica uma acção que o computador deve executar para
produzir certo efeito”
Coelho, Helder
Programa = Dados + Instruções básicas + Expressões +
Estruturas de Controlo + Subprogramas
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 32
4.1. Dados
Dados – constantes, variáveis e identificadores





Qualquer programa opera com dados
Os dados podem ser utilizados sob a forma de constantes ou de variáveis
As variáveis são sempre associadas a identificadores e num dado instante apenas
podem conter um determinado valor (simples ou composto)
Identificadores são nomes que se atribuem a variáveis, constantes ou outros
elementos com que se opera num algoritmo
As variáveis pretencem sempre a um tipo de dados, o qual define o tipo de valores
que a variável pode conter ao longo do tempo
Variáveis versus constantes:


Uma constante é um dado directo, inserido directamnete numa instrução do algoritmo
Ex. Escrever (“Bem-Vindo”) e Escrever (1999)
Quando os dados são ser introduzidos, processados, calculados, ..., devemos usar
variáveis
Ler(quantidade, preço)
Total := quantidade*preço
Escrever(total)
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 33
Variáveis: identificadores e endereços de memória
Identificadores
de variáveis
Conteúdo
das variáveis
Nome
Ana
Endereços
de memória
Conteúdo das
células
1001
Ana
1002
Morada
Coimbra
1003
Coimbra
1004
Telefone
6000
1005
6000
1006
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 34
Tipos de dados
Tipos de Dados
Simples
Estruturados
Ficheiros
Matrizes
Ordinais
Registos
Predefinidos
Definidos pelo
utilizador
Dinâmicos
Ponteiros
Conjuntos
Ficheiros
Inteiros/Reais
Caracteres
Enumerados
Subconjuntos
Booleanos
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 35
Tipos de dados Simples
 Ficheiro: Os seus valores são de um
determinado tipo e estão armazenados num
ficheiro (memória secundária).
Simples
- Tipo pré-definido é o ficheiro de texto (String)
Ficheiros
- Existem tipos de ficheiros estruturados
 Inteiro: de –32xxx a 64000
Ordinais
 Real: de xx x 10-123 até xxx
 Caracter: Tabela ASCII
 Booleano: Verdadeiro ou falso
 Subconjunto enumerado
dias-úteis = (segunda, terça, quarta, quinta,
sexta)
 Subconjunto ordenado
Predefinidos
Inteiros/Reais
Caracteres
notas_validas = 0..20
maiúsculas = ‘A’..’Z’
António Tavares, 2001/2002
Definidos pelo
utilizador
Enumerados
Subconjuntos
Booleanos
01 – Computadores e Linguagens de Programação
Acetato 36
Tipos de dados Estruturados
São conjuntos ou estruturas que
agrupam dados simples ou também
outroa dados estruturados
 Array
Matriz de variáveis todas do mesmo tipo
 Registo
Agrupamentos de dados que podem ser
de tipos diferentes
 Conjunto
Agrupamentos de dados do mesmo tipo
sem repetições
Estruturados
Matrizes
Registos
Conjuntos
Ficheiros
 Ficheiro
Agrupamentos de dados do mesmo tipo
num ficheiro em meória secundária
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 37
4.2. Instruções básicas
 Instruções de escrita ou output
Escrever(“O resultado é:”, resultado)
 Instruções de leitura ou input
Ler (nome, morada, resultado)
 Instruções de atribuição
quantidade  500
preço  1,5
nome  “Silva”
resultado  preço * quantidade
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 38
4.3. Expressões
 Uma expressão é um conjunto de operandos articulados entre si por
operadores
 Os operandos podem ser dados directos, identificadores de
constantes ou variáveis.
 Os operadores agrupam-se em:
– Operadores aritméticos
+, - , *, /, ...
– Operadores relacionais ou de comparação
<, >, <=, >=, <>, =
– Operadores lógicos ou booleanos
e, ou, negação, ....
António Tavares, 2001/2002
01 – Computadores e Linguagens de Programação
Acetato 39