Introdução a Algoritmos e Programação

Algoritmos fazem parte do nosso dia-a-dia, muitas vezes de formas que não esperamos. Criar uma definição informal de algoritmos é uma tarefa razoavelmente simples, e esta noção informal do que é um algortimo é de fácil entendimento. No entanto, uma definição formal de algoritmo, que corresponda a noção intuitiva do que é um algoritmo, continua sendo um problema em aberto.

Intuitivamente, definimos um algoritmo de forma que

Um algoritmo é uma seqüência finita de passos, que quando executados, na mesma ordem, sobre os mesmos elementos, resultará no mesmo resultado, sempre.

Utilizando uma linguagem formal, um algoritmo pode ser representado por um conjunto de instruções que executam a partir de um estado inicial, e um conjunto de dados iniciais. As instruções indicam computações, que quando executadas, alteram entre um conjunto de estados finitos e sucessivos, eventualmente, gerando um resultado.

Nesta forma mais livre de algoritmo, podemos pensar em várias situações onde seguimos instruções a partir de um mesmo conjunto inicial, para realizar uma tarefa. Por exemplo, na confecção de um bolo (Algoritmo 1).

Confecção de um bolo.

bolo (ingredientes):
    misture os ingredientes
    unte o tabuleiro com manteiga
    despeje a mistura no tabuleiro
    se há queijo parmesão,
        então espalhe sobre a mistura
    leve o tabuleiro ao forno
    enquanto não corar,
        deixe o tabuleiro no forno
    deixe esfriar
    experimente antes de servir

Para obter o resultado esperado na criação do bolo, é necessário seguir a receita exatamente como esta se apresenta, pois qualquer desvio irá criar um bolo diferente do esperado, e, em muitos casos, obter um resultado, não apenas diferente, mas errado.

Algoritmos computacionais

Quando falamos de algoritmos aplicados ao desenvolvimento de sistemas, podemos defini-los, informalmente, como sendo "um procedimento computacional, bem definido, que recebe um conjunto de valores de entrada, e produz um conjunto de valores de saída. Um algoritmo é, portanto, uma seqüência de passos computacionais que transforma uma entrada de dados, nos dados de saída.

Algoritmos são aplicados na solução de problemas (neste caso, problemas computacionais), e o enunciado do problema especifica, em termos gerais, a relação desejada entre os dados de entrada e saída. A partir desta definição do problema, é que obtemos quais são os dados que serão utilizados como entrada do sistema, e qual o resultado esperado. O algoritmo desenvolvindo, descreverá os passos necessários para transformar os dados de entrada na resposta correta.

Computadores

Um computador pode ser visto, de maneira simplificada como sendo uma máquina que segue a arquitetura de Von Neumann (Figura 1), onde dados e instruções são armazenados na memória, possui uma unidade central de processamento (CPU, do inglês Central Processing Unit) composta de uma unidade de controle e uma unidade lógica aritmética (ALU, do inglês Arithmetic/Logic Unit), e dispositivos de entrada e saída de dados.

Arquitetura de Von Neumann. Arquitetura de Von Neumann

Numa máquina com a arquitetura de Von Neumann, uma instrução deve ser carregada da memória para para a CPU, dependendo do formato da instrução, os dados no qual ela irá operar também são carregados da mesma memória para registradores da CPU. O resultado da instrução é então gravado em um registrador ou na memória.

Os programas e dados são carregados a partir do dispositivo de entrada, para a memória, a partir de onde a CPU obtém instruções e dados que serão processados pela unidade de controle e pela ALU, e os resultados finais são enviados para o dispositivo de saída.

Computadores possuem um conjunto finito de instruções que podem ser executadas (definidas pela unidade de controle e pela ALU), e são muito eficientes em executar tarefas repetidas vezes. A mesma tarefa pode apresentar resultados diferentes, caso a entrada de dados seja diferente.

A estrutura dos computadores limita ou orienta a forma como os algoritmos são criados, principalmente, porque, muitas vezes, o problema a ser solucionado é uma forma de contornar alguma limitação dos computadores (por exemplo, comprimir os dados para poder armazerar mais elementos no mesmo espaço disponível).

Programas

Um programa de computador é uma coleção de instruções organizadas de forma que podem ser processadas por um computador. Estas instruções devem ser reconhecidas pela CPU que irá processar o programa.

Os programas de computador são implementações de algoritmos escritos de forma que uma CPU seja capaz de processá-los. Dada uma entrada para este programa, obteremos uma resposta, de acordo com o algoritmo implementado.

Toda CPU tem um conjunto limitado de instruções que é capaz de executar, e CPUs diferentes, apresentam conjuntos de instruções diferentes, e portanto, um programa com instruções para uma CPU específica não pode ser executado em uma CPU diferente.

