Introdução
à Ciência da Computação - Notas de Aula 1
Capítulo 1 – Introdução
0.
Sumário
1.
Introdução
2.
Noções de Hardware
2.1 Formas de representar dados
2.2
Álgebra Booleana
2.3 Implementação com componentes eletrônicos
2.3.1
Dispositivos Eletro-eletrônicos
2.3.2.
Implementação das operações booleanas
2.3.3
Exemplos de circuitos construídos com blocos
2.4
Estrutura esquemática de um computador
3.
Noções de Software
3.1 Introdução
3.2 Sistemas Operacionais
3.3 Linguagens de Programação
3.4
Exemplo de uma máquina hipotética rodando um programa executável
3.5
Algoritmo
1. Introdução
O
que diferencia o computador de outras máquinas ou utensílios?
Estas,
em geral, têm uma finalidade bem específica. Por exemplo, um liquidificador de
cozinha, tem a finalidade de tornar líquido ou pastoso o que se coloca dentro
dele. Para operá-lo bastam dois botões: um para ligar e desligar; outro para
controlar a velocidade.
O
computador tem múltiplas finalidade e funções: pode ser utilizado para fazer
cálculos, para escrever textos, para armazenar e organizar os dados cadastrais
dos clientes de uma loja, etc.
Para
operar uma máquina com essa característica, não bastam alguns botões. É preciso
utilizar um programa, que permita ao usuário da máquina especificar o que ele
deseja.
Distinguem-se
então dois conceitos importantes:
hardware: parte física de um sistema computacional, conjunto de componentes
eletrônicos, elétricos, mecânicos, como placas, circuitos, fios, etc.
software: parte lógica de um sistema computacional, conjunto de
procedimentos, programas, instruções, que levam o computador a realizar uma
tarefa.
2.
Noções de Hardware
O
computador é uma máquina multi-funcional: pode ser utilizado para gerar textos,
tratar imagens, executar cálculos, etc. De forma geral, pode-se dizer que o
computador processa dados ou informações, que podem representar números,
textos, imagens, etc.
2.1 Formas de representação de dados
Um
primeiro problema que aparece é a escolha da melhor forma de representar os dados
dentro do computador.
a) Sistema decimal:
10 símbolos (algarismos 0 a
9): é a forma usual que os humanos utilizam para representar dados (embora
também haja outras: a dúzia, os 60 segundos para formar um minuto, etc.)
Pode-se
pensar em uma máquina operando com sistema decimal: é necessária alguma
grandeza física interna à máquina para se associar a cada algarismo (por
exemplo, engrenagens com 10 dentes cada uma). A grandeza física habitualmente
utilizada é uma tensão ou uma corrente elétrica. Para utilizar um sistema
decimal, os circuitos precisariam estar aptos a distinguir, sem erro, 10 níveis
diferentes de tensão elétrica. Naturalmente, o sistema se tornaria muito
sujeito a erros, pois facilmente se confundiria um nível de tensão com outro. O
sistema mais seguro possível é o que trabalha com o menor número de níveis de
tensão: dois níveis. Isto implica utilizar
um sistema de numeração binário.
b) Sistema binário: 2
símbolos (por exemplo, 0 e 1). É o sistema mais seguro possível, pois há apenas
dois níveis (0 ou 1, ligado ou desligado, etc.). Daqui deriva o conceito de bit (binay digit): menor unidade de informação possível
(pode assumir os valores 0 ou 1). Um conjunto de bits pode representar qualquer
quantidade de informações:
1
bit – duas informações : 0 1
2
bits – quatro informações: 00 01
10 11
3
bits – oito informações: 000 001 010
011 100 101
110 111
n
bits – 2n informações
Um
conjunto muito útil é o de 8 bits, denominado de byte – pode representar 256 informações.
Em
geral, os bytes são agrupados em múltiplos, da seguinte forma:
kilobyte 1024 bytes (
1024 = 210 )
megabyte 1024 kilobytes
gigabyte 1024 megabytes
Todos
os caracteres, algarismos e símbolos utilizados habitualmente podem ser armazenados
em bytes, organizando-se uma tabela. O padrão mais conhecido é o código ASCII (American Standard Code for Information
Interchange)
Exemplos
de alguns valores da tabela ASCII:
símbolo representação valor decimal
( 00101000 40
+ 00101011 43
0 00110000 48
1 00110001 49
2 00110010 50
A 01000001 65
B 01000010 66
C 01000011 67
a 01100001 97
b 01100010 98
c 01100011 99
c) Conversão
de sistemas binário – decimal
a) binário
para decimal:
A
notação posicional utilizada na construção de qualquer número significa que o
valor do número é dado pela soma dos produtos de cada algarismo pela base
elevada a um número inteiro que indica sua posição, a partir de zero. Por
exemplo, o número 527 significa:
5
2 7 |
|||
 |
