2019.1 FMC2, turmas de Thanos

Horários: 246T34 [14h55–16h35] @ A308 (U1; U2)
246N12 [18h45–20h25] @ A308 (U1; U2; U3)
Sala do prof:A225
Contato:thanos@imd.ufrn.br
Aulas gravadas: 2019.1; 2018.2
Study group: Telegram, atraves de link disponível em notícia do SIGAA [regras]
Monitoria/TA:fmc.imd.ufrn.br
Horário de atendimento:mande email para marcar (tente primeiro discutir tua dúvida no study group, e na monitoria)
Turmas anteriores: 2018.2; 2018.1; 2017.2; 2017.1; 2016.1

Prerequisitos

É prerequisito ter aprendido bem o conteudo transversal de FMC1. Sem aprender esses assuntos primeiro, não faz sentido se matricular em FMC2. (Obs.: aprenderpassar.)

Então—ANTES de começar—é bom estudar os:

  1. How to prove it, de Velleman (1, 2, 3)
  2. Do fmcbook os capítulos:
    • Linguagens
    • Demonstrações
    • Os números naturais: recusão; indução
    • Combinatória enumerativa
    • Teoria elementar de números
    • Congrüências
  3. Mathematical Proofs, de Chartrand, Polimeni, Zhang (0, 2)
  4. Comments on style de James Munkres.
  5. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

(Obs.: estudarler.)

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e provas. Demonstrações diretas e indiretas, refutações. Definições por recursão – provas por indução. A linguagem de conjuntos, funções, e relações.
Linguagem; Lógica; Recursão; Indução (U0)
Crash course!
Conjuntos, Funções, e Relações (U1)
Conjuntos, sua notação, suas operações, e seus leis. Uniões disjuntas, famílias e partições. Tuplas ordenadas e produto cartesiano. As operações unitárias de união e interseção. As relações de subconjunto, e de pertencer. Multiconjuntos e sequências. Funções, o conceito de função e suas propriedades. Intensão x extensão. Domínio, codomínio. Imagem, pre-imagem. Funções totais e parciais, injetivas, sobrejetivas, bijetivas. Aridade. Função constante, função identidade, projeções, funções características. Funções recursivas; recursão mutual. Funções de ordem superior. A notação de λ-calculus. Funções x predicados. Relações e suas propriedades. Relações de equivalência, clásses de equivalência. Operações em relações, inversão, composição, fechos.
Elementos de Álgebra abstrata (U2)
Conjuntos com estrutura. Operações. Teoria dos grupos. Demonstrações com o uso de identidades algébricas. Homomorfísmos. Outras estruturas: aneis, monoides, reticulados. Álgebras booleanas.
Elementos de Teoria de Conjuntos (U3)
Enumerações e conceito intuitivo de cardinalidade. Paradoxos e os axiomas Zermelo–Fraenkel. Representações de matemática (traduções). Os números naturais; axiomas Peano.
Elementos de Teoria de Ordem (U3)
Ordens parciais, totais, densas, bem-fundadas. Diagramas de Hasse. Elementos notáveis (majorantes, máximos, supremos). Conjuntos ordenados, reticulados, reticulados completos. Construções de conjutos ordenados. Dualidade. Ordens canônicas, ordens lexicográficas. Monotonicidade. Teoremas de ponto fixo. Conjuntos bem-ordenados.
Aplicações e assuntos auxiliares
Relações bem-fundadas e indução transfinita. Números ordinais. Limites de computação. Noções de decidibilidade e de semi-decidibilidade. λ-calculus, lógica combinatória. Elementos de teoria dos tipos. Noções de semántica de linguagens de programação. Y-combinator, fixpoints e recursão. Axiom of choice e suas conseqüências. Tipos de dados algébricos. Programação funcional. Programação lógica. Bancos de dados.

Bibliografia

(Conhece o libgen.io?)

Principal

Auxiliar

