apostila de C

Prévia do material em texto

Curso de Linguagem C
Em Construção
v0.003.11
Adriano Joaquim de Oliveira Cruz
Instituto de Matemáti
a
Nú
leo de Computação Eletr�ni
a
UFRJ
©2011 Adriano Cruz
17 de outubro de 2013
Sumário
1 Introdução 6
1.1 Su
essos e Fra
assos da Computação . . . . . . . . . . . . . . . . 6
1.2 Um Pou
o da História da Computação . . . . . . . . . . . . . . . 8
1.2.1 O Iní
io . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 A Era Moderna . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 O Desenvolvimento durante as Grandes Guerras . . . . . 11
1.2.4 As Gerações . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 O Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 Mi
ro
omputadores . . . . . . . . . . . . . . . . . . . . . 15
1.3.2 Memórias . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Bits e Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.4 Periféri
os . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 O Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Um programa em C . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Algoritmos 27
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Primeiros Passos . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Representação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Linguagem Natural . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Fluxogramas . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.3 Pseudo-Linguagem . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Modelo de von Neumann . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Estruturas Bási
as de Algoritmos . . . . . . . . . . . . . . . . . . 34
2.5.1 Comandos de leitura . . . . . . . . . . . . . . . . . . . . . 35
2.5.2 Comandos de es
rita . . . . . . . . . . . . . . . . . . . . . 35
2.5.3 Expressões . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1
2.5.4 Comandos de atribuição . . . . . . . . . . . . . . . . . . . 38
2.5.5 Comandos de 
ontrole . . . . . . . . . . . . . . . . . . . . 39
2.5.6 Comandos de repetição . . . . . . . . . . . . . . . . . . . 40
2.6 Exemplos de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . 41
2.7 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3 Tipos de Dados, Constantes e Variáveis 48
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Tipos de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 Tipos Bási
os . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 Modi�
adores de tipos . . . . . . . . . . . . . . . . . . . . 49
3.3 Constantes Numéri
as . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Constantes Inteiras na base 10 . . . . . . . . . . . . . . . 50
3.3.2 Constantes Inteiras O
tais . . . . . . . . . . . . . . . . . . 51
3.3.3 Constantes Inteiras Hexade
imais . . . . . . . . . . . . . . 52
3.3.4 Conversão entre Bases . . . . . . . . . . . . . . . . . . . . 52
3.3.5 Constantes em Ponto Flutuante . . . . . . . . . . . . . . . 53
3.4 Constantes Cara
teres . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 Constantes Cadeias de Cara
teres . . . . . . . . . . . . . 55
3.5 Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5.1 Nomes das Variáveis . . . . . . . . . . . . . . . . . . . . . 56
3.5.2 De
laração de variáveis . . . . . . . . . . . . . . . . . . . 56
3.5.3 Atribuição de valores . . . . . . . . . . . . . . . . . . . . . 57
3.6 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Entrada e Saída pelo Console 60
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Bibliote
a Padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Saída - A Função printf . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.1 Códigos de Conversão . . . . . . . . . . . . . . . . . . . . 62
4.4 Entrada - A Função s
anf . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Lendo e Imprimindo Cara
teres . . . . . . . . . . . . . . . . . . . 66
4.5.1 Funções get
har e put
har . . . . . . . . . . . . . . . . . 66
4.5.2 Lendo e Imprimindo Cadeias de Cara
teres . . . . . . . . 67
4.5.3 Lendo e Imprimindo 
adeias 
om s
anf e printf . . . . . 68
4.5.4 Lendo e Imprimindo 
adeias 
om gets e puts . . . . . . . 69
4.5.5 A Função fgets . . . . . . . . . . . . . . . . . . . . . . . 69
4.6 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2
5 Operadores e Expressões 72
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2 Operador de Atribuição . . . . . . . . . . . . . . . . . . . . . . . 72
5.3 Operadores Aritméti
os . . . . . . . . . . . . . . . . . . . . . . . 73
5.4 Operadores Rela
ionais e Lógi
os . . . . . . . . . . . . . . . . . . 74
5.4.1 Operadores Rela
ionais . . . . . . . . . . . . . . . . . . . 74
5.4.2 Operadores Lógi
os . . . . . . . . . . . . . . . . . . . . . 74
5.5 Operadores 
om Bits . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6 Operadores de Atribuição Composta . . . . . . . . . . . . . . . . 78
5.7 Operador vírgula . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.8 Operador sizeof() . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.9 Conversão de Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.10 Regras de Pre
edên
ia . . . . . . . . . . . . . . . . . . . . . . . . 81
5.11 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 Comandos de Controle 84
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.2 Blo
os de Comandos . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Comandos de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1 Comando if . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.2 Comando swit
h . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.3 Comando Ternário . . . . . . . . . . . . . . . . . . . . . . 89
6.4 Laços de Repetição . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4.1 Comando for . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4.2 Comando while . . . . . . . . . . . . . . . . . . . . . . . 94
6.4.3 Comando do-while . . . . . . . . . . . . . . . . . . . . . 95
6.5 Comandos de Desvio . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.5.1 Comando break . . . . . . . . . . . . . . . . . . . . . . . 96
6.5.2 Comando 
ontinue . . . . . . . . . . . . . . . . . . . . . 96
6.5.3 Comando goto . . . . . . . . . . . . . . . . . . . . . . . . 96
6.5.4 Função exit() . . . . . . . . . . . . . . . . . . . . . . . . 97
6.5.5 Comando return . . . . . . . . . . . . . . . . . . . . . . . 97
6.6 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3
7 Vetores e Cadeias de Cara
teres 101
7.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2 De
laração de Vetores Unidimensionais . . . . . . . . . . . . . . . 101
7.3 Cadeias de Cara
teres . . . . . . . . . . . . . . . . . . . . . . . . 104
7.4 De
laração de Vetores Multidimensionais . . . . . . . . . . . . . . 106
7.5 Vetores de Cadeias de Cara
teres . . . . . . . . . . . . . . . . . . 110
7.6 Ini
ialização de Vetores e Matrizes . . . . . . . . . . . . . . . . . 110
7.7 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
8 Funções 117
8.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2 Forma Geral . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.3 Protótipos de Funções . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4 Es
opo de Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4.1 Variáveis Lo
ais . . . . . . . . . . . . . . . . . . . . . . . 120
8.4.2 Variáveis Globais . . . . . . . . . . . . . . . . . . . . . . . 122
8.5 Parâmetros Formais . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.5.1 Passagem de Parâmetros por Valor . . . . . . . . . . . . . 123
8.5.2 Passagem de Parâmetros por Referên
ia . . . . . . . . . . 124
8.5.3 Passagem de Vetores e Matrizes . . . . . . . . . . . . . . . 124
8.6 O Comando return . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.7 Re
ursão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.7.1 Como pensar re
ursivamente? . . . . . . . . . . . . . . . . 130
8.7.2 O que faz re
ursão trabalhar? . . . . . . . . . . . . . . . . 131
8.8 Argumentos - arg
 e argv . . . . . . . . . . . . . . . . . . . . . . 131
8.9 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9 Ponteiros 136
9.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
9.2 Operações 
om Ponteiros . . . . . . . . . . . . . . . . . . . . . . 137
9.2.1 De
laração de Ponteiros . . . . . . . . . . . . . . . . . . . 137
9.2.2 Os Operadores Espe
iais para Ponteiros . . . . . . . . . . 138
9.2.3 Atribuição de Ponteiros . . . . . . . . . . . . . . . . . . . 139
9.2.4 In
rementando e De
rementando Ponteiros . . . . . . . . 141
9.2.5 Comparação de Ponteiros . . . . . . . . . . . . . . . . . . 142
9.3 Ponteiros e Vetores . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.4 Ponteiros e Cadeias de Cara
teres . . . . . . . . . . . . . . . . . 144
9.5 Alo
ação Dinâmi
a de Memória . . . . . . . . . . . . . . . . . . . 144
4
9.6 Ponteiros e Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.7 Vetores de Ponteiros . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.8 Ponteiros para Ponteiros . . . . . . . . . . . . . . . . . . . . . . . 150
9.9 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10 Estruturas 158
10.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
10.2 De�nições Bási
as . . . . . . . . . . . . . . . . . . . . . . . . . . 158
10.3 Atribuição de Estruturas . . . . . . . . . . . . . . . . . . . . . . . 161
10.4 Matrizes de Estruturas . . . . . . . . . . . . . . . . . . . . . . . . 161
10.5 Estruturas e Funções . . . . . . . . . . . . . . . . . . . . . . . . . 162
10.6 Ponteiros para Estruturas . . . . . . . . . . . . . . . . . . . . . . 165
10.7 Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
11 Entrada e Saída por Arquivos 170
11.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
11.2 Fluxos de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
11.2.1 Fluxos de Texto . . . . . . . . . . . . . . . . . . . . . . . 170
11.2.2 Fluxo Binário . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.2.3 Arquivos . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.3 Funções de Entrada e Saída . . . . . . . . . . . . . . . . . . . . . 172
11.4 Iní
io e Fim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
11.4.1 Abrindo um Arquivo . . . . . . . . . . . . . . . . . . . . . 173
11.4.2 Fe
hando um Arquivo . . . . . . . . . . . . . . . . . . . . 174
11.4.3 Fim de Arquivo . . . . . . . . . . . . . . . . . . . . . . . . 174
11.4.4 Volta ao Iní
io . . . . . . . . . . . . . . . . . . . . . . . . 175
11.5 Lendo e Es
revendo Cara
teres . . . . . . . . . . . . . . . . . . . 175
11.6 Testando Erros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
11.7 Lendo e Es
revendo Cadeias de Cara
teres . . . . . . . . . . . . . 179
11.8 Entrada e Saída Formatada . . . . . . . . . . . . . . . . . . . . . 180
11.9 Lendo e Es
revendo Arquivos Binários . . . . . . . . . . . . . . . 181
11.10Exer
í
ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
12 Problemas Extras 187
A Tabela ASCII 197
B Palavras Reservadas 199
5
Lista de Figuras
1.1 Fotogra�a de um 
ir
uito integrado de mi
ropro
essador Pentium. 7
1.2 Imagem de um ába
o. . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Blaise Pas
al . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Charles Babbage . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Fotogra�a da Di�eren
e Engine . . . . . . . . . . . . . . . . . . . 10
1.6 Computador Enia
 . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Diagrama Bási
