Um computador é portanto uma máquina programável de aplicação genérica. Serve para resolver problemas de muitos tipos diferentes, desde o problema de secretaria mais simples, passando pelo apoio à gestão de empresas, até ao controlo de autómatos e à concretização de sistemas inteligentes. O objectivo desta cadeira é ensinar os princípios da resolução de problemas através dum computador.
Os computadores têm uma arquitectura que, nos seus traços gerais, não parece muito complicada. No essencial, os computadores consistem num processador (o "cérebro") que, para além de dispor de um conjunto de registos ("memória de curta duração"), tem acesso a uma memória ("memória de média duração") e a um conjunto de dispositivos de entrada e saída de dados, entre os quais tipicamente discos rígidos ("memória de longa duração"), um teclado e um ecrã. Esta é uma descrição simplista dum computador. Na cadeira de Arquitectura de Computadores estes assuntos serão estudados com mais profundidade. Na cadeira de Sistemas Operativos estudar-se-ão os programas que normalmente equipam os computadores de modo a simplificar a vida ao seu utilizador.
A linguagem máquina caracteriza-se também por ser penosa para um humano: todas as instruções correspondem a códigos numéricos, difíceis de memorizar, e as instruções são muito elementares. Uma solução parcial passa por atribuir a cada instrução uma dada mnemónica. Às linguagens assim definidas chama-se linguagens assembly e aos tradutores de assembly para linguagem máquina assemblers ou assembladores. Soluções mais sofisticadas passam por equipar os computadores com compiladores, isto é com programas que são capazes de traduzir para linguagem máquina programas escritos em linguagens menos penosas para o programador e mais poderosas que o assembly. Infelizmente, não existem ainda compiladores para as linguagens naturais, que é o nome que se dá às linguagens humanas (e.g., português, inglês, etc.). Mas existem as chamadas linguagens de programação de alto nível (alto nível entre as linguagens de programação, bem entendido), que nos simplificam muito a vida como programadores. Nesta cadeira usar-se-á o C++ como linguagem de programação *.
Tal como o conhecimento profundo do português não chega para fazer um bom escritor, o conhecimento profundo duma linguagem de programação não chega para fazer um bom programador. O conhecimento da linguagem é necessário, mas não é de todo suficiente. Programar não é o simples acto de escrever ideias de outrem: é ter essas ideias, é ser criativo. Resolver problemas exige conhecimentos da linguagem, conhecimento das técnicas conhecidas de ataque aos problemas, inteligência para fazer analogias com outros problemas, mesmo em áreas totalmente desconexas, criatividade, intuição, persistência, etc. Programar não é um acto mecânico. Assim, aprender a programar consegue-se através do estudo e, fundamentalmente, do treino.
* Pode-se pensar num computador equipado com um compilador duma dada linguagem de programação como um novo computador, mais poderoso. É de toda a conveniência usar este tipo de abstração, que de resto será muito útil para perceber sistemas operativos, onde se vão acrescentando camada após camada de software para acrescentar "inteligência" aos computadores.
Mas a definição de algoritmo é um pouco mais completa. De acordo com Knuth [1] os algoritmos têm cinco características importantes:
Para além destas características dos algoritmos, pode-se também falar da sua eficiência, isto é, do tempo que demoram a ser executados para dadas entradas. Em geral, portanto, pretende-se que os algoritmos sejam não só finitos mas também "muito finitos" [1]. Significa isto que normalmente, e para a pior combinação possível das entradas, devem resolver o problema enquanto ainda somos vivos para estarmos interessados na sua resolução.
O estudo dos algoritmos, a algoritmia (algorithmics) é um campo muito importante da ciência da computação, que envolve por exemplo o estudo da sua correcção (verificação se de facto resolvem o problema), da sua finitude (será de facto um algoritmo, ou não passa dum "método computacional" [1] inútil na prática?) e da sua eficiência (análise de algoritmos). Estes temas serão inevitavelmente abordados nesta cadeira, embora informalmente, e serão fundamentados teoricamente na cadeira de Computação e Algoritmia. A cadeira Introdução à Programação (Programação I em IGE) serve portanto de ponte entre as cadeiras de Arquitectura de Computadores e Computação e Algoritmia, fornecendo os conhecimentos necessários para todo o trabalho subsequente em cadeiras de informática.
Seja o problema de, dados quaisquer dois inteiros positivos m e n, calcular os seu máximo divisor comum mdc(m, n).
A abordagem deste problema passa em primeiro lugar pela identificação da chamada pré-condição (PC), i.e., pelas condições que se verificam garantidamente à priori. Neste caso a pré-condição é PC: m, e n são inteiros positivos. Depois, deve-se formalizar a condição objectivo (CO). Neste caso a CO é: k = mdc(m, n). Assim, o objectivo é encontrar k que verifique a CO.
Para que o problema faça sentido, é necessário que, quaisquer que sejam m e n tais que a PC é verdadeira, exista pelo menos um inteiro positivo k tal que a CO é verdadeira. Para que a solução do problema não seja ambígua, é necessário restringir esta formulação para: quaisquer que sejam m e n tais que a PC é verdadeira, existe um e um só inteiro positivo k tal que a CO é verdadeira. Quando isto se verifica, pode-se dizer que o problema está bem colocado. É fácil verificar que, neste caso, o problema está bem colocado (note-se que a demonstração de que um problema está bem colocado muitas vezes se faz desenvolvendo um algoritmo: são as chamadas demonstrações construtivas).
Depois de se verificar que de facto o problema está bem colocado dadas a PC e a CO, é de todo o interesse identificar propriedades interessantes do mdc. Duas propriedades simples são:
a) Quaisquer que sejam m e n inteiros positivos,
mdc(m, n) >= 1.
b) Quaisquer que sejam m e n inteiros positivos,
mdc(m, n) <= min(m, n), em que min(m,
n)
é o menor dos dois valores m e n.
A veracidade destas duas propriedades é evidente, pelo que não se demonstra aqui.
Seja m % k uma notação que significa "o resto da divisão (inteira) de m por k", e seja <> o símbolo para a desigualdade. Duas outras propriedades que se verificará serem importantes são:
c) Quaisquer que sejam k, m e n inteiros
positivos, k >= mdc(m, n) e (m % k
=
0 e n % k = 0 [ou seja, k é divisor
comum a m e n]) => k = mdc(m, n), em
que e significa a conjunção. A demonstração
pode ser feita por absurdo. Suponhamos que k não é
o máximo divisor comum de m e n. Como k
é divisor comum, então conclui-se que mdc(m, n)
> k, isto é, há divisores comuns maiores que k.
Mas então mdc(m, n) > k >= mdc(m, n),
que é uma falsidade! Logo, k = mdc(m, n).
d) Quaisquer que sejam k, m e n inteiros
positivos, k >= mdc(m, n) e (m % k
<> 0 ou m % k <> 0 [ou seja, k não
é divisor comum a m e n]) => k > mdc(m,
n),
sendo neste caso a demonstração trivial.
Em que é que estas propriedades nos ajudam? Em primeiro lugar, a) e b) restringem a zona onde o mdc deve ser procurado, o que é obviamente útil. As propriedades c) e d) serão úteis mais tarde.
Não há nenhum método mágico de resolver problemas. Mais tarde ver-se-á que existem metodologias que simplificam a abordagem ao desenvolvimento de algoritmos, nomeadamente envolvendo iterações (repetições). Mesmo essas metodologias não são substituto para a intuição e a inteligência: é necessário ter intuição. Para já, usar-se-á apenas a intuição. Onde se deve procurar o mdc? A intuição diz que a procura deve ser feita a partir de min(m, n), pois de outra forma, começando por 1, é fácil descobrir divisores comuns, mas não é evidente se eles são ou não o máximo divisor comum: seria necessário testar todos os outros potenciais divisores até min(m, n). Então, duma forma informal, deve-se ir procurando divisores comuns partindo de min(m, n) para baixo até se encontrar algum, que será forçosamente o mdc.
Como transformar estas ideias num algoritmo e, simultaneamente, demonstrar a sua correcção? Seja k uma variável inteira (i.e., uma "folha de papel" onde se pode escrever valores inteiros) que guarda os candidatos a divisores comuns. Então, se se quiser começar pelo topo, deve-se atribuir a k o menor dos valores m e n:
se m < n então:em que "k <- n" significa "atribua-se o valor de n à variável k" (ou "apague-se a folha de papel k e escreva-se lá o valor de n".
k <- m
senão:
k <- n
Depois destas instruções, é evidente que se pode afirmar que k >= mdc(m, n), dada a propriedade b).
Em seguida, deve-se verificar se k divide m e n e, no caso contrário, passar ao próximo candidato:
enquando m % k <> 0 ou n % k <> 0 faça-se:A condição que controla o ciclo (chama-se ciclo porque é uma instrução que implica a repetição cíclica de outra: k <- k - 1) chama-se guarda (G). Neste caso temos G: m % k <> 0 ou n % k <> 0. A instrução k <- k - 1 chama-se o " progresso" do ciclo.
k <- k - 1
Quando este ciclo terminar, k é o mdc. Como demonstrá-lo? Repare-se que, dadas as propriedades c) e d), quer a inicialização de k quer a guarda e progresso garantem que há uma condição que se mantém sempre válida, desde o início ao fim do ciclo: a chamada condição invariante (CI). Neste caso CI: k >= mdc(m, n). A demonstração da correcção do algoritmo passa pois por demonstrar que CI é sempre verdadeira e que quando o ciclo termina (i.e., G é falsa) temos forçosamente CO verdadeira, i.e., CI e ~ G => CO, onde ~ representa a negação.
Assim, dada a inicialização
se m < n então:tem-se que k = min(m, n), o que, conjugado com a PC, nos garante que k >= mdc(m, n). Durante o ciclo, que acontece se a G for verdadeira? Diminui-se k de uma unidade, isto é progride-se. Mas, admitindo que a CI é verdadeira e sendo G também verdadeira, conclui-se pela propriedade d) que k > mdc(m, n). Mas, como k é um valor inteiro, isso é o mesmo que dizer que k - 1 >= mdc(m, n), donde, depois do progresso, CI continua verdadeira. No fundo, demonstrou-se por indução que CI se verifica do início ao final do ciclo. E, como CI e ~ G => CO, k termina de facto com o máximo divisor comum de m e n, quaisquer que sejam os seus valores, desde que inteiros e positivos.
k <- m
senão:
k <- n
Assim, o algoritmo completo é:
{PC: m e n são inteiros positivos.}em que texto entre {} são comentários, não fazendo parte do algoritmo.
se m < n então
k <- m
senão
k <- n
{k = min(m, n) >= mdc(m, n), ou seja, a CI é verdadeira.}enquando m % k <> 0 ou n % k <> 0 faça-se:
{Aqui a G é verdadeira. Logo, pela propriedade d), a CI mantém-se verdadeira
depois do seguinte progresso:}
k <- k - 1{Aqui a G é falsa. Logo, pela propriedade c), k = mdc(m, n), ou seja a CO é verdadeira.}
Uma questão importante que ficou por demonstrar é se é garantido que o ciclo termina sempre. Mas essa demonstração é simples. Em primeiro lugar, a inicialização garante que o valor inicial de k é >= 1 (pois m e n são inteiros positivos). O progresso, por outro lado, faz o valor de k diminuir. Como 1 é divisor comum de qualquer par de inteiros positivos, o ciclo, na pior das hipóteses, termina com k = 1 ao fim de no máximo min(m, n) - 1 repetições. Logo, é de facto um algoritmo, pois verifica a condição de finitude.
Resumindo, o conjunto de instruções que se apresentou é um algoritmo porque:
// Este programa calcula o máximo divisor comum de dois números.
#include <iostream>
using namespace std;
int main(void)
{
cout << "Cálculo do máximo divisor comum de dois números." << endl;
cout << "Introduza dois inteiros positivos: ";
int m, n;
cin >> m >> n;
// Assume-se que m e n são positivos!
// Como um divisor é sempre menor ou igual a um número, escolhe-se
// o mínimo dos dois!
int k;
if(n > m)
k = m;
else
k = n;
// Neste momento sabe-se que k >= mdc(m, n). */
while(m % k != 0 || n % k != 0) {
// Se o ciclo não parou, então k não divide m e n, logo,
// k != mdc(m, n) e k >= mdc(m, n). Ou seja, k > mdc(m, n).
k--;
// Progresso. Afinal, o algoritmo tem de terminar...
// Neste momento, k >= mdc(m, n) outra vez! É o invariante do
// ciclo!
}
// Como k >= mdc(m, n) (invariante do ciclo) e k divide m e n
// (o ciclo terminou, não foi?), conclui-se que k = mdc(m, n)!
cout << "O máximo divisor comum de " << m << " e " << n << " é "
<< k << endl;
}
* Estes erros assemelham-se ao "não" introduzido (acidentalmente?) pelo revisor de provas em "História do cerco de Lisboa", de José Saramago.
1.b) Compile e execute o programa.
1.c) Corra o programa linha a linha em modo de depuração (debug), observando atentamente a evolução do valor das variáveis.
1.d) Experimente fazer as seguintes alterações: