Aula01 Introducao2011

Prévia do material em texto

INF01202INF01202INF01202INF01202
Algoritmos e ProgramaçãoAlgoritmos e ProgramaçãoAlgoritmos e ProgramaçãoAlgoritmos e Programação
Prof. Anderson Maciel
amaciel@inf.ufrgs.br 
1
Utilizar Aplicativos
Editor de texto - Word
Planilha eletrônica Excel EscreverPlanilha eletrônica - Excel
Bancos de dados - Access
Correio eletrônico - Gmail
A à I t t F b k
Escrever 
Programas
Acesso à Internet - Facebook
Jogos
2
Objetivo da disciplinaObjetivo da disciplina
solução de problemas utilizando o computadorsolução de problemas utilizando o computador
Li HLinguagem Humana ou 
Natural
AlgoritmosAlgoritmosgg
CCCC
3 ProgramaçãoProgramação
Execução de Programas
Programa em 
Linguagem 
de Programação
Programa em 
Linguagem 
d Má i
COMPILADOR
de Programação de Máquina
Programa executávelPrograma fonte
4
INF01202INF01202
O que vamos fazer na disciplina:
INF01202INF01202
1 - análise do problema
q p
2 - escolha de uma solução para resolver o 
problema
3 - construção do algoritmos
linguagem algorítmicalinguagem algorítmica
4 - tradução do algoritmo para uma linguagem4 tradução do algoritmo para uma linguagem 
de programação imperativa 
5
Modelos e Paradigmas de Linguagens
Objetivo: atender a diferentes domínios de problemas
Modelo imperativo Modelo declarativo
Objetivo: atender a diferentes domínios de problemas
Modelo imperativo
• Programa: sequências 
de comandos que 
Modelo declarativo
• Linguagens não 
possuem o conceito de de comandos que 
efetuam 
transformações sobre 
possuem o conceito de 
sequências de 
comandos.
dados. 
• Paradigma:
• Paradigma:
– funcional 
– procedural 
– orientadas a 
– lógico
6
objetos
Paradigmas de Linguagens de 
ProgramaçãoProgramação
Modelo imperativo
Paradigma Procedural (ou Imperativo):
Modelo imperativo
Paradigma Procedural (ou Imperativo):
• solução implementada através de ações, executadas 
s i l tsequencialmente.
• Baseado nos princípios da PROGRAMAÇÃO 
ESTRUTURADAESTRUTURADA
• conceitos: variáveis, atribuição, sequenciação.
• linguagens procedurais: C, Pascal, Java, Algol, g g p
Fortran, PL/I, Basic, Ada.
7
Programação Estruturada
• Se refere a técnicas de construção de soluções e de 
critérios para estruturar e codificar programas; 
• Regula e limita:
• estruturas de controle utilizadas;
• forma de modularização do programa;
• utilização de identificadores e comandos;utilização de identificadores e comandos;
• estrutura da codificação (alinhamentos, separação de 
comandos...);)
• documentação do programa.
8
Programação Estruturada
Objetivos:
• Aumentar confiabilidade e legibilidade do 
programa;
• Minimizar a complexibilidade do programa; 
• Estabelecer uma metodologia disciplinada de 
programação;
• Aumentar a produtividade do programador;
• Facilitar a manutenção dos programas.
9
Programação EstruturadaProgramação Estruturada
Técnicas adotadas:
™Existe correspondência entre algoritmo e 
programa;
Técnicas adotadas:
programa;
™Refinamento gradual da solução, associado a 
dif t í i d b t ãdiferentes níveis de abstração;
• Projeto de solução modular: o problema se 
ó á
j
decompõem em etapas ou módulos hierárquicos; 
• Programa composto de módulos básicos (blocos), g p ( ),
cada um para uma tarefa específica;
• Programação top down e bottom-up.
10
Programação top_down e bottom up.
Programa
– Sequência correta de instruções: 
• o que fazer
• quando fazer
– Instrução:
• ação elementar a ser executada.
11
Fases para elaboração de um programa
• Coleta análise e especificação dos requisitos• Coleta, análise e especificação dos requisitos
• Algoritmo
Programa• Programa
• Testes
• Manutenção
Engenharia de Software
12
Elaboração de um Programa
Decomposição 
Estruturação
Problema Análise
Estruturação 
AlgoritmoAlgoritmoPrograma
13
Processo de geração de um Programa
• Análise e Definição do Problema
Processo de geração de um Programa
Off Line• Projeto do Algoritmo
• Validação do Algoritmo (teste de mesa)• Validação do Algoritmo (teste de mesa)
• Tradução do Algoritmo para uma linguagem de 
O Li
r uç g r m p r um ngu g m
programação (codificação) 
• Compilação On Line
Linguagem de Programação
Compilação
• Teste e Depuração
Linguagem de Programação
• Conclusão
14
Análise e Definição do Problema:
• Ler atentamente o enunciado do problema, até 
entendê-lo bem. 
Id tifi d d d t d• Identificar os dados de entrada.
• Identificar as saídas (resultados esperados).
O d f ( bj i ) i é • O que o programa deve fazer (objetivo), isto é, 
como transformar as entradas em saídas?
Id tifi s ist l s d d s • Identificar se existem valores ou dados 
intermediários, usados para transformar as 
entradas nas saídasentradas nas saídas.
• Pode ser dividido em subproblemas?
15
Projeto do Algoritmoj g
Definição: Definição: 
“Algoritmo é uma sequência finita 
e lógica de instruções ou passos e lógica de instruções ou passos 
básicos, especificados de acordo 
com uma determinada linguagem e com uma determinada linguagem e 
que serve para resolver um 
determinado problema ”pr blemadeterminado problema.problema
Paradigma
16
• Determinar as ações que levam ao resultado:
Projeto do Algoritmo
ç q
– identificar as ações e a sequência destas ações para 
obter o resultado final (como transformar as entradas 
nas saída desejadas).
• Construir o algoritmo:Construir o algoritmo:
– descrever os passos que levam à resolução do 
problema. p
17
ALGORITMOALGORITMO
• Propriedades:
– possui um estado inicial;– possui um estado inicial;
– contém uma sequência lógica e finita de ações
(comandos) claras e precisas com fluxo de execução(comandos), claras e precisas, com fluxo de execução
baseado em:
• sequência;sequência;
• seleção condicional (seleção de ações);
• iteração (repetição de ações);
Programação
Estruturadaiteração (repetição de ações);
– possui dados de entrada;
– produz dados de saída corretos;
Estruturada
produz dados de saída corretos;
– possui estado final previsível;
– deve ser eficaz
18
deve ser eficaz.
Algoritmo - atravessar a rua
• Desenvolver um algoritmo que instrua um 
bô t d ã d l d robô a atravessar uma rua de mão dupla de 
forma segura.
• Etapas envolvidas:
¾Análise e Definição do Problema
¾Projeto do Algoritmo
¾Validação do Algoritmo (teste de mesa)
19
Normas importantes para algoritmoso as po ta tes pa a a go t os
• Identificar o algoritmo (identificador).
• Incluir com clareza no topo do algoritmo a finalidade• Incluir com clareza, no topo do algoritmo, a finalidade
do algoritmo e suas entradas e saídas.
• Usar apenas 1 comando por linha (substantivo + verbo)Usar apenas 1 comando por linha (substantivo + verbo).
• Usar indentação (recuo de margens) para indicar o nível 
(hierarquia) de cada linha; (hierarquia) de cada linha; 
• Escolher nome significativos para variáveis e 
identificadores, mas que não sejam longos;, q j g
• Utilizar espaços e linhas em branco para maior 
legibilidade do algoritmo.
• Nunca utilizar desvios através de ‘vai para’ (go to).
P m : l itm t d id !
20
Programa : algoritmo traduzido !
Algoritmo - atravessar a ruag
Algoritmo AtravessaRua
// Faz com que chegue ao outro lado da rua de forma segura.
1 i í i1. início
2. pára no cordão da calçada
3. olha para a esquerda3. olha para a esquerda
4. vem veículo da esquerda para direita?
4.1 sim – retorna ao passo 3 
4 2 não segue para passo 5
desvio do tipo vai para!!!
4.2 não – segue para passo 5
5. olha para a direita
6. vem veículo da direita para esquerda?p q
6.1 sim – retorna ao passo3
6.2 não – segue para passo 7
7 atravessa a rua
desvio do tipo vai para!!!
7. atravessa a rua
8. fim Programação Estruturada:
substituídos por estruturas de repetição
21
substituídos por estruturas de repetição
Processo de geração de um Programa
9 Análise e Definição do Problema
9 P j t d Al it9 Projeto do Algoritmo
¾Validação do Algoritmo (teste de mesa)
T d ã d Al it li d • Tradução do Algoritmo para uma linguagem de 
programação (codificação e compilação)
Teste e Depuração• Teste e Depuração
• Implementação
22
Análise e Definição do Problema
Especificação do problema:
Enunciado:
• Ler um valor, informado através do teclado, que 
pode ser igual a 1 ou a 2.
• Se o valor lido for 1, informar 2.
• Se o valor lido for 2, informar 1.
Objetivo: ler um valor e informar 
outro valor alternativo.
Entradas: 1 ou 2
Saída: 2 ou 1
23
Saída: 2 ou 1
Projeto do Algoritmo
Algoritmo Alterna1e2
Obj ti l lObjetivo: ler valor; 
se = 1, informa 2;
se = 2, informa 1.
Entradas: 1 ou 2Entradas: 1 ou 2
Saídas: 2 ou 1
1. inicio
2 lê 2. lê x
3. se x = 2
3 1 então x ←13.1 então x ←1
4. se x = 1
4.1 então x ←2
5. informa x
6. fim
24
x lido x inform
Validação do Algoritmo - Teste de Mesa
x lido x inform.
1
2
2
2
• Algoritmo deve ser correto:
Algoritmo Alterna1e2 2 2Algoritmo Alterna1e2
Objetivo: ler valor; 
se = 1, informa 2;
se = 2 informa 1
9 Contexto: x=1 ou x=2 (garantido!)
9 Dica simular execução:se = 2, informa 1.
Entradas: 1 ou 2
Saídas: 2 ou 1
1 inicio
9 Dica - simular execução:
• 1o valor válido
• último valor válido
• 1o valor inválido inferior1. inicio
2. lê x
3. se x = 2
1 valor inválido inferior
• 1o valor inválido superior
/ Erro - valor informado sempre = 2
9 Vacina para este tipo de erro3. se x 
3.1 então x ←1
4. se x = 1
 