o de um Computador Digital . . . . . . . . . . . 15
1.8 Níveis de hierarquia da memória de um 
omputador. . . . . . . . 16
1.9 Tamanho de Bits, Bytes e Palavras . . . . . . . . . . . . . . . . . 18
1.10 Ci
lo de desenvolvimento de um programa. . . . . . . . . . . . . 23
2.1 Símbolos mais 
omumente usados em �uxogramas. . . . . . . . . 31
2.2 Fluxograma para resolver uma equação do primeiro grau. . . . . 32
2.3 Modelo de memória . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Fluxograma do 
omando se ... então ... senão. . . . . . . 39
2.5 Fluxograma para de
idir se deve levar um guarda-
huva. . . . . . 41
2.6 Fluxograma do 
omando enquanto. . . . . . . . . . . . . . . . . 43
7.1 Mapa de memória de uma matriz. . . . . . . . . . . . . . . . . . 110
9.1 Mapa de memória 
om duas variáveis e ponteiro. . . . . . . . . . 136
9.2 Ponteiro apontando para área de memória 
ontendo vetor. . . . . 137
9.3 De
laração de ponteiros. . . . . . . . . . . . . . . . . . . . . . . . 138
9.4 Atribuição de endereço de uma variável a um ponteiro. . . . . . . 139
9.5 Uso de um ponteiro para 
opiar valor de uma variável. . . . . . . 139
9.6 Exemplos de atribuições de ponteiros. . . . . . . . . . . . . . . . 140
9.7 Armazenamento de matrizes 
om vetores de ponteiros. . . . . . . 150
11.1 Fluxos de dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6
Lista de Tabelas
1.1 Transistores por 
ir
uito integrado nos mi
ropro
essadores da Intel 7
1.2 Tempo de exe
ução das instruções aritméti
as no ENIAC . . . . 12
1.3 Exemplos de Mi
ropro
essadores . . . . . . . . . . . . . . . . . . 15
1.4 Abreviações usadas em referên
ias às memórias. . . . . . . . . . . 19
1.5 Exemplos de periféri
os . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Operadores Aritméti
os. . . . . . . . . . . . . . . . . . . . . . . . 38
3.1 Tipos de dados de�nidos pelo Padrão ANSI C. . . . . . . . . . . 50
3.2 Constantes Inteiras na Base 10 . . . . . . . . . . . . . . . . . . . 51
3.3 Constantes o
tais . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Constantes hexade
imais . . . . . . . . . . . . . . . . . . . . . . . 52
3.5 Constantes em ponto �utuante . . . . . . . . . . . . . . . . . . . 54
3.6 Exemplos de 
onstantes 
ara
tere . . . . . . . . . . . . . . . . . . 55
3.7 Exemplos de 
ara
teres invisíveis. . . . . . . . . . . . . . . . . . . 55
3.8 Tabela do exer
i
io 6 . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1 Códigos de Conversão para es
rita de dados. . . . . . . . . . . . . 62
5.1 Operadores aritméti
os. . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 Operadores Rela
ionais. . . . . . . . . . . . . . . . . . . . . . . . 74
5.3 Operador Lógi
o E. . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4 Operador Lógi
o OU. . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Operador Lógi
o N�O. . . . . . . . . . . . . . . . . . . . . . . . . 76
5.6 Pre
edên
ia dos operadores lógi
os e rela
ionais. . . . . . . . . . 765.7 Operadores 
om bits. . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.8 Operador Lógi
o OU. . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.9 Pre
edên
ia dos operadores. . . . . . . . . . . . . . . . . . . . . . 81
7.1 Passos exe
utados durante o algoritmo da bolha. . . . . . . . . . 103
7
11.1 Exemplos de funções de Entrada e Saída. . . . . . . . . . . . . . 173
A.1 Conjunto de 
ara
teres ASCII . . . . . . . . . . . . . . . . . . . . 197
A.2 Conjunto de 
ódigos espe
iais ASCII e seus signi�
ados . . . . . 198
8
Lista de Algoritmos
2.1 Exemplo de Algoritmo. . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Algoritmo para resolver uma equação do primeiro grau. . . . . . . 29
2.3 Algoritmo para 
al
ular a média das notas de um aluno. . . . . . 31
2.4 Algoritmo para 
al
ular a maior nota de um grupo de notas. . . . 33
2.5 Modelo de memória e fun
ionamento de um algoritmo . . . . . . . 34
2.6 Comando se em pseudo-linguagem . . . . . . . . . . . . . . . . . . 39
2.7 Algoritmo para de
idir o que fazer no domingo. . . . . . . . . . . 40
2.8 Algoritmo para de
idir se deve levar um guarda-
huva. . . . . . . 40
2.9 Algoritmo para ler 10 números e imprimir se são pares ou não. . . 42
2.10 Algoritmo para ler números e imprimir se são pares ou não. A quantidade de números a ser lida é des
onhe
ida. 42
2.11 Algoritmo para 
al
ular a maior nota de uma turma de 25 alunos. 44
2.12 Algoritmo para 
al
ular a nota média de uma turma de 25 alunos. 44
2.13 Algoritmo para 
al
ular a maior temperatura do ano. . . . . . . . 45
2.14 Algoritmo do exer
í
io 11. . . . . . . . . . . . . . . . . . . . . . . 47
2.15 Algoritmo do exer
í
io 11. . . . . . . . . . . . . . . . . . . . . . . 47
3.1 Algoritmo para 
onverter inteiros na base 10 para uma base b. . . 53
9
Listings
1.1 Exemplo de Programa em C. . . . . . . . . . . . . . . . . . . . . 25
4.1 Exemplo de impressão de resultados . . . . . . . . . . . . . . . . 61
4.2 Exemplo de justi�
ação de resultados. . . . . . . . . . . . . . . . 63
4.3 Exemplo de uso de espe
i�
ador de pre
isão. . . . . . . . . . . . 64
4.4 Exemplo de uso de s
anf. . . . . . . . . . . . . . . . . . . . . . 66
4.5 Exemplo de uso de get
har e put
har. . . . . . . . . . . . . . . 67
4.6 Exemplo de uso de get
har e put
har. . . . . . . . . . . . . . . 67
4.7 Exemplo de uso de printf e s
anf na leitura de 
adeias. . . . . 68
4.8 Exemplo de uso de puts e gets na leitura de 
adeias. . . . . . . 70
5.1 Exemplo de operadores de deslo
amento. . . . . . . . . . . . . . 78
5.2 Exemplo do operador sizeof. . . . . . . . . . . . . . . . . . . . 80
5.3 Variáveis da questão 9. . . . . . . . . . . . . . . . . . . . . . . . 83
6.1 Exemplo de 
omandos if. . . . . . . . . . . . . . . . . . . . . . . 86
6.2 Programas 
om if's em es
ada e aninhados. . . . . . . . . . . . . 87
6.3 Exemplo de swit
h. . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.4 Exemplo de 
omando ternário. . . . . . . . . . . . . . . . . . . . 91
6.5 Exemplo de 
omando for. . . . . . . . . . . . . . . . . . . . . . . 92
6.6 Exemplo de 
omando for 
om testes sobre outras variáveis. . . . 92
6.7 Exemplo de 
omando for sem alteração da variável de 
ontrole. 93
6.8 Exemplo de 
omando for sem teste de �m. . . . . . . . . . . . . 93
6.9 Comando for aninhados. . . . . . . . . . . . . . . . . . . . . . . 94
6.10 Comando while 
om uma função. . . . . . . . . . . . . . . . . . 95
6.11 Programa do exer
i
io 17. . . . . . . . . . . . . . . . . . . . . . 100
7.1 Exemplo de vetores. . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.2 Produto es
alar de dois vetores. . . . . . . . . . . . . . . . . . . 104
7.3 Ordenação pelo método da bolha. . . . . . . . . . . . . . . . . . 105
7.4 Exemplos de funções para 
adeias. . . . . . . . . . . . . . . . . . 107
7.5 Leitura de uma matriz. . . . . . . . . . . . . . . . . . . . . . . . 108
10
7.6 Multipli
ação de duas matrizes. . . . . . . . . . . . . . . . . . . 109
7.7 Leitura de um vetor de nomes. . . . . . . . . . . . . . . . . . . . 111
7.8 Exemplos de tratamento de vetores. . . . . . . . . . . . . . . . . 112
7.9 Exemplos de tratamento de vetores. . . . . . . . . . . . . . . . . 113
7.10 Programa do exer
i
io 14. . . . . . . . . . . . . . . . . . . . . . 116
8.1 Exemplo de protótipos. . . . . . . . . . . . . . . . . . . . . . . . 120
8.2 Exemplos de variáveis lo
ais. . . . . . . . . . . . . . . . . . . . . 121
8.3 De�nição de variável dentro de um blo
o. . . . . . . . . . . . . . 121
8.4 De�nição de variável global. . . . . . . . . . . . . . . . . . . . . 122
8.5 Exemplo de passagem por valor. . . . . . . . . . . . . . . . . . . 123
8.6 Uso indevido de variáveis lo
ais. . . . . . . . . . . . . . . . . . . 124
8.7 Passagem de vetor 
om dimensões. . . . . . . . . . . . . . . . . 125
8.9 Fatorial 
al
ulado não re
ursivamente. . . . . . . . . . . . . . . 126
8.8 Passagem de vetores sem dimensões. . . . . . . . . . . . . . . . 127
8.10 Fatorial 
al
ulado re
ursivamente. . . . . . . . . . . . . . . . . . 128
8.11 Chamada re
ursiva direta. . . . . . . . . . . . . . . . . . . . . . 128
8.12 Chamada re
ursiva indireta. . . . . . . . . . . . . . . . . . . . . 129
8.13 Função re
ursiva para 
al
ular xn. . . . . . . . . . . . . . . . . . 129
8.14 Chamada re
ursiva 
om 
auda. . . . . . . . . . . . . . . . . . . 129
8.15 Chamada re
ursiva sem 
auda. . . . . . . . . . . . . . . . . . . . 130
8.16 Soma de vetor re
ursiva. . . . . . . . . . . . . . . . . . . . . . . 131
8.17 Uso de arg
 e argv. . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.18 Programa do exer
í
io 8. . . . . . . . . . . . . . . . . . . . . . . 134
8.19 Programa do problema 9. . . . . . . . . . . . . . . . . . . . . . . 134
9.1 Exemplo de atribuição de ponteiros. . . . . . . . . . . . . . . . . 140
9.2 Exemplos de operações 
om ponteiros. . . . . . . . . . . . . . . 141
9.3 Exemplo de subtração de ponteiros. . . . . . . . . . . . . . . . . 142
9.4 Exemplo de 
omparação de ponteiros. . . . . . . . . . . . . . . . 142
9.5 Exemplo de alterações inválidas sobre ponteiros. . . . . . . . . . 143
9.6 Exemplo de notações de vetores. . . . . . . . . . . . . . . . . . . 143
9.7 Exemplo de ponteiro variável. . . . . . . . . . . . . . . . . . . . 144
9.8 Exemplo de ponteiro para 
adeia de 
ara
teres. . . . . . . . . . 145
9.9 Exemplo de 
ópia de 
adeias de 
ara
teres. . . . . . . . . . . . . 145
9.10 Exemplo de uso de 
allo
 e free. . . . . . . . . . . . . . . . . . 146
9.11 Exemplo de uso de mallo
. . . . . . . . . . . . . . . . . . . . . . 147
9.12 Exemplo de matriz normal sem uso de ponteiros. . . . . . . . . 148
9.13 Exemplo de matriz mapeada em um vetor. . . . . . . . . . . . . 148
11
9.14 Exemplo de uso de vetor de ponteiros. . . . . . . . . . . . . . . 149
9.15 Exemplo de uso de ponteiros para ponteiros. . . . . . . . . . . . 151
9.16 Exemplo de uso de ponteiros para ponteiros usando funções. . . 152
9.17 Continuação do exemplo 9.16. . . . . . . . . . . . . . . . . . . . 153
9.18 Programa do exer
i
io 11. . . . . . . . . . . . . . . . . . . . . . 155
9.19 Programa do exer
i
io 12. . . . . . . . . . . . . . . . . . . . . . 156
9.20 Listagem do exer
í
io 13. . . . . . . . . . . . . . . . . . . . . . . 156
9.21 Programa do exer
í
io 14. . . . . . . . . . . . . . . . . . . . . . 157
10.1 De�nição de uma estrutura. . . . . . . . . . . . . . . . . . . . . . 159
10.2 Atribuição de Estruturas. . . . . . . . . . . . . . . . . . . . . . . 161
10.3 Ordenação de Estruturas. . . . . . . . . . . . . . . . . . . . . . . 162
10.4 Passando elementos para funções. . . . . . . . . . . . . . . . . . 163
10.5 Passagemde estruturas para funções. . . . . . . . . . . . . . . . 164
10.6 Função que ordena estruturas. . . . . . . . . . . . . . . . . . . . 164
10.7 Alo
ação de espaço para estruturas. . . . . . . . . . . . . . . . . 166
10.8 Alo
ação de espaço para vetores de estruturas. . . . . . . . . . . 167
10.9 Listagem do exer
i
io 3. . . . . . . . . . . . . . . . . . . . . . . 168
11.1 Uso da função feof(). . . . . . . . . . . . . . . . . . . . . . . . 175
11.4 Uso da função ferror(). . . . . . . . . . . . . . . . . . . . . . . 176
11.2 Exemplo de leitura e es
rita de 
ara
teres. . . . . . . . . . . . . 177
11.3 Exemplo de leitura e es
rita de 
ara
teres. . . . . . . . . . . . . 178
11.5 Exemplo de leitura e es
rita de 
adeias de 
ara
teres. . . . . . . 179
11.6 Exemplo de leitura e es
rita de dados formatados. . . . . . . . . 180
11.7 Exemplo de leitura e es
rita na forma binária. . . . . . . . . . . 182
11.8 Exemplo de leitura e es
rita de estruturas. . . . . . . . . . . . . 183
11.9 (I) Tre
ho de programa do problema 14. . . . . . . . . . . . . . 186
11.10(II) Tre
ho de programa do problema 14. . . . . . . . . . . . . . 186
12.1 Pro
essando o CPF. . . . . . . . . . . . . . . . . . . . . . . . . . 190
12.2 Estrutura do problema 8. . . . . . . . . . . . . . . . . . . . . . . 194
12
Capítulo 1
Introdução
1.1 Su
essos e Fra
assos da Computação
Os objetivos prin
ipais deste 
apítulo são mostrar para o aluno ini
iante alguns
aspe
tos da história da 
omputação e de�nir, informalmente, termos e palavras-
have que os pro�ssionais da área de 
omputação usam no seu dia a dia. Adriano
Cruz©.
A história do desenvolvimento dos 
omputadores tem sido impressionante.
O avanço da te
nologia e a presença da 
omputação na nossa vida são inegá-
veis. Embora a história deste fantásti
o desenvolvimento seja re
ente e bem
do
umentada, há la
unas e 
ontrovérsias impressionantes sobre diversos pontos.
Neste 
apítulo iremos ver histórias de espionagem e brigas na justiça por roubo
de ideias. Há oportunidades perdidas e gente que soube aproveitar a sua 
han
e.
Há verdades estabele
idas que tiveram de ser revistas.
O avanço na te
nologia dos 
omputadores se deu em passos tão largos que os
primeiros 
omputadores pare
em tão distantes no tempo quanto a Pré-História.
O aumento de velo
idade, desde os anos 40, foi da várias ordens de grandeza,
enquanto que o 
usto dos 
omputadores 
aiu de milhões de dólares para valo-
res em torno de 
entenas de dólares. As primeiras máquinas tinham milhares
de válvulas, o
upavam áreas enormes e 
onsumiam quilowatts de energia. O
mi
ropro
essador Pentium, lançado em 1993, tinha em torno de 3,1 milhões
de transistores, o
upava uma área de aproximadamente 25 cm2 e 
onsumia
alguns watts de energia, 
ustando aproximadamente 1000 dólares, somente o
mi
ropro
essador. A Figura 1.1 mostra a imagem de um 
ir
uito integrado de
mi
ropro
essador Pentium.
No entanto, esta história de redução de tamanho, aumento de velo
idade e
diminuição de gasto de potên
ia, pode, para alguns pesquisadores, já ter uma
data �xada para terminar. Em 1965, Gordon Moore, um dos fundadores da In-
tel, fabri
ante do Pentium e uma dos maiores fabri
antes de 
ir
uitos integrados
do mundo, enun
iou o que �
ou 
onhe
ido 
omo a Lei de Moore: �Cada novo
ir
uito integrado terá o dobro de transistores do anterior e será lançado dentro
de um intervalo de 18 a 24 meses.� Moore a
hava que esta lei seria válida so-
mente até 1975, no entanto, ela 
ontinua válida até hoje. Na tabela 1.1, pode-se
observar a evolução dos mi
ropro
essadores usados em nossos 
omputadores.
13
Figura 1.1: Fotogra�a de um 
ir
uito integrado de mi
ropro
essador Pentium.
Ano Pro
essador Transistores
1971 4004 2.250
1972 8008 2.500
1974 8080 5.000
1982 80286 120.000
1985 80386 275.500
1989 80486 DX 1.180.000
1993 Pentium 3.100.000
1997 Pentium II 7.500.000
1999 Pentium III 24.000.000
2000 Pentium 4 42.000.000
Tabela 1.1: Transistores por 
ir
uito integrado nos mi
ropro
essadores da Intel
Os transistores, que 
ompõem os 
ir
uitos eletr�ni
os, estão diminuindo de
tamanho, e estamos nos aproximando da fronteira �nal, os elétrons. Já se houve
falar em tamanho de transistores medidos em números de elétrons. Devemos nos
lembrar que toda a te
nologia atual está baseada em �uxo de elétrons, ou seja
uma 
orrente elétri
a. Os �os 
onduzem 
orrentes de elétrons e os transistores
ontrolam este �uxo. Se o tamanho diminuir além dos elétrons estaremos em
outro domínio.
No entanto, na história da 
omputação, muitas promessas não foram 
um-
pridas e falhas gigantes
as a
onte
eram. Como em diversas questões, artistas
geniais, apontam o que não 
onseguimos ou não queremos ver e mostram que
o rei está nu. Há uma frase de Pi
asso que diz: �Computadores são estúpi-
dos, eles somente 
onseguem responder perguntas�. Esta frase expõe 
om ironia
um fra
asso da 
omunidade de 
omputação que havia prometido 
riar rapida-
mente 
omputadores inteligentes, 
omputadores que poderiam questionar-se e
nos questionar. Muitos a
reditaram nesta promessa e muitos livros de �
ção 
i-
entí�
a foram publi
ados em que este tipo de 
omputador estaria disponível em
um futuro muito próximo. Com notável exemplo podemos 
itar o �lme �2001 -
Uma Odisséia no Espaço�, de Stanley Kubrik que estreou em 1968 e foi baseado
no 
onto �The Sentinel�, es
rito em 1950 por Arthur Clark, um dos mestres da
�
ção 
ientí�
a. Neste �lme o enlouque
ido 
omputador HAL 9000, que era
apaz de ver, falar, ra
io
inar et
, mata quase todos os tripulantes de uma nave
14
espa
ial. Ora, já passamos por 2001 e não existe a menor possibilidade de se
ver um 
omputador 
omo o HAL ou tão lou
o de pedra 
omo ele.
Na 
omputação, um exemplo fantásti
o de su
esso é a Internet. A Internet
está se tornando essen
ial para o fun
ionamento do mundo moderno. Freqüente-
mente ouvimos dizer que ela é o meio de 
omuni
ação que mais rapidamente se
difundiu pelo mundo. Pode pare
er verdade, já que 
onhe
emos tantos internau-
tas e as empresas estão se atropelando para fazer parte desta onda e aproveitar
as suas possibilidades. Esta 
orrida provo
ou alguns a
identes e muitos sonhos
de riqueza se esvaíram no ar. Hoje, pode-se fazer quase tudo pela Internet,
namorar, 
omprar, pagar 
ontas, fazer amigos, estudar, jogar et
. Quem sabe,
em um futuro próximo, voltaremos à Gré
ia Antiga e nos reuniremos em uma
enorme praça virtual para, demo
rati
amente, dis
utir nossas leis, dispensando
intermediários.
1.2 Um Pou
o da História da Computação
1.2.1 O Iní
io
A primeira tentativa de se 
riar uma máquina de 
ontar foi o ába
o. A palavra
vem do árabe e signi�
a pó. Os primeiros ába
os eram bandejas de areia sobre
as quais se faziam �guras para representar as operações. Aparentemente, os
hineses foram os inventores do ába
o de 
al
ular. No entanto, há 
ontrovérsias,
e os japoneses também reivindi
am esta invenção, que eles 
hamam de soroban.
Além disso há os russos, que inventaram um tipo mais simples, 
hamado de
ts
hoty. São 
onhe
idos exemplares de ába
o datados de 2500 A.C. A Figura
1.2 ilustra um exemplar 
om as suas 
ontas e varetas.
Figura 1.2: Imagem de um ába
o.
Em 1901 mergulhadores, trabalhando perto da ilha grega de Antikythera,
en
ontraram os restos de um me
anismo, pare
ido 
om um relógio, 
om aproxi-
madamente 2000 anos de idade. O me
anismo, de grande 
omplexidade, pare
e
ser um dispositivo para 
al
ular os movimentos de estrelas e planetas.
1.2.2 A Era Moderna
Em 1614 John Napier, matemáti
o es
o
ês, inventou um dispositivofeito de
mar�m para demonstrar a divisão por meio de subtrações e a multipli
ação por
15
meio de somas. A semelhança entre mar�m e ossos, fez 
om que o dispositivo
fosse 
onhe
ido 
omo os ossos de Napier.
Um dos primeiros instrumentos modernos de 
al
ular, do tipo me
âni
o, foi
onstruído pelo �lósofo, matemáti
o e físi
o fran
ês Blaise Pas
al (Figura 1.3).
Em 1642 aos 19 anos, na 
idade de Rouen, Pas
al desenvolveu uma máquina de
al
ular, para auxiliar seu trabalho de 
ontabilidade. A engenho
a era baseada
em 2 
onjuntos de dis
os interligados por engrenagens: um para a introdução
dos dados e outro para armazenar os resultados. A máquina utilizava o sistema
de
imal para 
al
ular, de maneira que quando um dis
o ultrapassava o valor 9,
retornava ao 0 e aumentava uma unidade no dis
o imediatamente superior.
Figura 1.3: Blaise Pas
al
Pas
al re
ebeu uma patente do rei da França, o que lhe possibilitou o lança-
mento de sua máquina no mer
ado. A 
omer
ialização das 
al
uladoras não foi
satisfatória devido a seu fun
ionamento pou
o 
on�ável, apesar dele ter 
ons-
truído 
er
a de 50 versões. As máquinas de 
al
ular, derivadas da Pas
alina,
omo �
ou 
onhe
ida sua máquina, ainda podiam ser en
ontradas em lojas até
alguns pou
os anos atrás. Antes de morrer, aos 39 anos, em 1662, Pas
al que
ontribuíra em vários 
ampos da Ciên
ia, ainda teve tempo de 
riar uma vari-
ante de sua máquina, a 
aixa registradora.
Em 1666, Samuel Morland adaptou a 
al
uladora de Pas
al para resolver
multipli
ações por meio de uma série de somas su
essivas. Independentemente,
em 1671 Leibniz projetou uma outra 
al
uladora que somava e multipli
ava.
Esta 
al
uladora só foi 
on
luída em 1694.
O primeiro 
omputador de uso espe
í�
o 
omeçou a ser projetado em 1819
e terminou em 1822, ou seja, há mais de 180 anos atrás, pelo britâni
o Char-
les (1791-1871, Figura 1.4), que o batizou de Di�eren
e Engine (Figura 1.5).
A motivação de Babbage era resolver polin�mios pelo método das diferenças.
Naquele tempo as tábuas astron�mi
as e outras tabelas eram 
al
uladas por
humanos, em métodos tediosos e repetitivos.
Em 1823, ele ini
iou o projeto de 
onstruir uma outra máquina mais avan-
çada e 
apaz de 
al
ular polin�mios de até sexta ordem. Ele esperava terminar
esta máquina em três anos, mas a 
onstrução se arrastou até 1834. Este projeto
que não foi 
ompletado, usou dinheiro do governo inglês e possivelmente a maior
parte da fortuna pessoal de Babbage. A máquina, inteiramente me
âni
a, teria
as seguintes 
ara
terísti
as:
ˆ Arredondamento automáti
o;
16
Figura 1.4: Charles Babbage
Figura 1.5: Fotogra�a da Di�eren
e Engine
ˆ Pre
isão dupla;
ˆ Alarmes para avisar �m de 
ál
ulo;
ˆ Impressão automáti
a de resultados em pla
as de 
obre.
Em 1834 ele tinha 
ompletado os primeiros desenhos da máquina que deno-
minou Analyti
al Engine que tinha as seguintes 
ara
terísti
as:
ˆ 50 dígitos de
imais de pre
isão;
ˆ Memória para 1000 destes números (165000 bits);
ˆ Controle por meio de 
artões perfurados das operações e endereços dos
dados;
ˆ Tempo de soma e subtração igual a 1 segundo; tempo de multipli
ação e
divisão igual a 1 minuto;
ˆ Sub-rotinas;
17
ˆ Arredondamento automáti
o e dete
ção de transbordo (over�ow );
Babagge nun
a 
onseguiu terminar este ambi
ioso projeto. No entanto, os
mais importantes 
on
eitos de 
omputação, que somente vieram a tona nos anos
40 do sé
ulo vinte, já tinham sido 
onsiderados por Charles Babbage em o seu
projeto.
Um fato 
urioso é que entre os auxiliares de Babagge estava Augusta Ada
Byron, Countess of Lovela
e. Considera-se, hoje, que ela es
reveu para Charles
Babbage o primeiro programa para 
omputadores. Ada que mudou seu nome
para Augusta Ada King, após seu 
asamento, estudava Matemáti
a 
om De-
Morgan que provou um dos teoremas bási
os da Álgebra Booleana, que é a base
matemáti
a sobre a qual foram desenvolvidos os projetos dos modernos 
ompu-
tadores. No entanto, não havia nenhuma ligação entre o trabalho do projetista
dos primeiros 
omputadores e o do matemáti
o que estudava o que viria a ser
o fundamento teóri
o de todo a 
omputação que 
onhe
emos hoje.
1.2.3 O Desenvolvimento durante as Grandes Guerras
Antes da Segunda Grande Guerra, em vários países, 
ientistas trabalhavam em
projetos que visavam 
onstruir 
omputadores 
om relés, que são dispositivos
eletrome
âni
os usados para ligar ou desligar 
ir
uitos elétri
os. Relés são os
dispositivos que ante
ederam os transistores na 
onstrução de 
omputadores.
Alguns destes 
omputadores eram de uso geral, outros tinha �nalidades espe
í-
�
as. Alguns destes projetos estão listados a seguir.
Na Alemanha
Em 1934 na Alemanha Konrad Zuze, engenheiro projetista de aviões, 
on
ebeu
uma máquina de somar para resolver os 
ál
ulos que deveria realizar em seus
projetos. Em 1938, ele 
on
luiu o Z1, um 
al
ulador me
âni
o 
om uma unidade
aritméti
a que usava a base 2 para representar os números, base que hoje os
omputadores modernos empregam. Em 1938 ele melhorou o desempenho do
Z1, graças aos relés.
O governo alemão patro
inou os trabalhos de Zuze e em 1941 estava pronto
o Z2, uma máquina eletrome
âni
a 
apaz de re
eber instruções por meio de uma
�ta de papel. Em 1941 foi introduzido o Z3, que 
al
ulava três a quatro adições
por segundo, uma multipli
ação em 4 ou 5 segundos e era 
apaz de extrair a
raiz quadrada.
Nos Estados Unidos
Em 1944 a IBM e H. Haiken da Universidade de Harvard, 
on
luíam a 
onstru-
ção de um verdadeiro 
omputador: o Harvard Mark I, que operava em base 10.
O Mark I efetuava as quatro operações fundamentais, mais o 
ál
ulo de funções
trigonométri
as, exponen
iais e logarítmi
as. As instruções eram forne
idas por
meio de �tas de papel e os dados lidos de 
artões perfurados. Os resultados eram
forne
idos em forma de 
artões perfurados ou impressos por meio de máquinas
de es
rever.
18
Em 1943 na Universidade da Pensilvânia, J. E
kert e J. Mau
hly ini
iaram a
onstrução de um 
omputador à válvulas, ou seja eletr�ni
o que foi 
hamado de
ENIAC. O projeto foi 
on
luído em 1946 e usado na segunda guerra mundial.
O ENIAC podia ser reprogramado para exe
utar diversas operações diferentes
através de ligações por meio de �os e 
one
tores.
Durante muitos anos o 
omputador ENIAC foi 
onsiderado o primeiro 
om-
putador eletr�ni
o 
onstruído. A máquina projetada pelos Drs. E
kert and
Mau
hly era gigantes
a quando 
omparada 
om os 
omputadores pessoais atu-
ais. Quando foi terminado, o ENIAC (Figura 1.6) en
hia um laboratório inteiro,
pesava trinta toneladas, e 
onsumia duzentos quilowatts de potên
ia.
Figura 1.6: Computador Enia
Ele gerava tanto 
alor que teve de ser instalado em um dos pou
os espaços
da Universidade que possuía sistemas de refrigeração forçada. Mais de 19000
válvulas, eram os elementos prin
ipais dos 
ir
uitos do 
omputador. Ele tam-
bém tinha quinze mil relés e 
entenas de milhares de resistores, 
apa
itores e
indutores. Toda esta parafernália eletr�ni
a foi montada em quarenta e dois
painéis 
om mais 2,70 metros de altura, 60 
entímetros de largura e 30 
entí-
metros de 
omprimento, montados na forma da letra U. Uma leitora de 
artões
perfurados e uma perfuradora de 
artões eram usados para entrada e saída de
dados.
Os tempos de exe
ução do ENIAC são mostrados na Tabela 1.2. Compare
estes tempos 
om os tempos dos 
omputadores atuais que estão na ordem de
nano segundos, ou 10−9 segundos.
Operação Tempo
soma 200 µs
multipli
ação 2,8 ms
divisão 6,0 msTabela 1.2: Tempo de exe
ução das instruções aritméti
as no ENIAC
Em 1939 John Vin
ent Atanaso� e Cli�ord E. Berry, na Universidade Esta-
dual de Iowa 
onstruíram um protótipo de 
omputador digital eletr�ni
o, que
usa aritméti
a binária. Em 19 de outubro de 1973, o juiz federal Earl R. Larson
assinou uma de
isão, em seguida a uma longa batalha judi
ial, que de
larava
19
a patente do ENIAC de Mau
hly e E
kert inválida e atribuía a Atanaso� a
invenção 
omputador eletr�ni
o digital, o ABC ou Atanaso�-Berry Computer.
Na Inglaterra
János von Neumann, emigrante húngaro que vivia nos EUA, sugeriu que a
memória do 
omputador deveria ser usada para armazenar as instruções do
omputador de maneira 
odi�
ada, o 
on
eito de programa armazenado. Esta
idéia foi fundamental para o progresso da 
omputação. Os primeiros 
omputa-
dores, 
omo o ENIAC, eram programados por �os que os 
ientistas usavam para
one
tar as diversas partes. Quando um programa terminava, estes 
ientistas
tro
avam os �os de posição de a
ordo 
om a nova tarefa a ser exe
utada. Com o
programa armazenado na memória, juntamente 
om os dados, não era mais ne-
essário interromper as atividades. Carregava-se o programa na memória, uma
tarefa extremamente rápida, junto 
om os dados e dava-se partida no programa.
Ao término da exe
ução do programa passava-se imediatamente para a próxima
tarefa sem interrupções para tro
a de �os.
Em 1949, na Inglaterra, dois 
omputadores que usavam a memória para
armazenar tanto programas 
omo dados foram lançados. Na Universidade de
Cambridge foi lançado o EDSAC, (Ele
troni
 Delay Storage Automati
 Cal
ula-
tor) e em Man
hester o 
omputador 
hamado de Man
hester Mark I. O EDSAC
é 
onsiderado o primeiro 
omputador de programa armazenado a ser lançado.
Curiosamente, a Universidade de Man
hester reivindi
a que o primeiro 
ompu-
tador de programa armazenado foi o 
hamado �Baby�, um protótipo do Mark I,
que 
omeçou a operar onze meses antes do EDSAC.
Outro fato 
urioso em relação à Inglaterra e que foi divulgado re
entemente
relata que um 
omputador 
hamado COLOSSUS entrou em operação se
re-
tamente na Inglaterra em 1943. Este 
omputador foi usado para auxiliar na
quebra dos 
ódigos de 
riptogra�a alemães durante a segunda grande guerra.
1.2.4 As Gerações
Costumava-se dividir os projetos de 
omputadores em gerações. Hoje em dia
omo a taxa de evolução é muito grande não se usa mais este tipo de termino-
logia. No entanto é interessante men
ionar estas divisões.
Primeira Geração: Os 
omputadores 
onstruídos 
om relés e válvulas são os
da primeira geração. Estes 
omputadores 
onsumiam muita energia e
espaço.
Segunda Geração: Os 
omputadores da segunda geração foram 
onstruídos
om transistores, os quais tinham a vantagem de serem mais 
ompa
tos e
onsumirem muito menos energia. Por gerarem menos 
alor eram máqui-
nas mais 
on�áveis.
Ter
eira Geração: Com o advento dos 
ir
uitos integrados, que são 
ompo-
nentes em que vários transistores são 
onstruídos em uma mesma base
de semi
ondutor, 
hegamos aos 
omputadores de ter
eira geração. Com
a integração o tamanho dos 
omputadores e seu 
onsumo diminuiu ainda
mais e aumentou a 
apa
idade de pro
essamento.
20
Quarta Geração: Os 
omputadores de quarta geração utilizavam 
ir
uitos
om a te
nologia (Very Large S
ale Integration), que permitia uma es
ala
de integração de transistores muito grande.
1.3 O Hardware
O hardware 
orresponde aos 
ir
uitos eletr�ni
os e 
omponentes me
âni
os que
ompõem o 
omputador. Um típi
o diagrama em blo
os de um 
omputador
digital monopro
essado esta mostrado na Figura 1.7. A Unidade Central
de Pro
essamento (UCP), em inglês Central Pro
essing Unit (CPU), 
omo o
próprio nome diz, é a unidade onde os dados são pro
essados, ou seja alterados,
no 
omputador. Ou seja, dentro das UCPs os dados são somados, subtraídos
et
. A UCP também 
ontrola a movimentação dos dados dentro de todo o
sistema. Os módulos que 
onstituem a UCP são os seguintes:
Unidade de Controle (UC): 
omanda a operação do 
omputador. Esta uni-
dade lê da memória tanto as instruções 
omo os dados e 
omanda todos
os 
ir
uitos para exe
utar 
ada instrução lida da memória. Atualmente as
unidades de 
ontrole são 
apazes de exe
utar mais de uma instrução por
i
lo de máquina, o que 
ara
teriza o pro
essamento paralelo. A té
ni
a
mais 
omum para 
onseguir este paralelismo é 
onhe
ida 
omo pipelining,
que será detalhada mais adiante.
Unidade Aritméti
a e Lógi
a (UAL): lo
al onde as transformações sobre
os dados a
onte
em. Atualmente esta unidade é bastante so�sti
ada e
diversos métodos são empregadas para a
elerar a exe
ução das instruções.
Alguns pro
essadores dupli
am 
ir
uitos para permitir que mais de uma
operação aritméti
a seja exe
utada por vez. É muito 
omum, por exem-
plo, a existên
ia de uma unidade aritméti
a para exe
utar instruções que
operam sobre números inteiros e outra sobre números reais, 
hamada de
unidade de ponto �utuante. As vezes a UCP 
onta 
om mais de uma de
ada uma destas unidades.
Unidade de Entrada e Saída (UES): 
ontrola a 
omuni
ação 
om os usu-
ários do 
omputador e os equipamentos periféri
os tais 
omo dis
os e im-
pressoras. Em alguns 
omputadores mais simples esta unidade não existe
independentemente, sendo distribuída pela Unidade Central de Pro
es-
samento. Em 
omputadores mais poderosos ao 
ontrário as Unidades de
Entrada e Saída são 
omputadores 
ompletos que foram programados para
ontrolar a 
omuni
ação 
om os periféri
os.
O termo pipelining que men
ionamos a
ima se refere a um dos modos de
omo o pro
essador pode paralelizar a exe
ução de instruções. Este termo pode
ser traduzido por linha de montagem, porque é exatamente isto que a té
ni
a
faz, uma linha de montagem de instruções. Por exemplo, em uma linha de
montagem de uma fábri
a de automóveis, mais de um automóvel é montado
ao mesmo tempo. No iní
io da linha o 
arro não existe. Em 
ada estágio da
linha de montagem os operários vão adi
ionando partes e ao �m da linha sai
um 
arro novo. Se vo
ê olhar a linha poderá ver 
arros em diversos estágios da
21
Unidade
 de
