Correcção do teste

Frequência - 8 de Julho de 1999

• Condições gerais da prova
• Questões

Condições gerais da prova

• Autorizada consulta de documentação própria;
• Tempo de realização da prova: 1 hora e 30 minutos.

Questões

1. Escreva um módulo em linguagem Erlang denominado treebin, que manipule árvores binárias ordenadas, representadas através de túplos de 3 elementos:

• O 1º corresponde ao elemento da folha;
• O 2º é um tuplo com a sub-árvore de valores menores que o 1º elemento;
• O 3º é um tuplo com a sub-árvore de valores maiores que o 1º elemento.

    Ex.:

{6,
	{3,
		{1,{},{}},
		{}
	},
	{9,
		{7,{},{}},
		{12,{},{}}
	}
}

1. Implemente a função treebin_insert/2, para inserção de valores ordenados;
2. Implemente a função treebin_delete/2, para apagar determinado valor;
3. Implemente a função treebin_exist/2, que indica se o valor existe ou não.

    Notas:

• A árvore não comporta valores repetidos, pelo que a inserção dum valor já existente deve ser ignorada;
• O primeiro parâmetro de cada função é o tuplo onde se realiza a operação.

Resposta:

-module(treebin).

-export([treebin_insert/2, treebin_delete/2, treebin_exist/2]).

treebin_insert( {}, Elem ) ->
	{ Elem, {}, {} };
treebin_insert( {Elem, I, S}, Elem ) ->
	{ Elem, I, S };
treebin_insert( {E, I, S}, Elem ) when Elem < E ->
	{ E, treebin_insert(I, Elem), S };
treebin_insert( {E, I, S}, Elem ) when Elem > E ->
	{ E, I, treebin_insert(S, Elem) }.

treebin_delete( {}, _ ) -> {};
treebin_delete( {E, I, S}, Elem ) when Elem < E ->
	{E, treebin_delete( I, Elem ), S};
treebin_delete( {E, I, S}, Elem ) when Elem > E ->
	{E, I, treebin_delete( S, Elem )};
treebin_delete( {Elem, I, S}, Elem ) ->
	treebin_rebalance( {}, I, S ).

treebin_rebalance( A, I, S ) ->
    A1 = treebin_inserttree( A, I ),
    A2 = treebin_inserttree( A1, S ).

treebin_inserttree( A, {} ) -> A;
treebin_inserttree( A, { Elem, I, S } ) ->
    A1 = treebin_insert(A, Elem),
    A2 = treebin_inserttree( A1, I ),
    treebin_inserttree( A2, S ).

treebin_exist( {}, _ ) -> false;
treebin_exist( {Elem, _, _}, Elem ) -> true;
treebin_exist( {E, I, S}, Elem ) when Elem < E ->
	treebin_exist( I, Elem );
treebin_exist( {E, I, S}, Elem ) when Elem > E ->
	treebin_exist( S, Elem ).

2. Suponha um sistema formado por um servidor (master) que opera a BD e os clientes que emitem operações sobre a BD. A BD consiste numa árvore binária e correspondentes operações tal como descrito na questão anterior.

As mensagens transmitidas entre servidor e clientes são descritas pelo diagrama seguinte:

1. Especifique o conteúdo das mensagens;
2. Supondo que o módulo treebin já existe, escreva um módulo em linguagem Erlang que modelize este sistema.

Resposta:

-module(questao2).

-export([master/1, dbase/0, insert/2, delete/2, exist/2]).

-define(BD, bd).

master( Node ) -> spawn(Node, ?MODULE, dbase, []).

dbase() ->
	register(?BD, self()),
	process_msg( {} ),
        io:format("fim~n").

process_msg( A ) ->
    receive
        { msg_insert, PidCliente, Elem } ->
            A2 = treebin:treebin_insert(A, Elem ),
            PidCliente ! { msg_insert_ack },
            io:format("~w inseriu ~w~n", [PidCliente, Elem] ),

            process_msg( A2 );

        { msg_delete, PidCliente, Elem } ->
            A2 = treebin:treebin_delete(A, Elem ),
            PidCliente ! { msg_delete_ack },
            io:format("~w apagou ~w~n", [PidCliente, Elem] ),

            process_msg( A2 );

        { msg_exist, PidCliente, Elem } ->
            Resposta = treebin:treebin_exist(A, Elem ),
            PidCliente ! { msg_exist_rply, Resposta },
            io:format("~w perguntou se ~w existe~n", [PidCliente, Elem] ),

            process_msg( A );

        A ->
            io:format("mensagem errada: ~w~n", [A])
    end.

