Algoritmos e Programação - teoria e prática

Algoritmos e Programação - teoria e prática

(Parte 1 de 3)

Algoritmos e Programação Teoria e Prática

Marco Medina Cristina Fertig

Novatec Editora

Capítulo 1 Introdução

Neste capítulo, faremos uma introdução geral sobre algoritmos, suas aplicações e alguns exemplos reais. Mostraremos as diferenças entre algoritmo e programa e também explicaremos o que são compiladores e montadores. Em seguida, descreveremos algumas formas populares de estruturação de algoritmos e apresentaremos a notação que adotaremos.

1.1 Conceituação

Muitas definições podem ser dadas à palavra algoritmo. Atualmente, tem-se associado algoritmo à computação, mas este não é um termo restrito à computação ou que tenha nascido com ela. Na realidade, a palavra algoritmo vem do nome do matemático iraniano Abu Abdullah Mohammad Ibn Musa al-Khawarizmi, nascido em Khawarizm (Kheva), ao sul do mar Aral, que viveu no século XVII. A influência de Khawarizmi no crescimento da ciência em geral, particularmente na matemática, astronomia e geografia, é bastante reconhecida. Também é considerado o fundador da álgebra, cujo nome derivou de seu livro Al-Jabr wa-al-Muqabilah. Mais informações a respeito de al-Khawarizmi podem ser encontradas na bibliografia (apêndice B).

O termo algoritmo também é utilizado em outras áreas, como engenharia, administração, entre outras. Vejamos algumas definições de algoritmo:

• Um procedimento passo a passo para a solução de um problema.

• Uma seqüência detalhada de ações a serem executadas para realizar alguma tarefa.

Assim, as ações que são necessárias para se fazer um balancete, por exemplo, constituem um algoritmo. Outro exemplo clássico de algoritmo é a receita culinária. Veja o exemplo a seguir de um bolo de chocolate:

• Ingredientes

• 4 xícaras (chá) de farinha de trigo.

14Algoritmos e Programação

• 2 xícaras (chá) de açúcar cristal. • 2 xícaras (chá) de achocolatado.

• 2 colheres (sopa) de fermento em pó.

• 2 xícaras (chá) de água morna.

• 1 xícara (chá) de óleo.

• Farinha de trigo para polvilhar.

• Modo de preparo

• Numa vasilha, misture 4 xícaras (chá) de farinha de trigo, 2 xícaras (chá) de açúcar cristal, 2 xícaras (chá) de achocolatado, 2 colheres (sopa) de fermento em pó e 1 pitada de sal. Junte 3 ovos, 2 xícaras (chá) de água morna e 1 xícara (chá) de óleo. Misture bem. Unte uma forma retangular de 25 cm x 37 cm com óleo e polvilhe farinha de trigo e despeje a massa. Asse em temperatura média (de 170°C a 180°C) por 30 minutos.

• A receita tem todas as características de um algoritmo. Ela tem uma seqüência detalhada de passos, descrita no modo de preparo. Apresenta a tarefa a ser realizada, que no caso é o bolo de chocolate. Além disto, podemos identificar na receita entradas (no caso os ingredientes) e uma saída, que é o próprio bolo.

• Poderíamos, então, nos perguntar por que a palavra algoritmo ficou tão associada à computação? Para compreendermos melhor os motivos, é preciso entender, mesmo que superficialmente, o funcionamento dos computadores.

1.2 Programas de computador

Nesta seção, veremos o processo necessário para se criar um programa e executá-lo. Primeiramente introduziremos os principais conceitos para a melhor compreensão de como um programa é visto pelo computador. Depois nos aprofundaremos nos detalhes de como um programa é transformado em um código que pode ser executado pelo computador.

1.2.1 O que é um programa

Os computadores das mais variadas arquiteturas têm funcionamento similar. A figura 1.1 apresenta a arquitetura simplificada de um computador.

15Capítulo 1 • Introdução

UCP – Unidade

Central deProcessamento Memória

Dispositivos Entrada/Saída

Teclado Mouse Monitor Impressora etc.

Conexões externas

Barramento

