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 à construção de sistemas inteligentes. O objectivo desta disciplina é 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 disciplina de Arquitectura de Computadores os vários componentes de um computador serão estudados com mais profundidade. Na disciplina de Sistemas Operativos, por outro lado, estudar-se-ão os programas que normalmente equipam os computadores de modo a simplificar a sua utilização.
A linguagem máquina caracteriza-se também por ser penosa de utilizar para os humanos: 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, ou seja, substituir os números que representam cada operação por nomes mais fáceis de decorar. Às linguagens assim definidas chama-se linguagens assembly e aos tradutores de assembly para linguagem máquina assemblers ou assembladores.
Uma solução preferível passa por equipar os computadores com compiladores, isto é com programas que são capazes de traduzir para linguagem máquina programas escritos em linguagens mais fáceis de usar pelo 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 se aproximam um pouco mais das linguagens naturais na sua facilidade de utilização pelos humanos, sem no entanto introduzirem as imprecisões, ambiguidades e dependências de contextos externos que são características das linguagens naturais. Nesta disciplina 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, longe disso. 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 e engenhoso. 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, engenho, 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 abstracçã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.
A noção de algoritmo não é simples de perceber, pois é uma abstracção. Algoritmos são métodos de resolver problemas. Mas à concretização dum algoritmo numa dada linguagem já não se chama algoritmo: chama-se programa. Sob esse ponto de vista, todas as versões escritas dum algoritmo são programas, mesmo que expressos numa linguagem natural, desde que não façam uso da sua característica ambiguidade. Abusando um pouco das definições, no entanto, chamaremos algoritmo a um método de resolução de um dado problema expresso em linguagem natural, e programa à concretização de um algoritmo numa dada linguagem de programação.
A definição de algoritmo é um pouco mais completa do que a apresentada. 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 suficientemente rápidos [1]. Ou seja, devem resolver o problema em tempo útil (e.g., enquanto ainda somos vivos para estarmos interessados na sua resolução) mesmo para a mais desfavorável combinação possível das entradas.
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 disciplina, embora informalmente, e serão fundamentados teoricamente na disciplina de Computação e Algoritmia. A disciplina de Introdução à Programação serve portanto de ponte entre as disciplinas de Arquitectura de Computadores e Computação e Algoritmia, fornecendo os conhecimentos necessários para todo o trabalho subsequente noutras disciplinas da área da 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 condição objectivo é
CO é: k = mdc(m, n).Assim, neste caso o objectivo do problema é encontrar um 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. No problema em causa não há quaisquer dúvidas: todos os pares de inteiros positivos têm um máximo divisor comum.
Para que a solução do problema não seja ambígua, é necessário garantir mais. Não basta que exista solução, é necessário que seja única: 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 (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). É fácil verificar que, neste caso, o problema está bem colocado: existe apenas um mdc de cada para de inteiros positivos.
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, de acordo com o Apêndice
A. 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) implica k = mdc(m, n),em que e significa a conjunção. Ou seja, se k é superior ou igual ao máximo divisor comum de m e n e se k é divisor comum de m e n, então k é o máximo divisor comum de m e n. 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,
Em que é que estas propriedades nos ajudam? Em primeiro lugar, a) e b) restringem a gama de possíveis divisores, i.e., o intervalo dos inteiros onde o mdc deve ser procurado, o que é obviamente útil. As propriedades c) e d) serão úteis mais tarde.k >= mdc(m, n) e (m ÷ k <> 0 ou m ÷ k <> 0) implicak > mdc(m, n),em que ou significa a disjunção. Ou seja, se k é superior ou igual ao máximo divisor comum de m e n e se k não é divisor comum de m e n, então k é maior que o máximo divisor comum de m e n. Neste caso a demonstração é trivial.
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 aqueles que envolvem iterações (repetições). Mesmo essas metodologias não são substituto para o engenho e a inteligência. 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). Deve-se portanto 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 (escrever na folha de papel) 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:
enquanto 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
k <- k - 1
G: m ÷ k <> 0 ou n ÷ k <> 0.A instrução k <- k - 1 chama-se o " progresso" do ciclo pois, como se verá, é ela que garante que o ciclo progride em direcção ao seu fim.
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).Dada a inicialização
se m < n então:e a PC, tem-se que k = min(m, n), o que, conjugado com a propriedade b), nos garante que k >= mdc(m, n).
k <- m
senão:
k <- 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 k <- k - 1, a veracidade da CI é recuperada, i.e., k >= mdc(m, n).
No fundo, demonstrou-se por indução que, como CI se verifica do início do ciclo, também se verifica durante todo o ciclo, inclusivé quando este termina. Ou seja, demonstrou-se que CI é de facto invariante.
Que acontece se, durante o ciclo, G for falsa? Nesse caso o ciclo termina e conclui-se que há duas condições verdadeiras: CI e ¬G (onde ¬ representa a negação). Mas a conjunção destas condições, pela propriedade c), implica que a CO é verdadeira, i.e., que k termina de facto com o máximo divisor comum de m e n.
A demonstração da correcção do algoritmo passa pois por demonstrar que CI é verdadeira do início ao fim do ciclo (é invariante) e que quando o ciclo termina (i.e., quando a G é falsa) temos forçosamente que a CO verdadeira, i.e.,
CI e ¬G implica CO.Assim, o algoritmo completo é:
{PC: m > 0 e n > 0.}onde o texto entre {} corresponde a comentários, não fazendo parte do algoritmo.
se m < n então
k <- m
senão
k <- n
{Aqui sabe-se que k = min(m, n) >= mdc(m, n), ou seja, que a CI é verdadeira.}enquanto 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. Se não se garantir não se pode chamar a esta sequência de instruções um algoritmo.
A 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 a cada repetição. 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()
{
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.
[Incompleto, ver páginas mais recentes.]
Entretanto consulte as aulas práticas.