Algoritmos e lp parte 1-introdução

Algoritmos e Linguagem de Programação de Programação

Professor: Mauro Jansen

Parte 1 - Introdução

09/2012

Prof. MauroAlgoritmos e Ling.de Programação

Introdução 2

Lógica

� A Lógica estuda os processos válidos e gerais pelos quais atingimos a verdade [...] É a ciência das leis do pensamento.

� Palavra criada pelo filósofo grego Aristóteles (séc. IV a.C.) para estudar o pensamento humano e distinguir


Introdução 3

a.C.) para estudar o pensamento humano e distinguir interferências e argumentos certos e errados

É a ciência dos argumentos, ou seja, ela trata das conclusões a que chegamos a partir das evidências que as sustentam

Lógica: sistema lógico

� Sistema lógico é um conjunto de axiomas e regras de inferência que visam formalizar o raciocínio válido, dedutivo ou indutivoAxioma: hipótese, sentença ou proposição


Introdução 4

� Axioma: hipótese, sentença ou proposição não provada mas considerada como óbvia ou de consenso inicial para formulação de uma teoria

� Inferência: é o processo pelo qual se chega a uma proposição, com base em axiomas

� Dedução caracteriza-se por apresentar conclusões que devem ser verdadeiras caso todas as premissas sejam verdadeiras.

� ExemploTodo ser humano é mortal.

Lógica: Dedução


Introdução 5

� Todo ser humano é mortal.� Pedro é um ser humano.� Portanto, Pedro é mortal.

Premissas

Conclusão

O pensamento dedutivoparte do geral para o

particular.

Lógica: Indução� Indução: o pensamento indutivo consiste em partir de premissas particulares, na busca de uma lei geral.

� Exemplo� O ferro conduz eletricidade.

O pensamento indutivo


Introdução 6

� O ferro conduz eletricidade.� O ferro é um metal.� O ouro conduz eletricidade.� O ouro é um metal.� O cobre conduz eletricidade.� O cobre é um metal.� Logo: os metais conduzem eletricidade.

O pensamento indutivoparte do particular para o

geral.


Introdução 7

Algoritmo� Sequência ordenada de passos (instruções) necessários

para a resolução de um problema ou processo.� Procedimento passo a passo para resolução de um

problema


Introdução 8

� Exemplos de possíveis problemas do mundo real solucionáveis com algoritmos:� Resolver uma operação matemática seguindo passos até chegar

ao resultado final � Assar uma pipoca no forno microondas� Tomar medicamentos seguindo orientações médicas� Cozinhar seguindo receitas culinárias

Algoritmo (exemplo)

� Receita de pipoca de microondas caseira1. Em um prato refratário com tampa, coloque um ou

mais “punhados” (mão cheia) de milho de pipoca comum

2. Acrescente 1 colher de sopa de água para cada


Introdução 9

2. Acrescente 1 colher de sopa de água para cada “punhado” de milho colocado anteriormente

3. Coloque o prato refratário no microondas, com a tampa, por mais ou menos 5 minutos

4. Aguarde esfriar5. Retire o prato do microondas

Adaptado de http://tudogostoso.uol.com.br

Dados e Informações� Dados: são os fatos em sua ordem primária.

� Matéria prima (bruta)� Ex: preço de venda, nota, horas trabalhadas

� Informação: parte utilizável dos dados, que pode ser armazenada, transmitida ou permitir a


Introdução 10

pode ser armazenada, transmitida ou permitir a dedução de novas informações.� Produto final (acabado, lapidado)� Ex: orçamento, resultado acadêmico, folha de pagamento

INFORMAÇÃO DADO CONHECIMENTO

Processamento de dados� Qualquer trabalho de manipulação de dados que tenha

como finalidade obter resultados previamente estabelecidos de modo a resolver determinado problema

� Tem 3 partes principais: ENTRADA, PROCESSAMENTO e SAÍDA

Envolve TRANSMISSÃO, ARMAZENAMENTO, RECUPERAÇÃO,


Introdução 11

� Envolve TRANSMISSÃO, ARMAZENAMENTO, RECUPERAÇÃO, COMPARAÇÃO, COMBINAÇÃO de informações

ENTRADA PROCESSAMENTO SAÍDA

Dados de entrada e saída� Ao tentar resolver um problema, devemos identificar alguns dados que auxiliarão na sua resolução.

� Dados de Entrada: dão suporte à solução do problema. Ponto de partida.


Introdução 12

problema. Ponto de partida.� Dados de Saída: resultados esperados após solução.