|||
7
x 100 = 7
2 x 101 = 20
5 x 102 = 500 valor = 500 + 20 + 7 = 527
Assim,
para se passar da notação binária para a decimal, multiplica-se o valor de cada
bit pela base (2) elevada ao expoente que marca sua posição
1
0 1 1 0
 |
 |
 |
 |
 |
|||||
0 x 20 = 0
1 x 21 =
2
1
x 22 = 4
0 x 23 = 0
1 x 24 = 16
resultado: 16 + 0 + 4 + 2 + 0 = 22
b) decimal para binário
Para
passar da base decimal para a binária, divide-se o número por 2, em seguida divide-se
o resultado por 2 e assim sucessivamente, até que o resultado seja 1. Então
escreve-se a seqüência formada pelo último resultado e os restos das divisões,
do último para o primeiro.
22 2
0
11 2
1 5
2
1 2 2
resultado: 1 0 1 1 0
0 1
d) Sistema
hexadecimal: utiliza 16 símbolos (os 10 algarismos
e as letras A B C D E F)
decimal binário hexadecimal
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 8
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
O
sistema hexadecimal proporciona um modo mais fácil de visualizar e manipular um
número dado na base binária. Para isso, separa-se o número binário em conjuntos
de quatro bits cada um, e em seguida substitui-se cada conjunto de 4 bits pelo
correspondente valor em
hexadecimal. Por exemplo:
180 10 =
101101002 = (1011) (0100) = B4h
Inversamente, A9h = (1010) (1001) = 101010012
= 16910
2.2
Álgebra Booleana
Foi
desenvolvida por George Boole, em 1854 e define operações para variáveis binárias,
isto é, variáveis que só podem assumir dois valores. Tem grande importância na
computação, por fornecer as ferramentas para manipular variáveis binárias.
As
variáveis assumem valores V (verdadeiro) ou F (falso). As operações básicas são
denominadas AND, OR e NOT, e correspondem
a operações lógicas que fazemos no dia a dia.
Exemplos:
a) se o tempo for bom AND eu
tiver dinheiro então vou viajar
Denominando:
a – tempo bom;
b – ter dinheiro;
z – viagem;
Pode-se preencher a tabela-verdade (valores
de saída para todas as combinações de valores de entrada) da função AND
z = a
AND b (também se representa z
= a . b)
a b z |
F F F
F V F
V F F
V V V
b) se
sair o pagamento OR eu conseguir empréstimo então vou viajar
a – sai o pagamento; b – eu consigo empréstimo; z – viagem
tabela-verdade da função OR
z = a
OR b (também se representa z
= a + b)
|
a b z
F F F
F V V
V F V
V V V
c) se
NOT chover então viajo ; se chover então NOT
viajo
a –
chove; z – viajo
tabela-verdade da função NOT
_
z = NOT a (também se representa z = a )
a z
F V
V F
d) representação por blocos
As
operações booleanas podem ser representadas através de blocos. Os blocos AND e
OR admitem qualquer número de entradas. Nos exemplos abaixo foram utilizados
blocos com 3 entradas. Os valores V ou F em geral são substituídos por 1 e 0,
respectivamente.
a
z
b
c
AND
a
b z
c
OR
 |
a z
NOT
e) exemplo combinando operações anteriores:
se tiver dinheiro AND (
NOT chover ) então viajo
a – tenho dinheiro; b – chove;
z – viagem
_
z
= x . y
a b z |
 |
||
0 0 0 a
0 1 0 z
1 0 1 b
1 1 0
2.3 Implementação com componentes eletrônicos
Cada
uma das operações booleanas pode ser construída com elementos eletrônicos. A
título de exemplo, abaixo se mostram implementações “simplórias”, dos blocos
básicos AND, OR e NOT. Tensão positiva é considerada “1” e tensão nula é “0” .
Essa
construção é meramente didática, pois as implementações reais são muito mais complexas.
2.3.1
Dispositivos Eletro-eletrônicos
a) resistor: tensão é proporcional à
corrente, em qualquer sentido
R
 |
v i v = R i
b) diodo: dispositivo que pode ser
construído por uma pastilha de semi-condutor (silício, por exemplo), dividida
em duas partes, nas quais são feitos tratamentos diferentes. Uma fica denominada
tipo P e a outra tipo N. O diodo apenas permite passagem de corrente do lado P
para o lado N.
|
i
i = 0
 |
|||
 |
|||
v @ 0 v
diretamente polarizado inversamente
polarizado
tensão é praticamente nula corrente é nula
(chave fechada) (chave aberta)
c) transistor: disposititvo construído por
uma pastilha de semi-condutor (silício, por exemplo) dividida em três partes,
nas quais são feitos tratamentos diferentes. Um caso é o que forma um sanduíche
de partes tipo N, P e N.
|
||||||
|
 |
|||||
i i = 0
|
|
v
v
|
|
||||
diretamente polarizado inversamente
polarizado
tensão positiva entre b e c tensão negativa
entre b e c
(chave fechada entre a e c) (chave aberta entre
a e c)
2.3.2.
Implementação das operações booleanas
Apresentam-se abaixo 3 exemplos de
circuitos implementados com resistores, diodos e transistor.
+
1 + 1
a
b _
z = a
c
a z = a+b+c
z = a.b.c
b a
c
AND OR NOT
2.3.3
Exemplos de circuitos construídos com blocos
a) Comparador de Bytes
É
um circuito que tem como entradas dois bytes a e b, e como saída uma variável booleana z. O byte a é dado pelas variáveis booleanas a7, a6, ... a1, a0; o byte b é dado pelas variáveis booleanas b7,
b6, ... b1, b0. Podemos encarar este circuito como um comparador de caracteres,
já que um byte representa um caractere, de acordo com a tabela ASCII. Esta operação
é uma pequena parcela de outras operações mais complexas utilizadas em um programa
de edição de textos, como por exemplo: procura de uma palavra em um texto,
substituição de uma palavra por outra em um texto, etc.
Em
primeiro lugar, é preciso criar uma operação para verificar a coincidência de
dois bits de entrada. A variável de saída w é igual a 1 quando as entradas x e
y forem 0 ou quando x e y forem 1. A
tabela com os valores de entrada e saída ficam do seguinte modo:
 |
x y w
 |
0 0 1
0 1 0
1 0 0
1 1 1
_
_
A
expressão booleana correspondente fica:
w = x . y +
x . y
E
o circuito que implementa esta operação fica então:
Podemos
simplificar a representação deste circuito para:
Com
este bloco que determina a coincidência entre dois bits, é possível descrever a
variável z, que determina a coincidência entre dois bytes, por:
z =
(a7 coincide b7) + ... + (a2 coincide b2)
+ (a1 coincide b1) + (a0 coincide b0)
Ou
seja, z vale 1 quando (a7 coincide com b7) e
(a6 coincide com b6) e (a5 coincide
com b5) .... e (a0 coincide com b0).
O
circuito para realizar esta função fica como na figura abaixo:
b) Operação de adição de 2 números
Tomemos como exemplo: 5 + 7 = 12
Em sistema binário: 101
111
+
1100
A
soma de dois bits pode ser definida por um bloco denominado “meia-soma”, que
consiste em duas funções s e v, que dependem de duas variáveis x e y. As variáveis x e y são os
bits a serem somados, s é o resultado, e v é o “vai-um”.
Pode-se
representar o bloco “meia-soma” do seguinte modo:
A
correspondente tabela-verdade e as expressões são:
x y s v
_ _
0 0 0 0 s = x . y + x .
y
0 1 1 0
1 0 1 0 v = x . y
1 1 0 1
O
circuito para implementar esta função fica então:
x y
s
v
Com
um conjunto de blocos “meia-soma” é possível construir um bloco para soma de vários
bits, ou seja, de um número inteiro.
2.4 Estrutura
esquemática de um computador
Do
mesmo modo como foram exemplificadas as construções de circuitos para comparar
bytes e para somar conjuntos de bits, pode-se, com grandes agrupamentos de blocos
básicos, construir todos os elementos da estrutura de um computador. Na figura
abaixo estão representados esquematicamente os elementos básicos de um
computador.
 |
