Guião da 6ª Aula Teórica

Sumário

Não há nenhum problema interessante cuja resolução não implique a utilização das palavras "se", "enquanto" ou "até".  Os "ses" vão ser tratados hoje: são as chamadas instruções de selecção ou condicionais.  Os "enquantos" e "atés" vão ser tratados nas próximas aulas: são as chamadas instruções iterativas.  Nesta aula falar-se-á das instruções de selecção, ficando as instruções alternativas guardadas para as próximas aulas.

Referir aqui que estas instruções já foram introduzidas informalmente em aulas anteriores, sendo agora formalizadas.

Os traçados abaixo devem ser feitos rapidamente, pois eles já devem saber bem como isto tudo funciona na prática.  O tom da abordagem também deverá ser alterado tendo esse facto em conta.

Existem duas instruções essenciais: a instrução de selecção e a instrução condicional.

A sintaxe da instrução de selecção é:

if(condição)
    instrução1
else
    instrução2

Quando é executada, o computador verifica se a condição é verdadeira ou não.  Se for, a instrução1 é executada.  Se não, a instrução2 é executada.  Em qualquer dos casos a execução continua após a instrução de selecção.  Nunca são executadas as duas instruções.  Executa-se sempre uma.

Fazer traçado do programa:

int x;
cin >> x;

if(x < 0)
    x = 0;
else
    x = 1;

cout << x << endl;

A sintaxe da instrução condicional é

if(condição)
    instrução1

Quando é executada, o computador verifica se a condição é verdadeira ou não.  Se for, a instrução1 é executada.  Senão nada acontece.  Em qualquer dos casos a execução continua após a instrução condicional.

Fazer traçado do programa:

int x;
cin >> x;

if(x < 0)
    x = 0;

cout << x << endl;

Assim sendo, uma instrução condicional pode sempre ser transformada na correspondente instrução de selecção.

if(condição)
    instrução1

é o mesmo que

if(condição)
    instrução1
else
    ; // Instrução nula!  Não faz nada!

É extremamente importante fazer o desenvolvimento disciplinado do código, o que implica naturalmente começar por o especificar completamente.  Isso vai ficar claro na aula prática.  

Na aula prática ser-vos-á pedido para resolverem um problema.  A primeira solução que proporão estará errada.  Os docentes das práticas dir-vos-ão porquê.  Vocês corrigirão e... a solução estará errada na mesma.  Eles dirão de novo porquê e vocês corrigirão.  Só à terceira vai ficar bem...  Depois propor-vos-ão que simplifiquem a solução.  O mais provável é que introduzam um erro na resolução!  Lembrem-se disto para tentarem não cometer nenhum erro!  Quem já leu as folhas teóricas (e sei que foram poucos) não pode participar neste jogo, pois já sabe a resposta...

Vamos começar com um problema simples.  Pretende-se escrever uma função que devolva o valor absoluto do dum inteiro passado como argumento.

A primeira coisa a fazer é escrever a estrutura da função, incluindo um comentário documentando a função:

/** Devolve o valor absoluto do argumento.
    @pre   ?.
    @post ?. */
int absolutoDe(int const valor)
{
    ...
}

É importante perceber que partes dizem "como se utiliza", "o que faz" e "como funciona" a função.  Alguém sabe dizer-me?

Discutir respostas.  Anotar código com cores (cabeçalho: como se usa, comentário de documentação: o que faz, corpo: como funciona).

Qual será a pré-condição?

Discutir.

A pré-condição é uma expressão com valor lógico que é verdadeiro quando os parâmetros tiverem valores para os quais a função "funciona".  Neste caso há restrições a impor a valor?

Discutir o assunto.  Na realidade deve-se impor a limitação de que valor <> numeric_limits<int>::min()!  Não se fará para simplificar, pois não é oportuno falar de numeric_limits aqui.

Logo, a expressão deve ser verdadeira independentemente do valor de valor.  Como não há mais nenhum parâmetro, a expressão tem der sempre verdadeira!

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post ?. */
int absolutoDe(int const valor)
{
    ...
}

Isto deve ser bem discutido, fazendo analogias com os conjuntos.

E a condição objectivo?  O que é o valor absoluto de um número valor?

Discutir.

É claro que o valor devolvido deve ser >= 0!  Mas chega?

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe. */
int absolutoDe(int const valor)
{
    ...
}

A condição objectivo tal como está não impõe qualquer relação entre o valor devolvido e valor!  Senão, repare-se:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe. */
int absolutoDe(int const valor)
{
    return 5;
}

Esta função está correcta?  Não!  Mas calma, devolvendo 5 verifica-se sempre ou não verifica a condição objectivo?

Então que mais devemos afirmar acerca do valor devolvido?

Discutir.  Concluir que deve ser:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    ...
}

Perfeito.  Agora, para simplificar, vamos definir uma variável para conter o valor a devolver pela função quando esta retornar:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    int absoluto;

    ...

    return absoluto;
}

Discutir nome parecido com o da função!

Podemos por isso repetir as condições que se admite ou se sabe serem verdadeiras em cada instante.  No início da função assumimos a pré-condição como verdadeira.  No seu final, antes do retorno, escrevemos a condição objectivo:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    // V.

    int absoluto;

    ...

    // 0 <= absoluto e (absoluto = valor ou absoluto = -valor).
    return absoluto;
}

A estes comentários com afirmações acerca do estado do programa, i.e., acerca dos valores das instâncias, em cada intervalo entre instruções chama-se asserções, como vocês já sabem.

É boa ideia colocar logo as respectivas instruções asserção:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    assert(true);
    // V.

    int absoluto;

    ...

    // 0 <= absoluto e (absoluto = valor ou absoluto = -valor).
    assert(0 <= absoluto and (absoluto == valor or absoluto == -valor));

    return absoluto;
}

Dizer que assert(true); não é muito útil, pelo que se eliminará.

De regresso ao problema que temos de resolver, digam-me: que instruções posso eu usar para resolver o problema, se não sempre, pelo menos em algumas circunstâncias?  Pensem em simples instruções de atribuição.  Inspirem-se na condição objectivo!

Discutir.  Fazê-los chegar a:

absoluto = valor;
absoluto = -valor;

Perfeito!  É claro que nem sempre cada uma destas instruções resolve o problema.  Em que circunstâncias o farão?  É claro que aqui podíamos recorrer apenas à intuição: este é um problema tão simples!  Em vez disso vamos formalizar um pouco, o que nos vai permitir perceber melhor o problema, as instruções de selecção, e vai também preparar-nos para resolver problemas mais complicados.

Comecemos por um parênteses.

Vamos supor uma dada instrução de atribuição.  Por exemplo:

double x, y;

...

y = x * x;

Em que circunstâncias se garante que, depois desta instrução, se tem 2 < y?

Antes de resolver o problema vamos transformar o nosso requisito acerca de y numa asserção que deve ser verdadeira depois da instrução:

y = x * x;
// 2 < y.

Então o nosso problema é achar uma asserção que, se for verdadeira antes da instrução, leve forçosamente ao resultado desejado:

// ?.
y = x * x;
// 2 < y.

Podem-se colocar asserções entre todas as instruções de um programa.  Cada asserção funciona com pré-condição para a instrução que se lhe segue e como condição objectivo para a instrução que a precede.  Logo:

// PC: ?.
y = x * x;
// CO: 2 < y.

O problema então é determinar uma PC tal que, depois da instrução, se verifique a CO.

Uma solução possível é

// PC: 100 < x.
y = x * x;
// CO: 2 < y.

É verdade, mas não será uma pré-condição demasiado forte?  É!

Discutir que uma asserção é mais forte se for mais restritiva, ou seja, se o conjunto dos valores que a verificam for "mais pequeno".

Vamos reformular o nosso problema: qual será a pré-condição mais fraca que garante que, depois da instrução, a condição objectivo se verifica?

Discutir que uma asserção é mais fraca se for menos restritiva, ou seja, se o conjunto dos valores que a verificam for "maior".  I.e., condições fortes correspondem a conjuntos pequenos e condições fracas correspondem a conjuntos grandes.

Repare-se que se pôs o problema ao contrário do que é usual: partimos da condição objectivo, e não ao contrário.  Fizemo-lo por duas razões:

  1. A solução do problema é mais simples!  Não parece, mas em geral é!
  2. A programação é uma actividade que deve sempre partir dos objectivos.
Perfeito.  E há alguma solução milagrosa para o nosso problema?  Milagrosa não é, mas funciona sempre!  Seja uma instrução de atribuição da forma:

variável = expressão;
// CO

onde CO é a condição objectivo, que se pretende que seja verdadeira depois da atribuição.  Então a pré-condição mais fraca que é necessário impor antes da instrução pode ser obtida substituindo na condição objectivo todas as ocorrências da variável pela expressão.

Como assim?  Regresse-se ao nosso exemplo:

// PC: ?.
y = x * x;
// CO: 2 < y.

Aplique-se a receita:

// PC: 2 < x2, ou seja, x < -2½ ou 2½ < x.
y = x * x;
// CO: 2 < y.
Perfeito!

