Upload
li-cristiane
View
148
Download
3
Embed Size (px)
Citation preview
OBI – Modalidade Iniciação: Métodos e Técnicas para a Resolução de Questões do Tipo Ordenação Linear
Prof. Wellington Santos MartinsInstituto de Informática, Universidade Federal de Goiás
Questão do Tipo Ordenação Linear Problemas envolvendo a ordem de objetos (variáveis - pessoas, locais, coisas, eventos etc);
Possuem 2 conjuntos de variáveis: Variável base: determina uma ordem - uma estrutura linear (reta) - desenhada na horizontal ou vertical;
Variável livre: será atribuída às posições determinadas pela variável base;
Para um problema envolvendo 6 variáveis base e 6 variáveis livres, temos 720 possibilidades!
As regras, definidas no cenário da questão e nas perguntas, reduz este número significativamente.
04/15/232 @copyright by Wellington Santos Martins
Tipos de Regras• Posicionamento:
associa um objeto a uma posição específica de um arranjo ordenado.
• Atribuição: associa objetos a grupos distintos.
• Sequenciamento: indica uma relação de ordem, do tipo antes-depois, entre objetos de um arranjo ordenado.
• Combinação: indica uma relação do tipo junto-separado, entre objetos dentro de um grupo ou um arranjo ordenado.
• Condicional: indica uma relação condicional, do tipo se-então, entre objetos de grupos ou de arranjos ordenados.
04/15/23@copyright by Wellington Santos Martins
3
Tipos de Problemas vs Tipos de Regras
• Posicionamento: Usada somente em questões do tipo Ordenação.
• Atribuição: Usada somente em questões do tipo Agrupamento.
• Sequenciamento: Usada somente em questões do tipo Ordenação. É a regra mais comum neste tipo de questão.
• Combinação: Usada tanto em questões do tipo Ordenação quanto Agrupamento.
• Condicional: Usada tanto em questões do tipo Ordenação quanto Agrupamento. É a regra mais comum em questões to tipo Agrupamento.
04/15/23@copyright by Wellington Santos Martins
4
Método para resolver uma questão de Ordenação Linear Leia o cenário e as regras atentamente; Faça anotações relacionadas ao cenário e às regras; Liste as variáveis declaradas na questão; Faça um diagrama representando os conjuntos de variáveis;
Faça um diagrama representando as regras; Faça inferências com relação às variáveis e às regras; Obtenha regras adicionais “ocultas” – que podem ser deduzidas a partir das regras e estrutura da questão;
Use as regras e as inferências para resolver a questão.
04/15/235 @copyright by Wellington Santos Martins
Exemplo 1: Vagas de Estacionamento (OBI-2009-F2N1)Em um prédio de uma companhia existem seis vagas de estacionamento, separadas das demais vagas, para os diretores da empresa. Elas estão dispostas uma ao lado da outra e são numeradas da esquerda para a direita de um a seis. Estas vagas são ocupadas por exatamente seis carros: C, D, F, H, O e V. As seguintes regras também são aplicadas:• Há exatamente três carros entre V e D. • Existe no mínimo um carro entre O e F. • C é adjacente a somente um único carro.
04/15/236 @copyright by Wellington Santos Martins
Analisando o CenárioVagas de Estacionamento (OBI-2009-F2N1)
Em um prédio de uma companhia existem seis vagas de estacionamento, separadas das demais vagas, para os diretores da empresa. Elas estão dispostas uma ao lado da outra e são numeradas da esquerda para a direita de um a seis. Estas vagas são ocupadas por exatamente seis carros: C, D, F, H, O e V.
Liste as Variáveis:Vagas (base): 1, 2, 3, 4, 5, 6Carros (livre): C, D, F, H,O, V
Faça um Diagrama das Variáveis:D F H O VC
2 3 4 5 61
A variável “Vagas” é escolhida como base visto que possui uma ordem inerente
04/15/237 @copyright by Wellington Santos Martins
Analisando as RegrasAs seguintes regras também são aplicadas:• Há exatamente três carros entre V e D. • Existe no mínimo um carro entre O e F. • C é adjacente a somente um único carro.
D F H OC
2 3 4 5 61
V
D V
V D
V D
V/D D/VV D
D V
D V
04/15/238 @copyright by Wellington Santos Martins
Diagrama de blocos representando a regra
Diagrama de disponibilidade/ocupação representando as Inferências
Analisando as RegrasAs seguintes regras também são aplicadas:• Há exatamente três carros entre V e D. • Existe no mínimo um carro entre O e F. • C é adjacente a somente um único carro.Diagrama:
Existem muitas possibilidades para a segunda regra! Vamos representar somente a condição que não pode acontecer.
O/F F/O ouO F
F O
04/15/239 @copyright by Wellington Santos Martins
Diagrama de blocos representando a regra
Analisando as RegrasAs seguintes regras também são aplicadas:• Há exatamente três carros entre V e D. • Existe no mínimo um carro entre O e F. • C é adjacente a somente um único carro.Diagrama:
D F H OC
2 3 4 5 61
C/? ?/CV
CC C C
04/15/2310 @copyright by Wellington Santos Martins
Diagrama de ocupação representando as Inferências
Diagramas das Regras e Inferências Produzidas
D F H OC
2 3 4 5 61
V
CC C C
D V
V D
O F
F O
V/D D/V
04/15/2311 @copyright by Wellington Santos Martins
Diagrama de blocos representando as regras
Diagrama de disponibilidade/ocupação representando as Inferências
Respondendo a 1ª pergunta1. Qual das seguintes opções é uma lista completa e correta de carros ocupando as vagas da esquerda para a direita?(A) V,O,C,F,D,H. (B) C,D,H,O,V,F. (C) C,V,O,F,H,D. (D) D,O,H,F,V,C. (E) C,F,V,O,H,D.D F H OC
2 3 4 5 61
V
CC C C
D V
V D
(A) Errada pois C não pode estar na terceira vaga;(B) Errada pois existem somente dois carros entre D e V;(C) Errada pois não existe nenhuma vaga entre O e F;(D) Correta! (E) Errada pois V não pode estar na terceira vaga;
O F
F O V/D D/V
04/15/2312 @copyright by Wellington Santos Martins
Respondendo a 2ª pergunta2. Qual das seguintes afirmações pode ser verdadeira?(A) D está na terceira vaga a partir da esquerda. (B) C está imediatamente ao lado de O. (C) O está na terceira vaga a partir da esquerda. (D) V está na quarta vaga a partir da esquerda. (E) D está imediatamente ao lado de H.
(A) Falsa pois D não pode estar na terceira vaga;(B) Falsa pois não terá como posicionar D e V;(C) Verdadeira;(D) Falsa pois V não pode estar na quarta vaga; (E) Falsa pois força F ser vizinho de O;
O F F O
04/15/2313 @copyright by Wellington Santos Martins
2 3 4 5 61V D
V D
D V
D V
H
H
H
H
C
C
C
C
Respondendo a 3ª pergunta3. Qual das seguintes opções é uma vaga que H pode ocupar? (A) 1. (B) 2. (C) 3. (D) 5. (E) 6.
(A) Falsa pois não existirá 3 vagas entre D e V;(B) Falsa pois forçará F ficar ao lado de O;(C) Verdadeira;(D) Falsa pois forçará F ficar ao lado de O;(E) Falsa pois não existirá 3 vagas entre D e V;
O F
F O
04/15/2314 @copyright by Wellington Santos Martins
2 3 4 5 61V D
V D
D V
D V
H
H
H
H
C
C
C
C
Respondendo a 4ª pergunta4. Qual das seguintes opções deve obrigatoriamente ser falsa? (A) C está adjacente ao D. (B) V está adjacente ao F. (C) D está adjacente ao O. (D) H está adjacente ao V. (E) O está adjacente ao H.
O F
F O
04/15/2315 @copyright by Wellington Santos Martins
Lembre-se que a 1ª pergunta mostrou que D,O,H,F,V,C é uma lista correta. Portanto as opções (B), (C) e (E) são verdadeiras. A opção (A) também é verdadeira pois C estando adjacente ao D requer que V esteja na extremidade oposta, com as 3 posições restantes sendo usadas por O, H e F. A opção (D) é falsa pois H adjacente ao V leva a uma situação na qual O deverá estar adjacente a F, o que não é permitido.
2 3 4 5 61V D
V D
D V
D V
H
H
H
H
C
C
C
C
Respondendo a 5ª pergunta5. Qual dos seguintes pares contém carros que podem ocupar a terceira ou a quarta vaga a partir da esquerda? (A) H e O. (B) D e F. (C) F e V. (D) H e D. (E) O e D.
D F H OC
2 3 4 5 61
V
CC C C
D V
V D
(A) Verdadeira;(B) Falsa pois D não pode estar na 3a posição;(C) Falsa pois V não pode estar na 4a posição;(D) Falsa pois D não pode estar na 4a posição;(E) Falsa pois D não pode estar na 4a posição;
O F
F O V/D D/V
04/15/2316 @copyright by Wellington Santos Martins
Diagrama das Regras: Blocos
A vem imediatamente antes de B:
A não vem imediatamente antes de B:
A é vizinho de B:
A não é vizinho de B:
B está a 3 posições depois de A:
Existem 2 posições entre A e B:
04/15/23@copyright by Wellington Santos Martins
17
A B
A/B B/A
A B
A/B B/A
A/B B/A
A B
Inferências com Blocos Blocos indicam uma relação espacial entre variáveis;
Inferências com blocos devem se concentrar no que é verdadeiro ou falso e não no que pode ser verdadeiro ou falso;
Exemplos:
04/15/23@copyright by Wellington Santos Martins
18
A B2 3 4 5 61
B A
A B 2 3 4 5 61
B AB A
A B Não é possível deduzir nenhuma regra simples
2 3 4 5 61A deve estar na posição 1 ou 2(colocação direta)
A A
Um dia de Trabalho (OBI-2008-F1N1)Um funcionário de uma empresa tem seis tarefas para realizar hoje. Essas tarefas são identificadas por R, B, G, S, W e T. As tarefas não podem ser realizadas ao mesmo tempo e devem ser feitas numa ordem que obedeça as restrições abaixo.• W é realizada em algum momento após G e algum momento após T.• S é realizada em algum momento após W.• R é realizada em algum momento antes de S.
04/15/2319 @copyright by Wellington Santos Martins
Analisando o CenárioUm dia de Trabalho (OBI-2008-F1N1)
Um funcionário de uma empresa tem seis tarefas para realizar hoje. Essas tarefas são identificadas por R, B, G, S, W e T. As tarefas não podem ser realizadas ao mesmo tempo e devem ser feitas numa ordem que obedeça as restrições abaixo.
Liste as Variáveis:Ordem de Execução das Tarefas (base): 1, 2, 3, 4, 5, 6Tarefas (livre): R, B, G, S,W,T
Faça um Diagrama das Variáveis:B G S W TR
2 3 4 5 61
04/15/2320 @copyright by Wellington Santos Martins
Analisando as Regras• W é realizada em algum momento após G e algum momento após T.
• S é realizada em algum momento após W.• R é realizada em algum momento antes de S.
04/15/2321 @copyright by Wellington Santos Martins
Diagrama de sequenciamento representando a regra
G W
WT
Analisando as Regras• W é realizada em algum momento após G e algum momento após T.
• S é realizada em algum momento após W.• R é realizada em algum momento antes de S.
04/15/2322 @copyright by Wellington Santos Martins
Diagrama de sequenciamento representando a regra
W S
Analisando as Regras• W é realizada em algum momento após G e algum momento após T.
• S é realizada em algum momento após W.• R é realizada em algum momento antes de S.
04/15/2323 @copyright by Wellington Santos Martins
Diagrama de sequenciamento representando a regra
R S
Analisando as Regras• W é realizada em algum momento após G e algum momento após T.
• S é realizada em algum momento após W.• R é realizada em algum momento antes de S.
04/15/2324 @copyright by Wellington Santos Martins
Diagrama de seqüenciamento representando as regras
R S
W S
G W
WT
Combinando as regras
WT S
G
R
B
Respondendo a 1ª pergunta1. Qual das opções abaixo é uma lista completa e correta da ordem de realização das tarefas, da primeira à última?(A) G,R,T,S,W,B. (B) G,T,W,S,R,B. (C) B,G,T,R,W,S. (D) G,B,W,R,T,S. (E) T,W,R,G,S,B.
(A) Errada pois S não pode vir antes de W;(B) Errada pois S não pode vir antes R;(C) Correta! (D) Errada pois W não pode vir antes T(E) Errada pois W não pode vir antes G;
04/15/2325 @copyright by Wellington Santos Martins
WT S
G
R
B
Respondendo a 2ª pergunta2. Qual das seguintes opções é sempre verdadeira?(A) S é realizada por último. (B) G é realizada primeiro. (C) S é realizada após B. (D) S é realizada após G. (E) W é realizada após R.
(A) Errada pois pode ser B;(B) Errada pois a primeira pode ser B, T, G ou R;(C) Errada pois nada foi dito sobre B;(D) Verdadeira;(E) Errada pois não existe uma relação de ordem entre W e R;
04/15/2326 @copyright by Wellington Santos Martins
WT S
G
R
B
Respondendo a 3ª pergunta3. Qual é o número total de possíveis tarefas que podem ser realizadas em primeiro lugar?(A) 1. (B) 2. (C) 3. (D) 4. (E) 5.
(A) Errada;(B) Errada;(C) Errada(D) Correta pois tanto B, T, G ou R podem ser realizadas em primeiro lugar.(E) Errada;
04/15/2327 @copyright by Wellington Santos Martins
WT S
G
R
B
Respondendo a 4ª pergunta4. Se R é a quinta tarefa a ser realizada então qual das opções é verdadeira?(A) W é a quarta tarefa a ser realizada.(B) S é a sexta tarefa a ser realizada.(C) B é a segunda tarefa a ser realizada.(D) T é a terceira tarefa a ser realizada.(E) G é a primeira tarefa a ser realizada.
(A) Errada pois a seqüência poderia ser G, T, W, B, R, S;(B) Correta pois se R é a quinta, e vem antes de S, S deve ser a sexta;(C) Errada pois a seqüência poderia ser G, T, W, B, R, S;(D) Errada pois a seqüência poderia ser G, T, W, B, R, S;(E) Errada pois a seqüência poderia ser T, G, W, B, R, S;
04/15/2328 @copyright by Wellington Santos Martins
WT S
G
R
B
Respondendo a 5ª pergunta5. Qual das opções abaixo é a posição mais tardia em que a tarefa T pode ser realizada?(A) Segundo Lugar. (B) Terceiro Lugar. (C) Quarto Lugar. (D) Quinto Lugar. (E) Sexto Lugar.
(A) Errada;(B) Errada;(C) Correta pois podemos ter {G, B, R} T W S; (D) Errada;(E) Errada;
04/15/2329 @copyright by Wellington Santos Martins
WT S
G
R
B
Diagrama das Regras: Sequenciamento
04/15/23@copyright by Wellington Santos Martins
30
F E A depois de E e E depois de F
C depois de A e B
A
B
C
A
D
BB depois de A e D
Combinando as anteriores
A
D B C
F D F antes de D
F
E A
Inferências com Seqüenciamento O seqüenciamento estabelece um posicionamento relativo de variáveis, diferentemente dos blocos onde o número de posições entre variáveis é fixo.
04/15/23@copyright by Wellington Santos Martins
31
2 3 4 5 61
B AC A
C B
2 3 4 5 61
B AA B
A B C
Inferências com Seqüenciamento O seqüenciamento estabelece um posicionamento relativo de variáveis, diferentemente dos blocos onde o número de posições entre variáveis é fixo.
04/15/23@copyright by Wellington Santos Martins
32
2 3 4 5 61
AC
A
B
CC
B
2 3 4 5 61
AA
B
CB
D
A e B vemAntes de C
A vem antesde B, C e D
C
D
AA