As instruções executadas por uma CPU é conhecida como linguagem de máquina, e é possível escrever um programa utilizando esta linguagem. No entanto, este programa depende tanto da CPU para a qual foi escrito, que não poderá ser executado em outra, a não ser que seja completamente reescrito.

Uma forma de melhorar esse comportamento é utilizar uma lingagem de programação, e escrever o algoritmo utilizado as construções oferecidas por essa linguagem. Esse código fonte pode ser então transformado em código de máquina para uma CPU específica. Desta forma, o programa não precisa ser reescrito, bastando que o mesmo programa seja transformado no código de máquina de outra CPU.

Linguagens de Programação

Uma linguagem de programação é uma linguagem formal que especifica um conjunto de instruções utilizados para imlpementar algoritmos como programas de computador. Milhares de linguagens de programação já foram desenvolvidas para os mais diversos fins, e com diversas características diferentes.

Algumas linguagens de programação são muito parecidas com a forma como as CPUs interpretam os comandos, estas linguagens são conhecidas como linguagens de baixo nível, e apresentam como principais características construções próximas ao hardware, execução muito eficiente, dificuldade de manutenção (normalmente devido à quantidade de código necessária, mesmo para tarefas simples), e a dificuldade de utilizar o mesmo programa em máquinas diferentes.

Linguagens de alto nível são linguagens cujas construções estão mais próximas da forma que lidamos ou especificamos os problemas, normalmente apresentando uma forma de abstração com relação ao hardware que irá executar os programas. Desta forma, estas linguagens apresentam maior portabilidade e facilidade de manutenção dos programas, no entanto, em alguns casos, a execução não é tão eficiente quanto linguagens de baixo nível.

A forma como se escreve um programa em uma linguagem de programação varia entre linguagens diferentes, porém, muitas linguagens apresentam características semelhantes, e algumas dessas características podem ser agrupadas defifnindo diferentes paradigmas de linguagens de programação.

Compilação vs. Interpretação

Uma linguagem de programação possui um conjunto de instruções, normalmente, próximos da linguagem humana, ao contrário das instruções de uma CPU (linguagem de máquina), que lida apenas com bits e bytes. Isto ocorre, porque cada uma das linguagens tem um foco diferente, as linguagens de programação são focadas em facilitar a programação de computadores, logo devem ser de fácil entendimento para os programadores. Já a linguagem de máquina, tem como objetivo a execução eficiente por uma CPU, logo não precisa ser necessariamente fácil de entender.

Para que seja possível executar um programa escrito em uma linguagem de programação, é preciso transformar o código fonte em código de máquina, e esse processo pode ser realizado em dois momentos, antes ou durante o processo de execução do programa.

Linguagens de Programação Interpretadas transformam o código fonte em código de máquina no momento da execução do programa. Entre as principais vantagens desse tipo de linguagem de programação estão a independência de plataforma (basta existir um interpretador para a CPU alvo que o programa poderá ser executado), e a rapidez com que se pode testar modificações (basta alterar o código fonte e reiniciar a execução). A principal desvantagem das linguagens interpretadas é a perda de eficiência na execução, se comparada com códigos em linguagem de máquina, pois é preciso, na medida que o código fonte é lido, verificar se o código está correto, convertê-lo em código de máquina, e repassá-lo para a CPU executar o código convertido.

Linguagens como BASIC e Logo utilizavam interpretadores. Muitas linguagens modernas também são linguagens interpretadas, como JavaScript, Python e Ruby.

Linguagens de Programação Compiladas utilizam compiladores para transformar o código fonte em código de máquina. Esta transformação é realizada por um programa, conhecido como compilador. O compilador é um programa que interpreta o código fonte e cria um arquivo objeto, que contém o código de máquina para uma CPU específica. As principais vantagens são a facilidade em criar compiladores de uma mesma linguagem para CPUs diferentes, e a eficiência de execução do código gerado, uma vez que este código não precisará ser interpretado antes de ser executado pela CPU. A principal desvantagem é a adição de um passo extra para executar o programa, o processo de compilação (desnecessário quando a linguagem é interpretada).

Diversas linguagens utilizam o processo de compilação como C, C++, Fortran, e Java.

Nos dias de hoje, tem sido muito comum a utilização de linguagens que compilam o código fonte em um código intermediário (muitas vezes chamado de bytecode), e este bytecode é então interpretado por uma máquina virtual. Este processo auxilia na geração mais simples do código executável, e acelera o processo de interpretação do programa final, uma vez que o bytecode é mais simples de converter em código de máquina que o código fonte de alto nível.

Linguagens compiladas ou interpretadas podem utilizar bytecodes, entre os exemplos atuais mais conhecidos, temos as linguagens Java e Python, que, de forma e em momentos diferentes, geram um bytecode que é então interpretado pela máquina virtual responsável pela execução do programa.