Funciona sempre?  Sempre.  Não falha.

Outro exemplo:

// PC: ?.
++x;
// CO: x <= 0.

Onde está a atribuição?  Bom, isto é equivalente a:

// PC: ?.
x = x + 1;
// CO: x <= 0.

Logo

// PC: x + 1 <= 0, ou seja, x <= -1.
x = x + 1;
// CO: x <= 0.

E se for:

// PC: ?.
x = x * x - 2;
// CO: 0 <= x.

O mesmo:
// PC: 0 <= x2 - 2, ou seja, 2 <= x2, ou seja, x <= -2½ ou 2½ <= x
x = x * x - 2;
// CO: 0 <= x.
Ver se perceberam bem!  Discutir.

Fim de parênteses!

Regressados ao nosso problema original, podemos agora perguntar-nos: quais as pré-condições mais fracas que permitem atingir os objectivos depois das duas instruções?

// PC1: ?.
absoluto = -valor;
// 0 <= absoluto e (absoluto = valor ou absoluto = -valor).

e
// PC2: ?.
absoluto = valor;
// 0 <= absoluto e (absoluto = valor ou absoluto = -valor).
Simples: são atribuições, aplique-se a receita.

// PC1: 0 <= -valor e (-valor = valor ou -valor = -valor), ou seja,
// PC1: valor <= 0 e (-valor = valor ou V), ou seja,
// PC1: valor <= 0 e V, ou seja,
// PC1: valor <= 0.
absoluto = -valor;
// 0 <= absoluto e (absoluto = valor ou absoluto = -valor).

e

// PC2: 0 <= valor e (valor = valor ou valor = -valor), ou seja,
// PC2: 0 <= valor e (V ou valor = -valor), ou seja,
// PC2: 0 <= valor e V, ou seja,
// PC2: 0 <= valor.
absoluto = valor;
// 0 <= absoluto e (absoluto = valor ou absoluto = -valor).

Conclusão de La Palisse: a instrução

absoluto = -valor;

só leva ao resultado pretendido se valor <= 0, e a instrução

absoluto = valor;

só leva ao resultado pretendido se 0 <= valor...

Bom, isto significa que precisamos mesmo de uma instrução de selecção, para seleccionar qual das duas instruções usar em cada momento:

if(valor <= 0)
    absoluto = -valor;
else
    absoluto = valor;

Aqui há um ponto importante: a instrução de selecção tem duas instruções alternativas.  A primeira é executada quando a condição for verdadeira.  Neste caso quando valor <= 0.  A segunda instrução alternativa é executada quando a condição for falsa.  Neste caso quando 0 < valor.

Mas 0 < valor não foi a condição encontrada para a instrução

absoluto = valor;

Será isso problemático?  Não, porque 0 < valor implica 0 <= valor.  Na nossa notação isso escreve-se colocando uma asserção após a outra:

// 0 < valor.
// 0 <= valor.

É importante perceber esta implicação: se um valor for maior que zero, então é forçosamente maior ou igual a zero.

Pode-se pensar em termos de teoria dos conjuntos: o conjunto dos valores maiores do que zero está contido no conjunto dos valores maiores ou iguais a zero.

Fixem esta relação: uma implicação corresponde nos conjuntos à relação "está contido".

Dizer também que se uma asserção implica outra, então a primeira é mais forte que a segunda.

Voltando ao problema, o que se passa neste caso é que a instrução de selecção nos força a decidir qual das instruções lida com o caso valor = 0.  Qualquer uma pode tratar desse caso, pelo que se escolheu que fosse a primeira.  Se se quisesse que fosse a segunda que alteração teríamos de fazer?

Discutir.  Escrever versão completa da função.

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    int absoluto;

    if(valor <= 0)
        absoluto = -valor;
    else
        absoluto = valor;

    assert( 0 <= absoluto and (absoluto == valor or absoluto = = -valor));

    return absoluto;
}

Para simplificar pode-se usar um operador especial: ? :.

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    int absoluto = valor <= 0 ? -valor : valor;

    assert( 0 <= absoluto and (absoluto == valor or absoluto = = -valor));

    return absoluto;
}

que se pode simplificar para:

/** Devolve o valor absoluto do argumento.
    @pre   V.
    @post 0 <= absolutoDe e (absolutoDe = valor ou absolutoDe = -valor). */
int absolutoDe(int const valor)
{
    return valor <= 0 ? -valor : valor;
}

Neste caso não é possível escrever a instrução de asserção para a condição objectivo, o que é uma desvantagem.

