Última alteração: Janeiro 24, 2002

ENGENHARIA DE CONTROLE E AUTOMAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Nivio Ziviani

Monitora: Claudine Santos Badue

Trabalho Prático 2

Data de Entrega: 21-fevereiro-2002


Comentários Gerais

1.
Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.
2.
Penalização por atraso: vide texto apresentação da disciplina.
3.
Este trabalho exercita conceitos apresentados no Capítulo 3 do livro de Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1986.
4.
Vão valer pontos clareza, indentação e comentários no programa.


O que deve ser apresentado:

1.
Listagem do programa em Pascal.
2.
Listagem dos testes executados.
3.
Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.
4.
Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).


Avaliação:

1.
Execução
(a)
Execução correta: 20%
(b)
Saída legível: 10%
2.
Estilo de programação
(a)
Código bem estruturado: 10%
(b)
Código legível: 10%
3.
Documentação
(a)
Descrição das estruturas de dados e principais decisões: 35%
(b)
Estudo da complexidade do tempo: 15%


Descrição do Problema


Um estudante de Ciência da Computação da Universidade Federal de Minas Gerais, Jorge Monte Carlo, resolveu comemorar o final do semestre escolar. Na sua cervejaria favorita do baixo Belô, a antiga Cervejaria Brasil (que hoje não existe mais), ele consumiu vasta quantidade de cerveja, e logo após estava bastante xumbregado. No momento de sair, a polícia estava nas ruas, pronta para prender quem estivesse dirigindo sob influenza. Apesar do estado inebriante de sua mente ele percebeu que poderia evitar a polícia enquanto dirigia para casa.

Sua estratégia para tentar chegar em casa foi a seguinte: ao chegar em uma esquina, ele olharia em direção aos cruzamentos seguintes, um de cada vez, e prosseguiria em direção à primeira esquina onde não houvesse sinal de polícia. Com um pouco de esperteza, ele percebeu que poderia caminhar em ziguezague, mas de forma que não voltasse a um mesmo cruzamento que já tivesse visitado. Chegando a um cruzamento, se a única rua não bloqueda fosse exatamente aquela por onde havia vindo, ele retornaria por esta rua e continuaria o algoritmo a partir do cruzamento anterior.

Apesar de a polícia estar em massa pelas ruas na noite em questão, ela poderia cobrir apenas 40% das esquinas, isto é, a probabilidade de que Jorge Monte Carlo possa prosseguir em direção a qualquer esquina deve ser p = 0,6 e a probabilidade de que a polícia esteja ocupando qualquer esquina é p = 0,4. Após sua saída, a polícia chegou à Cervejaria Brasil. Caso ele retornasse pelo caminho utilizado até a cervejaria, seria preso, autuado e encaminhado diretamente para o xadrez (com pagamento de multa e sem direito a fiança).

A figura abaixo representa o mapa adaptado do baixo Belô, mostrando a localização da Cervejaria Brasil (Aimorés com Maranhão), a casa do Jorge Monte Carlo (Rua Rio Grande do Norte com Tomé de Souza), e a casa da sua namorada (Pernambuco com Gonçalves Dias), lugar igualmente aceitável como refúgio para curtir o pileque. O problema proposto é o seguinte: encontre a probabilidade de que Jorge Monte Carlo seja capaz de chegar em casa ou na casa da namorada, partindo da Cervejaria Brasil.



\psfig {figure=tp2fig.eps,width=3.5in}

Como Submeter o Programa

A versão submetida deve gerar uma única tentativia de chegar em casa ou na casa da namorada a partir da Cervejaria Brasil. Imprima o resultado dessa tentativa ("Sucesso" ou "Insucesso"), bem como a situação de cada esquina ("S" tem policial e "N" não tem policial) linha a linha, sendo a esquina de número 1 Grão Pará X Carandaí, a de número 2 na mesma linha Grão Pará X Timbiras, a de número 10 na linha abaixo Maranhão X Carandaí, e assim sucessivamente, até a de número 72 na linha 8 Pernambuco X Tomé de Souza.

Observações

1.
Um dos usos mais importantes de computadores é na simulação de sistemas físicos para os quais o uso da matemática é difícil ou impossível. Ao estimar a probabilidade de ocorrência de um evento complexo, pode-se simular um número independente de amostras da situação e computar a proporção de vezes em que o evento ocorre. Este método é conhecido como o Método de Monte Carlo.
2.
Sugerimos que você simule 1000 tentativas de chegar em casa ou na casa da namorada a partir da Cervejaria Brasil, utilizando o sistema de computação a sua escolha, e conte o número de vezes em que Jorge Monte Carlo é bem sucedido.

Sugestão opcional: para cada vez que ele for bem sucedido compute os seguintes dados:

(a)
o número de quarteirões que ele percorreu (se ele for e voltar no mesmo quarteirão conte duas vezes);
(b)
o número médio de quarteirões que ele percorreu nas tentativas bem sucedidas;
(c)
a quantidade de vezes que cada esquina é visitada e o número médio de visitas por esquina;
(d)
Varie a percentagem de esquinas ocupadas por policiais, de forma a determinar a correlação entre esses valores e os dados computados no item anterior.

3.
Para sua simulação, você pode utilizar um gerador de números aleatórios existentes na biblioteca do sistema.

4.
Ignorar as modificações que a BHTRANS introduziu na malha de tráfego (isto é, vale qualquer sentido a esta hora da madrugada desde que a rua esteja transitável).


Nivio Ziviani
1/24/2002