Unidade 1 - Problemas e algoritmos

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 no papel, podem simular processos químicos, sintetizar voz e traduzir documentos, realizar sequenciamentos 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 é ligar ou desligar um conjunto (muito grande) de chaves. Essas chaves são chamadas de bits. Um bit é um valor armazenado na memória do computador 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.

Enquanto utilizemos os computadores para coisas incríveis e bastante sofisticadas, como as listadas acima, ele é projetado para executar tarefas bem simples. Essas tarefas têm a forma de instrução como faça um bit x receber valor 1, ou correspondem a uma pergunta acerca do valor dos bits, seguida de uma consequência, algo como se o bit x for 1, inverta o bit y.

Os computadores podem ser muito diferentes, tanto na forma, quanto nos conjuntos de instruções que são capazes de realizar. Mas todos eles, seja um computador pessoal, um celular, um chip automotivo, são baseados nos mesmos princípios gerais. Podemos sempre pensar nos computadores como uma máquina cheia de botões cujas engrenagens ligam ou desligam um conjunto de chaves, a depender da configuração desses botões e das próprias chaves.

Entendendo os termos

Quando utilizamos um computador, queremos realizar uma atividade determinada. Pode ser que um computador tenha exatamente uma única função, digamos, uma calculadora de balcão de supermercado que apenas soma os preços de itens digitados. Se também quisermos subtrair o preço de um item cancelado, essa calculadora não serviria e precisaríamos de uma calculadora com duas funções: soma e subtração. Mas se algum dia decidamos que a calculadora deveria também ser capaz de dar um desconto percentual?

O que gostaríamos na verdade é de uma calculadora geral que realizasse todas as operações. Assim, poderíamos sempre utilizar a mesma calculadora, não importa para qual tarefa venhamos a realizar. Mas se a calculadora é de uso geral, como podemos utilizar a calculadora para realizar uma tarefa específica? A resposta para essa pergunta é escrever um algoritmo para cada uma das tarefas necessárias.

Para entender o que é um algoritmo, vamos apelar para uma alegoria gastronômica. Imagine, por exemplo, que queremos fazer um bolo de chocolate. Iniciamos de posse dos ingredientes, a farinha, o açúcar, o cacau, o leite, o fermento. Os ingrediente são as entradas do processo. Nosso objetivo é terminar de posse de um bolo de chocolate. O bolo é a saída do processo. Para transformar os ingredientes em um bolo, vamos ter que executar uma série de atividades descritas em um livro de receitas: colocar os ingredientes em uma panela, misturar com uma colher, assar no forno, etc. A receita do bolo é o que chamamos de algoritmo.

Para que pudéssemos de fato seguir a receita, tivemos que utilizar uma série de ferramentas auxiliares, a panela, o forno, os talheres e até mesmo o cozinheiro. Esses utensílios não mudam, mas poderiam muito bem ser utilizados para preparar diversas outros pratos diferentes. Eles correspondem ao hardware do processo. Já a receita é apenas um conjunto de instruções escritas em um papel, ela corresponde ao que chamamos de software.

Algoritmos e computadores

Temos que diferenciar algoritmos da teoria dos algoritmos. O algoritmo é o texto propriamente dito, enquanto teoria dos algoritmos é disciplina que estuda os algoritmos. Podemos pensar numa analogia com Literatura: enquanto os objetos de estudo dessa disciplina são os poemas, os contos, os romances, a Literatura estuda a estrutura, o contexto, 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 dos algoritmos.

Enquanto estudantes de Computação, queremos descrever e escrever algoritmos para tarefas das mais diversas disciplinas e da própria Computação. E, para executar um algoritmo, normalmente utilizamos um computador. Assim, enquanto nós queremos resolver problemas, o computador é um mero instrumento de trabalho. Uma frase (de autor desconhecido) que descreve bem esse sentimento é a seguinte:

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

Entender isso é particularmente importante 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 vocês irão 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 tanto das simples contas de uma planilha de gastos, quanto dos genomas calculados de diversas espécies, dos enormes problemas de logística da indústria, dos incríveis e surpreendentes avanços do reconhecimento de padrões e das 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 inventado, ou talvez tenha apenas formalizado um algoritmo conhecido). Esse algoritmo serve 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 IX, 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 as máquinas de tecer criadas pelo francês Joseph Jacquard em 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 norte-americano e alemão John von Neumann.

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

Com relação à teoria dos algoritmos, a década de 1930 experienciou um rápido avanço do conhecimento. Mesmo antes de haver computadores eletrônicos viáveis (que só viriam anos mais tarde), vários matemáticos criaram as bases fundamentais da Computação. Algumas figuras-chaves são, de novo, o inglês Alan Turing, assim como o também 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 cursos de graduação voltados para a Computação. Por volta de meados de 1960, criando-se vários cursos de Ciência da Computação em várias universidades norte-americanas.

Vocês podem ver alguns links interessantes sobre a história de computadores e Computação:

Arquitetura de von Neumann

A maioria dos computadores modernos são organizados seguindo uma arquitetura genérica proposta por von Neumann. Nesse modelo, pensamos em um computador como uma coleção de células de memórias, organizadas nas mais diversas estruturas de dados. Os programas, que são as abstrações que implementam os algoritmos, correspondem a uma sequência de instruções para criar, percorrer e modificar essas estruturas, que ocorre ao ler e modificar os valores armazenados na memória. O modelo de von Neumann consiste na arquitetura de um computador digital que contém os seguintes componentes:

O tipo de memória que utilizamos hoje em dia chamada de memória de acesso arbitrário, ou random-access memory, a RAM. Dizemos que o acesso é arbitrário porque, embora a memória seja uma sequência de células muito grande, podemos acessar cada uma delas diretamente, bastando conhecer o endereço dessa célula. A memória RAM é volátil, que quer dizer que os dados armazenados nela podem ser perdidos sempre que desligamos o computador. Para que possamos armazenar dados permanentemente, normalmente utilizamos algum dispositivo de entrada e saída, como um disco rígido.

Nos computadores modernos, as unidades de processamento e de controle são normalmente integradas em um único módulo chamado unidade de processamento central, ou central processor unit, a CPU. O que liga os diversos componentes em um computador é um conjunto de circuitos e componentes 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 dessa receita — ou as entradas 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 do algoritmo são de seis a oito porções da deliciosa mousseline au chocolat. Aqui está a receita, ou o algoritmo:

Derreta o chocolate com 2 colheres de sopa de água em banho-maria. Quando derretido, misture o açúcar em pó e adicione a manteiga pouco a pouco. Deixe descansar. Bata as gemas até engrossar e ficar com a cor de limão, por cerca de 5 minutos. Dobre delicadamente o 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 de 6 a 8 porções.

A receita acima descreve uma sequência de passos para preparar a mousseline au chocolat. Mas ela só vai adiantar se pudermos seguir essa receita de fato. Para isso, precisamos nos preocupar com diversas propriedade que todos os algoritmos devem ter.

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 a essa pergunta é que o cozinheiro já sabe misturar açúcar com o chocolate derretido, então ele não precisa de detalhes adicionais.

Mas então por que não dizer faça uma mistura de chocolate com açúcar e manteiga? Quando escrevemos um algoritmo, devemos considerar o hardware utilizado. Se o cozinheiro for um chef francês experiente, todo esse algoritmo poderia muito bem ser resumido em uma única instrução: prepare mousseline au chocolat. Mas se o cozinheiro é um aprendiz na cozinha, de nada adiantaria essa receita resumida, porque ela contém instruções que o hardware não sabe executar.

