% (find-angg "LATEX/2010reducao.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010reducao.tex && latex    2010reducao.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010reducao.tex && pdflatex 2010reducao.tex"))
% (eev "cd ~/LATEX/ && Scp 2010reducao.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2010reducao.dvi"))
% (find-dvipage "~/LATEX/2010reducao.dvi")
% (find-pspage  "~/LATEX/2010reducao.ps")
% (find-pspage  "~/LATEX/2010reducao.pdf")
% (find-xpdfpage "~/LATEX/2010reducao.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvipdf         2010reducao.pdf 2010reducao.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2010reducao.ps 2010reducao.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2010reducao.ps 2010reducao.dvi && ps2pdf 2010reducao.ps 2010reducao.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2010reducao.pdf" (ee-twupfile "LATEX/2010reducao.pdf") 'over)
% (ee-cp "~/LATEX/2010reducao.pdf" (ee-twusfile "LATEX/2010reducao.pdf") 'over)
% (find-twusfile     "LATEX/" "2010reducao")
% http://angg.twu.net/LATEX/2010reducao.pdf

\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 2010reducao.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 \str#1{\ensuremath{\text{``{\tt #1}''}}}
\def\mstr#1{\ensuremath{\text{``$#1$''}}}

Em Matemática Discreta nós muitas vezes vamos ter que falar sobre {\sl
  expressões}, e vamos distinguir uma expressão do seu {\sl valor}...

Vamos usar aspas quando quisermos enfatizar que estamos falando de
expressões: $2·3+4·5 = 6+20$, mas $\mstr{2·3+4·5} \neq \mstr{6+20}$.
Computadores vêem expressões como seqüências de caracteres
(``strings''), e o valor de um string é o próprio string; a operação
que interpreta um string como uma expressão e calcula o valor desta
expressão se chama ``avaliação'' (em inglês ``evaluation'',
tradicionalmente abreviado para ``eval'' em linguagens de
programação). Um exemplo em Lua:

{\myttchars
\footnotesize
\begin{verbatim}
Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> function eval (str) return assert(loadstring("return "..str))() end
> print(2*3+4*5)
26
> print("2*3+4*5")
2*3+4*5
> print(type(2*3+4*5))
number
> print(type("2*3+4*5"))
string
> print(eval("2*3+4*5"))
26
> print( 2*3+4*5  ==  26)
true
> print("2*3+4*5" == "26")
false
> print("2*3+4*5" ==  26)
false
> 
\end{verbatim}
}

% (Vou exemplos em Scheme, Guile, Emacs Lisp, SBCL, Python e PERL
% depois).

Expressões em ``matematiquês'' podem ter subscritos, superscritos,
fontes diferentes, e símbolos que são difíceis de representar em
ASCII. Nas notas de aula em \LaTeX{} eu às vezes vou usar uma fonte
diferente (``typewriter'') pra indicar expressões em ASCII:

$$\begin{array}{ll}
  \mstr{2·3+4·5} & \str{2*3+4*5} \\
  \mstr{2+\sqrt{3}} & \str{2+sqrt(3)} \\
  \mstr{\sin \frac{\pi}{3}} & \str{sin(pi/3)} \\
  \mstr{2^{100}-2^{99}} & \catcode`^=12 \str{2^100-2^99} \\
  \end{array}
$$

A noção de ``redução'' que vamos usar durante o curso pode ser
formalizada matematicamente como uma {\sl relação} (sec.\ 11 do
Scheinerman) sobre um {\sl conjunto} (sec.\ 8) de expressões; e
podemos definir que as nossas expressões em ASCII são simplesmente uma
notação conveniente para {\sl listas} (sec. 6) de números:

$$\str{2*3+4*5} = (50, 42, 51, 43, 52, 42, 53)$$

O diagrama de reduções abaixo à esquerda pode ser visto como uma
notação convenient para o ``grafo direcionado'' à direita dele:

%L forths["~>"] = function () pusharrow("~>") end

%D diagram reds
%D 2Dx     100 +45 +40 +45
%D 2D  100 A   B   a   b
%D 2D                   
%D 2D  +20 C   D   c   d
%D 2D                   
%D 2D  +20     E       e
%D 2D
%D (( A .tex= 2·3+4·5  a .tex= \str{2*3+4*5}
%D    B .tex= 2·3+20   b .tex= \str{2*3+20}
%D    C .tex= 6+4·5    c .tex= \str{6+4*5}
%D    D .tex= 6+20     d .tex= \str{6+20}
%D    E .tex= 26       e .tex= \str{26}
%D    A B ~> A C ~> B D ~> C D ~> D E ~>
%D    a b -> a c -> b d -> c d -> d e ->
%D ))
%D enddiagram
%D
$$\diag{reds}$$

\def*{\ensuremath{\bullet}}

O livro não define explicitamente grafos direcionados, mas quase... veja:

* Ilustração de relações: p.83.

* Diagrama de Hasse: p.454.

O grafo direcionado acima pode ser representado como conjunto de pares
como:

$$\begin{array}{l}
  \llap{\{\;} (\str{2*3+4*5},\str{2*3+20}), \\
              (\str{2*3+4*5},\str{6+4*5}),  \\
              (\str{2*3+20},\str{6+20}),    \\
              (\str{6+4*5},\str{6+20}),     \\
              (\str{6+20},\str{26}) \;\}    \\
  \end{array}
$$



% (find-scheinermanpage (+  -10  83)   "Ilustração de relações")
% (find-scheinermanpage (+ -115 454)   "diagrama de Hasse")










Repr para relações como conjuntos de pares

Interpretar um diagram

Interpretar o conjunto de todas as reduções

Falar de fecho transitivo

Apontar para alfabetos e linguagens no Hopcropt/Ullman/Motwani

Falar de uma relação de equivalência que nao sabemos calcular - valor
de expressões numéricas

Falar de igualdades que são óbvias, e do que séries de igualdades
querem dizer, e como elas provam coisas que não queremos calcular

Mais geral: caso do n






%*

\end{document}



* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
function eval (str) return assert(loadstring("return "..str))() end
print(2*3+4*5)
print("2*3+4*5")
print(type(2*3+4*5))
print(type("2*3+4*5"))
print(eval("2*3+4*5"))
print(2*3+4*5 == 26)
print("2*3+4*5" == "26")
print("2*3+4*5" == 26)



 seqü





% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: