Exame de 1ª Época/Melhoria da Frequência Introdução à ...home.iscte-iul.pt/~mms/courses/ip/2003-2004/provas/... · 12. Deve-se poder ver o estado actual da conferência, i.e.,

Exame de 1ª Época/Melhoria da Frequência de Introdução à Programação

1/34

Recibo do Exame de 1ª Época/Melhoria da Frequência (riscar o que não interessa) Introdução à Programação (IGE e ETI), 2004/3/2, 1º semestre de 2003/2004, ISCTE

Nome do aluno: ..............................................................................................................................................

Número do aluno: ...........................................................................................................................................

Assinatura do docente: ....................................................................................................................................

Exame de 1ª Época/Melhoria da Frequência

Introdução à Programação

IGE e ETI

2004/3/2 – 1º semestre de 2003/2004

ISCTE Notas:

• Leia atentamente todo o enunciado (incluindo estas notas) antes de começar a prova.

• Esta prova tem 5 questões (4 para quem quiser realizar a frequência).

• Duração: 3:30h (três horas e trinta minutos) para o exame, e 1:45h para a frequência.

• As alíneas e questões só para exame estão marcadas com [Só exame!]. Quem quiser realizar apenas a frequência não lhes deverá responder.

• A prova deve ser efectuada sem consulta.

• Sobre a sua secretária só pode estar o enunciado, uma caneta e um documento de identificação (coloque pastas, telemóveis, estojos e quaisquer outros objectos sobre a cadeira ao seu lado).

• Desligue o telemóvel.

• Não é permitido sair da sala temporariamente durante a realização da prova, nem mesmo para ir à casa de banho.

• Deve responder a todas as questões no próprio enunciado, nos espaços reservados.

• Use a página em branco no final do enunciado para rascunho.

• Não destaque as folhas do enunciado (nem mesmo a de rascunho).

• Preencha o seu nome e número em todos os locais previstos, incluindo o recibo (não o destaque). Este recibo 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. Assinale em todos os locais previstos se pretende realizar o exame ou a frequência!

• As cotações encontram-se abaixo de cada alínea (total de 20 valores para o exame e de 12 valores para a frequência, posteriormente ajustados a 20 valores).

• As notas serão afixadas até às 19:00h de segunda-feira, dia 8 de Março de 2004.

• A revisão de provas terá lugar das 8:00h às 9:00h de quarta-feira, dia 10 de Março de 2004, no gabinete D6.18.

• As orais terão lugar a partir das 8:00h de sexta-feira, dia 12 de Março de 2004, no gabinete D6.18, devendo os interessados inscrever-se enviando uma mensagem de correio electrónico para [email protected] até às 18:00h de quinta-feira, dia 10 de Março de 2004.

• Boa sorte.


2/34

Questão 1 Assinale com V (Verdadeiro) as expressões que estão correctas e com F (Falso) as que estão incorrectas.

Os quadrados podem ser deixados em branco ou ser preenchidos com V ou F.

Em geral as alíneas podem ter zero ou mais respostas correctas. Cada resposta correctamente assinalada vale 0,5 valores. Respostas incorrectas correspondem a um desconto de 0,5 valores. Respostas em branco valem 0 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 (que não tem erros lógicos nem sintácticos):

#include <iostream>

#include <vector>

using namespace std;

class Portagem {

public:

Portagem(int const número_de_vias = 1, bool const abertas = false);

void abreAVia(int const índice_da_via);

void fechaAVia(int const índice_da_via);

void abreTodasAsVias();

void fechaTodasAsVias();

int númeroDeVias() const;

bool estáAbertaAVia(int const índice_da_via) const;

bool háAlgumaViaAberta() const;

private:

vector<bool> vias_abertas;

};

// ...

int main()

{

Portagem pontinha(3, true);

Portagem const castelo_branco(2);

// ...

}


3/34

Identificação

Tipo de prova a realizar: Exame de 1ª época/Melhoria da Frequência (riscar o que não interessa)

Nome do aluno: ..............................................................................................................................................

Número do aluno: ...........................................................................................................................................

1.1 Sabendo que o construtor da classe Portagem permite criar objectos que representam portagens com número_de_vias vias, estando estas inicialmente abertas ou não de acordo com o valor do parâmetro abertas, quais das seguintes implementações do construtor estão correctas?

� Portagem::Portagem(int const número_de_vias, bool const abertas) : número_de_vias(número_de_vias), abertas(abertas) { }

