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