Controle
Unidade
 de
Entrada
 e
Saída
Unidade
 Arimética Unidade
Central
de
Processamento
Memória Discos Vídeo
Figura 1.7: Diagrama Bási
o de um Computador Digital
montagem. Repare que a linha não pára, e a montagem de um 
arro não espera
que o que 
omeçou a ser montado antes dele esteja terminado. Nas linhas de
montagem muitos 
arros são montados ao mesmo tempo. O efeito �nal é que
ada 
arro 
ontinua levando bastante tempo para ser montado, mas 
omo vários
vão sendo montados ao mesmo tempo, alguém que se 
olo
asse no �nal da linha
de montagem teria a impressão que 
ada 
arro leva muito pou
o tempo para
ser montado. Isto porque no �nal da linha de montagem sai um 
arro a 
ada
pou
os minutos. O mesmo a
onte
e 
om a linha de montagem de instruções.
1.3.1 Mi
ro
omputadores
Uma UCP integrada em um úni
o 
ir
uito (
hip) é 
omumente 
hamada de
mi
ropro
essador . Os mi
ropro
essadores atuais in
luem outros 
ir
uitos que
normalmente �
avam fora da UCP, tais 
omo pro
essadores de ponto �utuante
e memórias 
a
he. Alguns exemplos de mi
ropro
essadores são mostrados na
Tabela 1.3
Mi
ropro
essador Empresa
Arquitetura Intel X86 Intel, AMD
PowerPC Consór
io Apple/IBM/Motorola
Power IBM
MIPS MIPS Te
hnologies
ARM ARM Te
hnologies
SPARC SUN
Tabela 1.3: Exemplos de Mi
ropro
essadores
Usualmente se 
hama de 
omputador, o proessador mais os seus periféri
os
e os sistemas para 
ontrolar estes periféri
os, ou seja todo o sistema de pro
es-
samento de dados. Os periféri
os são os dispositivos usados para fazer a entrada
e saída dos dados que serão pro
essados.
Os mi
ro
omputadores são 
omputadores baseados em mi
ropro
essa-
dores. As assim 
hamadas pla
as mãe dos mi
ropro
essadores atuais in
luem
22
diversos 
omponentes que formam o mi
ro
omputador. Por exemplo, uma pla
a
mãe pode in
luir o mi
ropro
essador e seus 
ir
uitos de suporte, que, no 
on-
junto são 
onhe
idos 
omo o 
hipset. Além disso a pla
a mãe pode in
luir tam-
bém a memória prin
ipal e as pla
as de 
ontrole de periféri
os, 
omo a pla
a de
vídeo, e os 
one
tores para os periféri
os, en�m, quase todo o sistema.
1.3.2 Memórias
Os dados no 
omputador podem ser armazenados em diversos níveis de memória
semi
ondutoras ou em periféri
os (dis
os, �tas, et
). Quanto mais rápida a
memória, usualmente mais 
ara ela é. A idéia por traz da separação em níveis
é 
olo
ar mais perto do pro
essador, em memórias rápidas e mais 
aras, os
dados que o pro
essador irá pre
isar mais freqüentemente. A medida que vamos
nos afastando do pro
essador as memórias vão, ao mesmo tempo, �
ando mais
baratas, aumentando de 
apa
idade e diminuindo de velo
idade. A Figura 1.8
ilustra esta hierarquia.
PROCESSADOR
REGISTRADORES
CACHE
DISCO
MEMÓRIA
Figura 1.8: Níveis de hierarquia da memória de um 
omputador.
No nível mais próximo do pro
essador estão os registradores , que, na ver-
dade, �
am internamente ao pro
essador. São pou
os e extremamente rápidos
e, portanto, não podem armazenar grandes quantidades de dados. Somente os
dados que são ne
essários ao pro
essador 
om rapidez extraordinária devem ser
olo
ados nos registradores.
Durante o pro
essamento normal, é na memória prin
ipal onde o pro
essa-
dor bus
a instruções e dados de um programa para exe
utar. Além da memória
prin
ipal estão os dis
os. Devido a sua velo
idade menor que a da memória
prin
ipal e a sua grande 
apa
idade, os dis
os são 
onsiderados dispositivos de
armazenamento se
undário. Os dis
os também são memórias de armazenamento
permanente, isto é, quando os 
omputadores são desligados o seu 
onteúdo se
mantém. Ao 
ontrário, a memória prin
ipal e os registradores são memórias
semi
ondutoras e perdem seus 
onteúdos quando a energia elétri
a é desligada.
Em alguns 
omputadores os dis
os estão sendo substituídos por memórias se-
mi
ondutoras.
Para a
elerar o a
esso aos dados freqüentemente usados, os 
omputadores
dispõem de memórias mais rápidas, porém de menor 
apa
idade, que �
am en-
tre os registradores e a memória prin
ipal. Estas fun
ionam 
omo as bolsas ou
arteiras em que 
arregamos do
umentos e outros itens que pre
isamos freqüen-
temente. Este tipo de memória é 
onhe
ido 
omo memória 
a
he. O 
a
he
opera de forma invisível para o pro
essador. Ao pedir um dado para memória,
23
ir
uitos espe
iais veri�
am se este dado está no 
a
he, 
aso esteja, ele é repas-
sado para o pro
essador. Para o pro
essador o que a
onte
eu é que a memória
entregou o dado 
om uma rapidez maior do que o normal.
Uma memória é 
omo se fosse uma série de 
ofres numerados 
apazes de
armazenar os dados, 
omo está ilustrado na Figura 2.3. Os dados e instruções
na memória são apontados ou referen
iados por estes números, 
onhe
idos 
omo
endereços. Ou seja, para ler um dado da memória é ne
essário forne
er um
endereço para que a memória possa en
ontrar e devolver o 
onteúdo pedido. Isto
é similar ao o que o
orre quando enviamos uma 
arta, o endereço faz 
om que o
arteiro saiba onde ele deve entregar a 
orrespondên
ia. Em operação normal,
toda vez que o pro
essador pre
isa de um dado ele envia um pedido de leitura
à memória junto 
om o endereço da memória onde o dado está. Nas es
ritas
o pro
essador envia o endereço, o dado e pedido de es
rita. Normalmente a
memória somente pode atender um pedido de 
ada vez. Portanto, para ler 1000
números o pro
essador terá de fazer 1000 a
essos seqüen
ialmente.
Os dois tipos bási
os de memória mais 
omuns são ROM e RAM. Estas
siglas têm diversas variações (PROM, EPROM, DRAM, et
), mas os prin
ípios
bási
os são os mesmos. Estas siglas indi
am os dois tipos bási
os de memória
que são usadas em 
omputadores. A sigla bási
a ROM signi�
a Read Only
Memory, ou seja, memória de somente de leitura. A outra sigla RAM (Random
A
ess Memory) signi�
a memória de a
esso rand�mi
o, portanto, memória que
se pode ler em qualquer endereço.
A sigla RAM é muito 
onfusa porque em uma memória ROM também se
pode ler em qualquer endereço. A diferença real é que nas RAMs se pode ler e
es
rever 
om a mesma velo
idade em qualquer endereço, enquanto que na ROM,
o a
esso é rápido somente para leituras, a es
rita é uma história mais 
ompli
ada.
A ROM normalmente 
ontém dados que não podem ser modi�
ados durante o
fun
ionamento do 
omputador. Outro tipo de dados armazenados em ROMs são
os que não devem ser perdidos quando o 
omputador é desligado. Exemplos de
uso de ROM são as memórias que armazenam os programas que são exe
utados
quando os 
omputadores são ligados, os famosos BIOS (Basi
 Input Output
System). Um 
omputador ao ser ligado deve ter um programa mínimo 
apaz
de ini
iar o seu fun
ionamento normal, 
aso 
ontrário seria 
omo uma pessoa
que perdeu totalmente a memória. Para isto são es
ritos programas simples que
fazem a
esso aos periféri
os em bus
a do Sistema Opera
ional da máquina.
As primeiras memórias do tipo ROM eram gravadas nas fábri
as e nun
a
mais eram modi�
adas. Isto trazia algumas di�
uldades, por exemplo, quando
um programa pre
isava ser atualizado. Para resolver este tipo de problemas
surgiram as PROMs, que são ROMs programáveis. Ou seja é possível desgravar
o 
onteúdo antigo e gravar novos programas nesta memória. Antigamente este
era um pro
esso 
ompli
ado e exigia que a memória fosse retirada �si
amente
do 
ir
uito e 
olo
ada em dispositivos espe
iais 
apazes de apagar o 
onteúdo
antigo. Em seguida um 
ir
uito programador de PROMs era usado para gravar
o novo 
onteúdo e somente após tudo isto a memória era re
olo
ada no lo
al.
O 
omputador �
ava literalmente sem a memória dos programas ini
iais. Hoje
em dia existem PROMs que podem ser apagadas e regravadas muito fa
ilmente.
Por exemplo, as EEPROMs (Eletri
aly Erasable PROMs), que são memórias
que podem ser apagadas eletri
amente sem a ne
essidade de serem retiradas
24
dos 
ir
uitos. Flash memory é uma forma de memória não volátil que pode
ser apagada e reprogramada eletri
amente. Diferentemente das EEPROMs, ela
deve ser apagada em blo
os de endereços. Este tipo de memória 
usta menos
do que EEPROMs e portanto são preferidas quando é ne
essário usar memória
não volátil em forma de 
ir
uitos integrados.
As memórias RAMs são as memórias onde os nossos programas 
omuns
rodam. Elas são modi�
áveis e de a
esso rápido tanto na leitura quanto na
gravação. Muitas siglas apare
em e desapare
em quando falamos de memórias
RAM. Existem as DRAM, memórias EDO, SIMM, et
. Tudo isto ou se refere ao
método de a
esso dos dados na memória ou a te
nologia de 
onstrução ou a outra
ara
terísti
a a
essória. O 
erto é que todas elas tem 
omo 
ara
terísti
a bási
a
o fato dos a
essos de leitura e es
rita poderem ser feitos na mesma velo
idade.
1.3.3 Bits e Bytes
A memória do 
omputador é 
omposta de bits, a menor unidade de informação
que o 
omputador armazena. Um bit pode 
onter o valor 0 ou 1,que são os
dígitos usados na base dois, a base usada nos 
omputadores. Um 
onjunto de
8 bits forma o byte. Uma palavra de memória é um 
onjunto de bytes.
Atualmente a maioria dos 
omputadores tem palavras de memória 
om largura
de 32 (4 bytes) ou 64 (8 bytes) bits. Na Figura 1.9 mostramos os diversos
tamanhos dos dados.
BIT
BYTE
8 BITS
PALAVRA
32 BITS
4 BYTES
Figura 1.9: Tamanho de Bits, Bytes e Palavras
Observar que estamos falando de dados na memória e não do tamanho dos
dados que o 
omputador pode pro
essar. Considere que este tamanho é rela
io-
nado 
om a quantidade máxima de algarismos que um número pode ter para ser
pro
essado. Um 
omputador pode ter 
apa
idade de pro
essar 64 bits de 
ada
vez. Caso sua memória tenha palavras de 32 bits o pro
essador deverá, então,
ler duas palavras da memória para poder pro
essar um número. Lembre-se que
as duas leituras são atendidas uma de 
ada vez. Da mesma forma o 
omputador
pode pro
essar 32 bits de 
ada vez e a memória ter largura 64 bits. Isto pode
a
elerar o pro
essamento, já que o pro
essador está se adiantando e re
ebendo
o que poderá ser o próximo dado a ser pro
essado, ou seja e
onomizando uma
leitura.
Devido a base 2 o fator kilo tem um signi�
ado diferente em 
omputação.
Por exemplo 1 Kbyte de memória 
orresponde a 2 elevado a 10 (210), ou seja
25
1024 bytes. Da mesma forma 1 Megabyte 
orresponde a 1024 x 1024 bytes e 1
Gigabyte é igual a 1024 x 1024 x 1024 bytes. Na Tabela 1.4 estão mostradas as
diversas abreviações usadas quando se fazem referên
ias às memórias.
Nome Símbolo Multipli
ador
Kilobyte Kb 210 = 1024
Megabyte MB 220
Gigabyte GB 230
Terabyte TB 240
Petabyte PB 250
Exabyte EB 260
Tabela 1.4: Abreviações usadas em referên
ias às memórias.
1.3.4 Periféri
os
Como já men
ionamos antes, os dados não �
am guardados somente na me-
mória, há também os periféri
os . Há periféri
os de entrada, outros de saída
e alguns que servem tanto para entrada 
omo saída de dados. Periféri
os não
servem somente para armazenar dados. Há periféri
os que são usados para per-
mitir a interação entre os usuários e o 
omputador. A tabela 1.5 ilustra alguns
destes periféri
os.
Entrada Saída Ambos
Te
lados Impressoras Dis
os Rígidos
Mouse Vídeo Fitas Magnéti
as
CD-ROM Plotter Disquetes
S
anner Alto-falantes Dis
os Zip
Tabela 1.5: Exemplos de periféri
os
1.4 O Software
Tudo isto que sobre o que a
abamos de es
rever 
onstitui o hardware do 
om-
putador, o que se vê e o que se to
a. A partir de agora falaremos brevemente
no software, o que não se vê nem se to
a, mas também está lá.
Para que um 
omputador exe
ute alguma tarefa primeiro se desenvolve um
algoritmo , que é uma espé
ie de re
eita que �diz pre
isamente, ao 
omputador�,
omo o problema deve ser resolvido. Esta de�nição informal de algoritmo é
enganosamente simples, e a 
have para entender o engano está nas palavras
�dizer pre
isamente ao 
omputador�. Por exemplo, uma re
eita em gastronomia
normalmente não é um algoritmo. Re
eitas são entendidas pela 
omunidade de
ozinheiros, que as seguem fa
ilmente durante o preparo do prato. No entanto,
re
eitas estão 
heias de expressões 
omo, por exemplo, �mexer até �
ar no ponto�
26
e �
olo
ar sal a gosto�. Fora da 
omunidade de 
ozinheiros estas expressões são
passíveis de várias interpretações. Para es
rever algoritmos pre
isamos de uma
linguagem matemati
amente pre
isa e sem ambigüidades.
A es
rita de um algoritmo 
onsta de uma de�nição do estado ini
ial do
problema a ser resolvido e de regras pre
isas que estabele
em a 
ada instante
os passos a serem seguidos. Como em um jogo, além de de�nir os passos, são
ne
essárias regras que de�nam se após a exe
ução de um passo do algoritmo o
novo estado do problema é válido. As regras do xadrez de�nem o estado ini
ial
do tabuleiro, os movimentos possíveis de 
ada peça e se após um movimento
de uma peça a 
on�guração atingida é válida. Ou seja pre
isamos veri�
ar em
ada instante qual dos movimentos (instruções) pode ser usado.
Algoritmos podem ser 
hamados de pro
edimentos efetivos e devem obede
er
aos seguintes limites:
ˆ sempre dar alguma resposta;
ˆ sempre dar a resposta 
orreta e nun
a uma resposta in
orreta;
ˆ terminar em um número �nito de passos;
ˆ trabalhar em todos os exemplos da 
lasse de problemas que o algoritmo
se propõe a resolver.
Em seguida este algoritmo deve ser traduzido para uma linguagem que possa
ser entendida pelo 
omputador ou que possa ser traduzida para esta linguagem.
No iní
io da 
omputação eletr�ni
a 
om programas armazenados, estes eram
es
ritos diretamente em linguagem de máquina que é a linguagem que o 
om-
putador realmente �entende�. Estas instruções são 
onjuntos de bits indi
ando
a operação que deve ser exe
utada e, 
aso ne
essário, onde 
omo a
har os dados
que serão operados. Por esta razão também 
ostuma-se dizer que são programas
es
ritos em binário.
Com a evolução da 
omputação os programas passaram a ser es
ritos em
assembly , que é uma representação em mnem�ni
os das instruções de máquina.
Deste modo era é mais fá
il es
rever os algoritmos. Por exemplo, um fragmento
de um programa es
rito em assembly do pro
essador PowerPC é:
li r3,4 * O primeiro numero a ser somado e 4.
li r4,8 * 8 e o segundo numero
add r5,r4,r3 * Some os 
onteúdos de r3 (4) e r4 (8)
* e armazene o resultado em r5
Este pequeno tre
ho de programa armazena os números 4 e 5 em registrado-
res internos do pro
essador em seguida os soma e armazena o resultado em um
ter
eiro registrador. As informações após os asteris
os são 
omentários usados
para expli
ar o que o programa está fazendo naquela instrução.
O PowerPC é um mi
ropro
essador 
riado em 1991 por um 
onsór
io for-
mado pela IBM, Apple e Motorola Os mi
ropro
essadores PowerPC podem ser
usados para equipar desde sistemas embutidos até 
omputadores de alto desem-
penho. A Apple usou este mi
ropro
essador para equipar suas máquinas até
2006.
27
Um programa es
rito em assembly deve ser traduzido para a representação
binária, tarefa que normalmente se 
hama de montar o programa. A palavra
assembler frequentemente é usada erradamente para signi�
ar a linguagem e
não o programa que traduz o programa de assembly para linguagem binária de
máquina. Este tipo de programação pode levar a se es
rever programas muito
e�
ientes, devido ao 
ontrole quase que total do programador sobre a máquina.
No entanto devido ao fato de ser uma linguagem próxima do 
omputador e afas-
tada da maneira de ra
io
inar do ser humano é mais difí
il de ser usada. Além
deste fato há outros problemas tais 
omo: di�
uldade de leitura por humanos,
di�
uldade de manutenção dos programas, maior tempo de desenvolvimento et
.
Para evitar estes problemas foram desenvolvidas as linguagens de progra-
mação 
hamadas de linguagens de alto nível, por estarem mais próximas da
linguagem natural empregada pelos serem humanos. Alguns exemplos de lin-
guagens de programação são:
Fortran: Usada em programação 
ientí�
a e engenharia;
Pas
al: Usada em ensino de linguagens e desenvolvimento de sistemas;
COBOL: Usada em ambientes 
omer
iais;
Basi
: O nome diz tudo, bási
a;
C: Mesmas 
ara
terísti
as do Pas
al 
om fa
ilidades que permitem mais 
ontrole
do 
omputador;
C++: Linguagem originária do C 
om metodologia de orientação à objetos;
Java: Linguagem também baseada na sintaxe do C e também seguindo o mo-
delo de orientação à objetos.
Delphi: Linguagem originária do Pas
al 
om metodologia de orientação à ob-
jetos;
Lisp e Prolog: Linguagens usadas paradesenvolver programas de Inteligên
ia
Arti�
ial.
Apli
ativos importantes para os programadores são os 
ompiladores. Es-
tes programas traduzem programas es
ritos em linguagens de alto nível para
a linguagem de máquina, de modo que o 
omputador possa exe
utá-los. De
maneira geral um 
ompilador é um programa que traduz um programa de uma
linguagem para outra.
Podemos resumir os passos ne
essários para 
riar um programa em uma
linguagem de programação, por exemplo C, nos passos des
ritos a seguir. A
Figura 1.10 ilustra a ordem em que se desenvolvem estes passos.
Criação do Algoritmo: neste passo é 
riado o algoritmo que irá resolver o
problema. As diversas maneiras de des
rever um algoritmo serão apresen-
tadas no próximo 
apítulo.
28
Codi�
ação do Algoritmo: O algoritmo preparado no passo anterior é es-
rito em uma linguagem de programação. Neste passo o programador
onta, normalmente, 
om a ajuda de um editor de textos (não pro
essa-
dor de textos). Para esta edição qualquer editor pode ser usado. Hoje
em dia muitos ambientes de desenvolvimento integram todas as ferramen-
tas ne
essárias para 
riar um programa, in
lusive o editor, em um úni
o
apli
ativo.
Compilação do Programa: O arquivo texto 
ontendo o programa passa por
um programa espe
ial 
hamado 
ompilador que gera, 
aso não hajam er-
ros, uma saída que é quase o programa exe
utável, ou seja o programa
em 
ódigo binário do pro
essador em que será exe
utado. Os erros mais
omuns nesta etapa são erros de uso 
orreto da linguagem de programa-
ção. Estes erros são 
hamados de erros de 
ompilação. As linguagens de
programação são baseadas em regras gramati
ais muito rígidas e qualquer
violação destas regras pode impli
ar em erro. No 
aso de erros serem
en
ontrados o programador deve voltar ao passo de 
odi�
ação para a
orreção dos erros.
Ligação: Em inglês este passo é 
onhe
ido por link edition. Um programa
ompleto é 
omposto por vários módulos que podem ter sido 
riados pelo
próprio programador ou por outras programadores. Por exemplo, em C
os tre
hos de programa que interagem 
om os usuários, os 
omandos de
entrada e saída de dados, normalmente vêm 
om o programa 
ompilador.
Estes tre
hos podem estar guardados em bibliote
as de programas e são
ligados ao programa do usuário para 
ompletar o programa.
Depuração e Testes: Nesta etapa o programa será testado para a retirada
dos possíveis erros de lógi
a que o programador 
ometeu. Caso algum
erro de exe
ução seja en
ontrado o programador deve reelaborar o que
estiver errado no algoritmo e em seguida ir para a etapa de 
odi�
ação do
algoritmo. Este 
i
lo pode repetir-se inúmeras vezes até que o desenvol-
vedor a
redite que os erros foram 
orrigidos.
Uso do Programa: O programa foi entregue aos seus usuários para ser usa-
do. Durante o uso, erros que não foram en
ontrados durante o desenvol-
vimento do programa podem ser des
obertos e pre
isam ser 
orrigidos. A
orreção pode ser feita pelos mesmos programadores que desenvolveram o
programa ou por outro grupo devidamente treinado. Costuma-se 
hamar
esta 
orreção de manutenção do programa.
Algumas linguagens de programação não são 
ompiladas e sim interpretadas.
Isto signi�
a que o programa para ser exe
utado não pre
isa ser traduzido dire-
tamente para linguagem de máquina, gerando um arquivo exe
utável. Este ar-
quivo �nal, se torna independente do programa fonte. Para exe
utar o programa
podemos usar somente o arquivo exe
utável. Em um programa interpretado um
apli
ativo lê o programa instrução por instrução, diretamente na própria lin-
guagem de alto nível, traduz 
ada uma destas instruções para linguagem de
máquina e as exe
uta. Não há, portanto, o pro
esso de tradução ante
ipada
do programa. A interpretação de um programa fun
iona 
omo o pro
esso de
tradução simultânea do dis
urso de um orador. A medida que ele pronun
ia seu
29
Início
Criação de
Algoritmo
Codificação do
Algoritmo
Compilacação do
Programa
Ligação
Depuração e 
Testes
Uso do programa
Erros de
Compilação?
Sim
Não
Erros de
Execução?
Erros de
Execução?
Não
Sim
Sim
Figura 1.10: Ci
lo de desenvolvimento de um programa.
dis
urso um tradutor repete as frases na linguagem destino. Um programa 
om-
pilado fun
iona 
omo se primeiro, o tradutor traduzisse todo o dis
urso e depois
o lesse. A linguagem Basi
 é uma linguagem interpretada. Em Java o
