2.1. Introdução

“Program construction consists of a sequence of refinement steps.”
Niklaus Wirth [88]

2.1.1. Algoritmos

O termo algoritmo é usado na Ciência da Computação para descrever métodos finitos, determinísticos e efetivos, que são adequados à implementação na forma de programas de computador [68]. Para entender melhor essa definição, vamos descrever um algoritmo para computar o máximo divisor comum (MDC) entre dois números inteiros positivos quaisquer:

Computar o MDC entre dois números inteiros positivos, p e q:

- Se q for 0, o resultado será p;

- Caso contrário, obter o resto da divisão r entre p e q.

- O MDC entre q e r será o resultado.

Observe que o algoritmo acima é formado pelo encadeamento de uma série de instruções ou ações, que, se seguidas, nos levarão à solucionar nosso problema: computar o MDC entre dois números inteiros positivos.

Para verificar esse algoritmo, vamos tomar como valores de \(p\) e \(q\), respectivamente, os números \(21\) e \(4\). A Tabela 2.1 mostra o que acontece quando seguimos os passos descritos no algoritmo acima:

Tabela 2.1 - Passos seguidos na execução do algoritmo \(MDC(p,q)\).

Inicialmente, \(p\) vale \(21\) e \(q\) vale \(4\).

Verificamos se o valor de \(q\) é igual a \(0\). Neste caso, como o valor de \(q\) é \(4\), vamos à próxima instrução.

Calculamos o resto da divisão entre \(21\) e \(4\), obtendo o valor \(1\).

Usando nosso algoritmo novamente, temos agora que computar o \(MDC(4,1)\).

Agora, \(p\) vale \(4\) e \(q\) vale \(1\).

Verificamos agora se o valor de \(q\) é igual a \(0\). Neste caso, como o valor de \(q\) é \(1\), vamos à próxima instrução.

Calculando o resto da divisão entre \(4\) e \(1\) obtemos o valor \(0\).

Usando nosso algoritmo novamente, temos agora que computar o \(MDC(1, 0)\).

Agora, na primeira instrução, o valor de \(q\) é \(0\). Neste caso, o resultado é então o valor \(1\).

Dica

Faça os passos acima para os número \(6\) e \(12\).

Podemos representar um algoritmo de diversas formas:

• Pseudocódigo: forma utilizada para descrever um algoritmo que utiliza uma linguagem próxima à natural, com algumas convenções especiais, como estruturas de controle e palavras reservadas para representar comandos e operações. Esta forma é conhecida também como Português Estruturado, Portugol ou Pseudocódigo.

• Diagrama de Blocos: representação gráfica dos fluxos de comandos de um algoritmo.

• Diagrama de Chapin: o diagrama de Chapin ou Nassi-Sneider é outra forma de expressão de algoritmos que utiliza quadros para fornecer uma visão hierárquica e mais estruturada de um algoritmo.

Nota

Atualmente, o aprendizado da programação por meio de pseudocódigo ou diagramas caiu em desuso, em favor do uso direto de linguagens de programação tais como C, C++, Java e Python.

2.1.2. Linguagens de Programação

Todo processador ou família de processadores, possui seu próprio conjunto de instruções e operações. Essas instruções e operações são representadas por padrões de bits que correspondem a diferentes comandos de máquina, como carga de dados nos registradores, adição, subtração, multiplicação ou divisão de valores de dois registradores, ou instruções para transferência do fluxo de execução de um programa. Essas instruções permitem que o computador realize as atividades mais básicas possíveis. A Tabela 2.2 apresenta um exemplo do formato das instruções do microprocessador MIPS (32-bit).

Tabela 2.2 - Exemplo de instrução MIPS.
Fonte: Wikipedia [85].

Tipo	bit
	31							0
R	opcode (6-bits)		rs(5)	rt(5)	rd(5)	shamt (5)	funct (6)
I	opcode (6-bits)		rs(5)	rt(5)	immediate (16)
J	opcode (6-bits)		address (26)

A Tabela 2.3 mostra como seria expressar uma operação que consiste em adicionar o conteúdo dos registradores 1 e 2 e armazenar o resultado no registrador 6.

Tabela 2.3 - Exemplo de operação baseada nas instruções MIPS.
Fonte: Wikipedia [85].

op	rs	rt	rd	shamt	funct
000000	00001	00010	00110	00000	100000