insert( Node, Elem ) ->
    {?BD, Node } ! { msg_insert, self(), Elem },
    receive
        { msg_insert_ack } -> ok;
        _ -> 'mensagem errada'
    end.

delete( Node, Elem ) ->
    {?BD, Node } ! { msg_delete, self(), Elem },
    receive
        { msg_delete_ack } -> ok;
        _ -> 'mensagem errada'
    end.

exist( Node, Elem ) ->
    {?BD, Node } ! { msg_exist, self(), Elem },
    receive
        { msg_exist_rply, Resposta } -> Resposta;
        _ -> 'mensagem errada'
    end.

3. Suponha um sistema composto por vários clientes e um servidor composto por várias entidades. Os clientes requisitam funções ao servidor, que depois as enviará para a entidade competente para ser processada. Depois de processado o resultado regressa ao servidor que a encaminha para o cliente requisitante.

Pretende-se que o (sistema) servidor realize operações aritméticas básicas (+, -, *, /) , sendo cada operação realizada por uma entidade diferente.
Escreva um módulo em linguagem Erlang de forma que:

1. Os clientes usem a função de interface exec/3: exec(Operador, Op_1, Op_2);
2. O sistema servidor deverá ser acedido através do nome calculadora;
3. O sistema servidor deverá ser um sistema robusto, pelo que o servidor deverá recriar automaticamente os processos caso estes "morram";
4. Os processos deverão garantir resultados apropriados com os operandos, mesmo que estes sejam inválidos ou incompatíveis.

Resposta:

-module(questao3).

-export([start/1, calculadora/0, processo/1, exec/3]).

-define(CALCULADORA, calculadora).
-define(NODE, andy@pcigb10).

start( ?NODE ) ->
    spawn(?NODE, ?MODULE, calculadora, []).

calculadora() ->
    register( ?CALCULADORA, self() ),
    process_flag(trap_exit, true ),
    L = cria_processos(['*', '+', '-', '/']),
    loop( L ).

loop( L ) ->
    receive
        { calcular, Pid, Operador, Op1, Op2 } ->
            case escolhe_processo( L, Operador ) of
                error ->
                    Pid ! { resultado, 'operacao indisponivel' };
                Processo ->
                    Processo ! { calcula, Operador, Op1, Op2 },
                    receive
                        { resultado, Resultado } -> Pid ! { resultado, Resultado };
                        _ -> Pid ! { erro }
                    end
            end,
            loop( L );

        { 'EXIT', Pid, Razao } ->
            LNova = recria_processo( Pid, L ),
            loop( LNova )
    end.

escolhe_processo( L, Operador ) ->
    case [ X || X <- L, element(1, X) == Operador] of
        [ { Operador, Pid } ] -> Pid;
        _ -> error
    end.

cria_processos( [] ) -> [];
cria_processos( [ Operador| L ] ) ->
    [ { Operador, spawn_link( ?MODULE, processo, [Operador]) } | cria_processos( L ) ].

recria_processo( Pid, L ) ->
    [ { Pid, Operador } ] = [ X || X <- L, element(2, X) == Pid ],
    [ ProcessoNovo ] = cria_processos( [ Operador ] ),
    [ ProcessoNovo | [ X || X <- L, element(2, X) =/= Pid ] ].

processo( Operador ) ->
    receive
        { Calcula, Operador, Op1, Op2 } ->
            case Operador of
                '+' ->    Resultado = Op1 + Op2;
                '-' ->    Resultado = Op1 - Op2;
                '*' ->    Resultado = Op1 * Op2;
                '/' ->    if
                            Op2 =/= 0 -> Resultado = Op1 / Op2;
                            true -> Resultado = 'divisao por zero'
                        end
            end,
            ?CALCULADORA ! { resultado, Resultado };

        Msg ->
            io:format("mensagem ~w nao processada.~n", Msg)
    end,
    processo( Operador ).

exec(Operador, Op1, Op2 ) ->
    { ?CALCULADORA, ?NODE } ! { calcular, self(), Operador, Op1, Op2 },
    receive
        { resultado, Resultado } -> Resultado;
        Msg -> io:format("~w.~n")
    end.

Última actualização: 14 Março 2000