orre um
pro
esso um pou
o diferente. Um programa em Java é traduzido para uma lin-
guagem intermediária e depois interpretado por meio de uma 
hamada máquina
virtual. Não há efetivamente uma 
ompilação para linguagem de máquina. A
exe
ução de um programa es
rito em uma linguagem interpretada é mais lenta,
já que o pro
esso de interpretação e exe
ução ao mesmo tempo é mais lento do
que a simples exe
ução de um programa traduzido ante
ipadamente.
Hoje em dia a maior parte dos usuários de 
omputadores não são programa-
dores e sim pessoas que usam programas para resolver seus problemas do dia
a dia. Apli
ativos típi
os que rodam nos 
omputadores são: editores de texto,
pro
essadores de texto, planilhas eletr�ni
as, 
ompiladores, ban
os de dados,
jogos, et
.
Para geren
iar os re
ursos do 
omputador existe um programa espe
ial nor-
malmente 
hamado de Sistema Opera
ional (S. O.). Por exemplo, 
onsidere o
problema de geren
iar 
omo os diversos programas que um usuário normalmente
utiliza partilharão o pro
essador do 
omputador. Um usuário pode estar ou-
vindo músi
a, digitando um texto e imprimindo um outro do
umento ao mesmo
tempo. Portanto, os 
omputadores são 
apazes de exe
utar um número de ta-
refas muito maior do que o número de pro
essadores disponíveis. Atualmente
a maior parte dos 
omputadores possui somente um pro
essador. O Sistema
Opera
ional 
ontrola a alo
ação de re
ursos tais 
omo: 
omuni
ação 
om os
usuários, espaço em dis
os, uso de memória, tempo que 
ada programa pode ro-
dar et
. Alguns dos sistemas opera
ionais 
onhe
idos são os baseados no padrão
UNIX, por exemplo o LINUX. Outros sistemas muito usados são os da família
30
Windows.
Compilando Programas Simples em C
Para resolver os exer
í
ios deste livro vo
ê irá pre
isar de um 
ompilador para a
linguagem C e de um editor de textos simples (não pro
essador 
omo o Word).
O editor pode ser tão simples quanto o Notepad, na verdade re
omendamos
fortemente que o editor seja simples para que vo
ê possa ter 
ontato 
om todas
as etapas do pro
esso de desenvolvimento de um programa. Para 
ompilar
empregaremos o 
ompilador g
 que é gratuito e pode ser obtido na Internet
