Quick
index
main
eev
eepitch
maths
angg
blogme
dednat6
littlelangs
PURO
(C2,C3,C4,
 λ,ES,
 GA,MD,
 Caepro,
 textos,
 Chapa 1)

emacs
lua
(la)tex
maxima
git
lean4
agda
forth
squeak
icon
tcl
tikz
fvwm
debian
irc
contact

2009.2 - Matemática Discreta

Sobre as VSs extras: a 1ª VS extra aconteceu na quarta, 6/jan/2010, e em príncipio as outras vão acontecer na quarta 13/jan/2010 e na quarta 20/jan/2010, sempre começando às 11:00 da manhã. Eu não estou conseguindo atualizar esta página com freqüência, então se você estiver interessado em fazer alguma das VSs extras por favor entre em contato comigo por e-mail: eduardoochs@gmail.com.


O livro oficial do curso é o Scheinerman.

Horários, sala, etc: veja a página sobre os cursos que eu estou dando.

Página do curso do semestre passado: aqui.


Cronograma (o que foi dado nas aulas que já aconteceram):


AGOSTO
2009-aug-24

(Aula 1)

Noção de "redução" para calcular os valores de expressões; valores podem ser números, valores de verdade (F, V), conjuntos, etc; "=" como comparação; contextos, valores de variáveis, definições; as operações lógicas "e" e "ou"; como interpretar "para todo" e "existe" sobre conjuntos finitos.
Exercícios pra casa: para A={1,2,3}, B={2,3,4}, C={2,3}, calcule a∈A.a∈C, Ɐa∈A.a∈B, ∃b∈B.3<b, Ɐa∈A.∃b∈B.a<b.

2009-aug-26

(Aula 2)

Aula cancelada (por causa de um concurso).

2009-aug-31

(Aula 3)

Mais operações lógicas: implicação, biimplicação, negação.


SETEMBRO
2009-sep-02

(Aula 4)

Tabelas de verdade; tautologias; contra-exemplos; seguimos a prova da p.18 do Scheinerman (a soma de dois pares é par) e fizemos uma correspondente para o exercício 3 da p.24 (o produto de dois pares é par), começando com um idéia em uma linha: "se x=2a e y=2b então xy=2(2ab)"; pedi pra todo mundo ler o capítulo 1 e descobrir o que ele diz sobre o nível de detalhe correto de provas.

2009-sep-07

(Aula 5)

Feriado.

2009-sep-09

(Aula 6)

