Baixe o app para aproveitar ainda mais
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
Compartilhar