[INCLUDE TH/speedbar.blogme] [SETFAVICON dednat4/dednat4-icon.png] [SETFAVICON IMAGES/forthsun.png] [# (defun c () (interactive) (find-blogme3-sh0-if "2010.1-MD")) ;; http://angg.twu.net/2010.1-MD.html ;; file:///home/edrx/TH/L/2010.1-MD.html #] [lua: LR = R -- (find-TH "2007dnc-lst") -- (eev-math-glyphs-edrx) eev_math_glyphs_edrx() sgmlify_table["\04"] = "δ" sgmlify_table["\05"] = "ε" sgmlify_table["\207"] = "ω" sgmlify_table["\209"] = "⊔" sgmlify_table["\209"] = "⊔" sgmlify_table["\163"] = "Γ" sgmlify_re = "([\1-\8\12\14-\31\128-\254])" ] [htmlize [J Matemática Discreta - 2010.1] [# # «.resumos-das-aulas» (to "resumos-das-aulas") # (find-books "__comp/__comp.el" "scheinerman") #] [P O livro principal do curso é Scheinerman: "Matemática Discreta, uma introdução". A biblioteca tem vários exemplares; o código dele na biblioteca é 510/S316.] [P Vamos usar o Hopcroft/Motwani/Ullman, "Introdução à teoria de autômatos, linguagens e computação", como livro auxiliar (mas praticamente só vamos usar o primeiro capítulo dele). O código dele na biblioteca é 005.73/H791.] [BE' Resumos das aulas que já foram dadas (e planos para algumas aulas futuras): Primeira aula (08/março): só um aluno veio Segunda aula (10/março): redução versus igualdade operações cujos resultados são valores de verdade: <, <=, =, >=, > operações definidas por tabelas: e, ou, implica, não operações cujo resultado nem sempre está definido: /, sqrt operações cujo domínio não está definido: + (serve para vetores e matrizes) tradução entre português e linguagem matemática análise sintática em português: sujeito, predicado, objeto, etc; árvores termos suprimidos em português: "o gato comeu o rato e cuspiu os ossos" versus: "o gato comeu o rato e depois o gato cuspiu os ossos do rato" em matematiquês tudo é explícito expansão de definições, substituição de valores; contextos que expressões são válidas? "12+3*+/-" não é válida vamos precisar de construções indutivas pra definir "expressões válidas" o que é uma demonstração? Exemplo do 2^100-2^99=2^99 quando é que uma demonstração está correta? quando é que uma demonstração está completa? a definição precisa de "demonstração" é indutiva Terceira aula (15/março): definição alternativa de "divide": (que pode não ser equivalente à definição "real"!) a|b se aÝN ´ bÝN ´ ÎkÝ{0,1,2,...b}.b=ka vimos várias definições para {0,1,2,...,-3} que pareciam razoáveis problemão: quando é que uma definição está "errada"? [vou completar o resumo da 3ª aula depois] Quarta aula (17/março): na aula anterior vimos que no ´ e F "domina", e no  o V "domina" usamos isto para reduzir 50|1000 a V rapidamente idéia parecida: Seção 4, Contra-exemplo (pp.24-26) comparação com 10*9*8*...*(-2)*(-3)*(-4) = 0 vimos como definir "proposições sobre números": P(x) = (x>4), P(x)=V a redução ýxÝA.P(x) -v^v-> F por contra-exemplo envolve encontrar um aÝA tal que P(a) seja falso, e envolve uma "justificativa" - uma anotação do lado da seta -v^v->, explicando o porquê. Seção 6: Listas listas são diferentes de números, de valores de verdade e de conjuntos duas listas são iguais se têm o mesmo comprimento e mesmas componentes já vimos pares ordenados: (3,4)ÝR^2, (3,4) \neq (4,3) em conjuntos a ordem não importa: {3,4}={4,3} redução para "Ý": aÝ{b,c,d} -v^v-> a=ba=ca=d a definição formal de produto cartesiano só aparece na p.72: A×B = {(a,b)|aÝA, bÝB} podemos pensar que "aÝA" e "bÝB" são "geradores", e geram todos os valores possíveis de a e b em C = {nÝ{10,...,20} | n é primo} o gerador é o nÝ{10,...,20}; o "n é primo" é um "filtro" que descarta certos valores de n filtros e geradores podem ser combinados: {(a,b) | aÝ{0,1,2}, bÝ{1,2,3}, a<=b} {a^2 | aÝ{-1,0,1,2}} -v^v-> {1,0,1,4} = {0,1,4} Quinta aula (22/março): Seção 5: Álgebra de Boole Esquema de prova 4: tabelas de verdade Apêndice C: Fundamentos Sexta aula (24/março): Exercício. Considere as expressões abaixo: ýxÝAþB.P(x) ýxÝAÌB.P(x) ÎxÝAþB.P(x) ÎxÝAÌB.P(x) ýxÝA.(xÝB->P(x)) ýxÝA.(xÝB´P(x)) ÎxÝA.(xÝB->P(x)) ÎxÝA.(xÝB´P(x)) Algumas são equivalentes entre si. Quais? Encontre modos de mostrar que algumas sentenças não são equivalentes. Dicas: podemos começar com A={1,2} e B={2,3}. P pode ser qualquer proposição definida sobre {1,2,3}. Exemplos de proposições: P(x) = (x=3) P(x) = (x=1->x=3) P(x) = V Pense em Álgebra e Cálculo 1... x e x^2 são funções diferentes mas que coincidem em x=0 e x=1; x^2 e (x+1)(x-1)+1 são duas funções de x "equivalentes", mas tivemos que aprender bastante Álgebra pra entender isto... estamos aprendendo métodos álgebricos para outras operações. Sétima aula (29/março): Distribuí uma folha que tinha o exercício da aula anterior e várias outros problemas relacionados: http://angg.twu.net/MD/MD_exercicios_2010mar29.pdf [Falta transcrever o resumo da aula]. Oitava aula (31/março): Funções como relações, i.e., como conjuntos de pares; consertamos a idéia de ver as oito expressões lógicas acima funções de três argumentos. [Transcrever o resumo da aula] Nona aula (5/abril): Relações reflexivas, simétricas, transitivas; fechos reflexivos, simétricos, transitivos; relações de equivalência; partições. Décima aula (7/abril): Revisão para a prova. O gabarito dos exercícios da sétima aula está em: http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.djvu http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.pdf Décima-primeira aula (12/abril): Primeira prova ("P1"). A matéria são as definições e construções das seguintes seções do livro: Seção 1. Definição Seção 2. Teorema Seção 3. Prova (só a discussão da p.22: "Omitindo passos") Seção 4. Contra-exemplo Seção 5. Álgebra de Boole Seção 6. Listas Seção 8. Conjuntos I: Introdução, Subconjuntos Seção 9. Quantificadores Seção 10. Conjuntos II: Operações Seção 11. Relações Seção 12. Relações de Equivalência Seção 13. Partições Seção 20. Funções Lembre que vimos algumas coisas em sala - como a relação de redução - que não estão no livro e que podem cair na prova, e lembre também que estamos deixando para ver as demonstrações direito na segunda unidade do curso. 12ª aula (14/abril): Discussão do gabarito da prova. Introdução à segunda unidade do curso: "demonstrações". 13ª aula (19/abril): Vou estar fora, num congresso. Depois vamos decidir como repor esta aula. 14ª aula (21/abril): Idem. 15ª aula (26/abril): Aula virtual - nesse dia eu já deveria ter voltado, mas só consegui um vôo de volta que chega no Rio na segunda de tarde... vou passar atividades pro monitor e deixar um scan dos exercícios na internet. 16ª aula (28/abril) "Prova direta de teoremas da forma se-então"... Examinamos com bastante cuidado a prova da p.18 do livro: 1) Vamos mostrar que se (x é par) e (y é par) então (x+y é par), ou seja: (x é par)´(y é par)->(x+y é par) 2) Seja xÝZ par. 2') Seja yÝZ par. 3) 2|x (por (2) e pela def 1.1) 4) 2|y (por (2') e pela def 1.1) 5) ÎaÝZ.x=2a (por (3) e pela def 1.2) 5') Seja aÝZ tal que x=2a (possível por (5)) 6) ÎbÝZ.y=2b (por (4) e pela def 1.2) 6') Seja bÝZ tal que y=2b (possível por (6)) 7) x+y=2a+2b=2(a+b) (por (5') e (6')) 8) Seja cÝZ tal que c=a+b 8') x+y=2c (por (7) e (8)) 8'') ÎcÝZ.(x+y)=2c (por (8) e (8')) 9) 2|(x+y) (por (8'') e pela def 1.2) 10) x+y é par (por (9) e pela def 1.1) 17ª aula (03/maio): Continuação da aula anterior. Exemplo: queremos provar que (P->Q)´(Q->R)´(R->S)->(P->S). Se seguimos o modelo da aula passada, temos: 1) queremos provar que (P->Q)´(Q->R)´(R->S)->(P->S). 2) Suponha (P->Q). 3) Suponha (Q->R). 4) Suponha (R->S). 5) Queremos provar que (P->S) é verdade. 6) Olhe todas as linhas da tabela-verdade que obedecem (2), (3) e (4); elas obedecem (P->S). Repare que no passo (6) nós olhamos para todos os "mundos" que obedecem as hipóteses (2), (3) e (4) e vimos que em cada um deles (P->S) é verdade. Podemos modificar isto um pouco: 1) queremos provar que (P->Q)´(Q->R)´(R->S)->(P->S). 2) Suponha (P->Q). 3) Suponha (Q->R). 4) Suponha (R->S). 5) Queremos provar que (P->S) é verdade. 6') Suponha que P é verdade. 7) Q é verdade (por (6) e (2)). 8) R é verdade (por (7) e (3)). 9) S é verdade (por (8) e (4)). Agora olhamos para todos os "mundos" que obedecem (2), (3), (4) e (6') e descobrimos que S é verdade em todos eles. No exemplo da aula anterior temos infinitos "mundos" que obedecem as hipóteses. 18ª aula (05/maio): Como muitas pessoas tinham a sensação de que o livro não tinha exemplos e exercícios suficientes de provas da forma "se-então" nós demos uma olhada em provas por indução. 19ª aula (10/maio): Provas por indução. Obs: antes da aula de 10/maio vou fazer mais uma apresentação informal sobre programação em Lua, das 14:00 às 16:00hs, na sala 2, pra quem estiver interessado. Os temas principais vao ser como usar linguagens dinâmicas (em contraposição a compiladas) e como programar e resolver problemas sem (quase) nunca pensar em I/O e usuários. 20ª aula (12/maio): Provas por contradição. 21ª aula (17/maio): Passei uma folha de exercícios pra ajudar a entender hipóteses contraditórias e provas por contradição. A versão LaTeXada dessa folha virou a 4ª página da versão online da P1: http://angg.twu.net/LATEX/2010-1-MD-prova-1.pdf 22ª aula (19/maio): Discussão dos exercícios da folha e da representação gráfica dos "mundos". Passei alguns problemas pras pessoas pensarem em casa: 1) o que acontece quando P,QÝ{F,V}, nÝN (N=conj dos naturais)? 2) Eu mostrei em sala uma representação boa desses mundos como números, e mostrei uma outra que eu disse que era ruim; encontrar dois mundos diferentes que a representação ruim encodifica como o mesmo número. 3) Como representar como números os mundos se as variáveis são P,QÝ{F,V}, m,nÝN? 4) Entender provas por contradição usando conjuntos de mundos. 23ª aula (24/maio): Não vou poder dar aula neste dia, vou repor depois. 24ª aula (26/maio): Não vou poder dar aula neste dia, vou repor depois. 25ª aula (31/maio): Torres de Hanói (detalhes depois). 26ª aula (2/junho): 27ª aula (7/junho): 28ª aula (9/junho): 29ª aula (14/junho): P2. Matéria: "demonstrações". Ainda vamos definir precisamente que "esquemas de provas" (ver p.525 do livro) podem cair... até a aula de 19/maio vimos estes aqui: 1 (p.20; "=>") 2 (p.22; "<=>") 3 (p.25; como refutar um "=>" por contra-exemplo) 4 (p.30; equivalência lógica via tabela verdade) 7 (p.57; "Î") 8 (p.58; "ý") 11 (p.136; contrapositiva) 12 (p.138; contradição) 17 (p.158; indução) http://angg.twu.net/LATEX/2010-1-MD-prova-2.pdf (find-angg "LATEX/2010-1-MD-prova-2.tex") 30ª aula (16/junho): 31ª aula (21/junho): Estruturas algébricas - introdução 31.5ª aula (22/junho - reposição): aritmética modular 32ª aula (21/junho): Grupos e permutações. Exercícios recomendados: p.210, 1,2,3,5. 33ª aula (28/junho): Aula cancelada por causa do jogo do Brasil. 33.5ª aula (29/junho): Cardinalidade, conjuntos infinitos enumeráveis e não-enumeráveis, teorema da diagonal de Cantor, paradoxo de Russell. 34ª aula (30/junho): Mais sobre grupos. 35ª aula (5/julho): mini-revisão. 35.5ª aula (6/julho): reposição?? 36ª aula (7/junho): P3, sobre estruturas algébricas (grupos). Exercícios recomendados: p.210: 1-12 Exercícios recomendados: p.334: 1-7,9-15 Exercícios recomendados: p.350: 1,2,4,7,9,10 37ª aula (12/julho): VR (ninguém fez) 38ª aula (14/julho): VS: http://angg.twu.net/LATEX/2010-1-MD-prova-VS.pdf (find-angg "LATEX/2010-1-MD-prova-VS.tex") 4ª feira, 28/julho: VS extra, no PURO, das 14:00 às 16:00hs.   Aviso   Esta é a VS extra que eu avisei que iria acontecer. Vamos ter uma "VS extra" (as regras ainda não estão totalmente definidas) no fim de julho, sobre provas formais e regras de dedução. Os exercícios de preparação para ela estão aqui: http://angg.twu.net/LATEX/2010-1-MD-exercs-P4.pdf (find-angg "LATEX/2010-1-MD-exercs-P4.tex") Obs: isto ^ é uma versão _muito_ preliminar, só com os primeiros exercícios! ] [# As reposições das aulas que eu faltei vão acontecer nas 3ªs, 16-18hs. #] [BE' Notas da P1, P2, P3, VR, VS (versão parcial - work in progress): P1 P2 P3 VS 10960036 ALVARO CESAR DE ANDRADE NETTO 4.1 2.2 0.0 11060036 ANA CAROLINA CLIVATTI FERRONATO 2.7 3.7 0.5 11060002 ANDREW DE CASTRO SANT ANNA 8.4 6.3 10.0 11060003 ARTHUR RORIS PEDROZO 2.2 11060010 BRISA JARDIM LOSQUE 10860017 CESAR AUGUSTO SALGADO CREMONEZI 4.0 2.6 20960059 CICERO MARQUES DE ALMEIDA 4.2 4.4 7.5 4.6 11060011 DANILO LUIZ EBIHARA BARBOSA 2.7 2.2 0.0 20960043 DAYANA GONCALVES BARBOSA 3.5 3.2 0.0 11060012 DIEGO GOMES DA SILVA 2.2 3.8 0.0 11060013 ELI JAMES DE SOUZA AGUIAR 0.2 4.4 0.5 11060014 ERICK OLIVEIRA DE MENDONCA 6.6 7.7 6.0 11060015 FABIO MARQUES RODRIGUES 11060029 FELIPE PINHEIRO ORNELLAS 2.6 4.4 4.5 3.1 10960026 FERNANDO ELIAS LIMA PICHONE 1.5 20960061 FERNANDO TEIXEIRA MAGALHAES 1.9 5.1 0.0 2.2 10960009 GABRIEL ALEIXO MORENO 5.7 6.0 4.5 3.6 11060030 GABRIELA QUEIROZ DE AVILA 7.0 6.8 11.0 11060004 HENRIQUE CARVALHAL SILVEIRA 1.6 2.2 0.0 20960045 HUGO CESAR BAUR SALGADO 6.2 5.1 10.0 11060005 HUGO RODRIGUES SILVA 1.0 1.2 10960012 IGOR DA CUNHA SOUZA --- 10860002 IURY DE OLIVEIRA GOMES FIGUEIREDO 4.1 3.2 0.5 11060016 JOSE SANTOS LOPES 1.4 3.1 0.0 20960047 JULIANA SALES MARTINS (P3 -> 1.2) 1.6 4.9 3.5 2.7 20960048 JULIO CESAR DE OLIVEIRA FREITAS 2.3 4.6 8.0 4.8 11060031 KILDARE ALVES DA SILVEIRA 0.9 2.5 11060038 LEANDRO GOMES BARRETO 3.2 5.2 1.6 11060017 LEONATHAN DE MESQUITA BRAGA 3.2 2.2 0.0 11060018 LUANA PESSANHA BAPTISTA DE ASSIS 0.9 5.7 0.0 2.7 20960051 LUCAS ALVES ALONSO 4.6 7.2 3.5 2.2 11060019 LUCAS GONCALVES WESTPHAL LIMA 0.0 11060006 LUCAS PERES MARQUES DA SILVA 3.0 2.2 11060020 LUCIANA ALMEIDA EPPINGHAUS 5.0 3.5 1.0 11060037 LUIS FELIPE SEABRA (P1 -> 5.5?) 11060021 LUIZ FELIPE ORPHAO DE MATTOS 1.8 20960063 MARCELLO DUARTE CRESCENCIO 11060032 MARCELO VAITSMAN NERCESSIAN M CANARIO 2.1 11060033 MARCO PAULO BRITO DE ALMEIDA MAINART 0.4 2.2 20960064 MARCO VINCIUS DA COSTA ALVES 0.5 2.2 20960065 MARCOS AURELIO JOSE RAMOS JUNIOR 0.4 4.6 0.5 3.8 11060022 MARIA CAROLINA SORIANO FREIRE 3.3 5.0 1.6 11060023 MAURICIO CARDOSO BARBOZA 4.1 5.4 4.0 4.6 11060024 MURILO DE MELO JATOBA 10960001 NATHAN ARAUJO FREITAS 1.0 20960067 PEDRO CAVALCANTI TRINDADE MARINS 1.9 6.0 0.0 11060008 PETER CLAYDER LOPES DA SILVA 20960069 RAFAEL LOURENCO GOMES 3.5 4.5 3.6 2.0 20960053 RAPHAEL BARBOSA DA SILVA MORATO 2.9 3.3 0.5 11060009 RENAN DA SILVA RODRIGUES 0.0 0.0 20960055 RENAN DO CARMO DE SOUZA 11060026 RODOLFO HAMMES BASTOS 6.0 6.5 11.8 11060034 ROMULO CARLOS ALMEIDA DA SILVA 11060027 THAIS QUESADA FERNANDES 4.7 5.5 6.5 11060028 ULYSSES ALESSANDRO COUTO ROCHA 1.0 20960057 WALLACE CABRAL DA SILVA 4.2 2.5 1.5 1.7 20960071 WILDER NICO BARCELOS 3.1 3.8 ???????? ALICE CIRUFO 3.0 0.5 1.1 ???????? JONOTHAS ] (- 18 3.5) [P [BF Ainda não terminei o plano de curso! 8-(]] [# «resumos-das-aulas» (to ".resumos-das-aulas") (defun eesum (s &optional e) (interactive "r") (let* ((str (ee-se-to-string s e)) (prg (format "(+ %s)" str)) (r (eval (read prg)))) (message "%s -> %s" prg (list r (/ r 3.0))))) (defun eesum2 () (interactive) ;; (eek "2*C-a 19* C-SPC 21*") (eek "C-a C-SPC 12*") (eesum (point) (mark))) (define-key my-mode-map "\M-v" 'eesum2) O curso vai ser dividido em três partes. Na primeira parte, "Construções indutivas", vamos ver mais ou menos rapidamente as seções abaixo do Scheinerman, nos concentrando ] [# ;; (find-scheinermanpage (+ 24 1) "Capítulo 1. Fundamentos") ;; (find-scheinermanpage (+ 24 1) "Seção 1. Definição") ;; (find-scheinermanpage (+ 24 7) "Seção 2. Teorema") ;; (find-scheinermanpage (+ 24 16) "Seção 3. Prova") ;; (find-scheinermanpage (+ 24 22) "Omitindo passos") ;; (find-scheinermanpage (+ 24 24) "Seção 4. Contra-exemplo") ;; (find-scheinermanpage (+ 24 27) "Seção 5. Álgebra de Boole") ;; (find-scheinermanpage (+ 24 29) "Equivalência lógica") ;; (find-scheinermanpage (+ 24 35) "Capítulo 2. Coleções") ;; (find-scheinermanpage (+ 24 35) "Seção 6. Listas") ;; (find-scheinermanpage (+ 24 44) "Seção 7. Fatorial") ;; (find-scheinermanpage (+ 24 49) "Seção 8. Conjuntos I: Introdução, Subconjuntos") ;; (find-scheinermanpage (+ 24 56) "Seção 9. Quantificadores") ;; (find-scheinermanpage (+ 24 62) "Seção 10. Conjuntos II: Operações") ;; (find-scheinermanpage (+ 24 77) "Capítulo 3. Contagem e Relações") ;; (find-scheinermanpage (+ 24 77) "Seção 11. Relações") ;; (find-scheinermanpage (+ 24 84) "Seção 12. Relações de Equivalência") ;; (find-scheinermanpage (+ 24 93) "Seção 13. Partições") ;; (find-scheinermanpage (+ 24 100) "Seção 14. Coeficientes Binomiais") ;; (find-scheinermanpage (+ 24 116) "Seção 15. Contagem de Multiconjuntos") ;; (find-scheinermanpage (+ 24 124) "Seção 16. Inclusão-Exclusão") ;; (find-scheinermanpage (+ 24 135) "Capítulo 4. Mais Provas") ;; (find-scheinermanpage (+ 24 135) "Seção 17. Contradição") ;; (find-scheinermanpage (+ 24 143) "Seção 18. Contra-exemplo Mínimo") ;; (find-scheinermanpage (+ 24 156) "Seção 19. Indução") ;; (find-scheinermanpage (+ 24 169) "Capítulo 5. Funções") ;; (find-scheinermanpage (+ 24 170) "Seção 20. Funções") ;; (find-scheinermanpage (+ 24 184) "Seção 21. O Princípio da Casa do Pombo") ;; (find-scheinermanpage (+ 24 191) "Seção 22. Composição") ;; (find-scheinermanpage (+ 24 197) "Seção 23. Permutações") ;; (find-scheinermanpage (+ 24 212) "Seção 24. Simetria") ;; (find-scheinermanpage (+ 24 219) "Seção 25. Tipos de Notação") ;; (find-scheinermanpage (+ 24 227) "Capítulo 6. Probabilidade") ;; (find-scheinermanpage (+ 24 228) "Seção 26. Espaço Amostral") ;; (find-scheinermanpage (+ 24 232) "Seção 27. Eventos") ;; (find-scheinermanpage (+ 24 241) "Seção 28. Probabilidade Condicional e Independência") ;; (find-scheinermanpage (+ 24 252) "Seção 29. Variáveis Aleatórias") ;; (find-scheinermanpage (+ 24 258) "Seção 30. Esperança") ;; (find-scheinermanpage (+ 24 279) "Capítulo 7. Teoria dos Números") ;; (find-scheinermanpage (+ 24 279) "Seção 31. Divisão") ;; (find-scheinermanpage (+ 24 285) "Seção 32. Máximo Divisor Comum") ;; (find-scheinermanpage (+ 24 296) "Seção 33. Aritmética Modular") ;; (find-scheinermanpage (+ 24 308) "Seção 34. O Teorema do Resto Chinês") ;; (find-scheinermanpage (+ 24 314) "Seção 35. Fatoração") #] [P Página da versão de 2009.2 do curso: [R 2009.2-MD.html].] ] [# # Local Variables: # coding: raw-text-unix # modes: (fundamental-mode blogme-mode) # End: #]