Paradigmas de Programação

Os paradigmas de programação são uma forma de classificar linguagens de programação baseado em suas principais características. Embora seja normal atribuir um único paradigma a cada linguagem de programação, a maioria das linguagens oferecem mais de um paradigma.

Os principais paradigmas utilizados em linguagens de programação são:

  • Imperativo
    Permite efeitos secundários para cada instrução, e cada instrução é um comando que altera o estado do sistema.
  • Estruturado
    Derivado do paradigma imperativo, utiliza estruturas, procedimentos e funções, agrupando o código em blocos estruturados de código.
  • Orientação a Objetos
    Agrupa no mesmo módulo estado e o código que acessa este estado.
  • Funcional
    Não permite efeitos secundários. É baseada na idéia de funções e na composição de funções.
  • Declarativo
    Não garante a ordem em que as operações serão executadas. São definidos objetivos a serem atingidos, e não a forma como se deve chegar nesse objetivo.
  • Lógico
    Possui um modelo de execução acoplado a um estilo particular de sintaxe e gramática. Derivado de sistemas de prova de teoremas.

Programação Imperativa

Na programação imperativa, são utilizados comandos que alteram o estado do programa. Estes comandos instruem as ações que o computador deve tomar para chegar a um resultado. Na programação imperativa, o foco é em descrever como um programa funciona, e uma vez que as instruções estejam corretas, eventualmente, o programa terminará com uma resposta.

A implementação do hardware, da maioria dos computadores, funciona de forma imperativa, onde o estado do sistema pode ser alterado por meio de comandos, seja o conteúdo da memória, ou os dados enviados a periféricos.

A programação imperativa é a base da maioria das linguagens de programação que utilizam os paradigmas estruturado e orientado a objetos, sendo assim, um dos modelos de programação mais utilizados.

Programação Estruturada

A programação estruturada é um paradigma de programação que visa melhorar a claridade e qualidade do código, fazendo uso extensivo de estruturas de controle como estruturas de repetição, decisão, e sub-rotinas.

É usual a existência de blocos de código nas linguagens que suportam esse paradigma. Com o uso destes blocos e sub-rotinas, novos comandos podem ser criados, e a linguagem extendida.

Programação Orientada a Objetos

O paradigma de programação orientada a objetos é baseado no conceito de objetos que podem conter estado (dados) e comportamento sobre esses dados, em um módulo encapsulado que provê um serviço para o sistema do qual faz parte.

Os principais elementos de uma linguagem orientada a objetos é a capacidade de encapsulamento dos objetos em unidades inpedenpendetes, que possuem a noção de identidade (às vezes utilizando palavras reservadas da liguagem como this ou self), composição de objetos, herança e polimorfismo.

Diversas linguagens apresentam o conceito de classes, e nesses casos, os objetos são vistos como instâncias dessas classes, as quais determinam o tipo de dado dos objetos.

Programação Declarativa

A programação declarativa está focada em definir o que um programa deve fazer, ao invés de como deve fazer algo. Neste paradigma de programação, programas são normalmente escritos em um sistema de lógica formal, e a computação é realizada como deduções neste sistema de lógica, não sendo utilizados os comandos com efeitos colaterais da programação imperativa.

Alguns sistemas bastante conhecidos de programação declarativa incluem sistemas de bancos de dados (SQL e XQuery), Dataflow (Excel), expressões regulares, programação lógica e programação funcional.

Programação Funcional

A programação funcional é um paradigma de programação que trata a computação como a avaliação matemática de funcões e evita a mudança de estado e dados que alterem seus valores. É um modelo declarativo de programação, que utiliza expressões e declarações, ao invés de comandos. Como não existem efeitos colaterais, sempre que uma função for invocada com os mesmos argumentos, irá produzir o mesmo resultado, ao contrário da programação imperativa, que pode armazenar estados locais e globais, produzindo resultados diferentes a cada execução.

Entre as principais liguagens funcionais, encontramos os diversos dialetos de LISP, Haskell, ML e R.

Diversas linguagens imperativas, hoje em dia, incluem elementos funcionais, como Python e Ruby, e até mesmo Java e C++ com os lambdas.

Programação em Lógica

A programação lógio é um paradigma de programação baseado na lógica formal. Todo programa é escrito coom um conjunto de senteças lógicas que expressam fatos ou regras sobre um domínio de problema. Na maioria das linguagens lógicas, as regras são escritas em forma de cláusulas e lidas como implicações lógicas.

Provavelmente a linguagem que segue o paradigma lógico mais conhecida é a linguagem Prolog, ainda utilizada em sistemas de processamento de linguagem natural.