apostila.pdf__
259 pág.

apostila.pdf__


DisciplinaAlgoritmos13.641 materiais163.033 seguidores
Pré-visualização50 páginas
linguagem formal que garanta que os pas-
sos do algoritmo sejam executados da maneira como se espera por quem executa as
instruc¸o\u2dces.
Vamos imaginar, a t´\u131tulo de ilustrac¸a\u2dco, 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\u2dco e´ o caso, pois a pessoa e´ inexperiente em cozinha e na\u2dco sabe o
que significa \u201cbater as claras em neve\u201d. Significa que o novato vai ficar sem o bolo.
O novato precisaria de algo mais detalhado, isto e´, de instruc¸o\u2dces 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\u131´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\u2dco parece na\u2dco ter fim.
Qual e´ o limite do processo de detalhamento da soluc¸a\u2dco?
O problema e´ que o cozinheiro que escreveu a receita original na\u2dco sabia o n´\u131vel de
instruc¸a\u2dco de quem ia efetivamente fazer o bolo. Para isto, e´ preciso que se estabelec¸a
o n´\u131vel m\u131´nimo de conhecimento para quem vai executar, assim quem escreve sabe ate´
onde deve ir o n´\u131vel de detalhamento de sua receita.
Um programa, neste sentido, e´ um algoritmo escrito de forma ta\u2dco detalhada quanto
for necessa´rio para quem executa as instruc¸o\u2dces. O algoritmo pode ser mais gene´rico,
o programa na\u2dco.
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\u2dces para posteriormente poder executa´-las com sucesso.
Qual e´, afinal, o conjunto de instruc¸o\u2dces 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´\u131cios
1. Escreva algoritmos como os que foram escritos neste cap´\u131tulo para cada uma
das soluc¸o\u2dces do problema discutido na sec¸a\u2dco 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´\u131tulo 4
O modelo do computador
Esta sec¸a\u2dco tem dois objetivos, o primeiro e´ mostrar como e´ o funcionamento dos
computadores modernos, isto e´, no n´\u131vel de ma´quina. A segunda e´ que o aluno
perceba, desde o in´\u131cio do seu aprendizado, as limitac¸o\u2dces a que esta´ sujeito quando
programa, e quais sa\u2dco todas as instruc¸o\u2dces que o computador conhece.
Ao final da leitura, o estudante deve compreender que, por mais sofisticada que
seja a linguagem de programac¸a\u2dco utilizada, a computac¸a\u2dco de verdade ocorre como
sera´ mostrado aqui.1
4.1 Histo´rico
Um computador (hardware) e´ um conjunto de circuitos eletro\u2c6nicos que manipulam
sinais ele´tricos e que sa\u2dco capazes de transformar sinais de entrada em sinais de sa´\u131da.
Os sinais ele´tricos podem ser representados, basicamente, pelos nu´meros zero e um.
Existem va´rias maneiras de se fazer isto, mas na\u2dco entraremos em detalhes neste texto.
O importante a destacar e´ que uma computac¸a\u2dco e´ uma manipulac¸a\u2dco de dados
residentes em memo´ria atrave´s de alterac¸o\u2dces de sinais ele´tricos realizadas por circuitos
integrados implementados normalmente em placas de sil´\u131cio.
Quando os computadores foram criados, na de´cada de 1930, a programac¸a\u2dco deles
era feita de maneira muito preca´ria. Era necessa´rio configurar uma situac¸a\u2dco 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\u2c6nicos.
1O texto que segue foi adaptado de outro escrito pelo prof. Renato Carmo para a disciplina CI-208
- Programac¸a\u2dco de Computadores ministrada para diversos cursos na UFPR.
21
22 CAPI´TULO 4. O MODELO DO COMPUTADOR
John von Neumann propo\u2c6s 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´\u131vel pela implementac¸a\u2dco em hardware de um limitado conjunto de
instruc¸o\u2dces que sa\u2dco usados pelo programa que esta´ em memo´ria. Isto revolucionou a
arte da programac¸a\u2dco. Os computadores modernos ainda funcionam assim.
Nesta sec¸a\u2dco pretende-se mostrar atrave´s de um exemplo os princ´\u131pios deste modelo.
4.2 Princ´\u131pios do modelo
Conforme explicado, Von Neumann propo\u2c6s que os dados e o programa poderiam ser
carregados em memo´ria ao mesmo tempo. Um elemento adicional denominado ciclo
de execuc¸a\u2dco de instruc¸o\u2dces controla a execuc¸a\u2dco do programa.
A ideia e´ implementar em hardware um pequeno conjunto de instruc¸o\u2dces que na\u2dco
mudam e programar o computador para realizar operac¸o\u2dces complexas a partir da
execuc¸a\u2dco de va´rias instruc¸o\u2dces ba´sicas da ma´quina.
Cada fabricante define o seu conjunto de instruc¸o\u2dces 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´\u131tulo 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\u2dco de
sinais ele´tricos que podem ser vistos pelo ser humano como uma seque\u2c6ncia absurda
de zeros e uns (chamados de bits).2
O ser humano costuma na\u2dco gostar muito desta forma de visualizac¸a\u2dco, enta\u2dco con-
vencionou algumas maneiras de enxergar nu´meros inteiros que representam os bits.
Na\u2dco vamos apresentar neste texto as diversas maneiras de conversa\u2dco de nu´meros, o
leitor interessado pode estudar sobre representac¸a\u2dco bina´ria na literatura.
Vamos imaginar que a memo´ria do computador e´ uma tabela contendo \u131´ndices
(enderec¸os) com conteu´dos (dados). A t´\u131tulo de exemplo, vamos considerar uma
\u201cfotografia\u201d 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\u2dco.
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
tarcio
tarcio fez um comentário
alguém tem as resoluções desses exercício dessa apostila, pois estou resolvendo e queria confirmar pra saber se estou fazendo correto. desde já obrigado
0 aprovações
Carregar mais