� Portagem::Portagem(int const número_de_vias, bool const abertas) : vias_abertas(número_de_vias, abertas) { }

� Portagem::Portagem(int const número_de_vias, bool const abertas) { vias_abertas = vector<bool>(número_de_vias, abertas); }

� Portagem::Portagem(int const número_de_vias, bool const abertas) : vias_abertas(número_de_vias) { }

[cotação: 2]

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?

� pontinha.vias_abertas[0] = true;

� castelo_branco.abreTodasAsVias();

� int n = pontinha.númeroDeVias();

[cotação: 1,5]

1.3 Assuma que as seguintes instruções são parte do corpo de um método de instância da classe Portagem que não tem quaisquer parâmetros e no qual não são declaradas variáveis ou constantes. Quais das seguintes instruções estão correctas?

� bool verdadeiro = háAlgumaViaAberta();

� bool verdadeiro = castelo_branco.háAlgumaViaAberta();

� vias_abertas = false;

[cotação: 1,5]


4/34

Questão 2 Durante uma conferência são apresentados artigos que passam por um processo prévio de submissão e revisão. Como esse processo é moroso e burocrático, embora essencial para garantir a qualidade das apresentações e posteriores publicações, os organizadores de uma dada conferência decidiram automatizá-lo. Para isso começaram por escrever um conjunto de definições e requisitos para o sistema a desenvolver, que depois enviaram para a equipa de desenvolvimento. O resultado foi a seguinte lista de requisitos:

1. Podem-se registar na conferência cientistas que farão parte da sua comissão técnica, i.e., que se encarregarão de rever os artigos que lhes forem atribuídos. A esses cientistas dá-se o nome de revisores.

2. Dos revisores, neste caso, só é necessário conhecer o nome, que para simplificar se assume consistir numa única palavra. Não se permitem nomes de revisores nulos (i.e., vazios).

3. Não se pode registar na conferência mais do que um revisor com o mesmo nome.

4. Podem-se registar na conferência artigos, que passarão por um processo de revisão. Estes artigos têm um título não-nulo, que se admite consistir numa única palavra, e uma lista de nomes não-nulos de autores, contendo pelo menos um autor, não se permitindo repetições de nomes de autores.

5. Não se pode registar na conferência mais do que um artigo com o mesmo título.

6. Deve ser possível também registar na conferência um processo de revisão, ou simplesmente uma revisão. Uma revisão relaciona um revisor, identificado pelo nome, com um artigo, identificado pelo título. Uma revisão pode estar incompleta, o que significa que o revisor ainda não deu a sua opinião acerca do artigo, ou completa. Se estiver completa, é possível saber se o revisor aceitou ou rejeitou o artigo, e quais os seus comentários (que para simplificar se admitem consistir no máximo numa única palavra e que podem ser nulos).

7. Não é possível registar revisões repetidas, i.e., duas ou mais revisões do mesmo artigo pelo mesmo revisor.

8. Deve ser possível indicar que um determinado revisor terminou a revisão de um determinado artigo, indicando se o aceitou ou não, e qual o seu comentário. Esta acção não pode ser repetida, i.e., se uma revisão está completa, não é possível completá-la de novo ou alterá-la.

9. Um artigo só se considera revisto quando todas as revisões a ele associadas estiverem completas.

10. Um artigo só é aceite se estiver revisto e tiver sido aceite por todas as revisões a ele associadas.

11. Um artigo é considerado rejeitado se estiver revisto e se pelo menos uma das suas revisões o tiver rejeitado.

12. Deve-se poder ver o estado actual da conferência, i.e., saber qual a lista de artigos aceites, incluindo as correspondentes revisões, qual a lista de artigos rejeitados, também incluindo as respectivas revisões, e qual a lista de artigos ainda por rever, de novo incluindo as respectivas revisões.


5/34

Identificação


Nome do aluno: ..............................................................................................................................................

Número do aluno: ...........................................................................................................................................

2.1 [Só exame, mas veja a classe na mesma!] Uma das classes fundamentais para implementar o sistema em causa é a classe Artigo, que representa os artigos da conferência. A equipa de desenvolvimento, analisados os requisitos acima, decidiu definir a classe como se pode ver abaixo:

