Introdução à Computação - Conversão de Decimal em Binário

Conversão de Decimal em Binário

Faz-se sucessivas divisões por dois até zerar as possibilidades. O resto da divisão (do último para o primeiro) será nosso número convertido.

Converter ${ 101 }_{ 10 }\rightarrow$ Binário

$\begin{matrix} 101 \\ 50 \\ 25 \\ 12 \\ 6 \\ 3 \\ 1 \end{matrix}\begin{matrix} \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \end{matrix}\begin{matrix} 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{matrix}\begin{matrix} = \\ = \\ = \\ = \\ = \\ = \\ = \end{matrix}\begin{matrix} 50 \\ 25 \\ 12 \\ 6 \\ 3 \\ 1 \\ 0 \end{matrix}\begin{matrix} resto \\ resto \\ resto \\ resto \\ resto \\ resto \\ resto \end{matrix}\begin{matrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix}$

Agora, com as divisões esgotadas pegamos os restos das divisões do último para o primeiro e formamos nosso número binário:

${ 101 }_{ 10 }\rightarrow{ 1100101 }_{ 2 }$

Ou seja, 101 na base 10 é igual a 1100101 na base 2!

O mais interessante nessas conversões é que o resto da divisão inteira sempre será ou um ou zero, por isso repito, a matemática é incrível! Basta lembrar que devemos utilizar o resto da divisão no sentido de baixo para cima e pronto, está feito!

Converter ${ 291 }_{ 10 }\rightarrow$ Binário

$\begin{matrix} 291 \\ 145 \\ 72 \\ 36 \\ 18 \\ 9 \\ 4 \\ 2 \\ 1 \end{matrix}\begin{matrix} \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \\ \div  \end{matrix}\begin{matrix} 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{matrix}\begin{matrix} = \\ = \\ = \\ = \\ = \\ = \\ = \\ = \\ = \end{matrix}\begin{matrix} 145 \\ 72 \\ 36 \\ 18 \\ 9 \\ 4 \\ 2 \\ 1 \\ 0 \end{matrix}\begin{matrix} resto \\ resto \\ resto \\ resto \\ resto \\ resto \\ resto \\ resto \\ resto \end{matrix}\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix}$

${ 291 }_{ 10 }\rightarrow{ 100100011 }_{ 2 }$

Ou seja, 291 na base 10 é igual a 100100011 na base 2!

_________________________________________________________________________________
Próxima postagem: Introdução ao Sistema Octal

Introdução à Computação - Conversão de Binário em Decimal

Conversão de Binário em Decimal

Não existe mistério na conversão de um número na base 2 (binária) para base 10 (decimal), mas considero importante que leia as postagens anteriores, começando pela dos Sistemas Numéricos Posicionais pois é importante que se entenda como é formado um número decimal. Para a conversão partimos do mesmo princípio, porém utilizamos a base 2 nos cálculos:

Converter ${ 10110 }_{ 2 }\rightarrow$ Decimal

Por enquanto trabalharemos apenas com números inteiros, números fracionários ganharão uma postagem à parte.

O dígito menos significativo (mais à direita é o que receberá a potência de ${ 2 }^{ 0 }$  o restante basta ir contando da direita para a esquerda, no dígito mais significativo ficara a maior potência de 2):

$=1*{ 2 }^{ 4 }+0*{ 2 }^{ 3 }+1*{ 2 }^{ 2 }+1*{ 2 }^{ 1 }+0*{ 2 }^{ 0 }$

$=1*16+0*8+1*4+1*2+0*1$

$=16+0+4+2+0$

$={22}_{10}\rightarrow$o número 10 significa base 10 (se fosse 2 seria base 2)

Portanto ${10110}_{2}={22}_{10}$

Converter ${ 11001100 }_{ 2 }\rightarrow$ Decimal

Para facilitar nos cálculos costuma-se cortar os zeros antes da conversão, pois como foi possível observar no exemplo anterior os zeros resultam em zero, o que não faz diferença no fim da conversão, apenas os usamos para contar as potências:

$\xleftarrow [ { 2 }^{ 7 }{ 2 }^{ 6 }{ 2 }^{ 5 }{ 2 }^{ 4 }{ 2 }^{ 3 }{ 2 }^{ 2 }{ 2 }^{ 1 }{ 2 }^{ 0 } ]{ 11001100 } $ contamos da direita para a esquerda para verificar o valor das potências.

