Questão 1

Deve preencher todos os espaços indicados por um sublinhado (___) com V ou F. Qualquer espaço não preenchido será considerado como uma resposta errada.

Em geral as alíneas podem ter zero ou mais respostas correctas.  Cada resposta correctamente assinalada vale 0,5 valores.

Nas alíneas em que apenas uma resposta está correcta (se existirem estão assinaladas no texto), responder com mais ou menos do que um V anula a cotação.  A resposta correcta corresponde à cotação completa.  Qualquer outra resposta corresponde a zero valores.

Em todos os casos em que não é explicitamente referida a localização de uma instrução, considere que esta é dada na função main() do programa seguinte:

#include <iostream>
#include <vector>

using namespace std;

class Lâmpada {
  public:
    Lâmpada(bool const está_acesa = true);

    bool estáAcesa() const;

    void acende();
    void apaga();

  private:
    enum Estado {apagada, acesa};

    Estado estado;
};

Lâmpada::Lâmpada(bool const está_acesa)
    : estado(está_acesa ? acesa : apagada)
{}

void Lâmpada::acende()
{
    estado = acesa;
}

void Lâmpada::apaga()
{
    estado = apagada;
}

bool Lâmpada::estáAcesa() const
{
    return estado == acesa;
}

int main()
{
    Lâmpada const vigia;
    ...
}

 

1.1  Admita que qualquer uma destas instruções é dada na função main() imediatamente após a definição da constante vigia.  Quais das seguintes instruções estão correctas?

  V    Lâmpada a;
  F    Lâmpada a(Lâmpada::apagada);

O enumerado Estado está definido na parte privada da classe Lâmpada, pelo que não é acessível de fora dessa classe. Por outro lado, está-se a tentar usar um valor de um enumerado num local onde se espera um valor do tipo bool.

  V    Lâmpada a(vigia.estáAcesa());

 [cotação: 1,5]

1.2  Admita que qualquer uma destas instruções é dada na função main() do programa acima.  Quais das seguintes instruções estão correctas?

  V    Lâmpada a = vigia;
  F    vigia.apaga();

vigia é uma constante, pelo que só podem invocar operações inspectoras, i.e., que garantem a constância da instância implícita.

  V    bool estado = vigia.estáAcesa();
  F    cout << vigia.estado;

estado é um atributo privado da classe Lâmpada, pelo que só pode ser acedido por membros dessa classe.

 [cotação: 2]

1.3  Assuma que as seguintes instruções são dadas dentro de uma função ou procedimento membro da classe Lâmpada e que não são declaradas quaisquer variáveis ou constantes dentro dessa função ou procedimento (que não tem quaisquer parâmetros).  Quais das seguintes instruções estão correctas?

  F    estáAcesa() = true;

estáAcesa() é uma função que devolve um bool por valor, pelo que não se lhe podem atribuir valores.

  F    estado = false;

estado é uma variável do tipo Estado, cujos valores possíveis são apagada e acesa.

 [cotação: 1]

1.4  Suponha o seguinte código adicional:

void acendeLâmpadasPares(vector<Lâmpada> luzes_de_natal)
{
    for(vector<Lâmpada>::size_type i = 0;
        i < luzes_de_natal.size();
        i += 2)
        luzes_de_natal[i].acende();
}

int númeroDeLâmpadasAcesas(vector<Lâmpada> const& luzes_de_natal)
{
    int número_de_lâmpadas_acesas = 0;

    for(vector<Lâmpada>::size_type i = 0;
        i != luzes_de_natal.size();
        ++i)
        if(luzes_de_natal[i].estáAcesa())
            ++número_de_lâmpadas_acesas;

    return número_de_lâmpadas_acesas;
}

int main()
{
    vector<Lampada> luzes_de_natal(50);
    acendeLâmpadasPares(luzes_de_natal);
    cout << númeroDeLâmpadasAcesas(luzes_de_natal) << endl;
}

  V    50
  F    0
  F    25
  F    26