Um outro exemplo.  O problema agora é escrever uma função:

double valorMaisPróximoDentroDe(double const v, double const mín, double const máx)
{
    double r;

    ...

    return r;
}

Dizer que r, v, mín e máx e  não são os melhores nomes para as variáveis, mas sim um compromisso para escrever expressões curtas no quadro.

A ideia é devolver o valor do intervalo fechado [mín, máx] que esteja mais próximo de v.

A primeira coisa a fazer é escrever a pré-condição e a condição objectivo.  Qual é a pré-condição?

Discutir.

É claro que isto só faz sentido quando mín <= máx!

E a condição objectivo?

Discutir.

A condição objectivo deve dizer que, das três uma,

  1. ou v é menor que mín e o valor devolvido é igual a mín;
  2. ou v é maior que máx e o valor devolvido é igual a máx;
  3. ou v pertence ao intervalo e o valor devolvido é igual a v!
Traduzindo:

/** Devolve o valor de v limitado ao intervalo dado.
   @pre mín <= máx.
   @post (v < mín e valorMaisPróximoDentroDe= mín) ou
         (máx < v e valorMaisPróximoDentroDe= máx) ou
         (mín <= v e v <= máx e valorMaisPróximoDentroDe= v). */
double valorMaisPróximoDentroDe(double const v, double const mín, double const máx)
{
    assert(mín <= máx);
    // PC: mín <= máx.

    double r;

    ...

    // CO: (v < mín e r = mín) ou (máx < v e r = máx) ou
            (mín <= v e v <= máx e r = v).
    assert((xv < mín and r == mín) or (máx < v and r == máx) or
            (mín <= v and v <= máx and r == v));

    return r;
}

Olhando para a condição objectivo vemos uma disjunção: há três termos no ou.  É provável, portanto, que o problema seja resolúvel com uma instrução de selecção.

Chamar a atenção para isto!

Que instruções resolvem o problema, pelo menos em algumas circunstâncias?  Fácil!  Basta olhar para a condição objectivo:

r = mín;
r = máx;
r = v;

Vamos ver quais as respectivas pré-condições mais fracas.

Para r = mín; temos:

// PC1: (v < mín e mín = mín) ou (máx < v e mín = máx) ou
//      (mín <= v e v <= máx e mín = v).
r = mín;
// (v < mín e r = mín) ou (máx < v e r = máx) ou
// (mín <= v e v <= máx e r = v).

Pode-se simplificar esta pré-condição:

// PC1: v < mín ou (máx < v e mín = máx) ou (v <= máx e mín = v).

Para r = máx; temos:

// PC2: (v < mín e máx = mín) ou (máx < v e máx = máx) ou
//      (mín <= v e v <= máx e máx = v).
r = máx;
// (v < mín e r = mín) ou (máx < v e r = máx) ou
//  (mín <= v e v <= máx e r = v).

Pode-se simplificar a pré-condição para:

// PC2: (v < mín e máx = mín) ou máx < v ou (mín <= v e máx = v).

Para r = v; temos:

// PC3: (v < mín e v = mín) ou (máx < v e v = máx) ou
//      (mín <= v e v <= máx e v = v).
r = v;
// (v < mín e r = mín) ou (máx < v e r = máx) ou
//  (mín <= v e v <= máx e r = v).

Pode-se simplificar esta pré-condição para:

// PC3: F ou F ou (mín <= v e v <= máx).

ou seja

// PC3: mín <= v e v <= máx.

Temos de escrever uma instrução de selecção com três instruções controladas.  Como cada instrução de selecção controla exactamente duas instruções, temos de encadear instruções de selecção:

// PC: mín <= máx.
if(C1)
    // PC1: v < mín ou (máx < v e mín = máx) ou (v <= máx e mín = v).
    r = mín;
else if(C2)
    // PC2: (v < mín e máx = mín) ou máx < v ou (mín <= v e  máx = v).
    r = máx;
else
    // PC3: mín <= v e v <= máx.
    r = v;
Sabendo que mín <= máx, as pré-condições podem ser simplificadas:

// PC: mín <= máx.
if(C1)
    // PC1: v < mín ou (máx < v e mín = máx) ou mín = v, ou seja,
    //      v <= mín ou (máx < v e mín = máx).
    r = mín;
else if(C2)
    // PC2: (v < mín e máx = mín) ou máx < v ou máx = v, ou seja,
    //      (v < mín e máx = mín) ou máx <= v.
    r = máx;
else
    // PC3: mín <= v e v <= máx.
    r = v;