� Através de um algoritmo os dados de entradapodem ser processados e teremos a solução do problema, que gerará uma saída de dados

Instrução e lógica de programação

� Instrução: Informação que indica ao computador uma ação elementar a executar

� Lógica de programação diz respeito à


Introdução 13

� Lógica de programação diz respeito à dedução de uma sequência de instruções tal que, fornecidos os dados de entrada, alcançaremos como saída a solução do problema inicialmente concebido, por meio da execução das instruções


Introdução 14

(Um pouco mais sobre algoritmos:Conceitos, características, importância e passos para criação)

Conceitos“Algoritmo é uma seqüência de passos que visa atingir um

objetivo bem definido”(FORBELLONE, 1999)

“Algoritmo é uma seqüência de passos que deve ser seguida para a realização de uma tarefa”


Introdução 15

para a realização de uma tarefa”(ASCENCIO, 1999)

“Algoritmos são regras formais para a obtenção de um resultado ou da solução de um problema, englobando

fórmulas de expressões aritméticas”(MANZANO, 1997)

Conceitos

“Um algoritmo é uma lista de instruções que, quando executadas, transformam dados de entrada até a saída. As instruções são um conjunto finito de etapas que podem ser


Introdução 16

conjunto finito de etapas que podem ser executadas, numa ordem precisa, por um

mecanismo determinista. Quando estas etapas são efetivamente executadas , a execução deve

terminar após um tempo finito.”(HOLLOWAY, 2006)

Características de um algoritmo

� Ter fim;� Não dar margem a dupla interpretação;� Capacidade de receber dados do mundo exterior;


Introdução 17

exterior;� Poder gerar informações de saída para o mundo externo ao ambiente do algoritmo;

� Ser efetivo;

Importância dos algoritmos

“A noção de algoritmo é básica para toda a programação de computadores”.

[KNUTH - Professor da Universidade de Stanford, autor da coleção “The art of computer programming”


Introdução 18

“O conceito central da programação e da ciência da computação é o conceito de

algoritmo”.[WIRTH - Professor da Universidade de Zurique, autor de diversos livros na área e responsável pela criação de linguagens de programação como ALGOL, PASCAL e

MODULA-2]

Passos para escrever um algoritmo

� Segundo ASCENCIO e CAMPOS (2002), os passos para a construção de algoritmos são os seguintes:� Ler atentamente o enunciado, destacando os pontos mais importantes;

� Definir os dados de entrada;Definir o processamento;


Introdução 19

� Definir o processamento;� Definir os dados de saída;� Construir o algoritmo uma das técnicas descritas a seguir;

� Testar o algoritmo realizando simulações.


Introdução 20

Responda:� Quais são os raciocínios lógicos básicos e qual a dinâmica

dos mesmos?� Qual a importância da lógica para a criação de algoritmos

e programação?� O que é um algoritmo? Dê exemplos.� O que são dados e informações?


Introdução 21

� O que são dados e informações?� Qual o princípio básico do processamento de dados?� O que é uma instrução? Dê exemplos.� Quais são as características de um algoritmo?� Qual a importância dos algoritmos?� Cite os passos básicos para criar algoritmos.

Resolva:

� Um homem está à margem de um rio com uma raposa, uma dúzia de galinhas e um saco de milho. Ele pretende atravessar o rio com a sua carga numa canoa que só comporta ele e uma das suas cargas. Ele


Introdução 22

comporta ele e uma das suas cargas. Ele não pode deixar a raposa com as galinhas, nem as galinhas com o milho. Qual a sequência da passos (algoritmo) para atravessar o rio e chegar à outra margem com a raposa, as galinhas e o milho?

Algoritmo da travessia do rio� Solução sem detalhes:

� Leva a galinha� Volta� Leva a raposa� Volta com a galinha

Deixa a galinha e Leva o milho

Prof. Mauro

� Deixa a galinha e Leva o milho � Volta� Leva o milho� Volta� Leva a galinha

Algoritmos e Ling.de Programação

Introdução 23

Algoritmo da travessia do rio� Solução com detalhes:

� INICIO� Pega a galinha e entra na canoa� Atravessa o rio até o lado destino, levando a galinha� Deixa a galinha no lado destino� Atravessa o rio de volta ao lado origem� Desce da canoa, pega a raposa que está no lado origem e entra na canoa

Prof. Mauro

� Desce da canoa, pega a raposa que está no lado origem e entra na canoa� Atravessa o rio até o lado destino, levando a raposa� Desce da canoa, deixa a raposa e pega a galinha� Entra na canoa e atravessa o rio de volta ao lado origem, trazendo a galinha� Desce da canoa, deixa a galinha e pega o milho � Entra na canoa e atravessa o rio até o lado destino, levando o milho� Deixa o milho e atravessa o ria de volta ao lado origem� Desce da canoa, pega a galinha que está no lado origem e entra na canoa� Atravessa o rio até o lado destino, levando a galinha� FIM

Algoritmos e Ling.de Programação

Introdução 24

Escreva os algoritmos:

� Escreva a sequência de passos (algoritmo) necessários para:� Calcular a área de um retângulo� Escovar os dentes


Introdução 25

Escovar os dentes� Fritar um ovo


Introdução 26

(Aonde queremos chegar com os algoritmos)

Linguagem de máquina

� O computador, nativamente, só entende uma linguagem: a linguagem (ou código) de máquina, que é uma linguagem que:� Tem grau de dificuldade acentuado� Requer do programador um conhecimento da


Introdução 27

� Requer do programador um conhecimento da arquitetura interna do hardware

� Exemplo de programa em código de máquina:

C000:C100 BF 00 74 68 51 66 56 57-1E 06 53 66 50 E8 BC 00

C000:C110 8B D9 D1 E1 16 5E 8E DE-8E C6 83 C5 02 8B C5 83

C000:C120 ED 16 8B F5 8B FD 2B F9-8B E8 B9 0C 00 FC F3 A5

C000 10111111

C001 00000000

C002 01110100

C003 01101000

...

Linguagens de programação (LP’s)

� As linguagens de programação existem para tornar a programação mais próxima da nossa linguagem natural� Maior facilidade� Maior produtividade


Introdução 28

� Maior produtividade

Código de máquina X linguagem de alto nível:


� Exemplo de programa em uma linguagem de programação (Pascal):

(*

Programa CONTADOR – conta de 1 a 10

*)


Introdução 29

*)