11001100 não usaremos mais os zeros nos cálculos, a não ser que você ache necessário.

$=1*{ 2 }^{ 7 }+1*{ 2 }^{ 6 }+1*{ 2 }^{ 3 }+1*{ 2 }^{ 2 }$

$=1*128+1*64+1*8+1*4$

$=128+64+8+4$

$={204}_{10}$

Portanto ${11001100}_{2}={204}_{10}$

Podemos ler assim também: 11001100 em binário é igual a 204 em decimal.
_________________________________________________________________________________
Próxima postagem: Conversão Decimal para Binário

Introdução à Computação - Introdução ao Sistema Binário

O Sistema Binário - Introdução

Usa dois algarismos: 0 e 1 (por isso é chamado de base 2) que representam níveis de tensão (origem na eletrônica).

O sistema binário foi criado para facilitar a manipulação e interpretação de dados pela máquina e tem como base a álgebra booleana.

BIT é a contração de BINARY DIGIT

Cada casa em um número binário é um bit.

Exemplo:

dígito mais significativo $\rightarrow$1 0 1 1 0$\leftarrow$dígito menos significativo 10110 é um número binário de 5 bits

Tabela Básica Binário $\rightarrow$ Decimal

Binário	Decimal
0	0
1	1
10	2
11	3
100	4
101	5
110	6
111	7
1000	8
1001	9
1010	10
1011	11
1100	12
1101	13
1110	14
1111	15
10000	16

Contar em binário

Para contar em binário é muito simples, na verdade segue o mesmo caminho que contar em decimal, quando todos nossos números estiverem setados em um devemos zerá-los e então acrescentar um na frente do dígito mais significativo:

Contando em binário de 100 até 100000

100 - 101 - 110 - 111 - 1000 - 1001 - 1010 - 1011 - 1100 - 1101 - 1110 - 1111 - 10000 - 10001 - 10010 - 10011 - 10100 - 10101 - 10110 - 10111 - 11000 - 11001 - 11010 - 11011 - 11100 - 11101 - 11110 - 11111 - 100000

Quantos números diferentes podemos representar com 3 bits binários?

Com 3 bits binários podemos contar até 111, ou 7 em decimal. Como sabemos disso?

Para sabermos quantos números podemos representar com uma certa quantidade de bits basta elevarmos nossa base que é dois ao número de bits necessários:

$2^n$, onde n é o número de bits. 

No caso de 3 bits é possível representar 8 números diferentes (do zero ao sete) pois $2^3 = 8$.

Quantos números diferentes podemos representar com 6 bits binários?

Seguindo a mesma lógica basta fazermos $2^6$ e o resultado é 64, portanto, com 6 bits binários podemos contar do zero até o 63, representando 64 números. Em binário contaríamos do zero até o 111111.

Até que número podemos contar com uma quantidade de bits n?

Com uma quantidade n qualquer de bits podemos contar de zero até  $2^n-1$, Portanto, com 8 bits binários podemos contar em decimal de zero até 255, pois $2^8-1=255$, para o mesmo número de bits em binário contamos de zero até 11111111 (o último número sempre serão os n bits setados em um).

_________________________________________________________________________________

Próxima postagem: Conversão Binário para Decimal

Introdução à Computação - Sistemas Numéricos Posicionais

Introdução

Essa é uma disciplina que muitas vezes assusta quem chega no curso sem saber nada sobre o assunto, mas com o tempo aprendi a amá-la, e quanto mais aprendia mais vontade tinha de pesquisar sobre o assunto. Meu conselho para quem está cursando essa disciplina: aproveite-a!

Vou começar direto na parte mais prática da disciplina, que são os sistemas numéricos.

Sistemas Numéricos Posicionais

Você já se perguntou porque os sistemas numéricos são posicionais? Pois foi apenas ao chegar nessa disciplina que me fiz tal pergunta. Um sistema numérico posicional significa que a posição ocupada por um algarismo em um número altera seu valor em uma potência (essa potência depende da base em que o número se encontra, no caso da base decimal é potência de 10), por exemplo ${ 2 = 2*10 }^{ 0 }$.

Base de um Sistema de Numeração

