|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (find-angg "LATEX/2009-1-MD-prova-2.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-2.tex && latex 2009-1-MD-prova-2.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2009-1-MD-prova-2.tex && pdflatex 2009-1-MD-prova-2.tex"))
% (eev "cd ~/LATEX/ && Scp 2009-1-MD-prova-2.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2009-1-MD-prova-2.dvi"))
% (defun p () (interactive) (find-pspage "~/LATEX/2009-1-MD-prova-2.pdf"))
% (defun p () (interactive) (find-pspage "~/LATEX/2009-1-MD-prova-2.ps"))
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2009-1-MD-prova-2.ps 2009-1-MD-prova-2.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2009-1-MD-prova-2.ps 2009-1-MD-prova-2.dvi && ps2pdf 2009-1-MD-prova-2.ps 2009-1-MD-prova-2.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2009-1-MD-prova-2.pdf" (ee-twupfile "LATEX/2009-1-MD-prova-2.pdf") 'over)
% (ee-cp "~/LATEX/2009-1-MD-prova-2.pdf" (ee-twusfile "LATEX/2009-1-MD-prova-2.pdf") 'over)
% «.Definicoes» (to "Definicoes")
% «.Header» (to "Header")
\documentclass[oneside]{book}
\usepackage[latin1]{inputenc}
\usepackage{edrx08} % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty" -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex % (find-dn4ex "edrxheadfoot.tex")
\begin{document}
\input 2009-1-MD-prova-2.dnt
%*
% (eedn4-51-bounded)
%Index of the slides:
%\msk
% To update the list of slides uncomment this line:
%\makelos{tmp.los}
% then rerun LaTeX on this file, and insert the contents of "tmp.los"
% below, by hand (i.e., with "insert-file"):
% (find-fline "tmp.los")
% (insert-file "tmp.los")
\def\depois#1{#1}
% (find-dn4ex "edrxdnt.tex" "defdiag")
\long\def\Def #1#2{\expandafter\def\csname #1\endcsname{#2}}
\def\ifUndef#1{\expandafter\ifx\csname #1\endcsname\relax}
\def\Assert #1{\ifUndef{#1}\errmessage{UNDEFINED: #1}\else\relax\fi}
\def\Expand #1{\Assert{#1}\csname #1\endcsname}
% \long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{#1 #2 #3 #4 #5 #6}
\long\def\defquestion cod#1 ref#2 val#3 qst#4 gab#5 spc#6{
\Def{Ref#1}{#2}
\Def{Val#1}{#3}
\long\Def{Qst#1}{#4}
\long\Def{Gab#1}{#5}
\long\Def{Spc#1}{#6}
}
% (find-LATEX "2009apr29-C1.tex")
% (find-LATEXfile "2009apr29-C1.tex" "newcounter")
% (find-es "tex" "newcounter")
\newcounter{questao}
\long\def\novaquestao{
\par\noindent
\refstepcounter{questao}
{\bf (\arabic{questao})}
}
% «Header» (to ".Header")
\long\def\Header{{
\setlength{\parindent}{0pt}
\par Matemática Discreta
\par PURO-UFF - 2009.1
\par Professor: Eduardo Ochs
\par Segunda prova - 26/junho/2009
}}
% «Definicoes» (to ".Definicoes")
\long\def\Definicoes{
% \par {\bf Dicas e definições:}
\par {\bf Definições:}
O {\sl conjunto das partes} de um conjunto $A$, $\Pts(A)$, é o
conjunto dos subconjuntos de $A$. Exemplo: se $A=\{4,5,6\}$ então
$\{4,5\} \in \Pts(A)$.
Se $A$ é um conjunto finito então $|A|$ é o número de elementos de
$A$.
A relação $R \subset A×A$ é {\sl reflexiva} quando $ýaÝA.\, aRa$.
A relação $R \subset A×A$ é {\sl simétrica} quando $ýa,bÝA.(aRb \to
bRa)$.
A relação $R \subset A×A$ é {\sl transitiva} quando $ýa,b,cÝA.(aRb ∧
bRc \to aRc)$.
Uma relação $R$ é uma {\sl relação de equivalência} quando $R$ é
reflexiva, simétrica e transitiva.
A {\sl classe de equivalência} de um elemento $a \in A$ pela relação
de equivalência $R \subset A×A$ é o conjunto $[a] = \sst{x \in
A}{aRx}$.
A {\sl inversa} de uma relação $R=\{(a_1,b_1), (a_2,b_2), \ldots\}$ é
a relação $R^{-1}=\{(b_1,a_1), (b_2,a_2), \ldots\}$.
{\sl Relação $R \subset A×A$ como grafo direcionado:} podemos
representar $R$ desenhando um grafo direcionado no qual os vértices
são os elementos de $A$ e cada seta $a \to b$ corresponde a um par
$(a,b) \in R$.
{\sl Relação $R \subset A×B$ como grafo direcionado:} podemos
representar $R$ desenhando o conjunto $A$ e o conjunto $B$ em separado
e desenhando uma seta $a \to b$ de um elemento $a \in A$ para um
elemento $b \in B$ para cada par $(a,b) \in R$.
A função $f: A \to B$ é {\sl injetiva} quando $ýa_1, a_2 \in A.\,
(f(a_1)=f(a_2) \to a_1=a_2)$.
A função $f: A \to B$ é {\sl sobrejetiva} quando $ýbÝB.\, ÎaÝA.\,
f(a)=b$.
Se $f:A \to B$ e $g: B \to C$ são funções, então a sua {\sl
composta}, $g¢f$, é uma função $g¢f: A \to C$, definida por
$ýaÝA.\, (g¢f)(a) = g(f(a))$.
A função {\sl identitidade em $A$}, $\id_A: A \to A$, é definida
por $ýaÝA.\, \id_A(a)=a$.
Duas funções $f:A \to B$ e $g:B \to A$ são {\sl inversas} quando
$f¢g = \id_B$ e $g¢f = \id_A$.
}
\long\def\Ask#1{
\novaquestao
\Expand{Qst#1}
\bsk
}
\long\def\Gab#1{
\par {\bf (Questão {\tt #1} - \Expand{Val#1} pontos)}
\Expand{Qst#1}
\ssk\par {\bf Gabarito:}
\par \Expand{Gab#1}
\bsk
\bsk
}
\def\Prova #1 #2 #3 #4 {
\setcounter{questao}{0}
\Header
\bsk
\Definicoes
\bsk
\bsk
\par {\bf Questões (2.5 pontos cada):}
\ssk
\Ask{#1}
\Ask{#2}
\Ask{#3}
\Ask{#4}
\newpage
}
% (find-kopkadaly4page (+ 12 126) "Index" "\\not")
% (find-kopkadaly4page (+ 12 631) "Index" "\\not")
% (find-kopkadaly4text)
% (find-LATEXfile "2008induction.tex" "\\def\\notS")
% (find-LATEXfile "2009-1-C1-prova-1.tex" "\\def\\sen")
\def\notR{\not\mathrel{R}}
\def\notQ{\not\mathrel{Q}}
\def\notD{\not\mathrel{D}}
\def\sen{\operatorname{sen}}
\def\arcsen{\operatorname{arcsen}}
\def\sinal{\operatorname{sinal}}
\def\sinal{s}
%%%%%%%%%%%%%%%%%%%%%%%%
\defquestion
cod{RRRRR}
ref{Sch 81/82 1, parte}
val{2.5}
qst{
Para cada uma das relações $R \subseteq \{1,2,3,4,5\}^2$ abaixo
diga se a relação $R$ é reflexiva, simétrica, e/ou transitiva;
quando não for, justifique porquê.
a) $R=\{(1,1), (2,2), (3,3), (4,4), (5,5)\}$,
b) $R=\{(1,2), (2,3), (3,4), (4,5)\}$,
c) $R=\{(1,1), (1,2), (1,3), (1,4), (1,5)\}$,
d) $R=\{(1,1), (1,2), (2,1), (3,4), (4,3)\}$,
e) $R=\{1,2,3,4,5\}^2$
}
gab{
a) Reflexiva, simétrica, transitiva.
b) Não-reflexiva ($1\notR1$), não-simétrica ($1R2$ mas $2\notR1$),
não-transitiva ($1R2$ e $2R3$ mas $1\notR3$).
c) Não-reflexiva ($2\notR2$), não-simétrica ($1R2$ mas $2\notR1$),
transitiva.
d) Não-reflexiva ($2\notR2$), simétrica, não-transitiva ($2R1$ e $1R2$ mas $2\notR2$).
e) Reflexiva, simétrica, transitiva.
}
spc{}
%%%%%%%%%
\defquestion
cod{Pipa}
ref{Inventei}
val{2.5}
qst{
Seja $A = \{0, 1, 2, 3, 4\}$. Considere a seguinte relação $G
\subset A×A$: $G=\{(0,1), (0,2), (1, 3), (2, 3), (3, 4)\}$.
Crie as relações $R$, $S$ e $T$,
acrescentando o menor número possível de pares a $G$, tais que
$G \subseteq R \subseteq A×A$,
$G \subseteq S \subseteq A×A$,
$G \subseteq T \subseteq A×A$,
\depois{$R$ é reflexiva, $S$ é simétrica, $T$ é transitiva,}
e:
a) Represente a relação $G$ como um grafo direcionado.
b) Represente a relação $R$ como um grafo direcionado.
c) Represente a relação $S$ como um grafo direcionado.
d) Represente a relação $T$ como um grafo direcionado.
e) Agora crie uma relação $F \subset G$ tal que $F$ tenha um
elemento a menos que $G$ e $F$ seja o gráfico de uma função $f$.
Descreva a função $f$ e diga o seu domínio e a sua imagem.
}
gab{
a) $G$ é uma pipa.
b) $R$ é a pipa com loops.
c) $S$ é a pipa com setas bidirecionais.
d) $T$ é a pipa com 4 setas a mais.
e) $F=\{(0,1), (1, 3), (2, 3), (3, 4)\}$ ou
$F=\{(0,2), (1, 3), (2, 3), (3, 4)\}$;
$f:\{0,1,2,3\} \to \{1, 3, 4\}$.
}
spc{}
%%%%%%%%%%
\defquestion
cod{Primos}
ref{Inventei}
val{2.5}
qst{
Seja $A = \{2, 3, 4, 6, 9, 12, 27, 36\}$. Considere a seguinte
relação $P \subset A×A$: $aPb$ se e só se ``é possível ir de $a$
para $b$ multiplicando $a$ por um primo'' --- ou seja, se e só se
existe um primo $p$ (lembre que 1 não é primo!) tal que $ap=b$.
\ssk
a) (0.3 pts) Represente $P \subseteq A \depois{× A}$ como um grafo
direcionado.
b) (0.3 pts) Represente $P$ como um conjunto.
\ssk
Agora crie as relações $R$, $S$ e $T$, acrescentando o menor
número possível de pares a $P$, tais que
$P \subseteq R \subseteq A×A$,
$P \subseteq S \subseteq A×A$,
$P \subseteq T \subseteq A×A$, e:
\ssk
c) (0.3 pts) Represente a relação $R$ como um grafo direcionado.
d) (0.3 pts) Represente a relação $S$ como um grafo direcionado.
e) (0.4 pts) Represente a relação $T$ como um grafo direcionado.
f) (0.5 pts) Represente como um grafo direcionado a relação $D
\subseteq A×A$ definida por: $aDb$ se e só se $a<b$ e $a$ é um
divisor de $b$.
g) (0.4 pts) A relação $D$ é reflexiva? É simétrica? É transitiva?
Quando não for, mostre porquê. A relação $D$ é igual a alguma das
relações dos itens anteriores?
}
gab{
Desenho:
$\left(
\begin{smallmatrix} 4 & 12 & 36 \\
2 & 6 & \\
& 3 & 9 & 27 \\
\end{smallmatrix}
\right)
$
a) $P$ é $4 \to 12 \to 36$, $2 \to 6$, $3 \to 9 \to 27$, e $2 \to
4$, $3 \to 6 \to 12$.
b) $P=\{(2,4), (2,6), (3,6), (3,9), (4,12), (6,12), (9, 27)\}$
c) $R$ é $P$ com loops.
d) $S$ é $P$ com setas bidirecionais.
e) $T$ é o fecho transitivo.
f) $D$ é $T$ com mais a seta $9 \to 36$.
g) $D$ não é reflexiva ($2\notD2$), não é simétrica ($2D4$ mas
$4\notD2$), é transitiva, é estritamnete maior que $T$.
}
spc{}
%%%%%%%%%%
\defquestion
cod{Arcsen}
ref{Sch p.183 8}
val{2.5}
qst{
A função seno, $\sen: \R \to \R$, não é nem injetiva nem
sobrejetiva, e a função $\arcsen: [-1,1] \to \R$ não é sobrejetiva,
mas mesmo assim costumamos dizer que o arcsen é a inversa do seno...
Explique isto, e defina duas funções, $s$ e $a$, ``parecidas'' com o
seno e o arcsen --- você vai ter que explicar em que sentido $s$ e
$a$ são parecidas com sen e arcsen! --- tais que $s$ e $a$ sejam
realmente inversas uma da outra. (Sugestões: funções compostas;
restrição de domínio).
}
gab{
$s: [-\pi,\pi] \to [-1,1]$, restrição do sen,
$a: [-1,1] \to [-\pi,\pi]$, restrição do arcsen,
$s = a^{-1}$
$a = s^{-1}$.
$ýxÝ[-1,1]. \, \sen(\arcsen(x))=x$.
$\arcsen(s(\theta))=x$.
}
spc{}
%%%%%%%%%%%
\defquestion
cod{Sinal}
ref{inventei}
val{2.5}
qst{
Seja $\sinal: \R \to \{-1,0,1\}$ a função que retorna -1 quando
recebe um número negativo, 0 quando recebe 0 e 1 quando recebe um
número positivo.
Sejam $A=\{-3,-2,0,2,4\}$ e $B=\{-4,-2,0,2,3\}$.
Seja $S \subseteq A×A$ a relação $S = \sst{(a_1,a_2) \in
A×A}{\sinal(a_1)=\sinal(a_2)}$. A relação $S$ é uma relação de
equivalência.
\ssk
a) (0.4 pts) Diga qual é a classe de equivalência do 2 por $S$.
b) (0.7 pts) Diga quais são todas as classes de equivalência de $S$.
Represente as classes de equivalência de $S$ graficamente ---
desenhe o conjunto $A$ e faça um círculo em torno de cada grupo de
elementos equivalentes.
\ssk
Seja $\sinal^2: \R^2 \to \{-1,0,1\}^2$ a função que recebe um par
$(x,y)\in \R^2$ e retorna $(\sinal(x), \sinal(y))$.
Seja $Q\subseteq (A×B)×(A×B)$ a relação que diz que $(a,b)Q(a'b')$ é
verdadeiro se e só se $\sinal(a)=\sinal(a')$ e
$\sinal(b)=\sinal(b')$.
\ssk
c) (0.4 pts) Mostre -- expandindo as definições --- que
$(2,2)Q(3,4)$ e $(2,3)\notQ(-2,3)$.
d) (1.0 pts) Represente $A×B \subseteq \R^2$ como um conjunto de
pontos do plano e represente suas classes de equivalência
graficamente, como no item (c).
}
gab{
a) (0.4 pts) $[2]=\{2,4\}$
b) (0.7 pts) $\{\{-4,-2\}, \{0\}, \{2,4\}\}$; $(-4,-2), (0), (2,
4)$.
c) (0.4 pts) $(2,2)Q(3,4) \bij
2R3∧2R4 \bij
(\sinal(2){=}\sinal(2) ∧ \sinal(2){=}\sinal(4)) \bij
(1{=}1 ∧ 1{=}1) \bij
V∧V \bij
V$;
$(2,3)Q(-2,3) \bij
2R-2∧3R3 \bij
(1{=}-1 ∧ 1{=}1) \bij
F∧V \bij
F$
d) (1.0 pts) 9 blobs no plano.
}
spc{}
%%%%%%%%%%%
\defquestion
cod{Partes}
ref{Sch 98 ex 13.7}
val{2.5}
qst{
Sejam $A = \{4, 5\}$, $B = \Pts(A)$, e seja $S \subseteq B×B$ a
relação ``tem o mesmo tamanho que''. A relação $S$ é uma relação de
equivalência sobre $B$.
a) (1.0 pts) Diga quem é $[\{4\}]$, a classe de equivalência de
$\{4\}ÝB$. (lembre que $[\{4\}] \subseteq B$). Diga quem é
$|[\{4\}]|$.
b) (1.5 pts) Seja $f:B \to \N$ a função que para cada $XÝB$ retorna
$|[X]|$. Seja $F$ o gráfico de $f$. $F$ é uma relação, e portanto um
conjunto. Diga quem é $F$.
}
gab{
a) $[\{4\}] = \{\{4\},\{5\}\}$; $|[\{4\}]| = 2$.
b) $F = \{(\{\}, 1),
(\{4\}, 2),
(\{5\}, 2),
(\{4,5\}, 1)\}$.
}
spc{}
\Prova RRRRR Primos Partes Arcsen
\Prova Primos RRRRR Sinal Arcsen
\Prova Partes Primos Arcsen RRRRR
\Prova RRRRR Arcsen Partes Primos
\Prova Pipa Sinal RRRRR Partes
\Prova RRRRR Primos Partes Arcsen
\Prova RRRRR Partes Pipa Sinal
\Prova RRRRR Sinal Arcsen Primos
\Prova Pipa Sinal Arcsen RRRRR
\Prova RRRRR Arcsen Sinal Primos
\Prova Sinal Partes Primos RRRRR
\Prova Arcsen Partes RRRRR Pipa
\Prova Partes RRRRR Primos Arcsen
\Prova Pipa Arcsen Partes Sinal
\Prova Partes RRRRR Sinal Primos
\Prova Partes RRRRR Sinal Pipa
\Prova Pipa Sinal Arcsen RRRRR
\Prova Pipa Arcsen Sinal Partes
\Prova Pipa Sinal RRRRR Arcsen
\Prova Arcsen RRRRR Primos Partes
\Prova Partes Pipa Arcsen RRRRR
\Prova Pipa Sinal Arcsen RRRRR
\Prova Primos Arcsen Partes Sinal
\Prova RRRRR Sinal Primos Partes
\Prova RRRRR Pipa Arcsen Sinal
\Prova RRRRR Pipa Sinal Arcsen
\Prova Partes Primos Sinal RRRRR
\Prova RRRRR Primos Arcsen Sinal
\Prova Partes Sinal Primos Arcsen
\Prova Primos Partes RRRRR Sinal
\Prova Sinal Arcsen Pipa RRRRR
\Prova Arcsen Partes Pipa RRRRR
\Prova Partes Arcsen Primos Sinal
\Prova Partes RRRRR Pipa Sinal
\Prova Arcsen Sinal Pipa RRRRR
% \Ask{R}
% \Ask{Pipa}
% \Ask{Primos}
% \Ask{Arcsen}
% \Ask{Sinal}
% \Ask{Partes}
\newpage
{\bf Gabarito:}
\bsk
\Gab{Pipa}
\Gab{Primos}
\Gab{RRRRR}
\Gab{Sinal}
\Gab{Arcsen}
\Gab{Partes}
% \defquestion
% cod{}
% ref{}
% val{}
% qst{}
% gab{}
% spc{}
%*
\end{document}
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
random = math.random
shuffle = function (A)
local B = {}
for i=1,#A do B[i]=A[i] end
for i=#A,2,-1 do
local r = random(1, i)
B[r], B[i] = B[i], B[r]
end
return B
end
from = function (A, n)
if n == nil then
return A[random(1, #A)]
end
A = shuffle(A)
while #A > n do A[#A] = nil end
return A
end
questoes = function ()
local a = from(split "Pipa Primos")
local B = from(shuffle(split "Sinal Arcsen RRRRR Partes"), 3)
tinsert(B, a)
return shuffle(B)
end
prova = function ()
local a, b, c, d = unpack(questoes())
printf("\\Prova %7s %7s %7s %7s\n", a, b, c, d)
end
for i=1,20 do PP(questoes()) end
for i=1,35 do prova() end
for i=1,10 do PP(from{"Pipa", "Primos"}) end
for i=1,10 do PP(from(split {"Pipa", "Primos"}) end
for i=1,40 do PP(shuffle({"aa", "bb", "cc", "dd", "ee"})) end
% Local Variables:
% coding: raw-text-unix
% ee-anchor-format: "«%s»"
% End: