Quick
index
main
eev
maths
blogme
dednat4
littlelangs
PURO
(GAC2,
λ, etc)
(Chapa 1)

emacs
lua
(la)tex
fvwm
tcl
forth
icon
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}=2a_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