Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Assinatura do docente: ________________________________________

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Turma: ____________

Notas:

• Leia atentamente todo o enunciado (incluindo estas notas) antes de começar a prova.
• Esta frequência tem cinco (5) questões.
• Duração: 1:30h (uma hora e trinta minutos).
• A prova deve ser efectuada sem consulta.
• Sobre a sua secretária só pode estar o enunciado e uma caneta (coloque pastas, roupa, telemóveis, etc. sobre a cadeira ao seu lado).
• Desligue o telemóvel.
• Deve responder a todas as questões no próprio enunciado, nos espaços reservados.
• Use as páginas em branco no final do enunciado para rascunho.
• Não destaque as folhas do enunciado (nem mesmo as de rascunho).
• Preencha o seu nome e número no recibo (não o destaque). Este ser-lhe-á entregue, assinado por um docente, depois da prova.
• Só um recibo assinado servirá de prova de que entregou a resolução deste enunciado.
• As cotações encontram-se abaixo de cada alínea (total de 20 valores).
• As notas serão afixadas até às 16:00h de quinta-feira dia 21 de Fevereiro de 2002.
• A revisão de provas terá lugar das 14:30 às 16:00h de sexta-feira dia 22 de Fevereiro de 2002 no gabinete 11.
• Boa sorte.

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?

__  Lâmpada a;
__  Lâmpada a(Lâmpada::apagada);
__  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?

__  Lâmpada a = vigia;
__  vigia.apaga();
__  bool estado = vigia.estáAcesa();
__  cout << vigia.estado;

 [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?

__  estáAcesa() = true;
__  estado = false;

 [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;
}

__  50
__  0
__  25
__  26

 [cotação: 0,5]

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

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]

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 removeMensagemNaPosicao(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<MensagensDeTexto> 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]

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]

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

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]

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.
• 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
• Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
CI e ¬G implica CO.

[cotação: 1,5]

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

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]