apostila
50 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I637 materiais7.932 seguidores
Pré-visualização50 páginas
a notac¸a\u2dco ou linguagem
de \u201calto n´\u131vel\u201d, que vai exigir a introduc¸a\u2dco dos chamados compiladores.

4.4 Abstrac¸a\u2dco das instruc¸o\u2dces (linguagem)

Apesar de todas as notac¸o\u2dces e convenc¸o\u2dces que foram feitas no programa, ate´ se chegar
na versa\u2dco mostrada na figura 4.9, de certa maneira, o programa ainda esta´ em um
formato muito parecido com o do programa original.

Para que seja poss´\u131vel aumentar o n´\u131vel de notac¸a\u2dco ainda mais e´ preciso contar com
a ajuda de programas tradutores, ou como eles sa\u2dco mais conhecidos, os compiladores.

Estes programas conseguem receber como entrada um texto escrito em um for-
mato adequado e gerar como sa´\u131da um programa no formato da ma´quina. Isto e´

32 CAPI´TULO 4. O MODELO DO COMPUTADOR

dois \u2190 2
quatro \u2190 4
B \u2190 \u2228
quadradoB \u2190 B × B
C \u2190 \u2228
quadruploC \u2190 quatro × C
discriminante \u2190 quadradoB - quadruploC
raizDiscriminante \u2190 \u221adiscriminante
dobroMenorRaiz \u2190 B - raizDiscriminante
menorRaiz \u2190 dobroMenorRaiz

dois

\ufffd \u2190 menorRaiz
dobroMaiorRaiz \u2190 B + raizDiscriminante
maiorRaiz \u2190 dobroMaiorRaiz

dois

\ufffd \u2190 maiorRaiz
\u2022

Figura 4.9: Programa reescrito com nomes para varia´veis.

poss´\u131vel apenas se os programas forem escritos em um formato que respeite regras
extremamente r´\u131gidas, pois sena\u2dco a tarefa na\u2dco seria poss´\u131vel.

As linguagens de alto n´\u131vel sa\u2dco definidas a partir de uma grama´tica extremamente
mais r´\u131gida que a do portugue\u2c6s, por exemplo. Estas grama´ticas, conhecidas como
grama´ticas livre de contexto, te\u2c6m como uma de suas principais caracter´\u131sticas que elas
na\u2dco permitem escrever programas amb´\u131guos. O portugue\u2c6s permite.

Sem entrarmos muito em detalhes desta grama´tica, a t´\u131tulo de exemplo mostrare-
mos verso\u2dces em mais alto n´\u131vel do programa da figura 4.9. Estas verso\u2dces sa\u2dco apresen-
tadas na figura 4.10.

read B
read C
discriminante \u2190 B2 - 4 × C
raizDiscriminante \u2190 \u221adiscriminante
menorRaiz \u2190 B\u2212raizDiscriminante

2

write menorRaiz
maiorRaiz \u2190 B+raizDiscriminante

2

write maiorRaiz

read B
read C

raizDiscriminante \u2190 \u221aB2 \u2212 4× C
write B - raizDiscriminante

2

write C + raizDiscriminante
2

Figura 4.10: Duas outras verso\u2dces do programa.

Estas verso\u2dces sa\u2dco compreens´\u131veis para o ser humano, mas ainda na\u2dco esta\u2dco no
formato ideal para servirem de entrada para o compilador, em particular por causa
dos s´\u131mbolos de frac¸a\u2dco ou do expoente. Os compiladores exigem um grau maior de
rigidez, infelizmente. A disciplina Construc¸a\u2dco de Compiladores, no sexto per´\u131odo do
curso, e´ exclusiva para o estudo profundo dos motivos desta dificuldade, tanto de se
verificar se o programa esta´ correto do ponto de vista gramatical, quanto do ponto de
vista de se traduzir o programa para linguagem de ma´quina.

4.5. CONCLUSA\u2dcO 33

No momento, vamos nos limitar a apresentar na figura 4.11 uma versa\u2dco do mesmo
programa escrito em Pascal. Apo´s compilac¸a\u2dco, o resultado e´ um programa que pode
ser executado pelo computador.

Em suma, o compilador Pascal e´ um programa que, entre outras coisas, consegue
transformar o co´digo de alto n´\u131vel mostrado na figura 4.11 e gerar um co´digo que o
computador possa executar tal como mostrado na primeira figura.

program bascara (input ,output) ;
var b, c , raiz discriminante : real ;

begin
read (b) ;
read (c) ;
raizdiscriminante:= sqrt(b\u2217b \u2212 4\u2217c) ;
write ((b \u2212 raizdiscriminante)/2) ;
write ((b + raizdiscriminante)/2) ;

end.

Figura 4.11: Versa\u2dco do programa escrito em Pascal.

4.5 Conclusa\u2dco

Nesta parte do texto procuramos mostrar que qualquer linguagem de programac¸a\u2dco
de alto n´\u131vel (tal como Pascal, C ou JAVA) e´ meramente uma notac¸a\u2dco convencionada
visando facilitar a vida do ser humano que programa o computador. Esta notac¸a\u2dco
trata de como um texto se traduz em um programa executa´vel em um determinado
sistema operacional (que usa um determinado conjunto reduzido de instruc¸o\u2dces).