omo veremos adiante. Não será ne
essário nenhum ambiente mais 
omplexo,
tal 
omo um �Integrated Development Environment� (IDE).
A 
oleção de 
ompiladores da GNU (GNU Compiler Colle
tion) usualmente
abreviada por g
, é uma 
oleção de 
ompiladores produzidos pelo projeto GNU.
A abreviação g
, originalmente, signi�
ava GNU C Compiler. Este apli
ativo
é distribuído gratuitamente pela Free Software Foundation (FSF) sob a li
ença
GNU GPL e GNU LGPL. Este é o 
ompilador padrão para os sistemas ope-
ra
ionais livres do tipo Unix, 
omo o LINUX, e diversos sistemas opera
ionais
proprietários 
omo o Apple Ma
 OS X. Atualmente o g
 pode 
ompilar C++,
Obje
tive-C, Java, Fortran e ADA, entre outras linguagens. Vamos 
onside-
rar, 
omo exemplo, um programa 
hamado teste.
. Para 
ompilar e gerar o
exe
utável para este programa digitamos o 
omando
g
 -o teste teste.
 -Wall
em uma janela de 
omandos no sistema Windows ou em um terminal nos siste-
masUnix. O su�xo .
 no nome do programa normalmente é usado para indi
ar
que o arquivo é de um programa C. Este 
omando deve ser digitado no diretório
onde está o arquivo fonte teste.
. O arquivo exe
utável será armazenado no
mesmo diretório.
Nos sistemas Unix normalmente o g
 faz parte da distribuição padrão e