CPU – central processing unit – unidade
central de processamento – unidade responsável pela execução dos programas e
pelo comportamento das outras unidades no sistema.
Unidade de
Controle – parte da CPU que busca na memória a próxima
instrução e a decodifica para ser executada. Dependendo do tipo de instrução,
pode transferir o controle para a Unidade Lógica e Aritmética. Também controla
o envio de dados para componentes externos à CPU.
Unidade Lógica e
Aritmética - parte da CPU que
efetua operações aritméticas (soma, subtração, etc.) e lógicas (verifica se
dois números são iguais ou não, verifica se duas afirmações são verdadeiras
simultaneamente, etc.).
Memória ROM – ROM (read only memory) – memória que contém
informações que não podem ser alteradas; contém programas internos que indicam
o que o computador deve fazer ao ser ligado, ou como efetuar operações básicas
com outras memórias e periféricos mais comuns. Não é volátil: as informações se
mantêm quando o computador é desligado.
Memória RAM ou Memória Principal – memória que guarda
temporariamente os programas e os dados que estão sendo usados (RAM – random access memory). É volátil, guardando
os programas e dados apenas enquanto o computador está ligado.
Registradores –
memórias de alta velocidade e pouca capacidade de armazenamento; indicam áreas
especiais da memória onde residem programas e dados; guarda informações sobre o
estado atual do sistema.
Memória Cache –
memória rápida que guarda dados recentemente processados; antes de procurar um
dado na RAM, o dado é procurado na Cache, cujo tempo de acesso é menor.
Memória Secundária –
memória não volátil para armazenamento a longo prazo, como disquete, disco
rígido, pen-drive. Têm grande capacidade de armazenamento e o acesso a elas é
mais lento que aos outros tipos de memória.
Periféricos de
Entrada e Saída – dispositivos que permitem a entrada e saída de
dados no computador, como por exemplo: teclado, mouse, monitor de vídeo,
leitora de disquetes, impressora, leitora de CD’s, entradas USB, etc.
Barramentos – vias
de tráfego de informações entre componentes. Sua largura (quantidade de bits
que pode transmitir simultaneamente) condiciona sua velocidade de operação.
Clock –
relógio, circuito oscilador que sincroniza o funcionamento dos outros
componentes do computador.
3.
Noções de Software
3.1 Introdução
Pode-se
dividir os programas de computação em três tipos básicos: aplicativos, utilitários
e básicos
a) aplicativos: programas voltados
para uma tarefa desejada diretamente pelo usuário, como por exemplo editores de texto (Word), planilhas
(Excel), gerenciadores de bancos de dados, jogos, etc...
b) utilitários: programas de apoio
que facilitam a tarefa do usuário, como por exemplo antivirus, compactadores de
arquivos, etc...
c) softwares básicos: programas que
permitem o correto funcionamento da máquina, como por exemplo os sistemas
operacionais, sistemas tradutores de linguagem, etc..
3.2 Sistemas Operacionais
Um
sistema operacional é um programa que gerencia e aloca recursos de hardware e
software. Provê, por exemplo, leitura de dados pelo teclado, visualização de
informações no vídeo, gerenciamento de programas pela CPU, gerenciamento das
memórias, etc. Exemplos de sistemas operacionais: Windows2000, Windows XP, Linux,
Unix, MS-DOS, etc. Parte do sistema operacional fica na ROM, gravado em hardware
(BIOS – Basic Input Output System) e
parte fica no HD. Quando o computador é ligado, a BIOS assume o controle e
depois o passa para o sistema em disco.
3.3 Linguagens de Programação
São
programas que permitem construir outros programas para a resolução de problemas
(ou seja, permitem a construção de aplicativos, utilitários e até de sistemas
operacionais). Há muitas linguagens diferentes, cada uma dispondo de recursos
que facilitem certas aplicações. De qualquer modo, um problema que possa ser
resolvido por uma linguagem, poderá ser resolvido por qualquer outra.
As
linguagens podem ser divididas em dois grandes grupos:
a) linguagem de baixo nível: é
aquela que está mais próxima à máquina, ou seja, seus comandos são parecidos
com as instruções do microprocessador. Têm maior velocidade de execução e os
programas gerados por ela são mais compactos (ocupam menos memória). Em compensação,
exige maior nível técnico do programador, sendo maior o tempo empregado no desenvolvimento
de um programa. Distingue-se “linguagem de máquina” como o conjunto de instruções
que podem ser interpretados e executados diretamente pela CPU de um dado computador,
e “linguagem Assembly” como a representação da linguagem de máquina através de
códigos mnemônicos. Ambas são características de cada tipo de processador.
b) linguagem de alto nível: é aquela
que independe do conjunto de instruções da linguagem de máquina do computador.
Está mais próxima do ser humano (o ideal seria a linguagem natural: português,
inglês, etc..). Cada comando de uma linguagem de alto nível equivale a várias
instruções da linguagem de máquina. Isso facilita a tarefa de programação, mas
exige uma etapa intermediária entre a linguagem de alto nível e a de baixo
nível, que pode ser a compilação ou a interpretação. Exemplos de linguagem de
alto nível: Pascal, C, Java, Lisp, etc..
A
compilação é o processo de tradução de um programa escrito em linguagem
de alto nível para uma linguagem de máquina. Uma vez convertido para linguagem
de máquina, o programa pode ser executado independentemente do compilador e do
programa original.
O
programa escrito originalmente recebe o nome de “programa fonte”, e o traduzido
é o “programa executável”. Aparecem nesse processo dois tipos de erros: erros
de compilação (sintaxe errada), que são mais fáceis de corrigir; e erros de
execução (podem ser óbvios como uma divisão por zero, ou, em geral, são mais
difíceis de corrigir, pois são originados por erros de raciocínio na elaboração
do programa). A eliminação desses erros é uma boa parte da tarefa do
programador
 |
 |