Var

c: integer;

Begin

for c:=1 to 10 do

writeln(c);

writeln(‘Fim!’);

End.


� São programas (softwares) usados para criar outros programas.

� Transformam um conjunto de instruções de uma linguagem acessível em instruções da linguagem do computador (linguagem de máquina)


Introdução 30

do computador (linguagem de máquina)� Exemplos: •Pascal

•Delphi•Visual Basic•Java•PHP

•C•C++•C#•PHP•Javascript

Características das LP’s

� Rigidez sintática:� Idioma limitado e construções bem definidas� A ordem dos termos ou uma vírgula a mais ou a menos faz diferença (a sintaxe deve ser seguida à risca)


Introdução 31

risca)

� Rigidez semântica: não pode haver ambiguidades.� O computador não tem idéia do que executa e nem inteligência para analisar a ordem

� Você deve ser bem claro em relação ao que quer que o computador execute

Características das LP’s

� Rigidez semântica - exemplo ilustrativo na língua portuguesa:� A frase “A velhinha ouviu o barulho da janela.” pode ser interpretada de três maneiras:


Introdução 32

� A velhinha ouviu o barulho produzido pela janela� A velhinha estava junto à janela e ouviu o barulho� A velhinha ouviu o barulho que veio através da janela

� Nesse caso, há pouca rigidez semântica

Tipos de linguagens de programação

� Quanto ao nível de abstração (facilidade de aprendizado)� Alto nível� Médio nível


Introdução 33

Médio nível� Baixo nível

� Quanto à forma de execução� Compiladas� Interpretadas

Nível de abstração das LPs

� Abstração: habilidade de concentrar nos aspectos essenciais de um contexto qualquer, ignorando características menos importantes ou acidentais


Introdução 34

� Contexto em questão: máquina� Está diretamente relacionada à facilidade de aprendizado e uso de uma linguagem de programação

Nível de abstração das LPs

� Alto nível: separa os detalhes da máquina. É mais próxima da linguagem humana

� Médio nível: separa os detalhes da


Introdução 35

� Médio nível: separa os detalhes da máquina, mas permite o acesso aos mesmos

� Baixo nível: diretamente relacionadas com a arquitetura do hardware

Nível de abstração das LPsHomem / linguagem humana

Linguagens de alto nível:ASP, C/C++, C#, Pascal/Object Pascal, Java,PHP, Python, Tcl, Basic/Visual Basic, Delphi


Introdução 36

MÁQUINA

Linguagens de médio nível:C, C++