O vector luzes_de_natal é inicializado com 50 elementos do tipo Lâmpada cujo estado é acesa.  (Repare-se que o construtor da classe Lâmpada tem um argumento com valor por omissão que faz com que as variáveis do tipo Lâmpada quando construídas sem ser passado qualquer valor ao construtor fiquem com estado acesa.)  Como este vector é passado por valor ao procedimento acendeLâmpadasPares(), qualquer alteração realizada dentro do procedimento perde-se.  Ou seja, após a invocação deste procedimento, o vector continua a ter 50 elementos do tipo Lâmpada cujo estado é acesa.  Por fim, a função númeroDeLâmpadasAcesas() devolve o número de lâmpadas acesas que é enviado para o ecrã.  Neste caso, 50.

 [cotação: 0,5]

Questão 2

Dada a grande quantidade de informação que actualmente é difundida usando o SMS (Short Message Service) começa a sentir-se a necessidade de dispor de sistemas de gestão de informação que permitam guardar as mensagens que são trocadas usando o telemóvel.  Normalmente, as mensagens recebidas são guardadas numa pasta de entradas e as mensagens enviadas numa pasta de saídas.  Ambas as pastas têm uma capacidade limitada, relativamente pequena.

Pretende-se desenvolver um sistema que permita gerir as mensagens de texto, trocadas usando o telemóvel, num computador pessoal.  Deste modo teríamos capacidade para guardar maior número de mensagens, bem como de aumentar o número de pastas permitindo uma melhor organização da informação.  As mensagens de texto são constituídas pelo texto da mensagem (cadeia de caracteres), pelo remetente (cadeia de caracteres), pela data (Data) e pela hora (Hora).

2.1  Defina apenas a interface de uma classe C++ MensagemDeTexto que representa uma mensagem de texto.  A classe C++ MensagemDeTexto deve dispor de um construtor que recebe os dados necessários à construção de uma mensagem de texto e operações que permitam inspeccionar:

• o texto da mensagem;
• o remetente;
• a data; e
• a hora.

Não é necessário nesta alínea definir quaisquer métodos da classe.

[cotação: 3]

/** Representa uma mensagem de texto.
    @invariant remetente_<> "". */
class MensagemDeTexto {
  public:
    /** Constrói uma mensagem de texto.
        @pre remetente <> "".
        @post texto() = texto e remetente() = remetente e
              data() = data e hora() = hora. */
    MensagemDeTexto(string const& texto, string const& remetente,
                    Data const& data, Hora const& hora);

    /** Devolve o texto da mensagem.
        @pre V.
        @post texto() é o texto da mensagem. */
    string const& texto() const;

    /** Devolve o remetente da mensagem.
        @pre V.
        @post remetente() é o remetente da mensagem. */
    string const& remetente() const;

    /** Devolve a data da mensagem.
        @pre V.
        @post data() é a data da mensagem. */
    Data const& data() const;

    /** Devolve a hora da mensagem.
        @pre V.
        @post hora() é a hora da mensagem. */
    Hora const& hora() const;

  private:
    string texto_;
    string remetente_;
    Data data_;
    Hora hora_;

    /** Devolve verdadeiro se o invariante se verificar.
        @pre V.
        @post cumpreInvariante = remetente_<> "". */
    bool cumpreInvariante() const;
};

2.2  A classe Pasta representa uma pasta onde são guardadas as mensagens de texto:

/** Representa uma pasta que guarda mensagens de texto.
    @invariant nome_ <> "". */
class Pasta {
  public:
    /** Constrói uma pasta.
        @pre nome <> "".
        @post nome() = nome e númeroDeMensagens() = 0. */
    Pasta(string const& nome);

    /** Devolve o nome da pasta.
        @pre V.
        @post nome() é o nome da pasta. */
    string nome() const;

    /** Devolve o número de mensagens na pasta.
        @pre V.
        @post númeroDeMensagens() é o número de mensagens da pasta. */
    int númeroDeMensagens() const;