nada pre
isa ser feito. No Windows uma maneira fá
il de obter uma versão
do g
 é instalar o MinGW (Minimalist GNU for Windows). MinGW é uma
oleção de arquivos e bibliote
as distribuídas livremente as quais 
ombinadas
om outras ferramentas da GNU permitem que programas para Windows sejam
produzidos sem a ne
essidade de bibliote
as extras e pagas. O MinGW dispõe
de um programa instalador que fa
ilita enormemente o pro
esso. Este programa
pode ser obtido no sítio o�
ial do MinGW. Caso após a instalação, o 
omando
indi
ado não fun
ione uma das razões para a falha pode ser que o sistema ope-
ra
ional não sabe onde se en
ontra o 
ompilador g
. Suponha que o programa
g
 foi instalado no diretório C:\MinGW\bin. Uma solução é digitar o 
aminho
ompleto do 
ompilador. Neste 
aso o 
omando se torna
C:\MinGW\bin\g
 -o teste teste.
 -Wall
Para que não seja ne
essário digitar o 
aminho 
ompleto, é pre
iso adi
io-
nar este 
aminho à variável PATH do Windows. Consulte o manual para obter
informações de 
omo fazer este passo no seu sistema Windows.
31
1.5 Um programa em C
Vamos terminar este 
apítulo mostrando um exemplo simples de programa es-
rito em C(Listagem 1.1). A úni
a 
oisa que este programa faz é imprimir Alo
Mundo! e terminar [?, ?, ?℄.
A primeira linha do programa avisa ao 
ompilador que irá usar funções de
entrada e saída de dados guardadas na bibliote
a stdio. Neste 
aso a função
usada é printf. A segunda linha é o iní
io real do programa. A linha indi
a que
esta é a função main que todo programa C deve 
onter, pois é nesta função que
o programa obrigatoriamente 
omeça sua exe
ução. A função vai retornar um
valor inteiro (int) ao �nal de sua exe
ução e não vai pre
isar re
eber nenhum
argumento para sua exe
ução (void). As 
haves ({ e }) mar
am o iní
io e o
�m da função. Para imprimir o texto Alo Mundo! o programa usa a função
printf. O iní
io e o �m do texto a ser impresso são mar
ados pelo 
ara
tere ".
A função termina 
om o 
omando return 0, que avisa ao sistema opera
ional,
que foi quem ini
iou a exe
ução do programa, que o programa terminou sem
problemas. Este programa simples ilustra alguns das estruturas bási
as que
serão usadas nos programas C que serão apresentados neste livro.
Listagem 1.1: Exemplo de Programa em C.
#in
lude <stdio.h>
int main (void)
{
printf("Alo Mundo!\n");
return 0;
}
32
1.6 Exer
í
ios
1.1: O que é o hardware do 
omputador?
1.2: Quais os prin
ipais 
omponentes de um 
omputador?
1.3: Quais as diferenças entre um mi
ropro
essador e o mi
ro
omputador?
1.4: Dê exemplos de mi
ropro
essadores e de mi
ro
omputadores.
1.5: Qual o número exato de bytes em 64 Kbytes?
1.6: Se vo
ê já usa 
omputadores, liste alguns apli
ativos que vo
ê normalmente
usa.
1.7: De�na Sistema Opera
ional.
1.8: Qual a diferença bási
a entre memórias ROM e RAM?
1.9: Pro
ure em manuais, internet e outras fontes quais são os tempos de a
esso
das memórias RAMs atuais.
1.10: Faça três listas, uma de periféri
os de entrada, outra de periféri
os de
saída e �nalmente uma de periféri
os de entrada e saída.
1.11: Explique o que faz um 
ompilador.
1.12: Dis
uta as vantagens e desvantagens das linguagens interpretadas e as
ompiladas.
1.13: O que são erros de 
ompilação e de exe
ução.
1.14: Pro
ure nomes de linguagens de programação não listadas no texto e diga
quais são as suas 
ara
terísti
as prin
ipais.
33
Capítulo 2
Algoritmos
2.1 Introdução
O objetivo deste 
apítulo é fazer uma breve introdução ao 
on
eito de algorit-
mos e apresentar algumas formas mais 
omuns de representar algoritmos para
fa
ilitar o entendimento dos demais 
apítulos deste livro. Iremos apresentar as
onstruções mais 
omuns empregadas no desenvolvimento de algoritmos e apre-
sentaremos exemplos bási
os de algoritmos usando algumas destas formas de
representação e 
onstruções.
Para resolver um problema no 
omputador é ne
essário que seja primeira-
mente en
ontrada uma maneira de des
rever este problema de uma forma 
lara
e pre
isa. É pre
iso que en
ontremos uma seqüên
ia de passos que permitam
que o problema possa ser resolvido de maneira automáti
a e repetitiva. Além
disto é pre
iso de�nir 
omo os dados que serão pro
essados serão armazena-
dos no 
omputador. Portanto, a solução de um problema por 
omputador é
baseada em dois pontos: a seqüên
ia de passos e a forma 
omo os dados serão
armazenados no 
omputador. Esta seqüên
ia de passos é 
hamada de algoritmo.
Usamos algoritmos em diversas atividades que realizamos diariamente. Uma
grande parte destas atividades não estão rela
ionadas 
om 
omputação. Um
exemplo simples e prosai
o, de 
omo um problema pode ser resolvido 
aso for-
neçamos uma seqüên
ia de passos que mostrem a maneira de obter a solução, é
uma re
eita para preparar um bolo.
Uma vez que foi 
riado um algoritmo para resolver um determinado pro-
blema usando 
omputadores passamos para a próxima fase que é a es
rita deste
algoritmo em alguma linguagem de programação.
A noção de algoritmo é 
entral para toda a 
omputação. A 
riação de algo-
ritmos para resolver os problemas é uma das maiores di�
uldades dos ini
iantes
em programação em 
omputadores. Isto porque não existe um 
onjunto de re-
gras, ou seja um algoritmo, que nos permita 
riar algoritmos. Caso isto fosse
possível a função de 
riador de algoritmos desapare
eria. Claro que existem
linhas mestras e estruturas bási
as, a partir das quais podemos 
riar algorit-
mos, mas a solução 
ompleta depende em grande parte do 
riador do algoritmo.
34
Geralmente existem diversos algoritmos para resolver o mesmo problema, 
ada
um segundo o ponto de vista do seu 
riador.
No seu livro Fundamental Algorithms vol. 1 Donald Knuth [?℄ apresenta
uma versão para a origem desta palavra. Ela seria derivada do nome de um
famoso matemáti
o persa 
hamado Abu Ja�far Maomé ibn Mûsâ al-Khowârism
(825) que traduzido literalmente quer dizer Pai de Ja�far, Maomé, �lho de
Moisés, de Khowârizm. Khowârizm é hoje a 
idade de Khiva, na ex União
Soviéti
a. Este autor es
reveu um livro 
hamado Kitab al jabr w�al-muqabala
(Regras de Restauração e Redução). O título do livro deu origem também a
palavra Álgebra.
O signi�
ado da palavra é muito similar ao de uma re
eita, pro
edimento,
té
ni
a, rotina. Um algoritmo é um 
onjunto �nito de regras que for-
ne
e uma seqüên
ia de operações para resolver um problema espe
í-
�
o. Segundo o di
ionário do prof. Aurélio Buarque de Holanda um algoritmo
é um:
Pro
esso de 
ál
ulo, ou de resolução de um grupo de problemas se-
melhantes, em que se estipulam, 
om generalidade e sem restrições,
regras formais para a obtenção de resultado ou de solução de pro-
blema.
Um algoritmo opera sobre um 
onjunto de entradas (no 
aso do bolo, farinha
ovos, fermento, et
.) de modo a gerar uma saída que seja útil (ou agradável)
para o usuário (o bolo pronto).
Um algoritmo 
omputa
ional tem 
in
o 
ara
terísti
as importantes:
Finitude: Um algoritmo deve sempre terminar após um número �nito de pas-
sos.
De�nição: Cada passo de um algoritmo deve ser pre
isamente de�nido. As
ações devem ser de�nidas rigorosamente e sem ambiguidades.
Entradas: Um algoritmo deve ter zero ou mais entradas. Entradas são as