Programação Estruturada e Desenho de Algoritmos Flashcards
Solução de um problema
Definição do problema
Modelação matemática
(construção do modelo)
Determinação da solução
Análise dos resultados
- validação do modelo
- análise da solução
Definição do problema
Definir/descrever o problema real que se pretende resolver
Modelação matemática(Construção do modelo)
- O problema real é transformado num problema matemático, por uma
formulação matemática denominada modelo matemático - Geralmente, o modelo matemático possui mais soluções que o problema real
Determinação da solução
*Escolha do método
*Elaboração do algoritmo
*Implementação do algoritmo
*Obtenção da solução
Escolha do método mais apropriado
Devemos ter em conta:
*precisão desejada para os resultados
*capacidade do método em conduzir aos resultados desejados
*esforço computacional despendido (tempo de processamento e memória)
Elaboração do algoritmo
A descrição do algoritmo é feita por um conjunto de comandos que, quanto
ativados (executados), resultam numa sucessão finita de ações (acontecimentos)
- Em vez de se implementar um método diretamente numa linguagem de programação, é
preferível descrevê-lo por uma notação algorítmica
*é possível abstrair-se dos detalhes da linguagem de programação do computador e
concentrar-se apenas nos aspetos matemáticos do método (raciocínio matemático)
*melhora o entendimento do algoritmo, facilitando assim a implementação do método
em qualquer linguagem de programação
Implementação do algoritmo(codificação do programa)
*O algoritmo é implementado na linguagem de programação escolhida
*Uma vez que os aspetos matemáticos do método já foram pensados na fase de
elaboração do algoritmo, agora apenas é necessário preocupar-se com os detalhes de
implementação na linguagem adotada
Obtenção da solução(Execução do programa)
- O código obtido da implementação do algoritmo deve ser executado pelo computador
- Se for detetado algum erro lógico na fase de processamento (a execução do programa
produzir resultados inesperados), então deve-se regressar à fase de elaboração do
algoritmo para o corrigir - Se não for detetado qualquer erro lógico na fase de processamento, então foram
obtidos os resultados do modelo matemático (a solução)
Análise dos dados
*Verificar a consciência da solução obtida
*Validação do modelo
*Análise da solução
Verificar a consciência da solução obtida
para o modelo matemático (validação do modelo), e
- a sua adequação ao problema real (análise da solução)
Validação do mundo
Se a solução não for satisfatória para o modelo (modelo
não válido), então deve-se
* construir um novo modelo matemático (uma nova formulação matemática), e
* determinar as soluções do novo modelo matemático
Análise da solução
Alguns modelos matemáticos podem
* produzir várias soluções (e não apenas uma), e
* algumas delas (ou todas) não terem sentido (ex: tempo negativo, …)
Um dos objetivos desta etapa é identificar qual a solução válida para o problema real
entre as várias obtidas para o modelo matemático (se existirem)
Programação estruturada
*Define um conjunto de regras para elaboração de programas/algoritmos,
*baseia-se no desenho modular dos programas/algoritmos (programação modular), e
*baseia-se no refinamento gradual do topo para a base (método descendente)
*Segundo este paradigma um programa pode ser definido da seguinte forma:
Programa = Estrutura de Dados + Algoritmo
* um algoritmo manipula os dados, que podem ser de diversos tipos
* a estrutura de dados é o modo como os dados são organizados, acedidos e alterados
*A Programação Estruturada permite o desenvolvimento de algoritmos usando um
número restrito de estruturas básicas de controle, para a construção da lógica de
um programa
* qualquer algoritmo, independentemente da área de aplicação, da sua complexidade e da linguagem de programação usada na sua codificação, pode ser descrito através destas
estruturas básicas de controlo
Goto
Comando de desvio incondicional (saltos)
técnica independente da linguagem de programação usada, que tem como
objetivo construir programas claros, legíveis, eficientes e de fácil manutenção
- Programa escrito com indentação (realce), espaços em branco e comentários para
facilitar a leitura do mesmo
- Desenho descendente e segmentação em módulos (subprogramas/funções)
- Construção de módulos (subprogramas/funções) de tamanho adequado
- Declaração do domínio de ação das variáveis locais (dentro das funções) e
globais (no programa inteiro)
- Documentação do programa
Programação Linear
Usa desvios incondicionais (saltos) para construir a lógica do programa
- a instrução goto era usada para implementar tais desvios incondicionais e o seu uso foi
descontinuado com o aparecimento da programação estruturada
- dependendo do tamanho do programa, esta abordagem podia tornar muito difícil a
manutenção do programa para correção de erros ou simples evolução do programa
- linguagens que usam este paradigma: “FORTRAN”
Algoritmo
Descrição detalhada (passo a passo) do método escolhido
para determinar a solução do modelo matemático que representa o problema real
- o problema real tem dados que têm que ser tratados computacionalmente
- o modelo matemático que foi construído para representar matematicamente o problema
real, tem que definir os dados e os resultados do problema real matematicamente
- o método que foi criado para resolver o modelo matemático, é definido através de
expressões aritméticas e lógicas para tratar os dados e os resultados (solução)
Programa
Tradução de um algoritmo numa determinada linguagem de
programação, de modo que possa ser executado pelo computador
*é a expressão de um algoritmo
Um programa pode ser definido da seguinte forma (segundo o PPE):
Programa = Estrutura de Dados + Algoritmo
- as estruturas de dados tratam os dados, e
- o algoritmo manipula os dados
Estrutura de dados
Forma ou processo como os dados são organizados
e tratados (acedidos e alterados)
Elaboração de um algoritmo
É uma das fases mais importantes na resolução de
um problema real, pois traduz o método escolhido para resolver o modelo
matemático construído numa forma próxima da linguagem de programação
Passos na elaboração do algoritmo:
- identificar os dados de entrada
- identificar os dados de saída (resultados)
- identificar o que é preciso para transformar os dados de entrada nos resultados (método
dividir-para-conquistar)
- construir o algoritmo
- testar manualmente o algoritmo
- executar o algoritmo
Método Cartesiano de Dividir-para-Conquistar
Também conhecido por método descendente (“top-down method”) ou método
de refinamento passo-a-passo
- Consiste em
- decompor o problema principal em subproblemas (modularização)
- refinar os subproblemas até encontrar problemas mais simples,
- refinar até se chegar a um nível de detalhe que permita implementar o algoritmo na
linguagem de programação
Modularização
Permite dividir o programa em módulos, com subprogramas
claramente delimitados, que podem ser implementados, separadamente, por
diversos programadores de uma equipa
Características fundamentais de um Algoritmo
*Finitude
*Definição
*Entradas
*Saídas
*Eficiência
Finitude
Um algoritmo deve sempre terminar após em número finito de passos
Definição
Cada passo de um algoritmo deve ser precisamente definido; as ações devem ser definidas rigorosamente e sem ambiguidades
Entradas
Um algoritmo deve ter zero ou mais entradas (as quantidades que lhe são fornecidas antes do algoritmo iniciar)
Saídas
Um algoritmo deve ter zero ou mais saídas (as quantidades, com uma relação específica com as entradas)
Eficiência
Todas as operações devem ser suficientemente básicas de modo que
cada uma delas possa ser, em princípio, executada com precisão num tempo
finito por um ser humano usando papel e lápis
Representação de um algoritmo
Existem várias formas de representar um algoritmo (notação algorítmica)
- descrição narrativa (usando uma linguagem natural)
- fluxograma (ou diagrama de fluxo)
- pseudocódigo (ou pseudo-linguagem)
Variáveis
- Para resolver problemas no computador é necessário manipular dados, sejam
números ou caracteres - Se for necessário calcular o resultado de uma única operação, então
provavelmente o melhor seria utilizar uma calculadora - A utilidade de se escrever um programa aparece quando usamos variáveis que
possuem a capacidade de guardar valores; é então possível calcular o resultado
de várias operações - As variáveis são identificadas por um nome (o chamado identificador)
- A denominação de variável deriva da possibilidade dos valores guardados nas
variáveis poderem variar (poderem serem substituídos)
Atribuição de valores
Para um programa, uma variável é um pedaço de memória identificado por um
nome, onde são guardados/armazenados dados
- Existem várias maneiras de indicar-se a atribuição de um valor a uma variável:
A = 5
d ← 8
- Numa linguagem de programação, isto é feito pela instrução mais importante das
instruções, a denominada “instrução de atribuição”
- A sintaxe (maneira como se escreve) varia de linguagem para linguagem
- O funcionamento é simples: após a execução da instrução pelo computador, a
variável recebe/guarda o valor indicado
- Exemplo: a variável x recebe/guarda o valor 10
x ←10 (linguagem algorítmica)
x = 10 (linguagem C)
Notações algorítmicas
- É uma representação diretamente numa linguagem natural, usando expressões
que evidencie como o problema pode ser resolvido computacionalmente - Apesar de pouco usada na prática, pois o uso da linguagem natural muitas vezes
causa má interpretação, ambiguidades e imprecisões, pode ser útil quando não
se consegue abstrair uma solução computacional para o problema apresentado - Não há um padrão da forma de representar um algoritmo
- Exemplo: calcular a soma de dois números e mostrar o resultado
1. Inserir/ler um número
2. inserir/ler outro número
3. calcular a soma entre os dois números inseridos/lidos
4. mostrar/escrever o resultado da soma
Fluxograma
- É uma representação gráfica de algoritmos, em que símbolos (ou formas)
geométricos diferentes implicam ações (instruções, comandos) distintas - Cada símbolo geométrico define a sua função genérica e no seu interior haverá
uma descrição do passo do algoritmo, donde se inclui as representações das três
estruturas básicas de controlo mencionadas antes: sequência, seleção e repetição - Os símbolos geométricos são ligados entre si por flechas que indicam o sentido
do fluxo das ações - É uma forma intermédia entre a descrição narrativa e o pseudocódigo, mas é
mais precisa do que a primeira - Não se preocupa com detalhes de implementação do programa, como o tipo das
variáveis usadas - Preocupa-se com detalhes de nível físico da implementação do algoritmo, como
distinguir dispositivos onde ocorrem as operações de entrada e de saída de dados
Pseudocódigo
- É a forma de representar algoritmos, podendo já indicar alguns requisitos que as
linguagens de programação necessitam, tais como os tipos de variáveis e as
instruções (comandos) similares aos usados em linguagens de programação - Nesta representação o algoritmo é descrito numa forma muito próxima de uma
linguagem de programação de computadores - O pseudocódigo também é uma linguagem estruturada, pois deve seguir uma
estrutura (ou padrão) que possui um formato semelhante ao das linguagens de
programação, facilitando a codificação em qualquer linguagem de programacao
Estrutura do algoritmo(pseudocódigo)
- O algoritmo deve iniciar-se com
algoritmo <nome-do-algoritmo></nome-do-algoritmo> - O algoritmo deve terminar com
fim_algoritmo - Os dados necessários à execução do algoritmo são indicados pelo comando (opcional)
parâmetros de entrada: <lista-de-variáveis></lista-de-variáveis> - onde <lista-de-variáveis> são os nomes das variáveis que recebem os dados iniciais</lista-de-variáveis>
- Os dados obtidos pelo algoritmo (resultados) são indicados pelo comando (opcional)
parâmetros de saída: <lista-de-variáveis></lista-de-variáveis> - onde <lista-de-variáveis> são os nomes das variáveis que recebem os resultados</lista-de-variáveis>
- A escrita de comentários para clarificar o algoritmo (parte não executável)
{ <comentários> }</comentários>
Comando de atribuição
- O símbolo ← é usado para atribuir o resultado de uma expressão a uma variável,
<variável> ← <expressão>
- onde <expressão> é uma expressão matemática ou um caráter
</expressão></expressão></variável>
Estruturas de entrada e saída
- Para a entrada/leitura de dados
ler: <lista-de-variáveis></lista-de-variáveis> - indica a <lista-de-variáveis> que está disponível para receber valores</lista-de-variáveis>
- Para a saída/escrita de dados
escrever: <lista-de-variáveis, mensagens> - deve ser utilizado para
- indicar quais e onde certos valores devem ser escritos,
- mostrar mensagens
Estruturas alternativas ou condicionais
- Permite a escolha de um conjunto de comandos a ser executado, mediante se uma
condição lógica é satisfeita ou não - Estrutura simples
se <condição> então
</condição><comandos>
fim_se
</comandos> - Estrutura composta
se <condição> então
</condição><comandos_1>
senão
<comandos_2>
fim_se
</comandos_2></comandos_1>
Ciclos
- Permite que um conjunto de comandos seja executado repetidamente, mediante se uma
condição lógica é satisfeita ou não (executa os comandos se a condição for satisfeita) - Verifica a condição lógica antes de executar os comandos (verifica à entrada do ciclo)
enquanto <condição> fazer
</condição><comandos>
fim_enquanto
</comandos> - Verifica a condição lógica depois de executar os comandos (verifica à saída do ciclo)
fazer
<comandos>
enquanto <condição>
</condição></comandos>
Expressões
É uma sequência de operandos e operadores
- Existem, essencialmente, dois tipos de expressões, dependendo do tipo de
operadores e de operandos (valores e variáveis) envolvidos
- aritméticas, e
- lógicas
Expressão Aritmética
É uma sequência de
- operadores aritméticos
- valores numéricos (inteiros e reais)
- variáveis do tipo numérico com valores
- funções matemáticas predefinidas: trigonométricas e numéricas
Expressão lógica(Condição)
É uma sequência de
- operadores relacionais e lógicos
- expressões matemáticas e carateres