Um programa que traduz um texto que emprega uma certa notac¸a\u2dco convencionada
em um programa executa´vel e´ chamado de \u201ccompilador\u201d.

Assim, a arte de se programar um computador em alto n´\u131vel e´, basicamente,
conhecer e dominar uma notac¸a\u2dco atrave´s da qual textos (ou programas fonte) sa\u2dco
traduzidos em programas executa´veis.

Programar, independentemente da linguagem utilizada, significa concatenar as
instruc¸o\u2dces dispon´\u131veis dentro de um reperto´rio a fim de transformar dados de entrada
em dados de sa´\u131da para resolver um problema.

Nas linguagens de alto n´\u131vel, as instruc¸o\u2dces complexas sa\u2dco traduzidas em uma
seque\u2c6ncia de operac¸o\u2dces elementares do reperto´rio ba´sico da ma´quina. Por isto os pro-
gramas fonte, quando compilados, geram executa´veis que sa\u2dco dependentes do sistema
operacional e do hardware da ma´quina onde o programa executa.

A partir destas ideias, partindo do princ´\u131pio que se tem um algoritmo que resolve
um problema, o que e´ preciso saber para se programar um computador?

\u2022 Ter a` disposic¸a\u2dco um editor de textos, para codificar o algoritmo na forma de
programa fonte;

34 CAPI´TULO 4. O MODELO DO COMPUTADOR

\u2022 Ter a` disposic¸a\u2dco um compilador para a linguagem escolhida (no nosso caso, o
Free Pascal), para transformar automaticamente um programa fonte em um
programa executa´vel.

No restante deste curso, vamos nos preocupar com a arte de se construir algoritmos,
tendo em mente que o estudante devera´ ser capaz de saber transformar este algoritmo
em forma de programa fonte de maneira que este possa ser compilado e finalmente
executado em um computador.

4.6. EXERCI´CIOS 35

4.6 Exerc´\u131cios

1. Para perceber como o ambiente do computador e´ limitado em func¸a\u2dco do redu-
zido nu´mero de instruc¸o\u2dces dispon´\u131veis em baixo n´\u131vel, voce\u2c6 pode tentar jogar
este jogo (http://armorgames.com/play/2205/light-bot). Nele, existe um
boneco que tem que cumprir um percurso com o objetivo de apagar todas as
ce´lulas azuis do terreno quadriculado usando apenas poucos comandos e com
pouca \u201cmemo´ria\u201d dispon´\u131vel. Voce\u2c6 pode fazer o uso de duas func¸o\u2dces que auxi-
liam nas tarefas repetitivas. Divirta-se!

2. Modifique a \u201cfotografia da memo´ria\u201d apresentada para que o computador resolva
a equac¸a\u2dco ax2 + bx + c = 0 pelo me´todo de Ba´scara. A diferenc¸a do que foi
apresentado e´ o coeficiente a do termo x2 e o sinal de b.

3. Leia os seguintes textos da wikipedia:

(a) http://pt.wikipedia.org/wiki/Arquitetura_de_von_Neumann, sobre a
arquitetura de von Neumann;

(b) http://pt.wikipedia.org/wiki/Von_Neumann, sobre a vida de von Neu-
mann, em especial a parte sobre computac¸a\u2dco.

36 CAPI´TULO 4. O MODELO DO COMPUTADOR

Cap´\u131tulo 5

Conceitos elementares

Agora que sabemos os princ´\u131pios de algoritmos e as limitac¸o\u2dces da ma´quina, e´ preciso
introduzir conceitos elementares de algoritmos, sem os quais na\u2dco e´ poss´\u131vel seguir
adiante.

Apresentaremos problemas simples o bastante para nos concentrarmos nas novi-
dades, isto e´, nos aspectos relevantes das estruturas de controle de fluxo e demais
conceitos presentes nas linguagens de programac¸a\u2dco. Nos pro´ximos cap´\u131tulos estas es-
truturas elementares sera\u2dco utilizadas na construc¸a\u2dco de soluc¸o\u2dces para problemas cada
vez mais sofisticados.

5.1 Algoritmos e linguagens de programac¸a\u2dco

Conforme vimos, os algoritmos devem ser escritos em um n´\u131vel de detalhamento su-
ficiente para que o compilador consiga fazer a traduc¸a\u2dco do co´digo para linguagem de
ma´quina.

O compilador precisa receber um texto formatado em uma linguagem simples, na\u2dco
amb´\u131gua, precisa. Para isto as linguagens de programac¸a\u2dco seguem uma grama´tica
r´\u131gida, se comparada com a da l´\u131ngua portuguesa. Tambe´m segue um vocabula´rio
limitado, constitu´\u131do de alguns poucos elementos.

O que vamos apresentar aqui e´ uma linguagem de mais alto n´\u131vel do que aquela
apresentada no cap´\u131tulo 4. Trata-se de uma maneira de escrever que e´ um ponto inter-
media´rio entre a capacidade de redac¸a\u2dco