Um programa, ou executável, é formado por um conjunto dessas instruções numa determinada ordem para realizar tarefas. Suponha por exemplo que você esteja colocando para rodar sua IDE de programação favorita. O Sistema Operacional irá copiar os bytes contendo as instruções do seu programa para a memória RAM do seu computador, e a CPU irá começar a executar seu programa a partir da primeira instrução.

Como pode-se perceber, o grande problema com o código de máquina é que ele é bastante inconveniente para a escrita, por seres humanos, até mesmo de pequenos programas. Por conta disso, foram desenvolvidas as linguagens de montagem (assembly), que usam símbolos chamados mnemonic para representar cada instrução ou operação (load, store, jump).

O Trecho de Código 2.2 mostra como seria escrever uma expressão para realizar a soma dos valores 9 e 71.

Trecho de Código 2.2 - Programa em Assembler: \(x = 9 + 71\).
Fonte: Wikibooks [86].

LDA #9  ;loads the number 9 into the accumulator

ADD #71 ;adds the number 71 to the contents of the accumulator = 80

STO 34  ;save the accumulator result to the memory address 34

Nota

O programa responsável por converter o programa escrito na linguagem de montagem para o código de máquina é chamado de montador ou assembler.

Nota

Uma linguagem de montagem contém o mesmo número de instruções que a linguagem de máquina associada, sendo porém mais legível.

Escrever um programa diretamente em linguagem de montagem não é uma tarefa simples, pelo menos nos dias de hoje, onde temos grandes sistemas para construir. Além de ser de difícil compreensão, os processadores possuem um conjunto de instruções bem reduzidos e nossas necessidades ao criar programas são bem maiores. Por conta dessas dificuldades, nos anos 50, foram criadas as linguagens de alto nível para fornecer abstrações de mais alto nível do que as instruções de máquina e mais próximas das linguagens naturais. Portanto, uma linguagem de alto nível é outra forma que temos para escrever nossos programas, como mostrado no Trecho de Código 2.3.

Trecho de Código 2.3 - Algoritmo MDC expresso em C++.
Fonte: Sedgewick e Wayne (2011) [68].

unsigned int MDC(unsigned int p, unsigned int q)
{
    if(q == 0)
        return p;

    unsigned int r = p % q;

    return MDC(q, r);
}

Uma das primeiras linguagens de alto nível, chamada Speedcoding [2], foi desenvolvida por John Backus em 1953. Essa linguagem foi concebida para ajudar no desenvolvimento de software para o computador IBM 701. Ao contrário das linguagens de máquina da época, ela introduzia uma linguagem simbólica com expressividade mais próxima à linguagem natural, além do suporte a aritmética em ponto flutuante. Tratava-se de uma linguagem interpretada (Figura 2.2).

Figura 2.2 - Fluxo de execução de um programa por um interpretador (Python).

Nota

O IBM 701 não possuia hardware para aritmética de ponto flutuante e, portanto, esse suporte era implementado em software.

Nota

As linguagens de alto nível também foram concebidas para evitar que um dado programa tivesse que ser reescrito toda vez que fosse ser executado em um arquitetura diferente.

Somente com o desenvolvimento da Linguagem FORTRAN [3] para o IBM 704 (Figura 2.3), é que as linguagens de alto nível passaram a ganhar ampla aceitação. O IBM 704 introduziu um hardware com capacidade de realização de aritmética em ponto flutuante. FORTRAN possibilitou que os programadores especificassem procedimentos numéricos usando uma linguagem próxima à da matemática, e ainda assim capaz de gerar código de máquina eficiente naquele sistema. Essa foi a maneira encontrada por Backus para reduzir o trabalho com a codificação e atividades de debug.

Figura 2.3 - Computador IBM 704 (1954).
Fonte: Wikipedia [84].

Nota Histórica

O grande problema identificado por Backus na época, e que motivou o desenvolvimento das linguagens de programação de alto nível, era que grande parte dos custos e do tempo para solucionar problemas científicos e de engenharia com a ajuda de grandes computadores, era gasto, respectivamente, com a preparação do problema (2/3 custo) e com a escrita e verificação do programa criado (90% do tempo) [3].

FORTRAN foi criada como uma linguagem compilada. Nas linguagens compiladas, existe um software chamado compilador que é responsável por traduzir o código na linguagem de alto nível em um código em linguagem de máquina que possa então ser executado pelo computador. A Figura 2.4 apresenta o fluxo de compilação para um compilador C++ (GNU g++).

