ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I717 materiais7.904 seguidores
Pré-visualização50 páginas
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 do ser humano e a capacidade de compreensa\u2dco
do computador.
A base das linguagens de programac¸a\u2dco, em geral, e´ constitu´\u131da por:
\u2022 a noc¸a\u2dco de fluxo de execuc¸a\u2dco de um programa;
\u2022 os comandos da linguagem que modificam os fluxo de execuc¸a\u2dco;
\u2022 os comandos, e demais conceitos da linguagem, que manipulam os dados em
memo´ria e a interac¸a\u2dco com o usua´rio (entrada e sa´\u131da de dados);
\u2022 as expresso\u2dces da linguagem que permitem a realizac¸a\u2dco de ca´lculos aritme´ticos e
lo´gicos;
37
38 CAPI´TULO 5. CONCEITOS ELEMENTARES
Neste cap´\u131tulo usaremos as regras do compilador Free Pascal e para isto o leitor
deve ter em ma\u2dcos algum guia de refere\u2c6ncia desta linguagem, por exemplo, o mini guia
de refere\u2c6ncia que esta´ dispon´\u131vel no site oficial da disciplina CI0551, onde as explicac¸o\u2dces
sa\u2dco detalhadas. Em sala de aula havera´ explicac¸a\u2dco satisfato´ria. Por outro lado, os
comandos da linguagem sa\u2dco suficientemente claros para que o programa fac¸a sentido,
basta traduzir literalmente os termos em ingle\u2c6s para suas verso\u2dces em portugue\u2c6s.
Os co´digos sera\u2dco escritos em Pascal, pois acreditamos que editar co´digo, compilar,
executar e testar programas ajuda o aluno a compreender os conceitos teo´ricos. Desta
forma os alunos podera\u2dco testar variantes em casa e melhorar o aprendizado.
5.2 Ca´lculo de ra´\u131zes de uma equac¸a\u2dco do segundo
grau
Problema: Calcular as ra´\u131zes da equac¸a\u2dco do segundo grau x2 \u2212 bx+ c = 0.
No cap´\u131tulo 4 no´s seguimos em detalhes o processo de obtenc¸a\u2dco da soluc¸a\u2dco em um
modelo de baixo n´\u131vel e chegamos a um co´digo de alto n´\u131vel escrito em Pascal. A
figura 5.1 e´ uma co´pia da soluc¸a\u2dco