Introdução

Os computadores são máquinas incríveis e, de fato, podemos ver aplicações das mais diversas possíveis. Por exemplo, ele pode te ajudar a fazer contas simples aritméticas, mas de maneira muito mais rápida do que feito no papel, podem simular processos químicos, sintetizar voz e traduzir documentos, sequenciar problemas genômicos, resolver problemas de trânsito, e uma outra incontável variedade de aplicações!

O que é surpreendente que tudo que o computador faz é manipular um conjunto (muito grande) de chaves. Essas chaves são chamadas de bits. Um bit é um valor armazenado que pode estar em dois estados, 0 ou 1. Tipicamente, nos computadores de hoje, esses estados são determinados por características elétricas, como carga positiva, ou negativa, etc.

Na verdade, embora utilizemos os computadores para coisas incríveis como as listadas acima, ele é projetado para executar tarefas bem simples, como inverta esse bit, faça um bit virar 1, ou realizar ações dependendo do valor do bit, como se o bit for 1, modifique o próximo bit, etc.

Os computadores podem ser muito diferentes, tanto na forma (um PC, um celular, um chip automotivo...), quanto na representação interna. Mas todos eles são baseado nos mesmos princípios gerais, sempre temos esse espírito de um conjunto de "botões" ou "manivelas" que manipulam os bits subjacentes.

Entendendo os termos

Para entender alguns termos importantes, vamos apelas para uma analogia gastronômica. Imagine que queremos fazer um bolo. Então vamos ter que considerar diversos elementos:

Os ingrediente são as entradas do processo.
O bolo é a saída.
A receita do bolo que lista as atividades que serem executadas é o algoritmo.

Ainda podemos distinguir duas partes importantes nesse processo

As receitas, ou algoritmos, correspondem ao que chamamos de software.
Já os utensílios utilizados (panela, forno, talheres e mesmo o cozinheiro) correspondem ao hardware.

Algoritmos e Computação

Aqui temos que diferenciar algoritmos de Computação. Algoritmos são os texto propriamente dito; já a teoria dos Algoritmos é a área da computação ue estuda os algoritmos.

Podemos pensar numa analogia com Literatura: enquanto os objetos de estudo dessa disciplina são os poemas, contos, romances, etc., a LIteratura é a ciência que estuda a estrutura, a forma, o modo, o tamanho, o ritmo desse conteúdo. Da mesma forma, na teoria dos algoritmos, queremos estudar a estrutura, a forma, o modo, a velocidade, as limitações, etc. dos algoritmos.

É preciso entender e diferenciar também o nosso papel nesse contexto. Enquanto nós queremos resolver problemas, o computador é um mero instrumento de trabalho. Uma frase bem conhecida que descreve esse sentimento, de origem desconhecida, é a seguinte:

Ciência da Computação é tanto sobre computadores, quanto Astronomia é sobre telescópios.

Isso é particularmente crítico quando lemos os termos em inglês, em que Ciência da Computação e Engenharia da Computação são traduzidos como "Computer Science" e "Computer Engineering". É bem verdade que nós vamos aprender no decorrer do curso como funciona um computador em um nível muito grande de detalhes e muitos podem até projetar a arquitetura de um computador. Mas é importante saber — e explicar! — que quando falamos de Computação estamos falando desde as simples contas de uma planilha de gastos no seu computador, até os enormes genomas calculados por computadores, aos diversos problemas de logística gigantescos da indústria, aos incríveis e surpreendentes avanços do reconhecimento de padrões, até as respostas a perguntas fundamentais matemáticas que atiçam a curiosidade humana.

Um pouco de história

Um dos primeiros algoritmos não triviais é o chamado algoritmo de Euclides, que vocês já devem ter estudado. Ele foi escrito provavelmente entre 400 e 300 a.C. pelo matemático grego Euclides (que talvez o tenha inventando ou apenas formalizado um algoritmo conhecido). Esse algoritmo server para encontrar o maior divisor comum (MDC) entre dois números inteiros positivos. Por exemplo, o MDC de 80 e 32 é 16

A palavra "algoritmo" é derivada do nome do matemático persa Mohammed al-Khowârizmı̂, do século nono, a quem são atribuídos os algoritmos de adição, subtração, multiplicação e divisão com números decimais. Aqueles que aprendemos nas primeiras séries da escola.

Uma das primeiras máquinas automáticas que poderiam ser controladas, ou digamos, programadas foram máquinas de tecer criadas pelo francês Joseph Jacquard in 1801 A forma dos padrões dos tecidos era determinada por cartões perfurados em vários locais!

Uma das primeiras máquinas que fizeram computação numérica foram as máquinas diferenciais, de Charles Babbage em 1833. Assim como as máquinas de Jacquard, a máquina de Babbage era de natureza mecânica, baseada em alavancas, rodas dentadas e engrenagens, ao invés eletrônicos e silício como os computadores de hoje.