A base de um sistema de numeração representa a quantidade de algarismos diferentes que estão disponíveis para sua representação, no caso do sistema decimal a base é 10 porque dispomos de 10 algarismos diferentes (zero ao nove). Vejamos o exemplo para os números decimais, que são atualmente os mais utilizados:

Sistema Decimal

A necessidade de contar surgiu faz muito tempo, quando os pastores precisavam controlar a quantidade de suas ovelhas. E se uma ovelha tivesse se perdido? Foi então que começaram a usar pedrinhas, cada pedrinha era guardada em uma bolsa e representava uma ovelha (é dessa pedrinha que hoje usamos a palavra cálculo, que vem do latim calculus, significando pedrinha), quando as ovelhas voltavam, para cada uma delas era retirada uma pedrinha da bolsa, se sobrassem pedrinhas era porque estava faltando ovelhas.

Porém os símbolos propriamente ditos tiveram origem com os egípcios, que tiveram a necessidade de representar uma grande quantidade de objetos para realizar cálculos. Os romanos também são importantes pois usaram seu próprio alfabeto para representar os números. Mas então um povo importantíssimo para a matemática inventou o sistema decimal: os hindus. 

Os hindus criaram um sistema com dez símbolos, com a invenção do zero. Esses símbolos tão conhecidos são chamados de HINDU-ARÁBICOS,cada um é um algarismo e é de base 10 pois com apenas esses dez algarismos podemos formar qualquer número. Agora me diga, é louco e lindo né?

Você conhece unidades, dezenas e centenas? Se não conhece ou não lembra, pesquise sobre isso antes de continuar, estamos combinados?

Então vamos contar:

0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9

Opa acabaram os algarismos e agora? Bem, agora começamos do número um e vamos acrescentando até chegar ao nove novamente:

10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19

E assim por diante, para o vinte, colocamos o dois com o zero e depois seguimos até o nove:

20 - 21 - 22 - 23 - 24 - 25 - 26 - 27 - 28 - 29

Quando esgotarmos as opções de números com apenas dois algarismos (dígitos) começamos com três e assim por diante. Isso é simples e parece mágica e é muito importante que todos consigam entender esse processo, pois a matemática é assim tão linda justamente pela sua simplicidade:

101 - 102 - 103 ...

Mas qual é o cálculo feito para formar os números, ou é aleatório?

Não é aleatório, tudo isso tem um fundamento, que parece mágica (estou repetindo isso eu sei, mas é maravilhoso).

Como exemplo, o número 58:     

58 =              

O número 10 é usado porque a base é 10!

Exemplo de número com vírgula, o número 58,6601:
58,6601 =

Após a potência zero indica a presença de vírgula, então começam as potências
negativas!

Com essa pequena instrodução, estamos prontos para iniciar os estudos das outras bases de numeração, em breve uma nova postagem sobre o sistema de numeração binário.
_________________________________________________________________________________

Próxima postagem: Introdução ao Sistema Binário

Programas para a Máquina de Post sem o uso do simulador

Máquina  de Post

O que eu considero mais interessante (e importante) no estudo das máquinas abstratas é que para entendê-las basta lápis e papel. Não existe a necessidade, a não ser para facilitar os estudos, do uso do simulador, podemos criar nossos programas à moda antiga, como tudo realmente começou. No caso da Máquina de Post darei um exemplo a seguir.

Fluxograma Máquina de Post Duplo Balanceamento

Retirei esse programa do livro "Teoria da Computação - Máquinas Universais e Computabilidade (Volume 5 - 3ª edição, página 184). O programa verifica o duplo balanceamento de palavras formadas pelos símbolos a e b, ou seja verifica se uma palavra é do tipo aaabbb ou bbbaaa, mesma quantidade de um símbolo seguida pela mesma quantidade do outro símbolo. Clique para ampliar o fluxograma:

Executando o programa

Caso 1: ACEITA

A seguir, a execução do programa (através da fila) para a entrada X = aaabbb

a

a

a

b

b

b

Primeiramente, o símbolo auxiliar é concatenado no fim da fila da palavra X:

X = aaabbb#

a

a

a

b

b

b

#

O primeiro símbolo é lido, como era um símbolo esperado ele é apenas destruído sem ser concatenado no fim da fila, pois não será mais necessário, a fila fica assim:

X = aabbb#

a

a

b

b

b

#

O segundo símbolo foi lido, como agora estamos esperando um b, enviamos o símbolo lido para o fim da fila, pois posteriormente ele será usado:

X = abbb#a

a

b

b

b

#

a

Novamente:

X = bbb#aa

b

b

b

#

a

a

Opa, finalmente encontramos um símbolo b respectivamente ao símbolo a que destruímos anteriormente, até agora está tudo ok, então o símbolo é apenas apagado:

X = bb#aa

b

b

#

a

a

Agora o programa vai ler um por um dos símbolos restantes e enviar ao fim da fila, até encontrar o símbolo auxiliar:

X = b#aab

b

#

a

a

b

Agora a primeira varredura da palavra foi completa, verifique como ficamos com dois símbolos à menos, isso porque, para verificar se a palavra está correta, o programa retira um símbolo a e um símbolo b. A partir de agora, para manter a estrutura do tipo fila, o programa realiza varreduras circulares na palavra até não restar mais nenhum símbolo ou até que a entrada seja rejeitada:

X = #aabb

#

a

a

b

b

X = aabb#

a

a

b

b

#

X = abb#

a

b

b

#

X = bb#a

b

b

#

a

X = b#a

b

#

a

X = #ab

#

a

b

X = ab#

a

b

#

X = b#

b

#

Após realizar as varreduras necessárias e não ter entrado em nenhum caso de REJEITA, restou apenas o símbolo auxiliar:

X = #

#

Mesmo assim o programa vai tentar realizar mais uma varredura, apagando o símbolo auxiliar e o concatenando no fim da palavra novamente:

X = #

#

É agora que o programa entra no caso do aceita, pois ao tentar realizar essa última varredura ele encontra apenas o # o destrói e a palavra é aceita, deixando a fila vazia e o programa termina sua execução:

Caso ainda não tenha entendido, basta pensar exatamente como uma fila funciona, quando alguém se retira de uma fila, ou volta para o fim, ou vai embora. No caso da máquina de Post, quando um símbolo é lido ou ele vai para o fim da fila ou é destruído.

_________________________________________________________________________________

Caso 2: REJEITA

A seguir, a execução do programa (através da fila) para a entrada X = aaabb, entrada que deve ser rejeitada pois apresenta um símbolo b a menos do que deveria:

a

a

a

b

b

Primeiramente, o símbolo auxiliar é concatenado no fim da fila da palavra X:

X = aaabb#

a

a

a

b

b

#

O primeiro símbolo é lido, como era um símbolo esperado ele é apenas destruído sem ser concatenado no fim da fila, pois não será mais necessário, a fila fica assim:

X = aabb#

a

a

b

b

#

O segundo símbolo foi lido, como agora estamos esperando um b, enviamos o símbolo lido para o fim da fila, pois posteriormente ele será usado:

X = abb#a

a

b

b

#

a

Novamente:

X = bb#aa

b

b

#

a

a

Opa, finalmente encontramos um símbolo b respectivo ao símbolo a que destruímos anteriormente, até agora está tudo ok, então o símbolo é apenas apagado:

X = b#aa

b

#

a

a

Agora a primeira varredura da palavra foi completa, verifique como ficamos com dois símbolos à menos, isso porque, para verificar se a palavra está correta, o programa retira um símbolo a e um símbolo b. A partir de agora, para manter a estrutura do tipo fila, o programa realiza varreduras circulares na palavra até não restar mais nenhum símbolo ou até que a entrada seja rejeitada:

X = #aab

#

a

a

b

X = aab#

a

a

b

#

X = ab#

a

b

#

X = b#a

b

#

a

X = #a

#

a

X = a#

a

#

Como tínhamos um símbolo b a menos na palavra ele não vai encontrar o símbolo correspondente e vai entrar em um caso de REJEITA pois encontrou o símbolo auxiliar antes da hora:

X = #

#

ENTRADA REJEITADA!

_________________________________________________________________________________

Com isso, encerro as postagens sobre a Máquina de Post, se estiverem com dúvidas, comentem à vontade!

Não deixem de ler as demais postagens sobre a Máquina de Post: 

 1.Introdução, definição e funcionamento
 2.Usando o Simulador da Máquina de Post
 3.Executando um programa no Simulador de Máquina de Post