/** Representa artigos de uma conferência. @invariant titulo_ ≠ "" ∧ 1 ≤ autores_.size() ∧ (Q j : 0 ≤ j < autores_.size() : autores_ [j] ≠ "") ∧ (Q i : 0 ≤ i < autores_.size () : (Q j : i + 1 ≤ j < autores_.size () : autores_ [j] ≠ autores_ [i])). Note-se que o último termo da CIC serve para indicar que não pode haver autores repetidos num artigo. */ class Artigo { public: /** Constrói um novo artigo com título e autores dados. @pre titulo ≠ "" ∧ 1 ≤ autores.size() ∧ (Q j : 0 ≤ j < autores.size() : autores[j] ≠ "") ∧ (Q i : 0 ≤ i < autores.size () : (Q j : i + 1 ≤ j < autores.size () : autores[j] ≠ autores[i])). @post titulo() = titulo ∧ autores() = autores. */ Artigo(string const& titulo, vector<string> const& autores);

/** Devolve o titulo do artigo. @pre V. @post titulo = título do artigo. */ string const& titulo() const;

/** Devolve um vector com os autores do artigo. @pre V. @post autores = vector com os autores do artigo. */ vector<string> const& autores() const;

/** Mostra o artigo no ecrã. @pre V. @post Ecrã contém, para além do que continha inicialmente: a) Nomes dos autores, separados por vírgula e terminados num ponto. b) Título do artigo, entre aspas, terminado por ponto. */ void mostra() const;

private: string titulo_; vector<string> autores_;

/** Indica se a condição invariante da classe é verdadeira. @pre V. @post cumpreInvariante = (titulo_ ≠ "" ∧ 1 ≤ autores_.size() ∧ (Q j : 0 ≤ j < autores_.size() : autores_[j] ≠ "") ∧ (Q i : 0 ≤ i < autores_.size () : (Q j : i + 1 ≤ j < autores_.size () : autores_[j] ≠ autores_[i]))). */ bool cumpreInvariante() const; };

Defina completamente o predicado Artigo::cumpreInvariante().

[cotação: 1]


6/34


7/34

2.2 Da mesma forma que anteriormente, decidiu-se definir uma classe para representar o conceito de revisão. Essa classe chama-se Revisao e está listada abaixo:

/** Representa uma revisão de um artigo por um dado revisor. @invariant titulo_do_artigo ≠ "" ∧ nome_do_revisor ≠ "" ∧ (esta_completa ∨ ¬(artigo_foi_aceite ∨ comentario_ ≠ "")). */ class Revisao { public: /** Constrói uma nova revisão. @pre titulo_do_artigo ≠ "" ∧ nome_do_revisor ≠ "". @post tituloDoArtigo() = titulo_do_artigo ∧ nomeDoRevisor() = nome_do_revisor ∧ ¬estaCompleta(). */ Revisao(string const& titulo_do_artigo, string const& nome_do_revisor);

/** Regista resultado da revisão. @pre ¬estaCompleta(). @post estaCompleta() ∧ artigoFoiAceite() = artigo_foi_aceite ∧ comentario() = comentario. */ void registaResultado(bool const artigo_foi_aceite, string const& comentario);

/** Devolve o titulo do artigo a rever. @pre V. @post tituloDoArtigo = título do artigo a rever. */ string const& tituloDoArtigo() const;

/** Devolve o nome do revisor. @pre V. @post nomeDoRevisor = nome do revisor. */ string const& nomeDoRevisor() const;

/** Devolve o comentário do revisor. @pre estaCompleta(). @post comentario = comentário do revisor. */ string const& comentario() const;

/** Mostra a revisão no ecrã. @pre V. @post Ecrã contém, para além do que continha inicialmente: a) Nome do revisor, seguido de dois-pontos. b) Se a revisão está incompleta, simplesmente "incompleta." c) Caso contrário, "aceite" ou "rejeitado", conforme o caso. d) " por " seguido do comentário. */ void mostra() const;

/** Indica se a revisão está completa. @pre V. @post estaCompleta = revisão está completa. */ bool estaCompleta() const;

/** Indica se o artigo foi aceite ou se, pelo contrário, foi rejeitado. @pre estaCompleta(). @post artigoFoiAceite = artigo foi aceite pelo revisor. */ bool artigoFoiAceite() const;

private: string titulo_do_artigo; string nome_do_revisor; bool esta_completa; bool artigo_foi_aceite; string comentario_;

/** Indica se a condição invariante da classe é verdadeira. @pre V. @post cumpreInvariante = (titulo_do_artigo ≠ "" ∧ nome_do_revisor ≠ "" ∧ (esta_completa ∨ ¬(artigo_foi_aceite ∨ comentario_ ≠ ""))). */ bool cumpreInvariante() const; };


8/34