Claramente há uma sobreposição das pré-condições.  Imagine-se que mín = máx e v > máx.  Esse caso é previsto tanto pela primeira instrução como pela segunda!  Pode-se eliminar da primeira pré-condição!  Imagine-se que mín = máx e v < mín .  Esse caso é previsto tanto pela primeira instrução como pela segunda!  Pode-se eliminar da segunda pré-condição!

// PC: mín <= máx.
if(C1)
    // PC1: v <= mín.
    r = mín;
else if(C2)
    // PC2: máx <= v.
    r = máx;
else
    // PC3: mín <= v e v <= máx.
    r = v;

Ainda sobram duas sobreposições: a primeira e a terceira instruções lidam bem com o caso v = mín e a segunda e a terceira instruções lidam bem com o caso v = máx.  Pode-se fazer com que seja a terceira instrução a lidar com esses casos:

// PC: mín <= máx.
if(C1)
    // PC1: v < mín.
    r = mín;
else if(C2)
    // PC2: máx < v.
    r = máx;
else
    // PC3: mín <= v e v <= máx.
    r = v;

Então que condições escolher para os if?

A primeira é fácil: v < mín!

E a segunda? v > máx.  Logo:

// PC: mín <= máx.
if(xv < mín)
    // PC1: v < mín.
    r = mín;
else if(máx < v)
    // PC2: máx < v.
    r = máx;
else
    // PC3: mín <= v e v <= máx.
    r = v;

Em que circunstâncias é executada a terceira instrução?  Quando mín <= v e v <= máx, como se pretendia!

Concluindo:

/** Devolve o valor de v limitado ao intervalo dado.
   @pre mín <= máx.
   @post (v < mín e valorMaisPróximoDentroDe= mín) ou
         (máx < v e valorMaisPróximoDentroDe= máx) ou
         (mín <= v e v <= máx e valorMaisPróximoDentroDe= v). */
double valorMaisPróximoDentroDe(double const v, double const mín, double const máx)
{
    assert(mín <= máx);

    double r;

    if(xv < mín)
        r = mín;
    else if(máx < v)
        r = máx;
    else
        r = v;

    assert( (v < mín and r == mín) or (máx < v and r == máx) or
            (mín <= v and v <= máx and r == v));

    return r;
}

O problema pode ser resolvido com instruções de retorno imediato (embora nessa caso a instrução de asserção para a condição objectivo não possa ser mantida):

/** Devolve o valor de v limitado ao intervalo dado.
   @pre mín <= máx.
   @post (v < mín e valorMaisPróximoDentroDe= mín) ou
         (máx < v e valorMaisPróximoDentroDe= máx) ou
         (mín <= v e v <= máx e valorMaisPróximoDentroDe= v). */
double valorMaisPróximoDentroDe(double const v, double const mín, double const máx)
{
    assert(mín <= máx);

    if(xv < mín)
        return mín;
    else if(máx < v)
        return máx;
    else
        return v;
}

Mas nesse caso os else são redundantes, pelo que é comum escrever-se:

/** Devolve o valor de v limitado ao intervalo dado.
   @pre mín <= máx.
   @post (v < mín e valorMaisPróximoDentroDe= mín) ou
         (máx < v e valorMaisPróximoDentroDe= máx) ou
         (mín <= v e v <= máx e valorPróximoDentro = v). */
double valorMaisPróximoDentroDe(double const v, double const mín, double const máx)
{
    assert(mín <= máx);

    if(xv < mín)
        return mín;
    if(máx < v)
        return máx;
    return v;
}

Discutir porque é assim!  Mas dizer que o mais claro é mesmo manter os else!

Seguimos uma metodologia no desenvolvimento desta instrução de selecção.  Essa metodologia diz o seguinte:

  1. Especificar bem o problema (escrever PC e CO).
  2. Olhar bem para a CO e perceber se é necessária uma instrução de selecção.  Um bom indício de que são precisas instruções de selecção é a existência de "ous" na condição alternativa.
  3. Se o for, continua-se.
  4. Olhar bem para a CO e tentar identificar n instruções (ou sequências de instruções) que pareçam permitir atingir o objectivo.
  5. Para cada uma dessas instruções ou sequências de instruções, determinar a respectiva pré-condição mais fraca.
  6. Cada instrução ou sequência de instruções seleccionada terá como guarda a condição mais fraca que, em conjunto com a pré-condição global, garanta a verificação da respectiva pré-condição.
  7. É fundamental que as guardas cubram todos os casos possíveis!  Se isso não acontecer, tem de se voltar atrás e tentar encontrar mais uma instrução ou sequência de instruções que cubra os casos em falta.