apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
a notac¸a˜o ou linguagem
de “alto n´ıvel”, que vai exigir a introduc¸a˜o dos chamados compiladores.

4.4 Abstrac¸a˜o das instruc¸o˜es (linguagem)

Apesar de todas as notac¸o˜es e convenc¸o˜es que foram feitas no programa, ate´ se chegar
na versa˜o 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´ıvel aumentar o n´ıvel de notac¸a˜o ainda mais e´ preciso contar com
a ajuda de programas tradutores, ou como eles sa˜o mais conhecidos, os compiladores.

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

32 CAPI´TULO 4. O MODELO DO COMPUTADOR

dois ← 2
quatro ← 4
B ← ∨
quadradoB ← B × B
C ← ∨
quadruploC ← quatro × C
discriminante ← quadradoB - quadruploC
raizDiscriminante ← √discriminante
dobroMenorRaiz ← B - raizDiscriminante
menorRaiz ← dobroMenorRaiz

dois

� ← menorRaiz
dobroMaiorRaiz ← B + raizDiscriminante
maiorRaiz ← dobroMaiorRaiz

dois

� ← maiorRaiz
•

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

poss´ıvel apenas se os programas forem escritos em um formato que respeite regras
extremamente r´ıgidas, pois sena˜o a tarefa na˜o seria poss´ıvel.

As linguagens de alto n´ıvel sa˜o definidas a partir de uma grama´tica extremamente
mais r´ıgida que a do portugueˆs, por exemplo. Estas grama´ticas, conhecidas como
grama´ticas livre de contexto, teˆm como uma de suas principais caracter´ısticas que elas
na˜o permitem escrever programas amb´ıguos. O portugueˆs permite.

Sem entrarmos muito em detalhes desta grama´tica, a t´ıtulo de exemplo mostrare-
mos verso˜es em mais alto n´ıvel do programa da figura 4.9. Estas verso˜es sa˜o apresen-
tadas na figura 4.10.

read B
read C
discriminante ← B2 - 4 × C
raizDiscriminante ← √discriminante
menorRaiz ← B−raizDiscriminante

2

write menorRaiz
maiorRaiz ← B+raizDiscriminante

2

write maiorRaiz

read B
read C

raizDiscriminante ← √B2 − 4× C
write B - raizDiscriminante

2

write C + raizDiscriminante
2

Figura 4.10: Duas outras verso˜es do programa.

Estas verso˜es sa˜o compreens´ıveis para o ser humano, mas ainda na˜o esta˜o no
formato ideal para servirem de entrada para o compilador, em particular por causa
dos s´ımbolos de frac¸a˜o ou do expoente. Os compiladores exigem um grau maior de
rigidez, infelizmente. A disciplina Construc¸a˜o de Compiladores, no sexto per´ıodo 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˜O 33

No momento, vamos nos limitar a apresentar na figura 4.11 uma versa˜o do mesmo
programa escrito em Pascal. Apo´s compilac¸a˜o, 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´ıvel 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∗b − 4∗c) ;
write ((b − raizdiscriminante)/2) ;
write ((b + raizdiscriminante)/2) ;

end.

Figura 4.11: Versa˜o do programa escrito em Pascal.

4.5 Conclusa˜o

Nesta parte do texto procuramos mostrar que qualquer linguagem de programac¸a˜o
de alto n´ıvel (tal como Pascal, C ou JAVA) e´ meramente uma notac¸a˜o convencionada
visando facilitar a vida do ser humano que programa o computador. Esta notac¸a˜o
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˜es).

Um programa que traduz um texto que emprega uma certa notac¸a˜o convencionada
em um programa executa´vel e´ chamado de “compilador”.

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

Programar, independentemente da linguagem utilizada, significa concatenar as
instruc¸o˜es dispon´ıveis dentro de um reperto´rio a fim de transformar dados de entrada
em dados de sa´ıda para resolver um problema.

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

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

• Ter a` disposic¸a˜o um editor de textos, para codificar o algoritmo na forma de
programa fonte;

34 CAPI´TULO 4. O MODELO DO COMPUTADOR

• Ter a` disposic¸a˜o 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´ıcios

1. Para perceber como o ambiente do computador e´ limitado em func¸a˜o do redu-
zido nu´mero de instruc¸o˜es dispon´ıveis em baixo n´ıvel, voceˆ 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 “memo´ria” dispon´ıvel. Voceˆ pode fazer o uso de duas func¸o˜es que auxi-
liam nas tarefas repetitivas. Divirta-se!

2. Modifique a “fotografia da memo´ria” apresentada para que o computador resolva
a equac¸a˜o 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˜o.

36 CAPI´TULO 4. O MODELO DO COMPUTADOR

Cap´ıtulo 5

Conceitos elementares

Agora que sabemos os princ´ıpios de algoritmos e as limitac¸o˜es da ma´quina, e´ preciso
introduzir conceitos elementares de algoritmos, sem os quais na˜o e´ poss´ıvel 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˜o. Nos pro´ximos cap´ıtulos estas es-
truturas elementares sera˜o utilizadas na construc¸a˜o de soluc¸o˜es para problemas cada
vez mais sofisticados.

5.1 Algoritmos e linguagens de programac¸a˜o

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

O compilador precisa receber um texto formatado em uma linguagem simples, na˜o
amb´ıgua, precisa. Para isto as linguagens de programac¸a˜o seguem uma grama´tica
r´ıgida, se comparada com a da l´ıngua portuguesa. Tambe´m segue um vocabula´rio
limitado, constitu´ıdo de alguns poucos elementos.

O que vamos apresentar aqui e´ uma linguagem de mais alto n´ıvel do que aquela
apresentada no cap´ıtulo 4. Trata-se de uma maneira de escrever que e´ um ponto inter-
media´rio entre a capacidade de redac¸a˜o