Ada Byron, condessa de Lovelace, foi programadora de Babbage. Ela é uma das figuras mais interessantes da história da Computação e é creditada por lançar as bases da programação, mais de cem anos antes do primeiro computador em funcionamento estar disponível.

No entanto, os primeiros computadores de uso geral foram construídos apenas na década de 1940, em parte, como resposta às necessidades computacionais de físicos e astrônomos e, em parte, como resultado natural da disponibilidade dos dispositivos eletromecânicos e eletrônicos apropriados. Alguns nomes de destaque nessa evolução são o inglês Alan Turing, os americanos Howard Aiken, John Mauchly, J. Presper Eckert, and Herman Goldstine, e o famoso matemático americano e alemão John von Neumann.

A figura a seguir é um computador ENIAC desenvolvido por Mauchly, Eckert e Goldstine:

Com relação à teria dos algoritmos, a década de 1930 experienciou uma rápida disseminação de conhecimento. Mesmo antes de haver máquinas viáveis (que só viriam anos mais tarde), várias matemáticos criaram as bases fundamentais da Computação! Algumas figuras-chaves são o inglês Alan Turing, o britânico Kurt Gödel, o russo Andreı̆ A. Markov e os americanos Alonzo Church, Emil Post e Stephen Kleene.

Depois disso, houve uma enormidade de descobertas e evolução, que acabaram por culminar na definição formal de um curso de computação por volta de meados de 1960, criando-se vários curso de Ciência da Computação em várias universidades americanas.

Alguns links interessantes que vocês podem ver:

Arquitetura de von Neumann

A maioria dos computadores modernos são organizados seguindo a arquitetura proposta por Von Neumann, que reúne os seguintes componentes:

A processing unit that contains an arithmetic logic unit and processor registers A control unit that contains an instruction register and program counter Input and output mechanisms[1][2]

Uma memória que guarda dados e instruções
Uma memória externa que guarda grandes quantidades de dados permanentemente
Uma unidade central de processamento, composta por diversos registradores e que realiza operações aritméticas e lógicas
Uma unidade de controle, cuja função é buscar um programa na memória, instrução por instrução, e executá-lo sobre os dados de entrada.

Atualmente, a arquitetura de von Neumann refere-se a qualquer computador em que o conjunto de instruções está armazenado na memória. O que liga os diversos componentes em um computador é o que chamamos de bus.

Algoritmos

Vamos tentar melhorar nossa definição de algoritmo. Primeiro, vamos ver uma receita de mousseline au chocolat (retirada da bibliografia).

Os ingredientes, ou a entrada desse algoritmo são: 8 onças de pedaços de chocolate meio amargo, 2 colheres de sopa de água, 14 xícaras de açúcar em pó, 6 ovos separados e assim por diante. As saídas são as seis ou oito porções da deliciosa mousseline au chocolat. Aqui está a receita ou o algoritmo para isso:

Derreta o chocolate e 2 colheres de sopa de água em banho-maria. Quando derretido, misture o açúcar em pó; adicione a manteiga pouco a pouco. Deixe descansar. Bata as gemas até engrossar e cor de limão, cerca de 5 minutos. Dobre delicadamente no chocolate. Reaqueça levemente para derreter o chocolate, se necessário. Misture o rum e a baunilha. Bata as claras em neve até formar espuma. Bata 2 colheres de sopa de açúcar; bata até formar picos duros. Dobre delicadamente as claras em uma mistura de gema de chocolate. Despeje em pratos individuais. Refrigere por pelo menos 4 horas. Sirva com chantilly, se desejar. Faz 6 a 8 porções.

Nível de detalhes

Considere a instrução "misture o açúcar em pó". Por que a receita não diz “pegue um pouco de açúcar em pó, despeje no chocolate derretido, mexa, tome um pouco mais, despeje, mexa,...”? A resposta é que o hardware sabe como executar a instrução e não precisa de detalhes adicionais.

Mas por que não dizer que ele sabe como fazer mistura de chocolate com açúcar e manteiga? Ou mesmo que o hardware sabe preparar mousseline au chocolat? Quando escrevemos um algoritmo, escrevemos pensando no hardware utilizado. Sempre devemos escrever uma instrução bem definida para o "computador" que executará o algoritmo.

Isso acontece, por exemplo, quando utilizamos um algoritmo para multiplicar 528 por 46, mas supomos que já sabemos multiplicar 8 por 6, etc.

Abstração

Enquanto nós dizemos que um computador realiza atividades extremamente simples, os nossos algoritmos vão utilizar instruções em mais diferentes níveis de detalhes. Por exemplo, um cozinheiro aprendiz pode necessitar da recita de mousseline au chocolat, mas para um chef experiente, a instrução prepare um mousseline au chocolat já é suficientemente clara.