Isso significa que o nível de detalhes de cada instrução deve ser compatível com o “computador” que executará o algoritmo. O conjunto de instruções que o computador realiza diretamente é normalmente chamado de conjunto de instruções elementares. Para dar um outro exemplo, lembre-se do algoritmo que aprendemos na escola para multiplicar 528 por 46. Para multiplicar esses números de dois dígitos, precisamos saber como multiplicar números de um dígito, como 8 vezes 6 e assim por diante. Nesse exemplo, multiplicar dois números de um dígito cada é uma instrução elementar.

Abstração

Embora os computadores só sejam capazes de executar instruções elementares diretamente, que são atividades extremamente simples, os nossos algoritmos irão utilizar instruções nos mais diferentes níveis de detalhes. O cozinheiro aprendiz irá precisar uma receita detalhando todos os passos da receita, mas um chef experiente iria precisar apenas de uma instrução prepare mousseline au chocolat e ainda assim seria capaz de executar todos o passos para preparar essa sobremesa. O que estamos fazendo ao escrever uma instrução como prepare mousseline au chocolat é abstrair uma sequência de instruções elementares. Abstrair significa esconder os detalhes de que não precisamos.

Em computação, abstração pode se referir tanto a um conjunto de instruções que o computador deve realizar, como um conjunto de dados armazenados na memória representando um objeto. Desse jeito, ao invés de escrevermos algoritmos que operaram diretamente sobre os 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.

Algoritmos e execução

É de se esperar que todas as vezes que preparamos mousseline au chocolat vamos levar o mesmo tempo. A razão para isso é que a receita acima tem uma lista fixa de ingredientes, então esse algoritmo sempre executa sobre a mesma entrada. Podemos também escrever algoritmos que recebam entradas diferentes. Por exemplo, suponha que queremos calcular o quanto iremos gastar no supermercado. Para isso, receberemos como entrada uma lista de itens de compra e os preços correspondentes. Podemos escrever o seguinte algoritmo para essa tarefa:

(1) tome nota do número 0;
(2) percorra a lista, somando o preço de cada item ao número anotado;
(3) quando terminar de percorrer a lista, devolva o número anotado.

Primeiro, precisamos verificar que esse algoritmo simples realmente realiza a tarefa solicitada. Para isso, vamos testá-lo com algumas listas. A primeira coisa a observar é que temos um número sendo “memorizado”, ou escrito em um espaço reservado no papel para representar valor subtotal atualmente sendo computado. Esse número começa com zero, mas após considerarmos o item 2 do algoritmo pela primeira vez, ele será o preço do primeiro item da lista. Na segunda vez que executarmos, ele conterá a soma dos dois primeiros preços e assim por diante. Não é difícil se convencer de que, ao terminarmos de executar, esse número terá a soma de todos os preços.

Aqui, podemos parar para fazermos algumas observações. Enquanto o algoritmo é um texto curto e de tamanho fixo definido, a duração do processo que esse texto descreve pode variar dependendo do tamanho da lista de compras. É de se presumir que o tempo para executar esse algoritmo para uma família com seis pessoas irá ser maior do que para uma pessoa que mora só, mas o texto do algoritmo é um só e tem tamanho limitado. Além disso, mesmo que o valor total para uma lista seja muito maior para famílias grandes, para qualquer uma das listas, só precisamos tomar nota de um único número, isso é, a quantidade de utensílios de que esse algoritmo em particular necessita é sempre a mesma.

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. 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.

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 lidos no ano, já que isso não faria sentido. Isso significa que as entradas do nosso problema devem ser especificadas de alguma maneira.

As saídas produzidas por cada algoritmo têm naturezas diferentes. Enquanto as saídas da receita são “porções de mousseline”, a saída do algoritmo para lista de compra é “uma soma dos preços”. Assim, também devemos ter uma especificação das saídas.

Repare 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 — como uma relação formada por

  1. uma caracterização de uma coleção válida, possivelmente infinita, das possíveis entradas do problema,

  2. uma especificação das saídas desejadas como uma 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:

Voltar Próximo →