Figura 2.4 - Fluxo de compilação de um programa C++.

Na sequência, vieram as Linguagens ALGOL, acrônimo de ALGOrithmic Language. A primeira versão, ALGOL 58, que inicialmente seria batizada de IAL (International Algorithmic Language), representa um marco histórico por ter sido desenvolvida em conjunto por cientistas americanos e europeus na tentativa de criar uma linguagem padronizada. ALGOL foi utilizada, principalmente, na comunidade científica para especificar os algoritmos apresentados em revistas e jornais, como a ACM.

Essa família de linguagens formalizou diversos recursos disponíveis nas linguagens atuais, entre elas, o uso de estrutura de comandos em blocos, comandos condicionais, laços, procedimentos e funções, formas de passagem de parâmetro (valor, referência, nome), funções aninhadas, escopo léxico. A Figura 2.4 mostra um exemplo de código em ALGOL 60.

Trecho de Código 2.4 - Exemplo de código em ALGOL 60.
Fonte: Wikipedia [83].

procedure Absmax(a) Size:(n, m) Result:(y) Subscripts:(i, k);

    value n, m; array a; integer n, m, i, k; real y;

comment The absolute greatest element of the matrix a, of size n by m,
        is transferred to y, and the subscripts of this element to i and k;

begin
    integer p, q;

    y := 0; i := k := 1;

    for p := 1 step 1 until n do
        for q := 1 step 1 until m do
            if abs(a[p, q]) > y then
                begin
                    y := abs(a[p, q]);
                    i := p; k := q
                end
end Absmax

Por conta da especificação da Linguagem ALGOL 58, Backus criou a notação BNF, refinada mais tarde por Peter Naur durante a especificação de ALGOL 60. ALGOL influenciou o desenvolvimento de diversas outras linguagens, como mostrado na Figura 2.5. Esta figura mostra uma pequena lista das linguagens de programação que já foram criadas.

Figura 2.5 - Genealogia das linguagens de programação.

Nota Histórica

Muitos pesquisadores contribuiram para o desenvolvimento da área de linguagens formais e linguagens de programação. A Figura 2.4 apresenta alguns dos pioneiros dessas duas áreas e que tiveram forte influência em seu estabelecimento.

Tabela 2.4 - Pioneiros da computação com forte influência no desenvolvimento das linguagens de programação.
Fonte: Wikipedia.

2.1.3. A Linguagem de Programação Python

A linguagem Python foi criada originalmente por Guido Van Rossum [81]. Atualmente, seu desenvolvimento é coordenado através de uma fundação chamada Python Software Foundation, sob uma licença de código aberto. Pode ser classificada como uma linguagem de script, orientada a objetos e interpretada. A implementação oficial encontra-se disponível para as plataformas computacionais mais comuns no site https://www.python.org/.

O core desta linguagem, descrito em [32], contém a gramática com as regras sintáticas e semânticas da linguagem, além das abstrações básicas tais como tipos de dados numéricos, sequências, dicionários, estruturas de repetição, comandos de decisão, funções, construtor de novos tipos (class), blocos para tratamento de exceções, entre outras abstrações.

A biblioteca padrão (standard library), descrita em [33], fornece inúmeros tipos de dados e funcionalidades, como tipos para manipulação de data e hora, manipulação de arquivos, comunicação em rede, entre outros.

Python apresenta as seguintes características:

• Possui um sistema de tipos dinâmicos, ou seja, realiza checagem de tipos durante a execução dos programas.

• Gerenciamento automático de memória (garbage collector).

• A linguagem contém um conjunto básico de abstrações bem poderosas: sequências (listas e tuplas), dicionários (hashes), funções e classes.

• Suporta orientação a objetos.

• Possui mecanismo para tratamento de exceções.

• Permite expressar conceitos e computações em poucas linhas de código.

• Oferece uma notação inspirada na linguagem Haskell conhecida como list comprehensions, que é bastante poderosa para criação de objetos como listas e dicionários.

• Possui uma grande quantidade de bibliotecas de código aberto que cobrem um grande espectro de funcionalidades.

• É extensível.

• Suporta diversos paradigmas de programação: estruturado, orientado a objetos, funcional.

Nota

Atualmente, Python é uma das linguagens mais populares. O TIOBE Index fornece um indicador da popularidade das linguagens de programação.