Para cada um dos assuntos que tratamos, procure a secção «Leitura complementar» no capítulo correspondente do fmcbook para mais referências.

  • Pierce et al: Software Foundations, Volume 1: Logical Foundations [SF1]
  • Lawvere & Schanuel: Conceptual Mathematics: A first introduction to categories (I, II)
  • Velleman: How to prove it (1–3)
  • Pinter: A book of abstract algebra (2–5, 6, 12, 17)
  • Davey & Priestley: Introduction to lattices and order (1, 2)
  • Paul Halmos: Naïve set theory
  • Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
  • Goldrei: Classic set theory, for guided independent study (4, 7, 8)
  • Raymond Smullyan: Satan, Cantor, and Infinity
  • Raymond Smullyan: A beginner's guide to mathematical logic (Volume 1)
  • Paul Halmos: Linear Algebra Problem Book (1)
  • Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)
  • Aluffi: Algebra: Chapter 0
  • Mac Lane & Birkhoff: Algebra (1.1–1.3)
  • Herstein: Topics in Algebra (2.1–2.5 [skip # and *])
  • Simmons: Introduction to topology and modern analysis (1)
  • Munkres: Topology (1)
  • Loomis & Sternberg: Advanced Calculus (0)
  • João Marcos: Lógica Aplicada à Computação website (TdC, R&I)

Programação

Links

Dicas

Avaliação

Pontos

A disciplina é dividida em 3 unidades (vejá Conteudo). Em cada unidade o aluno vai receber de 0 a 100 pontos. As provas escritas de cada unidade terão 100 pontos em total. (Para pegar uma idéia dessas provas, olhe nos sites das minhas turmas de FMC2 de semestres passados.)

Alem desses pontos, um aluno pode ganhar pontos extra: por participação; por homework; ou por provas-surpresas. Esses pontos valem igualmente com os pontos de prova escrita. Estou tenando ao máximo ser justo com esses pontos, mas nenhuma justificativa será dada por ganhar (ou não ganhar, ou perder!) pontos extra.

Umas regras: (1) nunca dê uma resposta que tu não pensou sozinho; (2) não tente “forçar a barra” dando respostas aleatórias nas minhas perguntas com objetivo único de ganhar pontos extra.

Umas provas escritas podem ter pontos bônus. Esses são pontos que são condicionalmente considerados: para considerá-los um aluno precisa ter pelo menos 50pts normais (não-bônus). As questões que valem pontos-bônus são em geral em assuntos auxiliares que, mesmo que merecem ser reconhecidos, não devem ser determinantes para aprovar na disciplina.

Presenças

Veja notícia no SIGAA para informações sobre presenças, chamadas, plickers, etc.

Provas

As provas principais serão avisadas com antecedência de pelo menos 48 horas.

Provinha 0

  • Provinha 0 (pts: 0; bônus: 0) (dia: 16/02/2019)
    { uncensored, answers }
    correções: p1 (8M), p2 (5M).

Unidade 1

Unidade 2

  • Prova 2.? (pts: ?; bônus: ?) (dia: ?)

Unidade 3

  • Prova 3.? (pts: ?; bônus: ?) (dia: ?)

Homework

Obs.:

  • Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.
  • «Até» é sempre inclusivo.
  • Homeworks marcados assim são opcionais; considero o resto obrigatório.
  • Depois de cada aula, um homework é sempre válido, obrigatório, e essencial: sem olhar para teu caderno, defina todas as noções e demonstre TODOS os teoremas da aula;
    while (não conseguiu) {
      estude o assunto;
      tente novamente;
    }
    

09/01/2019

  1. Estude os ítens que tenho nos prerequisitos.
  2. Brinque com Haskell ou PureScript.
  3. Estude a (pouca) coisa que tá escrita no capítulo «Estratégias de provas» do fmcbook.
  4. Estude e resolve os exercícios/problemas do capítulo 3 de Velleman.
  5. Estude o capítulo «Linguagens» do fmcbook.
  6. Estude o capítulo «A linguagem de lógica proposicional» do fmcbook.
  7. Estude os capítulos 1–2 de Velleman.
  8. Estude brutalmente o capítulo «Os números naturais: recursão; indução» do fmcbook, e assista minhas aulas relevantes do FMC2/2018.2 (as 3 primeiras aulas).
  9. Installe o Coq; dê uma lida no «Preface» do SF1 (link na Bibliografia); estude o capítulo «Basics» do SF1.

04/02/2019

  1. Estude as «Prova 0» dos semestres passados (2017.1; 2017.2; 2018.1; 2018.2). Tente resolvê-las sozinho. Depois, leia bem todas as correções digitalizadas dos alunos dos semestres anteriores, para aproveitar dos comentários disponíveis. (Melhor estudar isso «por página».)

13/02/2019

  1. Estude as poucas coisas que estão escritas no Capítulo I
  2. Capítulo 3: até §24
  3. Problemas: Π3.1–Π3.5.

16/02/2019

  1. Capítulo 3
  2. Capítulos 4–5

18/02/2019

  1. Capítulo 6: até §38

21/02/2019

  1. Faça finalmente o hw #9 do dia 09/01/2019!
  2. Faça finalmente o hw #8 do dia 09/01/2019!

23/02/2019

  1. Brinque com: Haskell; PureScript; ou Idris (lembra do hw #2 do dia 09/01/2019?)
  2. Numa das linguagens funcionais acima, implementa (você mesmo) o tipo de naturais, e defina a adição, multiplicação, e exponenciação
  3. Estude o capítulo «Proof by induction» do [SF1]
  4. Capítulo 11: estude bem e resolva todos os exercícios
  5. Problemas: Π11.1

24/02/2019

  1. Estude todas as correções da Prova 0

25/02/2019

  1. Problemas: Π11.2; Π11.3
  2. Problema: Π11.4

27/02/2019

  1. Estude as §§55–58 (cap. 7)
  2. Problemas: Π7.1; Π7.2; Π7.3; Π7.5; Π7.6
  3. Problemas: Π7.7; Π7.8; Π7.9
  4. Estude as §§104–106,109

01/03/2019

  1. Estude as §§104–113

08/03/2019

  1. Estude as §§114–116
  2. Problemas: Π12.1; Π12.2; Π12.3; Π12.8; Π12.9

11/03/2019

  1. Estude as §§114–124
  2. Problemas: Π12.4; Π12.5; Π12.6; Π12.7; Π12.10; Π12.11; Π12.12; Π12.13
  3. Problemas: Π12.14
  4. Defina recursivamente o somatório e produtório finito (bounded) duma seqüência {aₙ}ₙ

13/03/2019

  1. Estude as §§125–128

14/03/2019

  1. Assista a aula correspondente do 2018.2 para esclarecer a resolução dos Π12.11–12
  2. Comece estudar os Parts I & II do [Lawvere]

15/03/2019

  1. Estude as §§129–130

18/03/2019

  1. Estude as §§131–135

19/03/2019

  1. Re-estude a §130

20/03/2019

  1. Estude as §§136–137
  2. Problemas: Π13.1; Π13.2; Π13.3; Π13.4; Π13.5; Π13.9; Π13.10; Π13.11

21/03/2019

  1. Re-estude a §137
  2. Problemas: Π13.1; Π13.2; Π13.3; Π13.4; Π13.5; Π13.6; Π13.7; Π13.8

22/03/2019

  1. Re-estude a §136, especialmente as iterações
  2. Estude a §138

25/03/2019

  1. Resolva as atividades das secções instáveis mencionadas abaixo (especialmente todas as equivalências da «viagem épica»)
    AVISO: as secções «Uma viagem épica», «Estilo pointfree» não são estaveis no fmcbook; os assuntos são auxiliares; mas as atividades que aparecem lá são muita boa prática para os assuntos não-auxiliares!
  2. Estude as secções «Imagens; preimagens» e «Funções de ordem superior»
  3. Problemas: Π13.9; Π13.10; Π13.11; Π13.12; Π13.13; Π13.14

26/03/2019

  1. Problemas: Π13.9; Π13.10; Π13.11; Π13.12; Π13.13; Π13.14; Π13.15; Π13.19; Π13.20

27/03/2019

  1. Secções: «Funções parciais»; «Currificação»; «Fixpoint»; «Conjuntos indexados e famílias indexadas»; «Definições recursivas» [até o item «O que tá acontecendo?»]
  2. Problemas: Todos exceto o que se trata da «(FIB)»
  3. Resolva finalmente o hw do dia 21/03/2019, especialmente o Π13.8

30/03/2019

  1. Resolva todos os problemas das provas 1.1T, 1.1N, 1.2T, 1.2N
  2. Estude os gabaritos
  3. Estude a secção «Definições recursivas» inteira
  4. Estude a secção «Conjuntos indexados vs. famílias indexadas» do capítulo 12

03/04/2019

  1. Estude o Capítulo 15 até a §154

05/04/2019

  1. Estude as §§155–158
  2. Problemas: todos do primeiro intervalo de problemas

08/04/2019

  1. Estude a §159 «Relações de ordem»
  2. Estude as §§161–162
  3. Estude as §§163–164
  4. Problemas: todos os problemas do Capítulo 15 excéto o último
  5. Problemas: o último

11/04/2019

  1. Leia o artigo Revenge of the nerds, de Paul Graham
  2. Brinque com Haskell/PureScript/Agda/Idris, usando as idéias que temos encontrado na Unidade 1
  3. Conheça uma LISP: Racket e/ou Clojure
  4. Para programadores de Java, C++, e C#: palestra introduzindo Scala por Venkat Subramaniam

12/04/2019

  1. Estude o Capítulo 17
  2. Estude o Capítulo 18 até a §171

15/04/2019

  1. §172
  2. Problemas: Π18.1; Π18.2; Π18.3

16/04/2019

  1. Problemas: Π18.1; Π18.2; Π18.3; Π18.4

17/04/2019

  1. Resolva todo o homework que tu tem deixado pra lá
  2. §§173–175 até o Exercício x18.47
  3. §121: «Conjuntos indexados vs. famílias indexadas»

Pontos extra

Unidade 1

Pontos de participação

N T
Tyrone 32Victor Hugo 25
Jessiely 18Misael 4
Douglas 16João Mendes 21
Paulo H. 2 Gabriel Alves 5
Andrécio 3 Danilo 16
Maurício 21Francisco Assis B1
Jonathan 4 Lucas Emanoell 8
Hagliberto 5 José Eduardo 3
Francisco Assis CJ 5 Matheus Z. 3
Matheus Menezes 1 Daniel Oliveira 14
Karine 15Daniel Smith 1
Leo 9 Antonio Thiago 1
Moisés 11
Weverson 1
Mateus Melo 8
Levir 1
Keler 3
Cynthia 1
Adailton 5
Kaio 1

Unidade 2

Pontos de participação

N T
Tyrone 1João Mendes 2
Jessiely 1Victor Hugo 1
Franscisco Assis CJ1Jeckson 2
Moisés 1
Kaio 1
Maurício 1
Hagliberto 1

Histórico de aulas

13/02/2019: Introdução [video]

  • Apresentação dos assuntos principais
  • Erros comuns:
    • Type error
    • Erro de lógica
    • Erro de matemática
    • Erro de semântica
  • Os típos principais: afirmações (tbm: proposições); objetos (tbm: individuais)
  • Diferença entre as duas frases:
    • «Se __A__, (então) __B__.»
    • «Como __A__, (logo) __B__.»
  • Os dois erros principais em definições:
    • Não aceitar objetos que deveriam ser aceitos
    • Aceitar objetos que não deveriam ser aceitos
  • ⇒: ``somente se''; ⇐: ``se''
  • O significado da palavra «equivalente» em matemática
  • Noções primitivas – Definições
  • O contexto duma definição
  • Exemplos de definições na geometria euclideana.
  • Axiomas – Teoremas
  • Sinônimos de «teorema» e seus usos: lema, corolário
  • Hipótese; tese
  • Programando programas vs. provando teoremas
  • Lemmata como funções e bibliotecas de programação
  • Sintaxe vs. semântica
  • Uma linguagem para expressões aritméticas
  • Árvores de derivação
  • Parsing: de forma linear para arvore sintática

15/02/2019: Linguagens [video]

  • Números vs. numerais vs. dígitos
  • A notação BNF
  • Uma gramática em BNF para a linguagem de expressões aritmêticas
  • meta-: linguagens e metalinguagens; variáveis e metavariáveis
  • BNF para a linguagem de lógica proposicional
  • Limitações da linguagem da lógica proposicional
  • A linguagem de FOL

16/02/2019: Provinha 0

18/02/2019: Erros; Linguagens; Demonstrações [video]

  • «A ⇒ B ⇒ ... ⇒ true». E daí?!?
  • Prova errada: por afirmação do conseqüente
  • A vírgula mágica de roubo e seus amigos: «sendo», «com», etc.
  • Como e quando usar o «onde»
  • Diferença entre declarada e definida
  • Caligrafia em notação
  • [Jessiely] a expressão x₁,...,xₙ
  • Açúcar sintáctico e abreviações
  • Convenção: notação infixa
  • Demonstrações: como atacar e como usar cada proposição

20/02/2019: Demonstrações [video]

  • Como atacar e como usar o resto dos conectivos
  • Dar nome ou não?
  • A ordem de quantificadores importa?
  • Como demonstrar que duas formulas da FOL não são logicamente equivalentes.
  • Prova por casos
  • Outsourcing o tratamento de negações: botando pra dentro
  • Negação de fórmula atómica
  • Verdade por vacuidade

22/02/2019: Demonstrações; Naturais, recursão, indução [video]

  • Demonstrações
    • Igualdade
    • Reductio ad absurdum
  • Naturais, recursão, indução
    • Os naturais formalmente (Nat)
    • 3 jeitos de descrever a idéia da definição de Nat
    • «Nada mais.»
    • regras de inferência
    • arvore sintáctica dos numerais de Nat
    • Por que esses nats? O bom e o ruim.
    • Recursão
    • Definindo funções no Nat recursivamente
    • Definindo a adição
    • Calculando usando a definição
    • Focos, casamentos, e substituições
    • Cálculo: 3 + 2 = 5
    • Desafio: definir a multiplicação
    • Recursão «no tal argumento»
    • Casos para cada argumento?
    • Cadê a recursão?
    • O poder da recursão
    • Definição recursiva da multiplicação
    • Cálculo: 3 · 2 = 6
    • Provando propriedades sobre nossas operações
    • A + é associativa
      • O que significa?
      • Posso escrever a afirmação como uma fórmula?
      • Agora, bora provar!
      • Um aparente deadend
      • Não: posso separar casos
      • Prove então!
    • Tentando provar sem indução: separando em casos, e casos, e casos…
    • A idéia da indução

25/02/2019: Nats; recursão; indução [video]

  • Nats: definição e operações
  • Associatividade de adição: tentativa tradicional
  • Como escolher a variável para separar casos
  • O princípio da Indução nos Nats
  • Associatividade da +: primeira demonstração
  • Associatividade da +: segunda demonstração
  • Como escolher a variável para fazer indução
  • «indução "no k"»
  • Comutatividade da +
  • Igualdade sintáctica vs. denotacional
  • Uso de Lemmata
  • Recursão para definir relações
  • Por que aceitar o princípio da indução?
  • O que que têm especial os nats?
  • E sobre os não-nats?
  • Definições inductivas
  • Recursão e indução: dois lados da mesma moeda
  • Cadê princípio de recursão então??

27/02/2019: Nats, recursão, indução; Conjuntos [video]

  • Nats, recursão, indução
    • Outros princípios de indução
    • Indução a partir dum natural n
    • Indução forte
    • Princípio de Boa Ordem
    • Equivalência dos princípios
    • Mais que uma base
  • Conjuntos
    • os «def» em cima de = e de ⟺
    • Tipos de objetos e como introduzí-los
    • Conceito de conjunto
    • Noções primitivas: ser conjunto, pertencer (∈)
    • Conjuntos como “black boxes
    • Igualdade entre conjuntos: A=B
    • Intensão vs extensão
    • Notação
    • Set comprehension (Set-builder notation)
    • Não use «|» como abreviação de «tal que» nem em texto nem nas fórmulas existenciais!
    • Açucar sintáctico no set-builder
    • Erro comum: quantos elementos {x,y,z} tem?
    • As relações binárias: =, ⊆, ⊇, ⊊, ⊋
    • ⊈ vs. ⊊
    • Cardinalidade |A|

01/03/2019: Conjuntos [video]

  • Cuidado: O uso de ⊂ na literatura
  • Definindo o conjunto vazio: nossos deveres
  • O predicado Empty(–)
  • Variáveis livres e ligadas; sombreamento de variável
  • Obrigação de definir notação (nome) para objeto: artigo definido vs. indefinido
  • Provas de existência & unicidade
  • Teorema: existência do conjunto vazio
  • Teorema: unicidade do conjunto vazio
  • O conjunto vazio (Ø)
  • Singletons
  • O conjunto universal
  • Oito proposições sobre o Ø e um conjunto A
  • Escolhendo a ordem de atacar teoremas
  • {Ø} ≠ Ø
  • Operações entre conjuntos e dois jeitos de defini-las
  • As operações binárias: ∩, ∪, \, Δ
  • A operação unária de complemento: ~
  • O operador Powerset (℘)
  • Iterando o ℘ no Ø
  • Cardinalidade de ℘A

08/03/2019: Conjuntos [video]

  • Generalizando as operações de união e intersecção: as operações unárias ⋂, ⋃
  • Intuição sobre os ⋂, ⋃, e ℘ e as {, }
  • Iterando os ⋂, ⋃, e ℘ no Ø
  • tuplas como noções primitivas: igualdade, tamanho
  • tuplas como black boxes
  • projeções: πi
  • Implementando um tipo: 3-tuplas

11/03/2019: Conjuntos [video]

  • Recap
  • O tipo de 1-tuplas
  • O tipo de 0-tuplas
  • A única 0-tupla: ()
  • Como pensar no tipo void da C
  • Equações fundamentais de tuplas
  • Produto cartesiano (×)
  • Cardinalidade do A×B
  • Definindo o Aⁿ
  • Implementação-agnóstico
  • Seqüências
  • outras notações
  • União e Intersecção de seqüências de conjuntos
  • Famílias indexadas
  • Exemplo: Os conjuntos Aₚ e Cₚ de todos os ancestrais e todos os filhos de p
  • Traduzindo afirmações da linguagem natural para relações entre conjuntos e vice-versa
  • União e Intersecção de famílias indexadas de conjuntos
  • Família indexada como generalização de n-tuplas e seqüências
  • Σ vs. ⋃
  • Riemann's rearrangement theorem
  • Produto cartesiano generalizado (de família indexada de conjuntos)
  • Um exercício para aprender como atacar e como usar alvos que involvem operações grandes

13/03/2019: Conjuntos; Funções [video]

  • Conjuntos
    • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
    • Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente)
    • Como usar um fato do tipo D≠Ø em nossas provas: «Seja dD
    • lim inf, lim sup
  • Funções
    • Conceito, notação, igualdade.
    • Igualdade extensional vs. intensional
    • Duas religiões sobre funções e seus black boxes
    • O conjunto (A→B) (também denotado por BA)
    • (Co)domínios vazios.
    • Diagramas internos e externos.
    • Como definir e como não definir funções
    • Expressões com buracos.

15/03/2019: Conjuntos; Funções; Prova 1.1 [video]

  • Conjuntos
    • Seqüências de conjuntos: lim inf, lim sup, lim
    • Cuidado: “sejando” membros de conjuntos sem usar apenas uma variável
  • Funções
    • Diagramas internos e externos
    • Como definir e como não definir funções
    • Diferença entre f(x) e f
    • Expressões com buracos
    • A notação lambda

18/03/2019: Funções [video]

  • Mini-sermão sobre provas escritas
  • Um toque de λ-cálculo
  • Computação com λ
  • β-redex; β-reducção
  • α-renomeamento (α-equivalência) e captura de variável
  • η-equivalência
  • essas idéias vistas em conjuntos (set builder)
  • first-class citizens
  • desafio: achar almas (lambdas) para habitar corpos (típos)
  • funções de graça: identidade
  • composição
  • mais funções de graça: inclusão A↪B
  • leis de composição
  • operações totais vs parciais
  • associatividade da composição
  • comutatividade?
  • possui identidade(s)?
  • aplicação parcial
  • mais funções de graça: restricção
  • diagramas comutativos

20/03/2019: Funções [video]

  • constante: três definições
  • função com (co)domínio vazio
  • função característica
  • Unix shell: um calculador de booleanos
  • if-then-else expressions vs branching statements
  • mais funções de graça:
    • cross (f×g);
    • pair (f,g);
    • pointwise (f*g)
    • diagonal Δ
  • Funções injetoras, sobrejetoras, bijetoras: formalmente e informalmente
  • Exemplo: codificação dos pares de Nats nos Nats
  • Cardinalidade de (A↣B)

22/03/2019: Funções [video]

  • iterações
  • uma prova errada não quis dizer teorema errado
  • conseqüência de teorema errado não quis dizer que a conclusão é errada
  • a composição preserve as “-jetividades”
  • a frase «pela escolha de»
  • inversas com pontos–“por dentro”
  • exercícios
  • leis da inversa
  • o que podemos concluir se uma composição é bijetora

25/03/2019: Funções [video]

  • uma viagem épica: mono e epi
  • estilo pointfree (ou pointless)
  • imagem e preimagem
  • problema na notação
  • possível definição alternativa de preimagem
  • problema na notação alternativa f(X)?
  • funções de ordem superior
  • a função-imagem respeita as uniões e as intersecções?

27/03/2019: Funções [video]

  • função-imagem: nível coração
  • funções parciais
  • funções não-determinísticas
  • funções para implementar outros típos
  • seqüências, famílias indexadas
  • restrição com buraco: seu tipo
  • tipos dependentes
  • currificação
  • programando funções: escopos; dados; alvos;
  • definindo funções por recursão
  • quantas das k,d,c aceitas como definidas?

29/03/2019: Funções; Prova 1.2 [video]

  • definindo funções por recursão
  • associatividade algebrica de operador vs. associatividade sintáctica de conectivo
  • higher-order fun
  • um λ não terminante
  • Quantas idempotentes no 3?
  • de união para o coproduto

01/04/2019: Aula cancelada

03/04/2019: Funções; Categorias; Relações [video]

  • funções
    • Sermão: poluição do escopo
    • de união para o coproduto
    • o problema de definir a f∪g
    • união disjunta ; coproduto ; sum type
    • conjuntos isomórficos/isómorfos
    • definindo a f+g
    • produtos vs. coprodutos: nível coração
  • categorias
    • definição
    • exemplos
    • o conceito de produto
  • relações
    • conceito, notação
    • diagramas internos
    • definindo relações
    • igualdade
    • intensional vs extensional
    • construções e operações em relações
    • relação oposta
    • composição
    • RT=T? RF=F?

05/04/2019: Relações [video]

  • notação: R∘S vs S∘R
  • propriedades de relações
  • fechos informalmente
  • a ordem dos fechos importa?
  • fechos formalmente
  • potências/iterações de relação
  • preguiças nos diagramas internos
  • um exemplo de fecho
  • relações de equivalência
  • classes de equivalência

08/04/2019: Relações; Programação [video]

  • Relações
    • fechos: top-down vs bottom-up
    • partições
    • o conjunto quociente
    • enxergando o conjunto quociente
    • subconjuntos finitos vs cofinitos
    • relações de ordem
    • relações recursivas
    • relações de ordem superior
    • perigos de funções mal-definidas
    • ε-perto é uma relação de equivalência?
  • Programação
    • paradigmas
    • programação imperativa (procedural; OO)
    • puramente OO
    • programação declarativa (funcional; lógica)
    • side effects
    • lazy vs strict
    • static vs dynamic types
    • puramente funcional

10/04/2019: Relações; Programação [video]

  • Relações
    • Quantas relações de equivalência num conjunto com 3 membros?
  • Programação
    • Lazy vs strict (call-by-name, call-by-value, call-by-need, call-by-push-value)
    • turing-completeness
    • higher-order
    • dependent types
    • Lisps
    • Abuso de linguagens
    • Conselhos
    • Programação Funcional
    • Indução e recursão nas listas
    • Programação Lógica
    • Funções como relações
    • Entendi!

12/04/2019: Programação; Algebra abstrata; Teoria dos grupos; Prova 1.3 [video]

  • Programação
    • Turing complete vs Pacman complete
    • Bancos de dados
  • Algebra abstrata
    • História: de Euclides até Galois
    • uns problemas antigos e abertos na época
    • construções com régua e compasso
    • raízes de polinómios com fórmulas
    • a idéia da álgebra abstrata
    • Conjuntos estruturados
    • abusos notacionais
  • Teoria dos grupos
    • permutações
    • notação com parenteses e com cíclos
    • achando os membros do S₃
    • leis abstratas satisfeitas por S₃
    • primeira defição de grupo
    • ℘A é grupo com qual das operações binárias conhecidas de conjuntos?

15/04/2019: Teoria dos grupos [video]

  • Umas definições de grupo, com outros tipos de estrutura
  • Grupos abelianos
  • O que significa teoria dos grupos
  • Teorema: unicidade de identidade
  • Escolhendo leis
  • Nãœxemplo de grupo: strings com concatenação
  • Teorema: leis de cancelamento: (GCL) & (GCR)
  • operando por o mesmo lado
  • propriedade de igualdade: substituir iguais por iguais
  • cuidado com o uso do "⇒" nas demonstrações
  • Teorema: unicidade dos inversos
  • não podemos operar nos dois lados por lados diferentes
  • Notação: Grupos aditivos e multiplicativos
  • potências em grupos
  • Propriedades de inversos
  • G abeliano ⇒ (ab)⁻¹ = a⁻¹b⁻¹
  • Enxergando a mesma igualdade em maneiras diferentes
  • Teorema: inverso da identidade
  • Como podemos provar que algo é inverso/identidade?
  • Umas respostas erradas
  • Teorema: resolução de equações: (RESL) & (RESR)
  • Critério: Identidade e inversos mais baratos: (Id-bar) & (Inv-bar)
  • Teoremas: inverso de inverso & inverso de produto
  • {2ⁿ | n inteiro} vira um grupo com adição? Com multiplicação?

17/04/2019: Teoria dos grupos [video]

  • exemplos e nãœxemplos de grupos
    • números com adição
    • definição recursiva do 𝐧 = {0,…,n-1}
    • adição módulo n
    • matrízes com adição
    • números com multiplicação
    • multiplicação módulo n
    • os inversos chegam em pares/casais
    • matrízes com multiplicação
    • (℘A;Δ)
    • strings com concatenação
    • funções reais com pointwise adição e multiplicação
    • as potências de 2
  • duas maneiras de tomar membros dum conjunto indexado
  • previously on FMC2…
  • escolhendo leis (axiomas)
    • como demonstrar que algo não é demonstrável pelumas leis
    • Critérion: G finito + (G0) + (G1) + (GCL) + (GCR) ⇒ G grupo
    • Critérion: (G0) + (G1) + (G2L) + (G3L) ⇒ G grupo
    • o que é «critérion»
    • econômia vs claricidade/intuitividade
    • Critérion: (G0) + (G1) + (G2R) + (G3R) ⇒ G grupo
    • modularidade
    • (G0),(G1),(G2L)
    • magma, semigrupo, monóide, grupo, grupos abeliano
  • ordem de grupo: o(G) ou |G|
  • tem grupos de ordem 0?
  • tem grupos de ordem 1?
  • tabelas Cayley
  • jogando grupoku
  • o grupo ({0,1,2};+₃) e sua tabela Cayley
  • potências de membros de grupo
  • as potências aⁿ para n=-1,0,1,2,…
  • duas definições razoáveis para o a⁻²
  • Teorema: (a⁻¹)² = (a²)⁻¹
  • Definição: As potências aⁿ para n inteiro
  • um diagrama cuja comutatividade é a lei (a⁻¹)² = (a²)⁻¹
  • um diagrama cuja comutatividade é a lei (ab)⁻¹ = b⁻¹a⁻¹
  • ∀a∀b (ab)⁻¹ = a⁻¹b⁻¹ ⇐?⇒ G abeliano
  • ∀a∀b (ab)⁻¹ = a⁻¹b⁻¹ ⇐?⇒ G abeliano

Futuro (fluido)

22/04/2019: Teoria dos grupos

  • O (ab)²
  • Critério: ∀a∀b (ab)⁻¹ = a⁻¹b⁻¹ ⇒ G abeliano
  • Critério: ∀a∀b (ab)² = a²b² ⇒ G abeliano
  • Teorema: se a é um membro dum grupo, todas as suas potências (naturais) também são
  • Teorema: se a é um membro dum grupo, todas as suas potências (inteiros) também são
  • G abel ⇔ ∀a∀b ( (ab)² = a²b² )
  • Definição: ordem de membro de grupo: o(a)
  • o(2) = ∞ no grupo aditivo de reais
  • Quantas ordens diferentes dentro dos membros do S₃
  • Q: quantas de todas as potências de a são distintas?
  • Teorema: tem exatamente o(a) potências distintas de a
  • sinônimo: existem exatamente k potências de a
  • sermão: divisão de Euclides
  • O que podemos concluir se…
    • aᵐ = e para algum m inteiro ⇒ ?
    • o(a) = ∞ ⇒ ?
    • a⁻ᵖ = e para algum p positivo ⇒ ?
  • aᵐ = e ⇔ o(a)|m
  • o(a) = ∞ ⇒ todas as potências de a são distintas
  • Subgrupos: definição
  • Subgrupos: exemplos e nãœxemplos
  • Observação: associatividade de graça no H
  • Observação: H e G não podem ter identidades diferentes
  • Critério: quando H é não vazio, basta fechado pela operação e pelos inversos
  • Critério: quando H é finito e não vazio, basta fechado pela operação
  • Uma relação de equivalência: a RH b ⇐def⇒ ab⁻¹∊H
  • ≤ é uma ordem parcial
  • Critério: one-test
  • Teorema: intersecção de subgrupos é subgrupo
  • Em geral não é verdade para união
  • Uns subconjuntos dum grupo de matrizes. São subgrupos?
  • O subgrupo gerado por um membro de grupo
  • Geradores
  • Bottom-up
  • Top-down
  • Subconjuntos convexos do plano
  • Grupos cíclicos
  • O S₃ é cíclico?
  • (ℤ₆; +₆); (ℤ₆\{0}; ∙₆)
  • Fecho convexo

24/04/2019: Teoria dos grupos

  • Congruences and cosets
  • Existem H≤G tais que G infinito e {Ha₁, Ha₂, …, Haₙ} finito?
  • Congruência modulo subgrupo
  • Coclasses esquerdas/direitas
  • Aviso: o que Ha = H significa
  • Lema: Ha = H ⇔ a ∈ H
  • Conseqüência: a ∉ H ⇔ Ha ≠ H
  • Lema: a ∉ H ⇔ Ha, H disjuntos
  • Para quais a∈G, temos Ha ≤ G?
  • As coclasses direitas são disjuntas duas-a-duas
  • O que podemos concluir sobre a colecção de todas as coclasses direitas
  • Lema: todas as coclasses direitas têm a mesma cardinalidade
  • Teorema: a colecção de coclasses direitas é uma partição do G
  • Assim que tiver um H ≤ G…
  • Como provar que as duas famílias são iguais
  • Por que as coclasses direitas?
  • Os HK, KH
  • HK ≤ S₃? KH ≤ S₃?
  • Todas as coclasses tem a mesma quantidade de membros
  • O teorema de Lagrange
  • Teoria dos números revisitada
  • O teorema de Euler
  • Subgrupos normais
  • Conjugação em grupos
  • O grupo quociente
  • «é conjugado de» é uma relação de equivalência

26/04/2019: Teoria dos grupos; Álgebra abstrata

  • Simetrias do triângulo
  • Simetrias
  • Grupos isómorfos
  • (Homo)morfismos de grupos
  • Uns diagramas comutativos
  • Diagramas de Hasse
  • Critéria de homomorfismo
  • -morfismos, Aut(G), Inn(G)
  • Kernel, Image
  • O primeiro teorema de isomorfismo de grupos
  • Hom(G,H) & End(G)
  • H abel ⇒ Hom(G,H) abel
  • A categoria dos grupos Grp

29/04/2019: Aula cancelada

03/05/2019: Aula cancelada

06/05/2019: Álgebra abstrata

  • Monóide
  • Anel
  • Anel comutativo
  • Divisores de zero
  • Domínio de integridade
  • Domínio de cancelamento
  • DI ⇐?⇒ DC
  • Anel booleano
  • Corpos
  • D domínio de integridade finito ⇒ D corpo
  • Corpos ordenados
  • Lattices

08/05/2019: Os números reais

10/05/2019: O paraíso de Cantor

13/05/2019

15/05/2019

17/05/2019

20/05/2019

22/05/2019

24/05/2019

27/05/2019

29/05/2019

31/05/2019

03/06/2019

05/06/2019

07/06/2019

10/06/2019

12/06/2019

14/06/2019

17/06/2019

19/06/2019

21/06/2019

26/06/2019

28/06/2019

Last update: Thu Apr 18 03:28:59 -03 2019