Geração do
programa executável Execução do programa
A
interpretação é o processo pelo qual um programa escrito em linguagem de
alto nível é executado, comando por comando. É um processo mais lento que a
execução de um programa executável, mas permite que o código seja alterado
durante a própria execução. Neste caso não existe “programa executável”.
 |
Execução de um programa
interpretado
3.4
Exemplo de uma máquina hipotética rodando um programa executável
Para
formar uma melhor idéia de como um programa é executado em um computador, vamos
definir uma máquina hipotética, com a seguinte configuração:
a) Cada palavra (conjunto de bits que o computador processa de cada
vez) tem 8 bits: os 3 primeiros indicam
o código de execução da instrução e os outros 5 indicam um endereço.
b) Existe um único registrador, aqui denominado de acumulador (AC).
c) Com 3 bits, podem-se definir até 8 instruções (isto significa que
existem circuitos lógicos que, ao encontrar esses códigos, executam o que está
previsto abaixo):
000 – instrução não definida
001 – copia conteúdo do endereço
indicado para o AC
010 – copia conteúdo do AC para o endereço indicado
011 – soma conteúdo do endereço
indicado com o conteúdo do AC, colocando o resultado no
AC
100 – subtrai do conteúdo do AC o conteúdo
da palavra indicada, colocando o resultado no
AC
101 – desvia o fluxo de execução do
programa para o endereço indicado
110 – desvia o fluxo de execução do
programa para o endereço indicado se o
conteúdo do AC
é diferente de zero
111 – encerra a execução do programa
d) Com 5 bits para o endereçamento, pode-se construir uma memória de
32 bytes. No entanto, para o exemplo atual, bastam 16 bytes para armazenar o
programa e os dados. Na tabela abaixo é apresentado um
mapa da memória. O retângulo menor indica o endereço
e o maior, o conteúdo de cada byte da memória.
|
00000
|
00001
|
00010
|
00011
|
|
001
01010
|
010
01100
|
001
01110
|
011
01011
|
|
00100
|
00101
|
00110
|
00111
|
|
010
01110
|
001
01100
|
100
01101
|
010
01100
|
|
01000
|
01001
|
01010
|
01011
|
|
110
00010
|
111
00000
|
000
00011
|
000
00100
|
|
01100
|
01101
|
01110
|
01111
|
|
000
00000
|
000
00001
|
000
00000
|
000
00000
|
A execução do programa começa pela
instrução colocada no endereço 00000:
1. carrega em AC o conteúdo de 01010 ( AC = 00000011 )
2. armazena conteúdo de AC em 01100
3. carrega em AC o conteúdo de 01110 ( AC = 00000000 )
4. soma ao AC o conteúdo de 01011 ( AC = 00000100 )
5. armazena AC em 01110
6. carrega em AC o conteúdo de 01100 ( AC = 00000011 )
7. subtrai de AC o conteúdo de 01101 ( AC = 00000010 )
8. armazena AC em 01100
9. se AC <> 0 então desvia para 00010
(passo 3)
10. encerra
Percebe-se
que algumas áreas da memória contêm dados e não instruções; pode-se então dar
nomes a elas:
01010
=> n
01100 => contador
01110 => a
01011 => b
Pode-se
então reescrever a seqüência de outra forma:
1, 2
: contador ç n
3, 4, 5
: a ç a + b
6, 7, 8
: contador ç
contador - 1
9
: se contador <> 0 então
vá para 3.
10
: encerra
Fica
agora mais fácil perceber que o programa inicia com a = 0 e soma b ao a, n
vezes, ou seja a = b * n
3.5
Algoritmo
Um
algoritmo é uma seqüência finita, ordenada e sem ambigüidades, de passos que
levam à solução de um problema
Antes
de escrever um programa de computação em uma determinada linguagem, é preciso
equacionar a solução do problema através de um algoritmo. Tomemos como exemplo
a seqüência de passos para se dar um telefonema:
1. procure o número no catálogo
2. disque o número
3. se estiver chamando, vá para 5.
4. espere um tempo e vá para 2.
5. se não atender, espere um tempo maior e
vá para 2.
6. pare
O
algoritmo acima poderia ser reescrito de forma estruturada, isto é,
dividido em blocos (marcados com palavras chave, por exemplo inicio e fim),
de modo a evitar os comando “vá para”, que dificultam a compreensão, e
prescindindo da numeração de passos:
inicio
procure
o número no catálogo
enquanto
(não conseguiu falar) faça:
início
disque
o número
se
estiver ocupado
então
esperar
algum tempo
senão
se
atendeu
então
(conseguiu falar = verdade)
senão
(conseguiu falar = falso)
fim
fim
Vejamos
mais um exemplo: algoritmo para fazer uma prova.
Forma não estruturada;
1. ler a prova
2. pegar a caneta
3. se (acabaram as questões) vá para 10
4. se (tempo terminou) vá para 10
5. se (não souber a solução) vá para 8
6. resolver a questão
7. vá para 3
8. pule a questão
9. vá para 3
10. entregar a prova
Forma estruturada:
início
ler
a prova
pegar
a caneta
enquanto
(não acabaram as questões) e (tempo não terminou) faça
início
se
(souber a solução)
então
resolver a questão
senão
pular para a próxima
fim
entregar
a prova
fim
