Plano de aulas / resumo do que já aconteceu:
1ª aula (16/mar): Introdução às operações "e", "ou" e "não". Durante a
maior parte da aula usamos 0 e 1 como valores de verdade; no final
mudamos para F e V (em negrito). Mencionei que números, valores de
verdade e conjuntos são objetos de tipos diferentes.
2ª aula (18/mar): Distribuí uma folha sobre operações e circuitos
http://angg.twu.net/MD/MD_circuitos_2011mar18.pdf
http://angg.twu.net/MD/MD_circuitos_2011mar18.djvu
Pus um aviso enorme no quadro, com três caveirinhas embaixo,
enfatizando a importância do exercício 1a; ele dizia mais ou menos o
seguinte:
No exercício 1a eu peço pra vocês _definirem_ certas operações.
Reparem que definições são feitas em "matematiquês", que tem
pedaços em português, pedaços em símbolos matemáticos, e às vezes
diagramas e exemplos.
Vocês estão aprendendo uma língua nova, e o 1a é como uma
"redação" nessa língua nova.
Não existem redações "certas" e "erradas" - só melhores e piores.
Alguns critérios: clareza, não ter erros de sintaxe, tem que
convencer quem a lê (não pode ter argumentos errados), etc.
Programar é fazer definições - numa língua que o computador
entenda. Às vezes basta o computador entender o que vocês escreveu
- mas se o seu programa der um bug uma semana depois de ter sido
escrito você vai ter que entender o que escreveu uma semana antes
pra consertá-lo.
Em geral _vocês_ vão ter que entender o que escreveram...
Mas muitas vezes vocês vão ter que escrever coisas que _outras
pessoas_ entendam - por exemplo, nas matérias da faculdade.
Outro exemplo: quando a gente manda dúvidas pra listas de
discussão as dúvidas bem explicadas são bem respondidas, as outras
não.
Além disso vocês vão precisar fazer definições (claras) em
praticamente todas as matérias do curso.
Passamos a aula quase toda discutindo o 1a. No final lemos um pedaço
da seção 1 do Scheinerman ("Definições").
3ª aula (23/mar): D_n = conjunto dos divisores de n.
Conjuntos de objetos com uma certa propriedade.
Quantificadores e regras de redução para quantificadores.
4ª aula (25/mar):
http://angg.twu.net/MD/MD_exercicios_2010mar29.pdf
http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.pdf
Até a simplificação do E_4.
Construímos a tabela com 8 simplificações
5ª aula (30/mar): Avisei que antes da gente continuar com a história
das expressões equivalentes era melhor a gente aprender mais sobre
modos de construir conjuntos e sobre como calcular o valor de
expressões envolvendo conjuntos. Calculamos:
C_1 = { (a,b) | a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
C_2 = {(a,b-a)| a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
C_3 = { {a,b} | a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
E ficaram umas dúvidas: {1,0}={0,1}? {0,0}={0}?
Mostrei as definições do "contido ou igual", "contido e diferente",
"não contido-ou-igual", "=" para conjuntos, etc, e a regra de
redução do "∈". Passei um exercício pra casa, avisando que era MUITO
importante e razoavelmente difícil (uma caveira - "precisa de
perseverança"):
Mostre que {0}={0,0} por uma série de reduções, e encontre um modo
de explicar cada redução - por exemplo:
{0}={0,0}
\
/ pela regra A=B ~~~> A<=B ∧ B<=A
\ com A={0,0} e B={0}
v
{0}<={0,0}∧{0,0}<={0}
Tente encontrar um modo de fazer isto que fique MUITO claro.
Obs: a solução ocupa uma página inteira.
(Estou escrevendo "contido ou igual" como "<=").
6ª aula (01/abr): *** completar ***
Exercícios:
Representem estes grafos direcionados "formalmente", isto é, com a
notação de conjuntos e listas:
(1) 1 --> 2 --\
^ |^^--/
| v|
4 <-- 3
(2) {1,2} --> {1} --\
| ^--/
v
{2} {}
e represente estes grafos direcionados "graficamente":
(3) ({1,2,3}, {(2,1),(2,3),(2,1)})
(4) ({1,...,4}, {(a,b)∈{1,...,4}^2 | a<b})
(5) Calcule e represente graficamente:
({1,...,9},
{(a,b) ∈ {1,...,9}^2 | a|b})
Dica importante: dá pra fazer esta "conta" explicitamente desde que
a gente use reticências ns lugares certos. Treinem usar reticências
de um modo claro! (Obs: levem esta recomendação a sério! A gente
leva anos pra aprender a user reticências bem, e é muito útil -
comecem a treinar o mais rápido possível!)
7ª aula (06/abr): Definimos este grafo direcionado:
D9 = ({1,...,9}, {(a,b) ∈ (1,...,9}^2 | a|b})
e um outro, com menos setas:
9
^
|
3--->6
D9- = ^ ^
| |
1--->2--->4--->8
|\
| v
5 7
Vimos as definições formais de reflexividade, simetria e
transitividade para relações R \subseteq A^2, e as interpretações
gráficas para reflexividade/simetria/transitividade. Contei que
sempre existe um modo "mínimo" de acrescentar setas a uma relação
para obter uma relação reflexiva/simétrica/transitiva. Definimos um
outro grafo direcionado, D9', acrescentando a D9- as setas
correspondentes a "acessibilidade em dois passos". Passei um
problema (importante, duas caveirinhas, pra ser terminado em casa):
Mostre que no grafo direcionado D9' esta
sentença é falsa: ∀a,b,c∈A.aRb∧bRc->aRc.
As dicas eram:
1) Quem é A?
2) Quem é R?
3) Qual é a relação entre D9' e (A,R)?
4) Como calcular o valor de ∀a,b,c∈A.aRb∧bRc->aRc?
5) Como mostrar que ∀a,b,c∈A.aRb∧bRc->aRc é falso?
6) Depois que a gente cria um conjunto C a gente não pode mudá-lo
acrescentando mais elementos... mas podemos criar um conjunto
C' contendo todos os elementos de C e mais alguns.
7) Não escrevam ∀{1,...9}∈A.____! {1,...9} é constante.
8) Dá pra cacular o valor de ∀a,b,c∈A.aRb∧bRc->aRc fazendo uma
tabela com uma linha para cada valor "interessante" de a, b, c
-- mas a tabela vai ter 9^3 linhas.
8ª aula (08/abr): Começamos com um grafo direcionado mais simples que
os da aula passada: E=(A,R)=({1,...,7}, {(1,2),(3,2),(3,4),(5,6)}).
A gente viu na aula passada como calcular os fechos reflexivo,
simétrico e transitivo de uma relação graficamente, então introduzi
uma notação - R^refl, R^sim, R^trans - e pedi pros alunos calcularem
R^refl, R^sim, R^trans, (R^sim)^trans, ((R^sim)^trans)^refl, para a
relação R do grafo direcionado E. A minha idéia era usar a relação
S:=((R^sim)^trans)^refl para começar a discutir relações de
equivalência, mas a gente acabou parando antes disso - os alunos não
chegaram a um acordo sobre o resultado de (R^sim)^trans, e ficaram
discutindo métodos possíveis.
Uma definição "formalizável" de R^trans é a seguinte:
se R <= A×A, então R^trans é a _menor relação transitiva_
obedecendo R <= R^trans <= A×A (obs: aqui o "<=" é \subseteq).
Pra tentar esclarecer essa definição nós passamos um tempão
discutindo estes problemas (para a R do grafo E=(A,R)):
(4) Encontre uma relação R' transitiva tal que R^sim<=R'<=A×A.
(5) Encontre uma relação R'' transitiva tal que R^sim<=R''<=A×A e
R' \subsetneq R''.
Com isso ficou claro que temos várias relações transitivas entre
R^sim e A×A - queremos a menor delas. Um "método" (ineficiente, mas
matematicamente preciso) de calcular o R^trans para uma dada relação
R é o seguinte: calcule o conjunto \calR de todas as relações
transitivas entre R e A×A, e depois calcule a interseção de todos as
relações em \calR.
***Pra casa:*** Tentem fazer os exercícios das pags 81 a 83 do
Scheinerman (sec.11). Não é importante fazer estes exercícios em
detalhes por enquanto (vários deles dependem de ferramentas que
ainda não vimos) - mas tentem ler _todos eles_ e pensar um pouco
sobre cada um.
[Eu dei dicas importantes nas últimas aulas de GA - preciso
copiá-las aqui].
Algumas pessoas me perguntaram que sistema operacional eu uso -
porque elas viram um Emacs rodando na minha máquina numa janela
maximizada e sem bordas. Alguns links:
http://angg.twu.net/eev-current/anim/channels.anim.html
http://angg.twu.net/eev-current/doc/shot-f3.png
http://angg.twu.net/eev-current/doc/shot-f9.png
9ª aula (13/abr): Continuamos com o R do grafo direcionado da aula
anterior: E=(A,R)=({1,...,7}, {(1,2),(3,2),(3,4),(5,6)}).
Nós tínhamos visto que haviam várias relações transitivas entre
R^refl^sim e A×A. Peguei uma delas, que eu disse que era a menor
de todas; chamei ela de R^refl^sim^trans = R^eq. Defini relação de
equivalência, e enunciei isto:
Fato: R^sim^refl^trans é sempre relação de equivalência.
Defini clases de equivalência, e pedi pros alunos calcularem
[a]_R^eq para cada valor a∈A. Vimos uma representação gráfica - a
com blobs, como na p.92 do Scheinerman.
*** termino o resumo depois ***
10ª aula (15/abr): *** depois eu ponho o resumo ***
11ª aula (20/abr): véspera do feriado de Tiradentes.
*** depois eu ponho o resumo ***
12ª aula (22/abr): não vai ter aula (a UFF costuma enforcar 6ªs
quando tem feriado na 5ª).
13ª aula (27/abr):
consideramos a seqüência (e_0, e_1, ...) que obedece
e_0=0 ∧ ∀n∈N.((e_n=n -> e_(n+1)=10e_n+1) ∧
(e_n!=n -> e_(n+1)=e_n))
e vimos como calcular e_0, e_1, etc; pedi pros alunos calcularem
e_12. Defini - informalmente - uma operação de concatenação de
números, "++"; por exemplo, 12 ++ 345 = 12345, 100 ++ 10 = 10010.
Todo mundo ficou em dúvida a respeito de qual deveria ser o
resultado de 123 ++ 0, então tornamos a definição um pouco mais
precisa criando duas operações diferentes, ++_A e ++_B:
123 ++_A 0 = 1230,
123 ++_B 0 = 123.
(Obs: concatenação é uma operação muito comum em strings; a operação
++_A trata o 0 como o string "0", enquanto a operação ++_B trata o 0
como o string vazio ("").)
Mostrei que podemos usar a sequência (e_0, e_1, ...) para definir o
++ formalmente, generalizando isto aqui:
123 ++ 45 = 123·100 + 45
= 123·(e_45 + 1) + 45
Pedi pros alunos encontrarem uma definição formal para uma operação
++_C e usarem ela para calcular 123 ++_C 0, 0 ++_C 123, 20 ++_C 300,
300 ++_C 20. Apareceram várias idéias:
Idéia 1:
∀a,b,c∈R. a++b=c -> a(e_b + 1)+b=c
(problema: quanto é 10.2++(-3.140)?)
Idéia 2:
∀a,b,c∈N. a++b=c -> a(e_b + 1)+b=c
Idéia 3:
∀a,b∈N. a++b=a(e_b + 1)+b
A idéia 1 e a idéia 2 não são totalmente equivalentes. Passei um
exercício pra casa (aqui está mais detalhado que no quadro), que
era o seguinte. Digamos que as operações ++_D e ++_E obedecem:
∀a,b,c∈N. a ++_D b = c -> a(e_b + 1)+b = c
∀a,b ∈N. a ++_E b = a(e_b + 1)+b
Encontre funções (++_D) e (++_E) de N×N em Z, _diferentes_, que
obedeçam as duas condições acima. Se (++_D) e (++_E) são funções de
N×N em N então elas são necessariamente iguais; porquê?
Mostrei um truque que a gente pode usar pra escrever substituições
complicadas de um modo que todo mundo entenda (até colegas, e
professores de mau humor):
Sabemos que
∀a,b∈N. a++b = a(e_b + 1)+b
Para a=123 e b=0, temos:
123++0 = 123(e_0 + 1)+b
= 123(0 + 1)+0
= 123
Aí consideramos a função f:N×N->N, definida (informalmente) por
este diagrama:
y=3 | 9
y=2 | 5 8
y=1 | 2 4 7
y=0 | 0 1 3 6
+-------------------
x=0 x=1 x=2 x=3
Pedi pros alunos tentarem encontrar - pra sexta - uma definição
formal para esta f, e _testá-la_. Dicas: às vezes
f(y+1,x-1)=f(y,x)+1, às vezes f(a+1,0)=f(0,a)+1.
Avisei que depois vamos ver um modo de definir esta f que faz com
que f(x,y) seja fácil de calcular - pelo modo acima calcular
f(200,100) dá um trabalhão.
14ª aula (29/abr):
Problema dos dominós, torres de Hanói, representações.
Digamos que a gente tem uma sacola com um monte de dominós
(retângulos 2x1) indistinguíveis, e um retângulo 2x5 na parede que
queremos preencher com dominós. Quantos modos diferentes temos de
preenchê-lo? Liste-os. Obs:
_________ _________
|___|___| | | |___|___|
|___|___|_| e |_|___|___|
devem ser considerados como modos diferentes.
Definimos a sequencia de conjuntos (D_1, D_2, ...), onde cada D_n é
o conjunto dos modos de preencher o retângulo 2×n com dominós. Pedi
pros alunos tentarem calcular D_5 e D_6, e numa certa hora pus um
aviso no quadro:
"D_5 = 8" é um ***erro conceitual gravíssimo***
D_5 é um conjunto, 8 é um número, e um conjuntos nunca é igual a um
número!!!!!! Mas isto aqui é verdade: |D_5| = 8. Note que neste caso
o "|·|" não é o módulo, é a cardinalidade.
Encontramos uma representação que transforma cada "modo" num número
- e uma das vantagens disto é que nos permite por os modos em ordem,
e aí fica fácil cada um comparar o seu conjunto com o que o vizinho
obteve. Exemplos:
_________ _________
|___|___| | | | | | | |
|___|___|_| |_|_|_|_|_|
2 2 1 = 221, 1 1 1 1 1 = 11111.
Aí:
D_4 = {22, 112, 121, 211, 1111}
D_5 = {122, 212, 221,
1112, 1121, 1211, 2111,
11111}
D_6 = {222,
1122, 1212, 1221, 2112, 2121, 2211,
11112, 11121, 11211, 12111, 21111,
111111}.
Defini a sequência dos C_ns por:
C_1 = {1}
C_2 = {2, 11}
C_(n+2) = {2++a | a∈C_n}
∪ {1++b | b∈C_(n+1)} para n∈{1,2,3,...}
e pedi pros alunos calcularem alguns C_ns em casa e verificarem que
C_n = D_n para todo n, e que |C_1|+|C_2|=|C_3|, |C_2|+|C_3|=|C_4|,
etc. Há vários semestres atrás eu fiz um programa pra gerar os D_ns:
http://angg.twu.net/2009.1/MD/dominoes.lua.html
(find-angg "2009.1/MD/dominoes.lua")
Torres de Hanói
---------------
Problema: como representar cada "posição válida" das Torres de Hanói
como um número, um conjunto, uma lista, um string, um vetor, ou uma
matrix? Avisei os alunos que há muitas representações possíveis, e não
há uma melhor que todas as outras, e abri um espaço no quadro pra pôr
4 representações diferentes.
Representação 1:
| | | / 0 0 0 \
| | | vira | 0 0 0 | na represtação 1,
33333 | 1 | 3 0 0 |
4444444 1 222 \ 4 1 2 /
----------------------------
(34, 1, 2) na representação 2,
{21, 32, 13, 14} na representação 3,
(onde o 21 quer dizer "o disco 1 está no pino 2",
o 32 quer dizer "o disco 2 está no pino 3",
o 13 quer dizer "o disco 3 está no pino 1",
o 14 quer dizer "o disco 4 está no pino 1")
34012 na representação 4,
"34,0,12" na representação 5.
Vimos que a representação 4 é ambígua - as posições "1,2,34" e
"1,23,4" (na representação 5) ambas viram 1234 quando usamos a
representação 4.
Pra casa: representem o problema das Torres de Hanói com 4 discos como
uma relação - P_1 R P_2 vai ser verdade se e só se é possível passar
da posição P_1 para a posição P_2 em um movimento.
Obs: não confundam os nomes - usem nomes diferentes para discos,
pinos, posições e movimentos.
Dica: a parte trabalhosa do problema é descobrir como escrever isso
de um modo que a minha avó entenda; a parte conceitual é fácil em
comparação. Treinem usar tanto explicações gerais quanto exemplos, e
tanto Português quanto matematiquês! Clareza não é fácil de obter.
Obs: O trabalho que o Fred (ex-monitor de MD) apresentou na semana
de monitoria de 2010 era sobre as Torres de Hanói:
http://angg.twu.net/MD/fred_casteloes__hanoi_2010.pdf
http://angg.twu.net/MD/fred_e_eduardo__hanoi_figuras_2010.pdf
15ª aula (04/mai): *** depois eu completo o resumo desta aula! ***
Lembrem que as operações "+" e "·" estão definidas - de modos
diferentes! - em números, vetores e matrizes.
Vamos definir o "++" (concatenação) em listas:
(a_1, ..., a_n) ++ (b_1, ..., b_m) =
(a_1, ..., a_n, b_1, ..., b_m).
Exemplo: (20, 30) ++ (400, 500, 600) = (20, 30, 400, 500, 600).
i P_i d_i m_i
--------------------------
1 "1234,0,0" 1 "1AB" \
2 "234,1,0" | M_2ABC
3 "34,1,2"
4 "34,0,12"
4 "4,3,12"
5 "
Depois calcule a sequencia (m_1, m_2, m_15) de strings, que diz que
disco é movido de que pino para que pino.
Nós vamos trabalhar com "subsequencias" da sequencia (m_1, ..., m_15).
Def: M_nabc é a sequencia de movimenos necessaria para levar os discos
1, ..., n do pino a para o pino b, usando o pino c como auxiliar.
Def (formal):
M_nabc = / ("1ac") quando n=1,
|
| M_(n-1)acb ++
| ("nab") ++
\ M_(n-1)cba quando n>1.
Pedi pra todo mundo calcular M_3ABC...
Expressões (introdução)
-----------------------
Em qualquer livro sério sobre uma linguagem de programação vocês vão
encontrar uma "especificação em BNF" (ou EBNF) da linguagem - em
geral num apêndice. Obs: "Pascal Estruturado" não é um livro sério!
Exemplo (p.36 do Ghezzi / Jazayeri):
<expr> ::= <identifier>
| <number>
| (<expr>)
| <expr><operator><expr>
<operator> ::= +
| *
Obs: quando escrevemos uma especificação nesta forma não estamos
(aparentemente!) falando de conjuntos...
"123" é um <number> <- obs: "um" é um artigo indefinido!
"45" é um <number> A gente evita artigos indefinidos
"+" é um <operator> em matematiquês... "x é um real"
portanto: é formalizado como "x∈R"
"123" é uma <expr>
(porque todo <number> é uma <expr>),
"45" é uma <expr>, e
"123+45" é uma <expr>
(porque <expr><operator><expr> é uma <expr>).
(Fiquei de dar uma definição de certos tipos de expressões via
conjuntos...)
16ª aula (06/mai): Hoje: o conjunto das expressões válidas!
Vamos definir um conjunto de strings, E, cujos elementos vão ser
exatamente os strings que são expressões válidas formadas por números,
"+", "*", "(" e ")".
Vamos começar fixando <- (obs: usamos o termo "fixando" quando
o conjunto dos strings existem vários valores razoáveis para
que representam números. um objeto, e escolhemos um deles.)
Vai ser mais conveniente começar
com N={"n"} do que com N={"0", "1", "2", ..., "10", ...}.
Como N={"n"} vamos ter:
"n+n" ∈ E,
"(n+n)*(n*n+n)" ∈ E,
"" não pertence a E,
"nn" não pertence a E,
")+*n" não pertence a E, etc.
Idéia pra construção:
E_0 = N,
E_1 = E_0 ∪ (o conjunto dos strings da forma "e+e'", e,e'∈E_0)
∪ (o conjunto dos strings da forma "e*e'", e,e'∈E_0)
∪ (o conjunto dos strings da forma "(e)", e∈E_0)
Mais precisamente: para n∈N,
E_(n+1) = E_n
∪ {e++"+"++e' | e,e'∈E_n}
∪ {e++"*"++e' | e,e'∈E_n}
∪ {"("++e++")" | e∈E_n}
Reparem que agora estamos usando concatenação ("++") em strings!
Mas, formalmente, strings são listas de números...
Exercício: calculem E_1.
Substituindo n por 0 e E_0 por N={"n"} na fórmula anterior, temos:
E_1 = {"n"}
∪ {e++"+"++e' | e,e'∈{"n"}}
∪ {e++"*"++e' | e,e'∈{"n"}}
∪ {"("++e++")" | e∈{"n"}}
= {"n"} ∪ {"n+n"} ∪ {"n*n"} ∪ {"(n)"}
= {"n", "n+n", "n*n", "(n)"}
Def: E = E_0 ∪ E_1 ∪ E_2 ∪ ...
Dá um trabalhão escrever o E_10 explicitamente (nós calculamos o E_2
em sala), mas é fácil provar que
"(n*n)+(n+(n*n))" ∈ E_10
e como E = E_0 ∪ E_1 ∪ ... ∪ E_10 ∪ ...
então "(n*n)+(n+(n*n))" ∈ E.
Vamos ver isto passo a passo.
(Obs: isto é uma introdução à segunda parte do curso!)
1) "n"∈E_0
2) "n*n"∈E_1 (porque "n*n" = "n"++"*"++"n"
∈ {e++"+"++e' | e,e'∈E_0},
e E_0 está contido em E_1)
3) "(n*n)"∈E_2 (porque "n*n"∈E_1)
4) "n"∈E_1 (porque E_0 está contido em E_1)
5) "n"∈E_2 (idem)
6) "n+(n*n)"∈E_3 (por (5) e (3))
7) "(n+(n*n))"∈E_4 (por (6))
8) "(n*n)"∈E_3 (por (3))
9) "(n*n)"∈E_4 (por (8))
10) "(n*n)+(n+(n*n))"∈E_5 (por (9) e (7))
11) "(n*n)+(n+(n*n))"∈E_6 (por (10))
etc.
17ª aula (11/mai): (veja abaixo)
18ª aula (13/mai): Vou estar fora a semana toda, num congresso,
apresentando isto aqui: <http://angg.twu.net/LATEX/2011ebl-abs.pdf>.
19ª aula (18/mai): árvores binárias.
20ª aula (20/mai): pergunta do dia: que passos podemos usar numa
"prova direta"? O apéndice C do Scheinerman (p.522, "Fundamentos") e
o capítulo 1 falam de regras básicas, definições, teoremas, lemas...
A gente começou vendo um pouquinho sobre provas em árvore, depois a
gente passou pra isso aqui: sabemos que + e · são comutativos,
associativos, temos 0, "-", distributividade, etc. Como provar,
_passo a passo_, que (a+b)(a-b) = a^2-b^2? (Vimos uma prova,
enorme).
Porque é que ninguém nunca faz essas provas em todos os detalhes?
O apêndice C do livro dá só as regras básicas...
No cap 1 do livro há uma discussão sobre definições, teoremas,
lemas, etc... e cada vez que a gente usa um teorema a gente pode
expandí-lo, se quiser (tem exercícios sobre isto numa lista do
semestre passado).
Pedi pros alunos provarem que se n>4 e 2^n<n! então 2^(n+1)<(n+1)!
passo a passo; apareceu uma solução, mas ela usava a regra:
a<b a'<b'
----------(?)
aa'<bb'
Uma das próximas técnicas de demonstração que vamos aprender é
indução...
21ª aula (25/mai): **** Paralisação do Pólo ****
Tínhamos marcado a P1 para este dia, mas ela vai ter que ser transferida.
22ª aula (27/mai):
23ª aula (01/jun): exercício de revisão pra P1.
Considere o seguinte problema: um homem está na margem esquerda de
um rio com os seus três animais (?!?) de estimação - um lobo, uma
cabra e um repolho - e ele quer atravessar para a margem direita
usando um barco no qual só cabe ele e um dos "animais" de cada vez.
Mas se o lobo for deixado sozinho com a cabra ele come a cabra, e se
a cabra for deixada sozinha com o repolho ela come o repolho.
Descreva como representar (todos!!!!!!!!!!!!) os movimentos
possíveis deste problema num grafo direcionado.
24ª aula (03/jun): P1. Questões e gabarito:
http://angg.twu.net/MD/MD_P1_2011jun02.pdf
http://angg.twu.net/MD/MD_P1_2011jun02.djvu
25ª aula (08/jun): aula (meio improvisada) sobre o que é um seqüente e
o que quer dizer um seqüente ser "verdadeiro". Não chegamos a ver
com detalhes o que são as "variáveis livres" de um seqüente, mas
mostrei que podemos testar se um seqüente como
P->Q,Q->R|-P->R
é verdadeiro fazendo uma tabela com todos os valores possíveis de
P,Q,R, marcando como "interessantes" todas as linhas nas quais todas
as hipóteses são verdadeiras, e testando se em cada linha
interessante a conclusão é verdadeira:
hip1 hip2 conc
P Q R P->Q Q->R P->R
-------------------------
F F F V V V <= linha interessante
F F V V V V <= linha interessante
F V F V F V
F V V V V V <= linha interessante
V F F F V F
V F V F V V
V V F V F F
V V V V V V <= linha interessante
Nós vamos usar seqüentes para entender regras de dedução, e muitas
vezes vamos usar seqüentes cujas tabelas seriam infinitas, como:
a∈Z|-a^2>0
Avisei pros alunos que haveria um trabalho extra, em grupos de no
máximo 3 pessoas, pra aumentar a nota, sobre clareza e modos de
argumentar. Cada grupo teria que mandar pelo menos um representante
pra assistir a reunião do CONPURO de 10/junho e fazer anotações...
26ª aula (10/jun): deixei cópias de um trecho do livro da Judith
Gersting na sala e levei os "representantes" pra reunião do CONPURO.
O plano original era eles assistirem só o trecho entre 11:00 e
12:00hs da reunião, mas às 12:00 estava começando uma votação
confusa e interessante e eles pediram pra ficar um pouco mais.
Depois a gente voltou pra sala de aula, os não-representantes já
tinham debandado, e a gente discutiu o que todo mundo tinha visto na
reunião e como o trabaho seria feito. É pra analisar pelo menos
isto:
* _como_ cada lado expõe seus argumentos,
* que argumentos parecem furados (e porquê),
* quem vocês acham que está sendo claro, sincero, etc,
* que "técnicas" certas pessoas usaram pra ser claras (ou
convincentes, ou interessantes, ou simpáticas, etc; obs: ninguém
nasce sendo claro - e a gente está tentando aprender a ser claro
nos nossos argumentos matemáticos e não-matemáticos),
* _quem_ cada lado defende - que grupos e atitudes eles protegem, e
que grupos eles atacam, ignoram, excluem, etc.
* que argumentos eram usados pra atacar os inimigos
O trabalho é pra ser entregue em duas semanas.
27ª aula (15/jun):
28ª aula (17/jun):
28.5ª aula (17/jun, 14-16): aula extra.
29ª aula (22/jun): P2, sobre demonstrações. A matéria é o início do
capítulo 2 do livro da Judith Gersting (até indução - detalhes
depois); como a biblioteca está fechada por causa da greve eu
scaneeei o cap.2:
http://angg.twu.net/MD/judith_p59_a_110.pdf
http://angg.twu.net/MD/judith_p59_a_110.djvu
30ª aula (24/jun): enforcado.
31ª aula (29/jun):
32ª aula (01/jul):
33ª aula (06/jul): P3
34ª aula (08/jul):
35ª aula (13/jul): VR
Matéria da VR e da VS:
Relações e funções; construções indutivas: como calcular certas
funções definidas indutivamente e como definir funções;
demonstrações: determinar se sentenças com ∀, ∃ e -> são verdadeiras
ou falsas e mostrar porquê; prova direta, prova por exaustão, prova
por indução.
36ª aula (15/jul): VS
***** Dicas pra VS: *****
Construções indutivas - como na questão 1 da VR (e na questão 1b da
P3) - vão ser MUITO importantes! Certifique-se de que você sabe
calcular conjuntos definidos indutivamente - por exemplo, faça A={1}
na questão 1 da VR e calcule T_A0, T_A1, T_A2, e garanta que você
sabe visualizar o resultado de T_A e T_N - e que você sabe definir
formalmente funções recursivas, como fib (onde, por exemplo, fib(8)
é o oitavo termo da série de Fibonacci - você vai precisar de
definições por casos para definir fib) e o Lin_N. Além disso garanta
que você sabe definir formalmente funções como: "f(n) é n quando n é
um natural e f(p) é f(a)*f(b) quando p é da forma (a,b)". MESMO QUE
VOCÊ LEVE MEIA HORA PRA ENTENDER A SINTAXE CERTA PARA ESTAS
DEFINIÇõES NÃO DESISTA!
Scans (depois eu ponho eles nos "dias" certos; todos têm gabarito):
http://angg.twu.net/MD/MD_P2_2011jun22.djvu
http://angg.twu.net/MD/MD_P2_2011jun22.pdf
http://angg.twu.net/MD/MD_P3_2011jul06.djvu
http://angg.twu.net/MD/MD_P3_2011jul06.pdf
http://angg.twu.net/MD/MD_VR_2011jul13.djvu
http://angg.twu.net/MD/MD_VR_2011jul13.pdf
http://angg.twu.net/MD/MD_VS_2011jul15.djvu
http://angg.twu.net/MD/MD_VS_2011jul15.pdf <-- Vejam!
|