    /** Adiciona a mensagem de texto recebida como argumento no fim da pasta.
        @pre númeroDeMensagens() = n e (Q j : 0 <= j < n : mensagem(j) = m_j).
        @post (Q j : 0 <= j < númeroDeMensagens() - 1 : mensagem(j) = m_j) e
               mensagem[númeroDeMensagens() - 1] = mensagem_de_texto
             e númeroDeMensagens() = n + 1. */
    void adiciona(MensagemDeTexto const& mensagem_de_texto);

    /** Remove a mensagem de texto na posição recebida como argumento.
        @pre 0 <= posição e posição < númeroDeMensagens()
            e númeroDeMensagens() = n e (Q j : 0 <= j < n : mensagem(j) = m_j).
        @post (Q j : 0 <= j < posição : mensagem(j) = m_j) e
             (Q j : posição <= j < númeroDeMensagens() : mensagem(j) = m_j+1)
               númeroDeMensagens() = n - 1. */
    void removeMensagemNaPosição(int const posição)

    /** Devolve a mensagem de texto na posição recebida como argumento.
        @pre 0 <= posição e posição < númeroDeMensagens().
        @post mensagem() é a mensagem de texto na posição posição. */
    MensagemDeTexto const& mensagem(int const posição) const;

    /** Mostra no ecrã o cabeçalho de todas as mensagens de texto.
        @pre V.
        @post ¬canal ou o ecrã contém o remetente, a data e a hora de todas as mensagens.
    void mostraMensagens() const;

  private:
    string nome_;
    vector<MensagemDeTexto> mensagens_de_texto;

    /** Devolve verdadeiro se o invariante se verificar.
        @pre V.
        @post cumpreInvariante = nome_ <> "". */
    bool cumpreInvariante() const;
};

Defina os métodos:

• void removeMensagemNaPosicao(int const posição), sem esquecer que, de acordo com a CO, a ordem das mensagens na pasta não deve ser alterada (note que dadas estas especificações, seria mais adequado usar uma lista (list<Tipo>) em vez de um vector (vector<Tipo>) na representação da pasta, no entanto, só na disciplina de POO é que estas serão abordadas); e
• void mostraMensagens() const, sabendo que o cabeçalho de uma mensagem é composto pelo remetente, a data e a hora.

No caso do método void removeMensagemNaPosicao(int const posição) coloque instruções de asserção para verificar a PC e a CIC. Não tente explicitar nestas asserções os termos das condições envolvendo quantificadores.

[cotação: 3.5]

void Pasta::removeMensagemNaPosição(int const posição)
{
    assert(0 <= posição and posição < númeroDeMensagens());
    assert(cumpreInvariante());

    for(vector<MensagemDeTexto>::size_type i = posição;
        i != mensagens_de_texto.size() - 1;
        ++i)
        mensagens_de_texto[i] = mensagens_de_texto[i + 1];
    mensagens_de_texto.pop_back();

    assert(cumpreInvariante());    
}

void Pasta::mostraMensagens() const
{
    assert(cumpreInvariante());

    for(vector<MensagemDeTexto>::size_type i = 0;
        i != mensagens_de_texto.size();
        ++i)
        cout << "Remetente: " << mensagens_de_texto[i].remetente()
             << "Data:      " << mensagens_de_texto[i].data()
             << "Hora:      " << mensagens_de_texto[i].hora() << endl;
}

Questão 3

Considere um tipo abstracto de dados que permita representar números binários como cadeias de '0' e '1'.

Uma cadeia é binária se contiver apenas '0' e '1' ou se estiver vazia.  Uma cadeia binária é normalizada se for binária, tiver comprimento maior ou igual a um, e não contiver '0' à esquerda, excepto se contiver um único '0'.

/** Indica se a cadeia recebida contém apenas '0' e '1'.
    @pre V.
    @post éBinario = 
         (Q j : 0 <= j < bits.length() : bits[j] = '0' ou bits[j] = '1'). */
