apostila

linguagem formal que garanta que os pas-
sos do algoritmo sejam executados da maneira como se espera por quem executa as
instruc¸o˜es.
Vamos imaginar, a t´ıtulo de ilustrac¸a˜o, que e´ a primeira vez que a pessoa entra na
cozinha em toda a sua vida e resolve fazer um bolo de chocolate seguindo o algorimo 3.1
O algoritmo 3.1 foi escrito por um cozinheiro para ser executado por um outro
cozinheiro, o que na˜o e´ o caso, pois a pessoa e´ inexperiente em cozinha e na˜o sabe o
que significa “bater as claras em neve”. Significa que o novato vai ficar sem o bolo.
O novato precisaria de algo mais detalhado, isto e´, de instruc¸o˜es meticulosas de
como se obte´m claras em neve. Poderia ser algo como ilustrado na figura 3.2.
Algoritmo para fazer claras em neve
inı´cio
Repita os tre^s seguintes passos:
Pegue um ovo.
Quebre o ovo.
Separe a clara da gema.
Coloque somente a clara em um prato fundo.
Ate´ que todos os ovos tenham sido utilizados.
Pegue um garfo.
Mergulhe a ponta do garfo no prato.
Repita os seguinteis passos:
Bata a clara com o garfo por um tempo.
Levante o garfo.
Observe se a espuma produzida fica presa no garfo
Quando a espuma ficar presa no garfo, pare.
Neste ponto suas claras em neve est~ao prontas.
fim.
Figura 3.2: Algoritmo para fazer claras em neve.
Ja´ temos algo mais detalhado, mas nosso inexperiente cozinheiro pode ainda ter
problemas: como se separa a clara da gema? Este tipo de situac¸a˜o parece na˜o ter fim.
Qual e´ o limite do processo de detalhamento da soluc¸a˜o?
O problema e´ que o cozinheiro que escreveu a receita original na˜o sabia o n´ıvel de
instruc¸a˜o de quem ia efetivamente fazer o bolo. Para isto, e´ preciso que se estabelec¸a
o n´ıvel mı´nimo de conhecimento para quem vai executar, assim quem escreve sabe ate´
onde deve ir o n´ıvel de detalhamento de sua receita.
Um programa, neste sentido, e´ um algoritmo escrito de forma ta˜o detalhada quanto
for necessa´rio para quem executa as instruc¸o˜es. O algoritmo pode ser mais gene´rico,
o programa na˜o.
Como estamos pensando em deixar que o computador execute um algoritmo, pre-
cisamos escrever um programa em uma linguagem que o computador possa entender
3.2. O QUE E´ UM PROGRAMA? 19
as instruc¸o˜es para posteriormente poder executa´-las com sucesso.
Qual e´, afinal, o conjunto de instruc¸o˜es que o computador conhece? Para responder
a esta pergunta precisamos conhecer melhor como funciona um computador, para, em
seguida, continuarmos no estudo de algoritmos.
20 CAPI´TULO 3. SOBRE ALGORITMOS E PROGRAMAS
3.3 Exerc´ıcios
1. Escreva algoritmos como os que foram escritos neste cap´ıtulo para cada uma
das soluc¸o˜es do problema discutido na sec¸a˜o 2.1.
2. Escreva um algoritmo para o problema da troca de um u´nico pneu de um carro.
3. Escreva um algoritmo para o problema de trocar um pneu de uma bicicleta.
Cap´ıtulo 4
O modelo do computador
Esta sec¸a˜o tem dois objetivos, o primeiro e´ mostrar como e´ o funcionamento dos
computadores modernos, isto e´, no n´ıvel de ma´quina. A segunda e´ que o aluno
perceba, desde o in´ıcio do seu aprendizado, as limitac¸o˜es a que esta´ sujeito quando
programa, e quais sa˜o todas as instruc¸o˜es que o computador conhece.
Ao final da leitura, o estudante deve compreender que, por mais sofisticada que
seja a linguagem de programac¸a˜o utilizada, a computac¸a˜o de verdade ocorre como
sera´ mostrado aqui.1
4.1 Histo´rico
Um computador (hardware) e´ um conjunto de circuitos eletroˆnicos que manipulam
sinais ele´tricos e que sa˜o capazes de transformar sinais de entrada em sinais de sa´ıda.
Os sinais ele´tricos podem ser representados, basicamente, pelos nu´meros zero e um.
Existem va´rias maneiras de se fazer isto, mas na˜o entraremos em detalhes neste texto.
O importante a destacar e´ que uma computac¸a˜o e´ uma manipulac¸a˜o de dados
residentes em memo´ria atrave´s de alterac¸o˜es de sinais ele´tricos realizadas por circuitos
integrados implementados normalmente em placas de sil´ıcio.
Quando os computadores foram criados, na de´cada de 1930, a programac¸a˜o deles
era feita de maneira muito preca´ria. Era necessa´rio configurar uma situac¸a˜o dos
circuitos para manipular os sinais ele´tricos da maneira desejada para cada programa
particular. Para se executar outro programa era necessa´rio alterar os circuitos, assim
se reprogramando o computador para manipular os dados de outra maneira.
Um computador era algo raro naqueles tempos, e devia rodar va´rios programas
diferentes, o que resultava em imenso trabalho para os engenheiros (os programadores
eram engenheiros na e´poca).
A memo´ria do computador, naqueles tempos, era exclusividade dos dados que
seriam manipulados. O programa era feito nos circuitos eletroˆnicos.
1O texto que segue foi adaptado de outro escrito pelo prof. Renato Carmo para a disciplina CI-208
- Programac¸a˜o de Computadores ministrada para diversos cursos na UFPR.
21
22 CAPI´TULO 4. O MODELO DO COMPUTADOR
John von Neumann propoˆs um modelo bastante simples, no qual tanto o programa
quanto os dados poderiam ficar simultaneamente em memo´ria, desde que a parte que
ficaria programada nos circuitos pudesse interpretar o que era dado e o que era o
programa e realizar os ca´lculos, isto e´, manipular os dados.
Isto foi poss´ıvel pela implementac¸a˜o em hardware de um limitado conjunto de
instruc¸o˜es que sa˜o usados pelo programa que esta´ em memo´ria. Isto revolucionou a
arte da programac¸a˜o. Os computadores modernos ainda funcionam assim.
Nesta sec¸a˜o pretende-se mostrar atrave´s de um exemplo os princ´ıpios deste modelo.
4.2 Princ´ıpios do modelo
Conforme explicado, Von Neumann propoˆs que os dados e o programa poderiam ser
carregados em memo´ria ao mesmo tempo. Um elemento adicional denominado ciclo
de execuc¸a˜o de instruc¸o˜es controla a execuc¸a˜o do programa.
A ideia e´ implementar em hardware um pequeno conjunto de instruc¸o˜es que na˜o
mudam e programar o computador para realizar operac¸o˜es complexas a partir da
execuc¸a˜o de va´rias instruc¸o˜es ba´sicas da ma´quina.
Cada fabricante define o seu conjunto de instruc¸o˜es ba´sicas, mas o importante a
observar e´ que, uma vez implementadas, este conjunto define tudo o que o computador
sabe fazer. E´ isto que queremos saber.
Neste cap´ıtulo vamos usar como exemplo um computador fabricado pela Big Com-
puter Company (BCC).
4.2.1 Enderec¸os versus conteu´dos
O computador da BCC implementa o modelo Von Neumann, logo, sua memo´ria
conte´m os dados e o programa.
A memo´ria do computador em um dado instante do tempo e´ uma configurac¸a˜o de
sinais ele´tricos que podem ser vistos pelo ser humano como uma sequeˆncia absurda
de zeros e uns (chamados de bits).2
O ser humano costuma na˜o gostar muito desta forma de visualizac¸a˜o, enta˜o con-
vencionou algumas maneiras de enxergar nu´meros inteiros que representam os bits.
Na˜o vamos apresentar neste texto as diversas maneiras de conversa˜o de nu´meros, o
leitor interessado pode estudar sobre representac¸a˜o bina´ria na literatura.
Vamos imaginar que a memo´ria do computador e´ uma tabela contendo ı´ndices
(enderec¸os) com conteu´dos (dados). A t´ıtulo de exemplo, vamos considerar uma
“fotografia” da memo´ria de um computador da BCC em um certo momento, fotografia
esta apresentada na figura 4.1
2Quem assistiu ao filme Matrix pode imaginar a complicac¸a˜o.
4.2. PRINCI´PIOS DO MODELO 23
Enderec¸o Conteu´do
0 1
1 54
2 2
3 1
4 50
5 4
6 7
7 46
8 4
9 47
10 46
11 46
12 7
13 48
14 4
15 49
16 50
17 48
18 3
19 51
20 47
Enderec¸o Conteu´do
21 49
22 6
23 52
24 51
25 3
26 53
27 46
28 52
29 5
30 55
31 53
32 54
33 8
34 55
35 2
36 56
37 46
38 52
39 5
40 57
41 56
Enderec¸o Conteu´do
42 54
43 8
44 57
45 9
46 33
47 2
48 76
49 67
50 76
51 124
52 14
53 47
54 235
55 35
56 23
57 78
58 243