Linguagens de baixo nível: Assembly e Linguagem de máquina

Linguagem compilada – visão geral

� Linguagem compilada� Converte o programa na linguagem de alto nível (programa fonte) para a linguagem de máquina (programa executável ou arquivo do tipo APLICATIVO)


Introdução 37

tipo APLICATIVO)� Funcionamento:

Programafonte Compilador Linkeditor Programa

executávelCódigoobjeto

bibliotecas

Linguagem compilada - elementos� Programa fonte: (ou código fonte) instruções e símbolos de uma linguagem de programação escritos de forma lógica e ordenada, com o objetivo de comandar um computador na execução de uma função� Normalmente são arquivos com extensão definida pela


Introdução 38

� Normalmente são arquivos com extensão definida pela LP: .C , .PAS , .JAVA , .PHP , etc

� Compilador: (ou tradutor) programa que traduz um programa fonte em uma linguagem para um código objeto ou linguagem de mais baixo nível

� Código objeto: (ou código intermediário). Código resultante da compilação. Ainda não é executável diretamente pelo computador.

Linguagem compilada - elementos

� Linkeditor: (ou ligador) programa que liga os objetos gerados pelo compilador, criando o arquivo executável

� Bibliotecas: conjuntos de sub-programas, ou objetos previamente existentes que serão (re)utilizados na criação do programa executável


Introdução 39

objetos previamente existentes que serão (re)utilizados na criação do programa executável

� Programa executável: arquivo final, que pode ser executado pelo computador através do sistema operacional� Normalmente são arquivos com a extensão .EXE ou .COM

Linguagem compilada - exemplos

� Delphi� Pascal/Object Pascal� C� Visual Basic


Introdução 40

� Visual Basic� Assembler, etc.

Linguagem interpretada – visão geral

� Linguagem interpretada� Executa os comandos sem converter para a linguagem de máquina (não gera programa executável)Funcionamento:

Programa Interpretador


Introdução 41

� Funcionamento:� Ou:

Programafonte

Interpretador(executa)

Interpretadorou

Máquina virtual(executa)

Códigoobjeto

Programafonte Compilador

Linguagem interpretada – exemplos:

� Java � HTML � ASP� PHP


Introdução 42

� PHP� Javascript

Ambientes de desenvolvimento

� São ambientes de desenvolvimento que integram diversas ferramentas para a criação de programas em uma linguagem de programação

� Também chamados de IDE´s (Integrated Development Environment)


Introdução 43

Development Environment)� Exemplo de ferramentas encontradas nos IDE´s:

� Editor de textos adequado para a programação� Ajuda (Help) on-line� Compilador, linkeditor e depurador integrados� Ferramentas para desenho de janelas (formulários)

Desenvolvimento de software

� Segue um ciclo de vida� Análise: definição do QUÊ o programa deverá fazer

� Projeto: definição de COMO o programa executará seu objetivo


Introdução 44

executará seu objetivo� Implementação: codificação (criação de um ou mais programas em uma linguagem)

� Testes: testes isolados e de integração

Programação de computadores

� O que preciso saber para programar?� Noções de algoritmos e lógica de programação� Conhecer a estrutura, comandos e símbolos da linguagem de programação escolhida


Introdução 45

� Para linguagens de baixo nível, conhecer a arquitetura do hardware

� Prática... Muita prática

Atividade: Questionário 2� Qual a linguagem nativa do computador e qual as

características da mesma?� O que são linguagens de programação? Cite exemplos.� Quais as características das linguagens de programação?� Como classificam-se as linguagens de programação

quanto ao: (dê exemplos de cada grupo)


Introdução 46

quanto ao: (dê exemplos de cada grupo)� Grau de dificuldade� Modo de execução

� Explique o funcionamento dos diferentes tipos de LPs


Introdução 47

(Estruturas básicas para criação e representação de algoritmos)

Estruturação de algoritmos

� São formas possíveis de resolução e representação de algoritmos� Resolução

� Sequencial� Condicional


Introdução 48

� Condicional� Repetição

� Representação� Linguagem natural / descrição narrativa� Fluxograma� Diagrama de Chapin� Pseudocódigo

Estruturas de resolução

� Ao buscar uma solução de um problema criando um algoritmo, sempre teremos pelo menos uma das seguintes estruturas:� Resolução Sequencial: sequência linear de instruções, uma após a outra


Introdução 49

instruções, uma após a outra� Resolução Condicional: existência de “condições” para executar algumas instruções.