bool éBinário(string const& bits);

/** Indica se a cadeia recebida é binária e está normalizada, i.e., não contém zeros
    à esquerda (excepto se existir um único bit).
    @pre V.
    @post éBinárioNormalizado = éBinário(bits) e bits.length() != 0
         e (bits.length() = 1 ou bits[0] = '1'). */
bool éBinárioNormalizado(string const& bits);

/** Devolve a versão normalizada da cadeia binária à entrada.
    @pre éBinário(bits).
    @post éBinárioNormalizado(versaoBináriaNormalizadaDe) e
         versaoBináriaNormalizadaDe e bits representam o mesmo
          número binário. */
string versaoBináriaNormalizadaDe(string bits);

/** Devolve uma versao invertida da cadeia à entrada.
    @pre V.
    @post inversoDe.length() = cadeia.length() e
         (Q j : 0 <= j < cadeia.size() :
             inversoDe[j] = cadeia[cadeia.length() - 1 - j]). */
string inversoDe(string const& cadeia);

/** Representa números binários como cadeias de '0' e '1'.
    @invariant éBinárioNormalizado(bits_). */
class Binário {
  public:
    /** Constrói novo número binário dada uma cadeia de bits.
        @pre éBinário(bits).
        @post *this e bits representam o mesmo número binário. */
    Binário(string const& bits);

    /** Devolve a cadeia de bits correspondente ao binário.
        @pre V.
        @post eBinárioNormalizado(bits) e bits e *this representam o mesmo
             número binário. */
    string const& bits() const;

    /** Devolve o "ou" binário (bit a bit) do binário com outro binário dado.
        @pre V.
        @post operator or é o ou bit a bit dos números binários *this e outro. */
    Binário const operator or (Binário const& outro) const;

  private:
    string bits_;

    /** Indica se o binário cumpre a condição invariante de classe.
        @pre V.
        @post éBinárioNormalizado(bits_). */
    bool cumpreInvariante() const;
};

Sabendo que

string const& Binário::bits() const
{
    assert(cumpreInvariante());

    return bits_;
}

bool Binário::cumpreInvariante() const
{
    return éBinárioNormalizado(bits_);
}

implemente os métodos restantes, de modo a que o seguinte código seja válido.

    Binário um_número_binário("001");
    cout << um_número_binário.bits() << endl;               // Aparece 1;

    Binário outro_número_binário("1000");
    cout << outro_número_binário.bits() << endl;            // Aparece 1000;

    Binário disjunção = um_número_binário or outro_número_binário;
    cout << disjunção.bits() << endl;                       // Aparece 1001;

 [cotação: 3,5]

#include <iostream>
#include <string>

using namespace std;

/** Indica se a cadeia recebida contém apenas '0' e '1'.
    @pre V.
    @post eBinario = (Q j : 0 <= j < bits.length() : bits[j] = '0' ou bits[j] = '1'). */
bool eBinario(string const& bits)
{
    return bits.find_first_not_of("01") == string::npos;
}

/** Indica se a cadeia recebida é binária e está normalizada, i.e., não contém
    zeros à esquerda (excepto se existir um único bit).
    @pre V.
    @post eBinarioNormalizado = eBinario(bits) e bits.length() != 0 e
          (bits.length() = 1 ou bits[0] = '1'). */
bool eBinarioNormalizado(string const& bits)
{
    return eBinario(bits) and bits.length() != 0 and 
           (bits.length() == 1 or bits[0] == '1');
}

/** Devolve a versão normalizada da cadeia binária à entrada.
    @pre eBinario(bits).
    @post eBinarioNormalizado(versaoBinariaNormalizadaDe) e
         versaoBinariaNormalizadaDe e bits representam o mesmo número binário. */
string versaoBinariaNormalizadaDe(string bits)
{
    assert(eBinario(bits));

    if(bits.find('1') == string::npos)
        return "0";

    return bits.substr(bits.find('1'));
}

/** Devolve uma versão invertida da cadeia à entrada.
    @pre V.
    @post inversoDe.length() = cadeia.length() e
         (Q j : 0 <= j < cadeia.size() : inversoDe[j] = cadeia[cadeia.length() - 1 - j]). */
string inversoDe(string const& cadeia)
{
    return string(cadeia.rbegin(), cadeia.rend());
}

/** Representa números binários como cadeias de '0' e '1'.
    @invariant éBinárioNormalizado(bits_). */
class Binario {
  public:
    /** Constrói novo número binário dada uma cadeia de bits.
        @pre eBinario(bits).
        @post *this e bits representam o mesmo número binário. */
    Binario(string const& bits);

    /** Devolve a cadeia de bits correspondente ao binário.
        @pre V.
        @post eBinarioNormalizado(bits) e bits e *this representam o mesmo número binário. */
    string const& bits() const;

    /** Devolve o "ou" binário (bit a bit) do binário com outro binário dado.
        @pre V.
        @post operator or é o ou bit a bit dos números binários *this e outro. */
    Binario const operator or (Binario const& outro) const;

  private:
    string bits_;

    /** Indica se o binário cumpre a condição invariante de classe.
        @pre V.
        @post eBinarioNormalizado(bits_). */
    bool cumpreInvariante() const;
};

Binario::Binario(string const& bits)
{
    assert(eBinario(bits));

    bits_ = versaoBinariaNormalizadaDe(bits);

    assert(cumpreInvariante());
}

string const& Binario::bits() const
{
    assert(cumpreInvariante());

    return bits_;
}

Binario const Binario::operator or (Binario const& outro) const 
{
    assert(cumpreInvariante() and outro.cumpreInvariante());

    string disjuncao_invertida;
    string outro_invertido;
    if(bits_.length() < outro.bits_.length()) {
        disjuncao_invertida = inversoDe(outro.bits_);
        outro_invertido = inversoDe(bits_);
    }
    else {
        disjuncao_invertida = inversoDe(bits_);
        outro_invertido = inversoDe(outro.bits_);
    }
    for(string::size_type i = 0; i != outro_invertido.length(); ++i)
        disjuncao_invertida[i] =
            disjuncao_invertida[i] == '1' or outro_invertido[i] == '1' ? '1' : '0';

    Binario disjuncao(inversoDe(disjuncao_invertida));

    assert(disjuncao.cumpreInvariante());

    return disjuncao;
}

bool Binario::cumpreInvariante() const
{
    return eBinarioNormalizado(bits_);
}

#ifdef TESTE

int main()
{
    assert(not eBinario("acds"));
    assert(eBinario(""));
    assert(eBinario("0101"));

    assert(not eBinarioNormalizado("acds"));
    assert(not eBinarioNormalizado(""));
    assert(not eBinarioNormalizado("0101"));
    assert(eBinarioNormalizado("101"));

    assert(eBinarioNormalizado(versaoBinariaNormalizadaDe("")));
    assert(eBinarioNormalizado(versaoBinariaNormalizadaDe("0101")));

    assert(versaoBinariaNormalizadaDe("") == "0");
    assert(versaoBinariaNormalizadaDe("000") == "0");
    assert(versaoBinariaNormalizadaDe("100") == "100");
    assert(versaoBinariaNormalizadaDe("00100") == "100");

    assert(inversoDe("abcd") == "dcba");
    assert(inversoDe("abc") == "cba");
    assert(inversoDe("a") == "a");
    assert(inversoDe("") == "");

    assert(Binario("").bits() == "0");
    assert(Binario("0010").bits() == "10");
    assert(Binario("000").bits() == "0");
    assert((Binario("") or Binario("")).bits() == "0");
    assert((Binario("1") or Binario("")).bits() == "1");
    assert((Binario("") or Binario("1")).bits() == "1");
    assert((Binario("1") or Binario("0")).bits() == "1");
    assert((Binario("") or Binario("000110")).bits() == "110");
    assert((Binario("0101") or Binario("100110")).bits() == "100111");
}

#else

int main()
{
    Binario um_binario("00000001");
    Binario outro_binario("01000");

    cout << um_binario.bits() << endl; // Aparece 1.
    cout << outro_binario.bits() << endl; // Aparece 1000.

    Binario resultado = um_binario or outro_binario;

    cout << resultado.bits() << endl; // Aparece 1001.
}

#endif

Questão 4

Suponha a função double traçoDe(double const m[tamanho][tamanho], int const n) que devolve o traço da matriz quadrada de double definida pelos n×n primeiros elementos de m:


int const tamanho = 10;

double traçoDe(double const m[tamanho][tamanho], int const n)
{
    assert(0 <= n and n <= tamanho);

    double traço = 0.0;

    for(int i = 0; i != n; ++i)
        traço += m[i][i];

    return traço;
}

[cotação: 1,5]

PC: 0 <= n <= tamanho.
CO: traçoDe = (S j : 0 <= j < n : m[j][j]).

CO': traço = (S j : 0 <= j < n : m[j][j]).
CI:  traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i <= n.

4.2  Prove que o ciclo está parcialmente correcto verificando que:

• Se a PC for verdadeira, então a CI também é verdadeira após a inicialização das variáveis e antes da primeira iteração do ciclo, i.e.:
// PC
init
// implica CI.

// PC: 0 <= n <= tamanho.
double traço = 0.0;
int i = 0;
// CI:  traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i <= n, ou seja,
// CI:  0.0 = (S j : 0 <= j < 0 : m[j][j]) e 0 <= 0 <= n, ou seja,
// CI:  0.0 = 0.0 e 0 <= n, ou seja, dada a PC,
// CI:  V.

• Se a guarda G e a CI  do ciclo forem verdadeiras no início de um passo, então a CI também é verdadeira no fim desse passo, i.e.:
// G e CI
passo
// implica CI

// CI e G: traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i <= n e i <> n, ou seja,
// CI e G: traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i < n.
traço += m[i][i];
++i;
// implica CI: traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i <= n

A demonstração pode ser feita duma forma directa, deduzindo as asserções verdadeiras após cada instrução:

// CI e G: traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i < n.
traço += m[i]m[i];
// traço = (S j : 0 <= j < i : m[j][j]) + m[i][i] e 0 <= i < n, ou seja,
// traço = (S j : 0 <= j < i + 1 : m[j][j]) e 0 <= i < n.
++i;
// traço = (S j : 0 <= j < (i - 1) + 1 : m[j][j]) e 0 <= i - 1 < n, ou seja,
// traço = (S j : 0 <= j < i : m[j][j]) e 1 <= i < n + 1, ou seja,
// traço = (S j : 0 <= j < i : m[j][j]) e 1 <= i <= n,
// que implica a CI, pois é mais forte que a CI.

• Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
CI e ¬G implica CO.

CI e ¬G: traço = (S j : 0 <= j < i : m[j][j]) e 0 <= i <= n e i = n, ou seja,
traço = (S j : 0 <= j < n : m[j][j]) e 0 <= n <= n e i = n, ou seja,
traço = (S j : 0 <= j < n : m[j][j]) e V e i = n, que implica
CO':  traço = (S j : 0 <= j < n : m[j][j]), que por sua vez implica
CO: traçoDe = (S j : 0 <= j < n : m[j][j]).

Questão 5

Explique porque, numa determinada máquina, sucede a seguinte situação:

int n = 2147483647;
++n;
cout << n << endl; // Aparece no ecrã -2147483648

Se lhe parecer conveniente para a explicação, admita que os int têm três bits.

[cotação: 2]

R: Ver Capítulo 2 das Folhas Teóricas, Secção 2.3 (Tipos básicos), Subsecção 2.3.1 (Tipos aritméticos).