Exame de CASS

Exame de CASS
5 Janeiro 2011
(duração: 2h:30m+30m)
I
Considere o seguinte procedimento escrito numa linguagem da famı́lia Java
int select(int a[], int size, int element, int b[]) {
int s = 0;
int t = 0;
while(s != size) {
if( a[s] <= element ) {
b[t] = a[s];
t = t + 1;
}
s = s + 1;
}
return t;
}
1. Indique para a função select a pré-condição mais fraca e a pós-condição mais forte que
achar conveniente. (Nota: na linguagem de asserções, pode usar o valor constante inteiro
b.length() que indica o número de elementos alocados num vector b dado.)
2. Mostre que a função select apresentada acima garante de facto a pós-condição sempre que
os seus argumentos verifiquem a pre-condição (use as condições que indicou na resposta à
alı́nea anterior). Indique todas as asserções intermédias que considerou em todos os pontos
do programa, incluindo a condição invariante do ciclo while.
II
Considere a seguinte especificação da função replace disponı́vel na classe java.lang.String.
public String replace(char oldChar, char newChar)
Returns a new string resulting from replacing all occurrences of oldChar
in this string with newChar. If the character oldChar does not occur in the
character sequence represented by this String object, then a reference to this
String object is returned. Otherwise, a new String object is created that
represents a character sequence identical to the character sequence represented
by this String object, except that every occurrence of oldChar is replaced by
an occurrence of newChar.
Examples:
"mesquite in your cellar".replace(’e’, ’o’) returns "mosquito in your collar"
"the war of baronets".replace(’r’, ’y’) returns "the way of bayonets"
Parameters:
oldChar - the old character.
newChar - the new character.
Returns:
a string derived from this string by replacing every occurrence of oldChar
with newChar.
1
1. Defina um modelo (isto é, um programa equivalente) da função replace na linguagem imperativa base usada nas aulas. (Nota: Pode substituir a string a que se aplica a operação
(objecto this) e a string resultado, por dois parâmetros (char[]) da função modelo.)
2. Para o modelo que construiu na alı́nea anterior, defina as pré-condições e a pós-condições
que achar mais adequadas.
3. Justifique detalhadamente usando lógica de Hoare, que o seu modelo da função replace
satisfaz a pós-condição se for executado num estado que satisfaça a pré-condição.
III
Este exercı́cio trata de controlo de concorrência usando monitores programados correctamente em
Java. Considere o problema de implementar uma matriz de acesso concorrente para processamento
de uma imagem através de filtros. Considere uma classe Matrix, que implementa um constructor
que aceita a largura e altura da matriz, os métodos int get(int i,int j) e void set(int i,
int j, int v). Tendo em conta que a aplicação de filtros a uma imagem normalmente requer
ler uma quantidade de grande de pontos em posições adjacentes ao ponto que se quer modificar,
pretende-se suportar o processamento de vários pontos em paralelo. Apresente o código de uma
classe wrapper, CMatrix que disponibilize a classe Matrix a um número indeterminado de threads.
A sua implementação deverá assegurar como invariante que não existem acessos simultâneos de
escrita à matriz (races).
1. Apresente o código da sua solução. Explique que variáveis-condição são necessárias para
definir o monitor, e qual é a asserção associada a cada uma. Indique também para cada
método pré-condições adequadas.
2. Exprima a invariante da classe, e argumente que ela é válida para uso de CMatrix’s por um
número arbitrário de threads, da forma mais rigorosa possı́vel.
IV
Imagine que se pretende definir um algoritmo de análise estática para programas imperativos
simples (declaração, afectação, if-then, while e output), que apenas manipulam valores inteiros e
que dispõem das quatro operações usuais e comparação de igualdade (linguagem SPL usada nas
aulas teóricas). Pretende-se que a análise seja utilizada para eliminar variáveis cujo valor nunca
é utilizado (e a respectiva expressão de inicialização) e para melhorar a alocação de variáveis a
registos no processo de compilação.
1. Explique que informação é necessário associar a cada nó de um CFG (grafo de fluxo de
controlo) para realizar a análise, usando a técnica geral abordada na disciplina.
2. Indique, para cada tipo de nó num CFG, como a informação a ele associada é calculada
com base na informação associada aos seus predecessores e antecessores no CFG.
3. É possı́vel que a sua análise não indique todas as variáveis num programa que seria possı́vel
eliminar? Justifique com exemplos concretos.
4. Aplique a técnica que definiu acima ao programa seguinte e enuncie quais os resultados que
se extraem da análise estática, e use-os para optimizar o seguinte programa:
int x,y,z,v,w;
x = 0;
y = x + 1;
z = 2*x;
v = 0;
while( z < 100 ) {
if( x%2 == 1 ) {
v = v + 1;
w = x + y + z;
}
z = 2*v;
}
out v;
2