9 Vacina para este tipo de erro -
• nunca alterar diretamente 
valores lidos
tili iá i dif t4.1 então x ←2
5. informa x
6 fim
• utilizar variáveis diferentes
para armazenar resultados
/ Usar mnemônicos
25
6. fim (identificadores)!
 lid i f
Validação do Algoritmo - Teste de Mesa
x lido x inform.
1
2
2
2
• Algoritmo deve ser correto:
Algoritmo Alterna1e2 2 2Algoritmo Alterna1e2
Objetivo: ler valor; 
se = 1, informa 2;
se = 2 informa 1
9 Contexto: x=1 ou x=2 (garantido!)
9 Di i l ãse = 2, informa 1.
Entradas: 1 ou 2
Saídas: 2 ou 1
1 inicio
9 Dica - simular execução:
• 1o valor válido
• último valor válido
1o l i álid i f i1. inicio
2. lê x
3. se x = 2
• 1o valor inválido inferior
• 1o valor inválido superior
/ Erro - valor informado sempre = 2
93. se x 3.1 então x ←1
4. se x = 1
 
9 Vacina para este tipo de erro -
• nunca alterar diretamente 
valores lidos 1
4.1 então x ←2
5. informa x
6 fim
• utilizar variáveis diferentes
para armazenar resultados 1
/ Usar mnemônicos 1
26
6. fim / Usar mnemônicos
(identificadores)!
1 Programação Estruturada
l i f
Validação do Algoritmo - Teste de Mesa
• Algoritmo deve ser eficiente:
Algoritmo Alterna1e2
val_lido val_inf
1 2g
Objetivo: ler valor; 
se = 1, informa 2;
se = 2, informa 1.
Entradas 1 o 2 9 Contexto: x=1 ou x=2
2 1
Entradas: 1 ou 2
Saídas: 2 ou 1
1. início
2 lê l lid
9 Contexto: x=1 ou x=2 
(garantido!)
☺ Utilização de nomenclatura 
2. lê val_lido
3. se val_lido = 2
então val inf
ç
significativa - mnemônicos!
(val_lido e val_inf)então val_inf
← 1
4. se val_lido = 1
tã l i f
. Limitação:
redundância de operações
(se x = 2 então obviamente então val_inf
← 2
5. informa val_inf
(se x = 2, então, obviamente, 
x ≠ 1, e vice-versa)
9 Dica - evitar operações 
27
_
6. fim
p ç
repetidas ou redundantes
Validação do Algoritmo - Teste de Mesa
• Algoritmo deve ser eficiente:
Algoritmo Alterna1e2
Objetivo: ler valor; 
se = 1, informa 2; 9 Contexto: x=1 ou x=2, ;
se = 2, informa 1.
Entradas: 1 ou 2
Saídas: 2 ou 1
9 Contexto: x 1 ou x 2 
(garantido!)
☺ Eficiência melhorada
1. início
2. lê val_lido
3 se val lido = 2
9 Dica – eliminar repetição de 
teste de condições mutuamente 
exclusivas3. se val_lido = 2
então val_inf ← 1
senão val_inf ← 2
4 i f l i f
exclusivas
4. informa val_inf
5. fim
28
Validação do Algoritmo - Teste de Mesa
• Algoritmo deve ser facilmente entendido:
l lid l i fAlgoritmo Alterna1e2
Objetivo: ler valor; 
se = 1 informa 2;
Algoritmo Alterna1e2
Objetivo: ler valor; 
se = 1 informa 2;
val_lido val_inf
1
2
2
1se = 1, informa 2;se = 2, informa 1.
Entradas: 1 ou 2
Saídas: 2 ou 1
se = 1, informa 2;
se = 2, informa 1.
Entradas: 1 ou 2
Saídas: 2 ou 1
2 1
9 Contexto: x=1 ou x=2
1. início
2. lê val_lido
{alterna valores entre 1 e 2}
1. início
2. lê val_lido
{alterna valores entre 1 e 2}
9 Contexto: x 1 ou x 2 
(garantido!)
☺ Código muito eficiente{alterna valores entre 1 e 2}
3. val_inf ← 3 - val_lido
4. informa val_inf
5 f
{alterna valores entre 1 e 2}
3. val_inf ← 3 - val_lido
4. informa val_inf
5 f
. Perigo - solução não trivial
9 Vacina -
documentar bem um programa5. fim5. fim • documentar bem um programa
• informar o que faz (e não como)
29
Processo de solução de problemas
Enunciado do Problema:
Processo de solução de problemas
Ler dois valores informados pelo
t l d l l i fteclado, calcular e informar a soma 
destes valores
30
Análise e Definição do Problema
Identificar objetivo, entradas e saídas:
Análise e Definição do Problema
Objetivo: informar a soma de 2 
valores lidos
Entradas: 2 valores numéricos
S í é SOSaída: 1 valor numérico ↔ SOMA
31
Processo de geração de um ProgramaProcesso de geração de um Programa
9Análise e Definição do Problemaç
¾ Projeto do Algoritmo
¾Validação do Algoritmo (teste de mesa)¾Validação do Algoritmo (teste de mesa)
32
FluxogramaEnunciado:
Calcular a soma de dois
início
Calcular a soma de dois 
números inteiros.
Linguagem algorítmica Ler A
Algoritmo Soma2
1. Ler A
2 L B
Ler B
2. Ler B
3. Soma := A + B
4. Escrever Soma Soma := A + B
5. Terminar.
Soma := A + B
Escrever
Soma
33
fim
Programa em C
/*
Este programa pega dois inteiros, os soma e exibe o 
resultado na tela
*/
#i l d tdi h#include <stdio.h>
int a, b; //Declaração da variável com os parâmetros
int soma; //Declaração da variável com o resultadoint soma; //Declaração da variável com o resultado
int main(void)
{{
a = 2;
b = 3;
soma = a + b;soma = a + b;
printf("Resultado da soma: %d", soma);
}
34
}
Linguagens de Programação
execuçãocompilação
correção sintática
execuçãocompilação
C
Programa 
codificação
C Objeto
Programa
Fonte sintaxe Sim Nãoexecução 
correta? correta?
Sim
Não Fim
Sim
ã â ti
35
correção semântica