Definições equivalentes; substituição de iguais por iguais; três definições diferentes de "divide" (chamei elas de divide, divide', divide''; só uma delas tinha expansão finita)

2009-sep-14

(Aula 7)

Começamos o capítulo 2 do Scheinerman. Introduzi algumas operações que vamos usar e que não estão definidas explicitamente no livro: comprimento de uma lista e extração de uma componente de uma lista. A definição formal de "a=b" quando a e b são listas. Os problemas de contagem do Scheinerman usam duas outras operações implicitamente que nós vimos em detalhes na aula: {(a,b) | a∈A, b∈B, P(a,b)} e contagem dos elementos de um conjunto. A correspondência entre B={(a,b) | a,b∈{1,...,4}, b≠a} e C={(a',b') | a'∈{1,2,3,4}, b'∈{1,2,3}} - em C o b' diz qual dos elementos que "ainda não foi escolhido" (i.e., que é diferente de a) é escolhido para ser o b.

2009-sep-16

(Aula 8)

Auto-teste: pedi pros alunos escolherem ou o problema 4 da p.43 ou o 4 da p.24 do Scheinerman, resolverem do modo mais claro possível (30 mins pra isso) e depois trocarem com um colega pra cada um "corrigir" o do outro, apontando o que estava errado ou pouco claro e indicando melhorias possíveis. Não valia nota, então todos deveriam ficar à vontade pra apontar todos os erros e melhorias possíveis.
Depois os alunos que quisessem mais dicas de correções e melhorias deveriam se juntar em grupos de no mínimo 4 pessoas, preparar uma só folha com a melhor resposta que conseguissem, e me entregar pra eu "corrigir" ela fazendo comentários por escrito.

2009-sep-21

(Aula 9)

Conjuntos, A=B, ∈, ⊆, ⊊, ⊈, ℘(A), A×B

2009-sep-23

(Aula 10)

Como construir ℘(A) por uma árvore de decisões; tipos de objetos; conjuntos e listas podem ter elementos de vários tipos; avisei que vamos ver outros tipos depois, mas que eles geralmente vão poder ser representados por conjuntos, listas, etc; definição formal de interseção; conjuntos definidos por propriedades: por enquanto vimos ℘(A) = {B|B⊆A}, A×B = {(a,b)|a∈A, b∈B} e A∩B = {a∈A|a∈B} - as propriedades que vão nos interessar mais retornam conjuntos finitos quando recebem conjuntos finitos. Mencionei que R = {A conjunto | A∉A} contraditório - R∈R e R∉R (vamos ver isto com detalhes depois). Pedi pra todo mundo tentar fazer todos os problemas das páginas 55 e 56.

2009-sep-28

(Aula 11)

Produtórios, somatórios, fatoral, (¬∃a∈A.P(a))=(Ɐa∈A.¬P(a)), (¬Ɐa∈A.P(a))=(∃a∈A.¬P(a)).

2009-sep-30

(Aula 12)

(Aula pra muito poucas pessoas, porque foi depois da prova de Cálculo 2, que acabou tarde).
O que é uma "proposição qualquer"; como encontrar todas as proposições sobre um conjunto de 4 elementos.


OUTUBRO
2009-out-05

(Aula 13)

(Revisão)

2009-out-07

(Aula 14)

P1 (PDF, LaTeX; inclui uma versão preliminar do gabarito). Matéria: seções 1-6 e 9 do Scheinerman.

2009-out-12

(Aula 15)

Feriado.

2009-out-14

(Aula 16)

Poucos alunos vieram, aí a gente só discutiu as questões da prova.

2009-out-19

(Aula 17)

Semana acadêmica.

2009-out-21

(Aula 18)

Semana acadêmica.

2009-out-26

(Aula 19)

Feriado.

2009-out-28

(Aula 20)

Aula sobre definir proposições... não deu muito certo, vamos voltar a esse assunto depois.


NOVEMBRO
2009-nov-02

(Aula 21)

Feriado.

2009-nov-04

(Aula 22)

Começamos o capítulo 3 do Scheinerman; vimos a seção 11 ("Relações"), e eu pedi pros alunos fazerem os problemas das págs 81 a 83. Estou tentando insistir bastante na idéia de que uma relação pode ser representada de vários modos.
Estou devendo um texto comparando matematiquês, Pascal, C e linguagens como Ruby, Python e Lua.

2009-nov-09

(Aula 23)

2009-nov-11

(Aula 24)

2009-nov-16

(Aula 25)

Passei um exercício pra ser feito em grupos de no máximo 3 pessoas e entregue na aula seguinte, com todos os detalhes, valendo nota; passamos a aula tirando dúvidas do exercício.
O enunciado do exercício era: "Quantas relações de equivalência temos no conjunto {1,2,3}? Encontre todas usando uma árvore de decisão, represente todas de todos os modos que já vimos, e diga quais são funções. Além disso faça o gráfico (como em Cálculo I) dessas funções e relações, e descubra o domínio e a imagem de cada uma."

2009-nov-18

(Aula 26)

Defini (em Português) uma função "delete" que recebe uma particão de um conjunto e retorna uma partição de um conjunto menor; usei ela (e a inversa dela) pra mostrar como conseguir a árvore de decisão que resolve o problema de encontrar todas as partições no conjunto {1,2,3,4,5}. Passei um exercício pra casa pra esclarecer isto: T_3 é o conjunto de todas as partições de {1,2,3}, T_4 o das partições de {1,2,3,4}, etc; delete4 é uma função de T_4 em T_3, e pedi que as pessoas encontrassem delete3^{-1} e mostrassem como usar essa relação pra construir a "segunda escolha" da árvore de decisão que encontra todas as partições de conjuntos cada vez maiores.
Exercícios pra casa, do livro: p.182, 2, 3, 4.
Vimos que listas podem ser vistas como funções (o domínio é o conjunto de índices), e vimos como listas infinitas ("seqüências") costumam ser definidas ("definição indutiva"), e calculamos (a_1, a_2, a_3, a_4, ...) para um caso simples.
Avisei que o texto sobre a comparação (src) entre matematiquês, Pascal, C e Lua estava pronto.

2009-nov-23

(Aula 27)

2009-nov-25

(Aula 28)

Aula sobre as Torres de Hanói; começamos a ver em sala como resolver o problema e possíveis modos de representá-lo "matematicamente", isto é, usando conjuntos, listas, etc. Voltamos à idéia de definições indutivas para seqüências infinitas: primeiro seqüências de números, por exemplo, a_0=1, a_{n+1}=2·a_n, depois seqüências de conjuntos, p.ex. A_0={0}, A_{n+1}=A_n∪{n+1}. Avisei que a solução geral das Torres de Hanói pode ser vista como uma seqüência, mas não é uma seqüência de números, então vamos deixá-la pra depois.
Passei um exercício pra ser feito em grupos de no máximo 3 pessoas e entregue no dia 2/dezembro, sobre como representar matematicamente posições, movimentos e seqüências de movimentos no jogo das Torres de Hanói; começamos a discutir representações possíveis na sala, e vimos que algumas representações propostas eram ruins, e porquê. Os alunos ficaram de pensar o resto e escrever tudo em casa.
Avisei muito enfaticamente que eles têm que começar a escrever direito e arriscar a escrever em português o que eles pensam, mesmo que no início fique confuso. Eu não vou mais aceitar respostas que sejam só rabisquinhos sem explicação, muito menos rabisquinhos iguais aos dos outros grupos, e menos ainda rabisquinhos que não só estão iguais aos dos outros como ainda estão errados.

2009-nov-30

(Aula 29)

Introdução a provas por indução. Definimos uma seqüência a_n por a_1=1, a_{n+1} = 2a_n + 1, uma outra, b_n, que calcula a expansão binária de n, e uma outra por c_n = 2^n-1; vimos que o conjunto A = {n∈{1,2,...} | a_n=c_n} parece ser o próprio conjunto {1,2,...}, mas como provar isto?... Aí vimos o enunciado do princío de indução (seção 19 do Scheinerman, p.156) e vimos vários conjuntos que obedecem ou não obedecem a condição Ɐn∈N.n∈B→(n+1)∈B.
Não passei nenhum exercício pra nota - deixei pra quarta, mas pedi pros alunos lerem a seção 19 do livro.


DEZEMBRO
2009-dez-02

(Aula 30)

2009-dez-04

(Aula 31)

2009-dez-07

(Aula 32)

2009-dez-09

(Aula 33)

P2. Matéria: relações (inclui partições, etc), funções, seqüências, um pouco sobre definições indutivas e indução.

2009-dez-14

(Aula 34)

VR

2009-dez-16

(Aula 35)

VS