Defina completamente o método Revisao::registaResultado(), não se esquecendo de verificar explicitamente, através de instruções de asserção, a pré-condição (PC), a condição objectivo (CO) e condição invariante de classe (CIC).

[cotação: 1]


9/34

2.3 Uma outra classe fundamental é a que representa uma conferência em preparação. Essa classe, chamada Conferencia, deve possuir os registos dos revisores, artigos e revisões que os relacionam, e permitir as seguintes operações:

• Construir uma nova conferência, sem artigos, sem revisores e sem revisões.

• Registar um novo artigo, cujo título não pode constar já na conferência.

• Registar um novo revisor na conferência, dado o seu nome. O nome do revisor não pode ser repetido.

• Registar a revisão de um artigo com um dado título por um revisor com um dado nome. Não pode existir já na conferência uma outra revisão do mesmo artigo pelo mesmo revisor.

• Registar o resultado de uma revisão de um artigo com um dado título por um revisor com um dado nome. Tem de haver já uma revisão desse artigo por esse revisor, revisão essa que não pode estar terminada. O resultado indica se o artigo foi aceite (ou não) e um comentário.

• Obter um artigo dado o seu título. Assume-se que a conferência tem um artigo com esse título.

• Saber o número de artigos na conferência.

• Saber o número de revisores na conferência.

• Saber o número de revisões em falta (i.e., incompletas) na conferência.

• Saber se está registado na conferência um artigo com um dado título.

• Saber se está registado na conferência um revisor com um dado nome.

• Saber se está registada na conferência a revisão de um artigo com um dado título por um revisor com um dado nome. Se o título do artigo ou o nome do revisor não constarem na conferência, considera-se que a revisão não existe

• Saber se já há na conferência resultados da revisão de um artigo com um dado título por um revisor com um dado nome. Assume-se que essa revisão está registada na conferência.

• Saber se foi aceite um artigo com um dado título por um revisor com um dado nome. Assume-se que essa revisão está registada na conferência e que já há tem resultados disponíveis.

• Saber se um artigo foi aprovado. I.e., se já foram terminadas todas as suas revisões com a respectiva aceitação. Um artigo sem quaisquer revisões considera-se aprovado. Admite-se que o artigo está registado na conferência.

• Saber se um artigo foi reprovado. I.e., se já foram terminadas todas as suas revisões e houve pelo menos uma rejeição. Admite-se que o artigo está registado na conferência.

• Saber se um artigo está por rever, i.e., se alguma das suas revisões está ainda por completar. Admite-se que o artigo está registado na conferência.

• Mostrar o estado da conferência.

• Mostrar as revisões de um artigo com um dado título. Admite-se que o artigo está registado na conferência.


10/34

Defina a classe Conferencia:

• Coloque a documentação da classe, indicando a respectiva CIC.

• Não defina nenhum dos métodos da classe.

• Coloque a documentação, incluindo PC e CO, apenas nas operações que precisar de definir nas próximas alíneas. I.e., quem está a responder para frequência tem de colocar menos comentários de documentação.

• Indique claramente, usando a notação C++ apropriada, quais das operações não alteram a instância implícita.

• Declare o predicado necessário para saber se a CIC se verifica.

[cotação: 2]


11/34


12/34


13/34

2.4 Defina o método da classe Conferencia corresponde à operação de registo do resultado de uma dada revisão, que se admite já existir mas estar ainda incompleta. Não se esqueça de verificar explicitamente, através de instruções de asserção, a pré-condição (PC), a condição objectivo (CO) e condição invariante de classe (CIC).

[cotação: 1]


14/34

2.5 [Só exame!] Defina os métodos correspondentes às seguintes operações:

• Obter um artigo dado o seu título. Assume-se que a conferência tem um artigo com esse título.

• Saber o número de revisões em falta (i.e., incompletas) na conferência.

Não se esqueça de verificar explicitamente, através de instruções de asserção, a pré-condição (PC), a condição objectivo (CO) e condição invariante de classe (CIC).

[cotação: 2]


15/34


16/34


17/34

2.6 [Só exame!] Para implementer o sistema completo, considerou-se útil o desenvolvimento de uma classe GestorDeConferencia, que gere uma conferência, encarregando-se da interface com o utilizador. A definição da classe é:

/** Representa um gestor de conferências. @invariant V. */ class GestorDeConferencia { public: /** Gere uma conferência. @pre V. @post Uma conferência foi gerida do princípio ao fim. */ void gere();

private: Conferencia conferencia;

/** Indica se a condição invariante da classe é verdadeira. @pre V. @post cumpreInvariante = V. */ bool cumpreInvariante() const;

/** Pede dados de um novo artigo e insere na conferência. @pre V. @post A conferência tem o novo artigo, excepto se o título fornecido pelo utilizador for repetido. */ void introduzNovoArtigo();

/** Pede dados de um novo revisor e insere na conferência. @pre V. @post A conferência tem o novo revisor, excepto se o nome fornecido pelo utilizador for repetido. */ void introduzNovoRevisor();

/** Pede dados de uma nova revisão de artigo e insere na conferência. @pre V. @post A conferência tem a nova revisão, excepto se o título fornecido pelo utilizador não existir, se o nome do revisor não existir ou se já houver a revisão dada. */ void introduzNovaRevisao();

/** Pede dados de resultados de uma revisão de artigo e insere na conferência. @pre V. @post A conferência tem o novo resultado da revisão, excepto se a revisão dada não existir ou se já tiver resultados. */ void introduzResultadoDeRevisao(); };

Defina os métodos GestorDeConferencia::gere() e GestorDeConferencia::introduzNovaRevisao(). Para simplicar:

1. Não verifique o sucesso de operações de extracção do teclado.

2. Quando o utilizador se engana, ou se pede novamente sem mais comentários, ou se emite uma mensagem de erro.

Um exemplo da interacção com o utilizador que ocorre quando se invoca a operação GestorDeConferencia::gere() encontra-se na próxima página:

[cotação: 2]


18/34

1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 1 Introduza o título: Título1 Introduza o número de autores do artigo: 1 Introduza o autor 1: Autor1 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 1 Introduza o título: Título1 Título já existe na conferência. 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 1 Introduza o título: Título2 Introduza o número de autores do artigo: 0 Introduza o número de autores do artigo: 2 Introduza o autor 1: Autor1 Introduza o autor 2: Autor2 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 2 Introduza o nome: Revisor1 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 2 Introduza o nome: Revisor2

1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 3 Introduza título do artigo: Título1 Introduza o nome do revisor: Revisor1 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 3 Introduza título do artigo: Título2 Introduza o nome do revisor: Revisor1 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 3 Introduza título do artigo: Título2 Introduza o nome do revisor: Revisor3 Revisor não existe na conferência. 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 3 Introduza título do artigo: Título2 Introduza o nome do revisor: Revisor2 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 3 Introduza título do artigo: Título1 Introduza o nome do revisor: Revisor1 Esse revisor já está encarregado desse artigo.

1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 4 Introduza título do artigo: Título1 Introduza o nome do revisor: Revisor1 Introduza o resultado da revisão ([A]ceite/[R]ejeitado): a Introduza o comentário de revisão: Comentário1 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 4 Introduza título do artigo: Título2 Introduza o nome do revisor: Revisor2 Introduza o resultado da revisão ([A]ceite/[R]ejeitado): r Introduza o comentário de revisão: Comentário2 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 5 Artigos aceites: Autor1. "Título1". Revisor1: aceite, Comentário1. Artigos rejeitados: Artigos por rever: Autor1 e Autor2. "Título2". Revisor1: incompleta. Revisor2: rejeitado, Comentário2. 1. Introduzir novo artigo. 2. Introduzir novo revisor. 3. Introduzir nova revisão. 4. Introduzir resultado de revisão. 5. Estado da conferência. 6. Sair. Introduza a sua opção: 6


19/34


20/34


21/34


22/34


23/34

Identificação


Nome do aluno: ..............................................................................................................................................

Número do aluno: ...........................................................................................................................................

Questão 3 Suponha-se o seguinte quantificador:

(Max i : 0 ≤ i < n : 7 – |i - 3|)

O seu objectivo é representar o máximo de 7 – |i - 3| quando i é uma variável inteira variando entre 0 inclusive e n exclusive. No caso de n = 5, o valor deste quantificador é 7 (obtido quando i é 3). Admite-se que este quantificador tem o valor -∞ (menos infinito) quando o conjunto de possíveis valores para i for vazio, por exemplo quando n = 0.

Seja max(a, b) uma função que devolve o máximo dos seus dois argumentos. Uma propriedade interessante do quantificador anterior é:

max((Max i : 0 ≤ i < n : f(i)), f(n)) = (Max i : 0 ≤ i < n + 1 : f(i))

Considere agora a seguinte função:

/** Devolve o maior dos itens de v (devolve -∞ se o vector estiver vazio). @pre ?. @post máximoDe = (Max j : 0 ≤ j < v.size() : v[j]). */ double máximoDe(vector<double> const& v) { // Inicialização com -∞: double máximo = -numeric_limits<double>::infinity();

for(vector<int>::size_type i = 0; i != v.size(); ++i) máximo = max(máximo, v[i]);

return máximo; }

3.1 Indique a pré-condição (PC), a condição objectivo (CO), a condição invariante (CI) e a guarda (G) do ciclo usado nesta função.

[cotação: 0,5]


24/34

3.2 Prove que o ciclo está correcto verificando que:

1. 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

// ⇒ CI

2. 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 ∧ CI

passo

// ⇒ CI

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

// CI ∧ ¬G ⇒ CO

[cotação: 1,5]


25/34


26/34


27/34

Questão 4 [Só exame!] Considere a função int mmc(int const m, int const n) que devolve o mínimo múltiplo comum de dois inteiros positivos m e n.

Desenvolva, utilizando um ciclo, uma implementação da função mmc(). Siga os passos da metodologia de Dijkstra sugeridos nas alíneas desta questão.

Os seguintes cabeçalho e esqueleto do corpo da rotina devem ser respeitados:

/** Devolve o mínimo múltiplo comum de dois inteiros positivos. @pre 0 < m ∧ 0 < n. @post max(m, n) ≤ mmc ∧ mmc ÷ m = 0 ∧ mmc ÷ n = 0 ∧ (Q j : max(m, n) ≤ j < mmc : j ÷ m ≠ 0 ∧ j ÷ n ≠ 0). */ int mmc(int const m, int const n) { int mmc = max(m, n);

// Ciclo: while(G) { passo }

return mmc; }

Admita que está disponível uma função max() que devolve o maior dos seus dois argumentos.

Atenção! Use a factorização da condição objectivo!

4.1 [Só exame!] Indique a pré-condição (PC) e a condição objectivo (CO) da rotina e ainda a condição invariante (CI) do seu ciclo interno.

[cotação: 0,5]


28/34

4.2 [Só exame!] Prove que a inicialização usada no ciclo é tal que, se a PC for verdadeira, então a CI também é verdadeira após a inicialização e antes da primeira iteração do ciclo, i.e.,

// PC int mmc = max(m, n); // ⇒ CI.

[cotação: 0,5]


29/34

4.3 [Só exame!] Indique uma guarda G tal que CI ∧ ¬G ⇒ CO. Prove explicitamente que de facto CI ∧ ¬G ⇒ CO.

[cotação: 0,5]


30/34

4.4 [Só exame!] Defina um passo passo tal que 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 ∧ CI

passo

// ⇒ CI.

Prove explicitamente que de facto:

// G ∧ CI

passo

// ⇒ CI.

[cotação: 0,5]


31/34

Identificação


Nome do aluno: ..............................................................................................................................................

Número do aluno: ...........................................................................................................................................

Questão 5

5.1 Suponha o seguinte código: void mostraMenu();

void jogaNovoJogo() { …

mostraMenu(); }

void mostraMenu() { cout << “1. Jogar novo jogo.” << endl << “2. Sair.” << endl << endl << “Introduza a sua opção: “; int opção; cin >> opção;

if(opção == 1) jogaNovoJogo(); }

int main() { mostraMenu(); }

Identifique os principais problemas desta forma como este código está estruturado e explique como os resolveria.

[cotação: 1]


32/34

5.2 [Só exame!] Suponha que um aluno, durante o desenvolvimento do Trabalho Final de IP, desenvolveu todo o código, tirou todos os erros, pôs o programa a funcionar e, no dia antes de entregar a resolução aos docentes, e porque isso era obrigatório de acordo com o enunciado, explicitou a CIC de todas as classes através da definição de predicados cumpreInvariante(), e colocou instruções de asserção usando esses predicados em todos os métodos públicos das várias classes do seu trabalho, tendo em seguida compilado e testado o programa sem detectar quaisquer erros.

Explique o que fez o aluno de errado do ponto de vista do método de desenvolvimento da sua resolução do Trabalho Final, o que deveria ter feito e o que ganharia com isso.

[cotação: 1]


33/34


34/34

Documents

Exame de 1ª Época/Melhoria da Frequência Introdução à ...home.iscte-iul.pt/~mms/courses/ip/2003-2004/provas/... · 12. Deve-se poder ver o estado actual da conferência, i.e.,