A parte física do computador é chamada de hardware, que é formado basicamente por uma Unidade Central de Processamento (UCP), pela memória e pelos dispositivos de entrada e saída. O barramento faz a ligação desses componentes.

A UCP (ou processador) contém um conjunto relativamente pequeno de instruções que é capaz de executar. Cada processador contém um conjunto diferente de instruções, apesar de similares entre si. As instruções que o processador executa são buscadas da memória. Essas instruções podem ser desde operações matemáticas a interações com os dispositivos de entrada e saída. Chamamos de programa de computador um conjunto de instruções que será executado pelo processador em uma determinada seqüência. Esse programa leva o computador a executar alguma tarefa.

Como podemos perceber, um programa nada mais é que um tipo de algoritmo. Sua particularidade é que suas operações são específicas para o computador e restritas ao conjunto de instruções que o processador pode executar. Podemos considerar esse conjunto de instruções como a primeira linguagem de programação do computador, também chamada de linguagem de máquina. Classificamos as linguagens de programação segundo a sua proximidade com a linguagem de máquina. Quanto maior a semelhança com a linguagem de máquina, mais baixo é o nível da linguagem. As linguagens de programação mais semelhantes à linguagem de máquina são conhecidas como linguagens de baixo nível. Analogamente, linguagens de programação “distantes” da linguagem de máquina são conhecidas como linguagens de programação de alto nível. Linguagens de programação de alto nível são mais próximas da linguagem natural e guardam pouca similariedade com a linguagem da máquina em que serão executadas.

A linguagem de programação que um computador é capaz de compreender é composta apenas de números. Assim, fazer algoritmos na linguagem de programação do computador ou em sua linguagem de máquina é um processo extremamente complicado para nós, seres humanos, acostumados com a nossa própria linguagem. Por isso, para facilitar a programação de computadores, foi necessária a criação de um código que relacionasse a linguagem de máquina a uma linguagem mais fácil de ser compreendida. A linguagem de montagem (ou assembly) é um código que tem uma instrução alfanumérica (ou mnemônica) para cada instrução numérica em linguagem de máquina.

16Algoritmos e Programação

Para que um programa escrito em linguagem de montagem possa ser executado pelo computador, é necessário que seu código seja traduzido para o código de máquina. Isto é feito por meio de um programa chamado assembler. A figura 1.2 apresenta o esquema de tradução feita por um assembler.

Código em linguagem de montagem

Código em

linguagemde máquina Assembler

Figura 1.2 – Tradução para a linguagem de máquina.

A linguagem de montagem é muito próxima da linguagem de máquina e, por isso, é uma linguagem de programação de baixo nível. Para cada processador, há uma linguagem de montagem já que há uma relação direta entre as instruções em linguagem de montagem e em linguagem de máquina. Isto faz com que o código tenha que ser refeito se quisermos executar um programa em um processador não compatível com o qual ele foi escrito inicialmente. Neste caso, dizemos que o código não é portável.

A implementação de programas nesse tipo de linguagem ainda é muito complexa e dependente do conhecimento das instruções do processador. Para aumentar a produtividade dos programadores e a portabilidade dos programas, foram criadas as linguagens de programação de alto nível. Essas linguagens são independentes do processador em que serão executadas. Suas características principais são que seu código é mais elaborado, contemplando operações mais complexas e mais próximas da “lógica humana”. Para que possam ser processadas por um computador, os comandos da linguagem precisarão ser traduzidos para a linguagem de máquina. Essa tradução é feita por meio de um compilador ou de um interpretador, dependendo do caso, como veremos a seguir.

1.2.2 Executando um programa

O compilador, a partir do código em linguagem de alto nível, chamado de código-fonte, gera um arquivo com o código em linguagem de máquina, conhecido como códigoobjeto. Esse código-objeto fica em disco e só é carregado em memória no momento da execução. O interpretador faz o mesmo trabalho, porém não gera o arquivo em código-objeto. As instruções são traduzidas para linguagem de máquina em tempo de execução, instrução a instrução. A figura 1.3 mostra os passos para a execução de um código em linguagem de alto nível por meio da compilação. A figura 1.4 apresenta o esquema similar para a interpretação.

Código-fonte em linguagem de alto nível

Código em

(Parte 1 de 3)

Comentários