� Resolução com Repetição: algumas instruções precisam ser executadas várias vezes.

Estruturas de representação

� Linguagem natural / descrição narrativa� Fluxograma� Diagrama de Chapin� Pseudocódigo


Introdução 50

� Pseudocódigo

Linguagem natural

� Apesar de ser possível escrever algoritmos para pessoas usando a linguagem natural, ela não é adequada para a construção de algoritmos para o computadorNão tem características das LP´s:


Introdução 51

� Não tem características das LP´s:� Não têm rigidez sintática:

� Traga caneta azul ou preta.� Traga caneta (Azul ou preta)

� Não tem rigidez semântica:� A velhinha ouviu o barulho da janela

Linguagem natural x LP´s

� Ao decidir entra a linguagem natural ou as LP´s, temos um impasse, pois:� A linguagem natural não é adequada por não ter rigidez sintática e semântica


Introdução 52

� Torna-se impossível para o computador processar

� A linguagem de programação não é adequada por ter rigidez sintática e semântica

� Torna-se difícil para o programador iniciante

� Então, precisamos de outras alternativas...

Fluxograma

� São representações gráficas de algoritmos:� Formas geométricas para representar o início, término e as instruções a serem executadas

� Setas para indicar o fluxo das ações


Introdução 53

� Alguns símbolos representam situações especiais dos algoritmos:� Tomadas de decisão e desvios� Repetição

Fluxograma: símbolos básicos

Início e término do algoritmo

Setas indicam o fluxo da execução


Introdução 54

Instrução (entrada, saída, armazenamento ou processamento de dados)

Tomada de decisão com possível desvio do fluxo

Fluxograma: exemploAlgoritmo em forma de fluxograma, para solicitar dois números e mostrar qual o maior:

Início

Leia num1, num2

Num1>num2?sim não


Introdução 55

Num1>num2?

Maior � num1 Maior � num2

Escreva Maior

Fim

Fluxograma� Vantagens:

� Facilidade proporcionada para compreensão do funcionamento

� Facilmente entendível por pessoas visuais� Desvantagens:

� Não é uma representação prática: a correção implica


Introdução 56

� Não é uma representação prática: a correção implica em alterar vários desenhos

� Inadequado para algoritmos complexos e longos� Inadequado para uso como ferramenta principal� Recomendável apenas para representar a idéia geral de um algoritmo ou como “ensaio” para criação da solução

Diagrama de Chapin

� Criado por Ned Chapin a partir de trabalhos de Nassi-Shneidermann

� Apresenta uma visão hierárquica e estruturada da lógica do programa


Introdução 57

estruturada da lógica do programa

Diagrama de Chapin: exemplo

Leia num1, num2num1>num2

Algoritmo referente ao problema do maior número, representado em diagrama de Chapin:


Introdução 58

sim nãomaior� num1 maior � num2

Escreva “O maior é: ”,maiorFim

num1>num2

Pseudocódigo

Assemelha-se à forma como os programas são escritos.

Forma para a representação de algoritmos rica em detalhes, como a definição dos tipos das

variáveis usadas no algoritmo.


Introdução 59

� Assemelha-se à forma como os programas são escritos.� Para traduzir o pseudocódigo para uma linguagem de

programação, basta conhecer o vocabulário e regras sintáticas da linguagem.

� Busca a rigidez sintática e semântica, porém sem o detalhamento exigido nas linguagens de programação

Pseudocódigo – estrutura básica

� Estudaremos o pseudocódigo com mais detalhes posteriormente. Por enquanto, conheceremos apenas a estrutura básica de um pseudocódigo:


Introdução 60

Algoritmo <nome do Algoritmo>

Variáveis

<lista de variáveis>

Início

<bloco de comandos>

Fim

Pseudocódigo - exemplo

� Pseudocódigo referente ao problema do maior número:

Algoritmo Maior

Var num1, num2, maior: inteiro:

Inicio


Introdução 61

Inicio

Leia(num1,num2);

se (num1>num2) então

maior �� num1;

senão

maior �� num2;

fimse;

escreva(maior);

Fim

Atividade – questionário:

� Quais as estruturas básicas de resolução de problemas com algoritmos?

� Quais as formas de representação de algoritmos?

Qual a característica, vantagens e


Introdução 62

� Qual a característica, vantagens e desvantagens de cada uma delas?

� Qual a mais adequada para representação de algoritmos?

� Construa um fluxograma para somar dois números e mostrar o resultado

Documents

Algoritmos e lp parte 1-introdução