Abstrair significa esconder os detalhes de que não precisamos. Do mesmo jeito, no computador, ao invés de operarmos sempre sobre bits — o que seria muito tedioso, vamos agrupar os bits em grupos de 8 bits, chamados bytes. Ainda, agruparemos um ou mais bytes em caracteres, depois um ou mais caracteres em *palavras" e assim por diante.

Texto finito

Suponha que queremos calcular quanto iremos gastar no supermercado. Para isso, receberemos como entrada uma lista de itens e valores. Podemos escrever o seguinte algoritmo para essa tarefa:

tome nota do número 0
percorra a lista, adicionando o valor de cada item ao número anotado
quando terminar de percorrer a lista, responda o número anotado

Primeiro, precisamos nos convencer de que esse algoritmo simples realmente realiza a tarefa solicitada. Para isso, vamos testá-lo com algumas listas. Observe que precisamos reservar um espaço no papel para guardar o "valor" atualmente sendo computado.

Executando esse algoritmo, fazemos algumas observações.

Enquanto o texto do algoritmo é um texto curto e de tamanho fixo definido (3 linhas), o processo que esse texto descreve pode variar em duração dependendo do tamanho da lista de exercícios.
Além disso, mesmo que o valor possa ser bem diferente para listas de diferentes famílias (pense numa pessoa que mora sozinha em contraste com uma família seis pessoas!), o espaço no papel que separamos para executar esse algoritmo é sempre o mesmo. O que isso quer dizer é que mesmo que o processo possa produzir valores diferentes, os recursos utilizar por ele são sempre limitados.

O problema algorítmico

Observe que o algoritmo para calcular o valor da lista de compras é genérico e não interessa qual o tamanho família ou lista de compras em particular que é fornecida como entrada. Assim, esse algoritmo funciona para um conjunto infinito de entradas diferentes.

Repare que isso é em contraste com o a receita de mousseline au chocolat, que sempre que executado por um cozinheiro vai produzir as mesmas porções de mousseline. Mas mesmo esse algoritmo pode ser tornado genérico, se mudarmos os ingredientes para algo como "X onças de pedaços de chocolate, X / 4 colheres de sopa de água, X / 32 xícaras de açúcar em pó, etc.". Assim, o resultado produzido pela receita poderia ser "rende de 3/4 X a X porções de X".

Um outro aspecto importante é que a entrada deve ser válida. Assim, devemos fornecer uma lista de compras para o algoritmo da soma, e não podemos tentar executar esse algoritmo com uma lista dos livros mais vendidos no ano, já que isso não faria sentido. Isso significa que as entradas do nosso problema devem ser especificadas de alguma maneira.

Observe que as saídas produzidas por cada algoritmo podem ter natureza diferentes. Enquanto as saídas da receita são "porções de mousseline", as saídas do algoritmo da soma são números. Assim, também devemos ter uma especificação das saídas.

Além disso, observe que para cada entrada, queremos encontrar uma saída correspondente. A descrição dessa saída independe do algoritmo que a obtém. Desse modo, separamos problemas dos algoritmos que os resolvem! Veja a imagem extraída da bibliografia.

Agora já estamos em posição de definir problemas e algoritmos. Vamos definir um problema algorítmico --- algumas vezes também vamos chamá-los de problema computacional --- uma relação formada por

uma caracterização de uma coleção válida, possivelmente infinita, das possíveis entradas do problema,
uma especificação das saídas desejadas como função das entradas.

Uma vez entendido o que é um problema algorítmico, você pode escrever uma definição de algoritmo da sua maneira preferida. Aqui, eu vou dizer que um algoritmo é uma sequência de instruções que resolve um determinado problema. Mas, independentemente da forma com que você defina seu algoritmo, temos que considerar algumas propriedades fundamentais:

Essa sequência de instruções deve ser finita. Isso é porque não queremos considerar sequências infinitas de instruções, já que elas sequer podem ser escritos ou armazenadas em um computador.
O algoritmo deve conter apenas instruções elementares. Aqui, temos que lembrar que um algoritmo é escrito para determinado hardware — ou computador, assim apenas instruções que podem ser compreendidas por esse hardware de forma clara e inambígua podem ser utilizadas.
O texto do algoritmo deve ser uma sequência sistemática de passos. Isso quer dizer que sabemos exatamente qual a ordem em que as instruções são executadas. Dito de outra maneira, após realizar cada uma das instruções, devemos saber se ainda há alguma instrução a ser executada ou se o processo deve terminar.
Sempre que for fornecida uma entrada válida, o algoritmo deve sempre terminar com uma saída correspondente. Isso implica duas coisas: primeiro, que o tempo gasto pelo algoritmo é finito e, segundo, que os demais recursos utilizados, como espaço no papel, ingredientes, etc., também são limitados.