- Professor: Hugo Nobrega
- Códigos no SIGA:
- ICP035 Tóp. Esp. em Teoria da Computação I, turma 8823 (currículo novo BCC)
- ICP531 Tóp. Especiais em Teoria dos Grafos, turma 12857 (currículo antigo BCC)
- Grupo de discussões: Discord
- Local: Sala DCC (dentro do Instituto de Computação, segundo andar)
Funcionamento da disciplina
O meio primário de comunicação entre os alunos, monitores e professores será o grupo no Discord listado acima.
As aulas serão realizadas em modalidade presencial, com aulas às 3as e 5as de 13:00 às 15:00 na sala F2-014.
Bibliografia
PDF com os conteúdos dos quadros ao longo do semestre (arquivo atualizado periodicamente)
Não seguiremos nenhum livro texto específico; nossas três principais referências são o livros:
- Milewski - Category Theory for Programmers: livro voltado para introduzir categorias para pessoas com perfil de programação. Livro gratuito!
- Menezes, Haeusler - Teoria das Categorias para Ciência da Computação: idem acima, mas com uma pegada um pouco mais teórica (e em português!). Um pouco difícil de achar.
- Awodey - Category Theory: livro mais no estilo “preciso”, e voltado principalmente para um público da matemática, mas que serve bem como referência.
Playlists de Youtube:
- Fong, Milewski, Spivak - Programming with Categories
- Milewski - Category Theory
- Richard Southwell - Category Theory For Beginners: vídeos longos (!) e não muito produzidos (!!), porém extremamente acessíveis sobre categorias
- The Catsters: diversas playlists de vídeos curtos falando sobre alguns (mas não todos) assuntos de categorias
Outros livros (em ordem alfabética):
- Asperti, Longo - Categories, Types, and Structures; An Introduction to Category Theory for the Working Computer Scientist
- Barr, Wells - Category Theory for Computing Science
- Bird, de Moor - Algebra of Programming: livro bastante técnico, principalmente em sua segunda parte onde trata de uma generalização de categorias (“alegorias”)
- Fong, Spivak - Seven Sketches in Compositionality; An Invitation to Applied Category Theory: bastante discussão sobre a aplicação de categorias em diversos contextos
- Perrone - Notes on Category Theory with examples from basic mathematics
- Pierce - Basic Category Theory for Computer Scientists: infelizmente um pouco difícil de achar, mas trata de assuntos básicos de teoria de categorias para pessoas com background em computação de forma bem acessível.
- Riehl - Category Theory in Context
Outros links interessantes:
- http://www-di.inf.puc-rio.br/~hermann/categoria/catecurso/index.htm: slides de um curso de teoria de categorias do prof. Hermann (PUC-Rio), autor de um dos livros acima.
Listas de Exercícios
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 (atualizada 29/9) | 11 de outubro no começo da aula |
| Lista 2 | 18 de outubro no começo da aula |
| Lista 3 (atualizada 26/10) | 3 de novembro no começo da aula |
| Lista 4 (atualizada 2/12) | 22 de dezembro no começo da aula |
| Lista 5 e Parser.hs | 14 de janeiro às 23:59 |
Regras de colaboração
As listas de exercícios podem ser entregues em duplas. Não poderá haver repetição de duplas em diferentes listas! Isso é feito para aumentar a confiança do professor ao dar uma nota individual para cada aluno no final da disciplina.
As diferentes duplas podem sempre discutir os problemas e as ideias de como resolvê-los (e isso é recomendado, pois é uma ótima forma de estudar e aprender!), porém: soluções de exercícios não devem ser compartilhadas entre diferentes duplas (nem de outros períodos). O recomendável é que você não mostre suas soluções completas para alunos de outras duplas, nem veja as soluções completas de outros.
Soluções iguais ou parecidas demais entre duplas diferentes serão desconsideradas.
Cronograma planejado/registro de atividades
| Data | Aula | Conteúdo | Quadros |
|---|---|---|---|
| ter 30/8 | Aula 1 | Introdução; Discussão sobre abstração; Funções puras e “impuras”; A ideia de Categorias | 1 a 8 |
| qui 1/9 | Aula 2 | Exemplo de abstração em matemática (“unicidade de elemento neutro de uma operação, quando existe”); Definição semi-formal de categoria; primeiro exemplo (conjuntos e funções) | 9 a 19 |
| ter 6/9 | Aula 3 | Definição “oficial” de categorias; Exemplos | 20 a 32 |
| qui 8/9 | Aula 4 | Resolução do exercício (categoria vinda de um conjunto+relação); mais exemplos de categorias (“1”, “1+1”, “2”, “categoria oposta” ou “dual”); primeira discussão da ideia de “preservação de estrutura” | 33 a 44 |
| ter 13/9 | Aula 5 | Discussão mais precisa de assinaturas, estruturas e homomorfismos (“mapeamentos que preservam estrutura”); funtores (“homomorfismos entre categorias”) | 45 a 59 |
| qui 15/9 | Aula 6 | Prova de que P (“powerset”, conjunto das partes) é um funtor Set -> Set; exemplo de categoria (Prog), dos tipos e funções em uma linguagem de programação funcional pura (fortemente tipada) | 60 a 69 |
| ter 20/9 | Aula 7 | Recap do funtor “partes” (Set -> Set) e de funtores Prog -> Prog (construtor de tipos F :: t -> s + implementação de fmap :: (t -> s) -> (F(t) -> F(s))); ideia de “como seria” o fmap de listas em python (código de python); primeiro contato com Haskell, exemplo de funtores List e Maybe; definição de um novo funtor “Talvez”; definição (incompleta) de um novo funtor “ArvBin”; código de haskell | 70 a 73 |
| qui 22/9 | Aula 8 | haskell: definindo tipos [exemplo com Naturais], a ideia do “lazy”. Código em haskell | 74 e 75 |
| ter 27/9 | Aula 9 | haskell: definindo funções prefixas e infixas; definindo classes de tipos (typeclasses); definindo instâncias de classes de tipos; código em haskell | 76 e 77 |
| qui 29/9 | Aula 10 | haskell: condicionais em haskell; listas; lazy “just in time evaluation”); exemplo de Fibonacci e Crivo de Eratóstenes (da Aula 8; código em haskell | 78 a 80 |
| ter 4/10 | Aula 11 | haskell: foldr, foldl; “funções produtivas” e laziness; código em haskell ; output do REPL do haskell; código em python; output do REPL do python | 81 e 82 |
| qui 6/10 | Aula 12 | haskell: exemplos de uso do fold: produto, soma, length; “fold para Natural”: soma, produto, potência, etc, como folds; hierarquia de funções recursivas de crescimento muito rápido; motivação para os próximos assuntos: “como especificar que um tipo X serve como retorno de uma função se eu queria na verdade retornar um Integer e uma String?”; código em haskell; output do REPL do haskell | 83 a 87 |
| ter 11/10 | Aula 13 | especificação de “produto de A e B” em haskell; implementação (3 versões: “manual”, tuplas, records); discussão sobre especificação usando apenas a linguagem das categorias; código em haskell; output do REPL do haskell | 88 a 95 |
| qui 13/10 | Aula 14 | Diagramas e diagramas comutativos; produto (definição e exemplos: em Haskell, em Set, na categoria “Naturais com menor ou igual”, na categoria “Naturais com divisibilidade”, na categoria do Rufino da Aula 3) | 96 a 109 |
| ter 18/10 | Aula 15 | Mais discussão sobre produtos; prova de que o exemplo com “Dumbo” e “papagaio” (exemplo 2b) é um produto em Set; isomorfismos em categorias (motivação e definição); prova de que produtos são “únicos a menos de isomorfismo” | 110 a 120 |
| qui 20/10 | Aula 16 | Discussão sobre definições equivalentes para “isomorfismos”; coproduto (definição e exemplos) | 121 a 130 |
| ter 25/10 | Aula 17 | Discussão sobre a expressão “… a menos de isomorfismo único” usada para falar sobre produtos, coprodutos, etc (o isomorfismo é único, mas em outra categoria!); busca por coproduto de monoides (difícil!) | 131 a 137 |
| qui 27/10 | Aula 18 | Coprodutos (“tipos soma” ou “sum types”) em Haskell; Produtos e coprodutos no poset “conjuntos e ‘contido’”; Coprodutos para monoides gerais não é o produto (mas funciona para monoides comutativos!); Coprodutos de monoides (a ideia de “geração livre”) | 138 a 147 |
| ter 1/11 | Aula 19 | Mais sobre construções livres (magma livre); construções livres em haskell; “eliminadores”: setas obtidas pela UMP de um coproduto (either para Either, bool para Bool, ±foldr para listas); desvio discutindo relação entre recursão, soluções de “equações” e pontos fixos; código em haskell | 148 a 153 |
| qui 3/11 | Aula 20 | Mais discussão sobre recursão, soluções de “equações” e pontos fixos; recap da ideia de “a menos de isomorfismo único”: construção de uma categoria dos diagramas com “formato de produto”; definição de objetos iniciais e objetos terminais | 154 a 164 |
| ter 8/11 | Aula 21 | Exemplos de objetos iniciais e terminais em diversas categorias (incluindo Hask); visão geral da construção da aula 20: índices, diagramas, cones, limites; código em haskell; output do REPL | 165 a 176 |
| qui 10/11 | Aula 22 | Definição de cones, cocones, limites, colimites de um diagrama; recap da lista 1: como ver um grafo como um funtor da categoria •⇉• para Set; homomorfismos de grafos nesse novo contexto; transformações naturais: definição e alguns exemplos | 177 a 188 |
| ter 15/11 | sem aula | Feriado | |
| qui 17/11 | Aula 23 | ||
| ter 22/11 | Aula 24 | ||
| qui 24/11 | sem aula | Jogo do Brasil na Copa | |
| ter 29/11 | Aula 25 | ||
| qui 1/12 | Aula 26 | ||
| ter 6/12 | Aula 27 | haskell: Applicative; código em haskell; output do REPL | |
| qui 8/12 | Aula 28 | haskell: mais sobre Applicative; código em haskell; output do REPL | |
| ter 13/12 | Aula 29 | haskell: Alternative e Traversable; código em haskell; output do REPL | |
| qui 15/12 | Aula 30 | haskell: Monad; código em haskell | |
| ter 20/12 | Aula 31 | Última aula! haskell: código em Haskell | |
| qui 22/12 | sem aula | Recesso de fim de ano | |
| ter 27/12 | sem aula | Recesso de fim de ano | |
| qui 29/12 | sem aula | Recesso de fim de ano | |
| ter 3/1 | |||
| qui 5/1 | |||
| ter 10/1 | |||
| qui 12/1 |
Método de avaliação
A definir…