- Professor: Hugo Nobrega
- Turma 11974
- Códigos no SIGA:
- ICP35 Tóp. Esp. em Teoria da Computação I (currículo novo BCC)
- ICP531 Tóp. Especiais em Teoria dos Grafos (currículo antigo BCC)
- Grupo de discussões: Telegram
- Fotos dos quadros: (a definir)
- 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 Telegram listado acima.
As aulas serão realizadas em modalidade presencial, com aulas às 3as e 5as de 15:00 às 17:00 na sala DCC.
Bibliografia
Não seguiremos nenhum livro texto específico; nossas 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.
- Leinster - Basic Category Theory: outro livro gratuito sobre teoria de categorias (recomendado por um ex-aluno da disciplina).
- 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):
- 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.
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 | 4 de outubro às 23:59 |
| Lista 2 | 4 de dezembro às 23:59 |
| Lista 3 | 23 de dezembro à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/Links |
|---|---|---|---|
| qui 10/8 | 1 | Introdução à disciplina; discussão sobre abstração | 0 a ? |
| ter 15/8 | - | sem aula | |
| qui 17/8 | - | sem aula | |
| ter 22/8 | 2 | Mais discussão sobre abstração e programação funcional | |
| qui 24/8 | 3 | Definição informal de categorias e exemplos | ? a 24 |
| ter 29/8 | - | sem aula | |
| qui 31/8 | 4 | Definição formal de categorias e exemplos | 25 a 31 |
| ter 5/9 | 5 | Mais exemplos de categorias; a ideia de estruturas e preservação | 32 a 40 |
| qui 7/9 | - | sem aula | |
| ter 12/9 | 6 | Preservação de estrutura (homomorfismos) | 41 a 51 |
| qui 14/9 | 7 | Preservação de estrutura em categorias: Funtores | 52 a 64 |
| ter 19/9 | 8 | Exemplos de funtor Set -> Set: “imagem direta”; discussão de funtores Prog -> Prog | 65 a 74 |
| qui 21/9 | 9 | Introdução a Haskell; funtores em Haskell | 75 a 77; código; output do REPL |
| ter 26/9 | 10 | Mais introdução a Haskell: “condicionais” via pattern matching, if-then-else, case, guards; classes de tipos Show, Eq, Ord; construtor de tipos ArvBin + declaração de funtor | 78; código; output do REPL |
| qui 28/9 | 11 | Haskell: listas finitas e infinitas; fold | código |
| ter 3/10 | 12 | Dúvidas da Lista 1; Haskell: discussão sobre “fold” para Naturais e Árvores Binárias | 79 a 81; código; output do REPL |
| qui 5/10 | 13 | Haskell: Maybe; Categorias: produtos e coprodutos (discussão, intuição e definição) | 82 a 88 |
| ter 10/10 | 14 | Exemplos de produtos e coprodutos | |
| qui 12/10 | - | sem aula | |
| ter 17/10 | 15 | Mais sobre produtos e coprodutos (também em Haskell) | slides; código em haskell; output do REPL |
| qui 19/10 | 16 | Coproduto de monoides (exemplo de “construção livre”); isomorfismos (“produto é único a menos de isomorfismos”) | slides |
| ter 24/10 | 17 | Mais construções livres (monoides, magmas, números naturais, fórmulas da lógica proposicional); mais dicussão sobre isomorfismos | slides; código em haskell; output do REPL |
| qui 26/10 | 18 | Correção da frase “produtos de um mesmo par de objetos são únicos a menos de isomorfismo único”; diagramas, cones; objetos terminais; categoria de fatias | slides |
| ter 31/10 | 19 | Diagramas, cones, limites, cocones, colimites; transformações naturais entre funtores | vídeo; slides |
| qui 2/11 | - | sem aula | |
| ter 7/11 | - | sem aula | |
| qui 9/11 | 20 | Transformações Naturais: motivação, definição, exemplos | vídeo; slides; output do REPL |
| ter 14/11 | 21 | Cones e co-cones como transformações naturais de/para funtores constantes; transformações em Haskell são necessariamente naturais; isomorfismos naturais; equivalências de categorias; funtores adjuntos (pré-definição) | vídeo; slides; código |
| qui 16/11 | 22 | Adjunção: definição “misteriosa” usando o “método da mochila”; definição “mais intuitiva” buscando uma especificação da noção de “livre” para monoides | vídeo; slides; código; output do REPL |
| ter 21/11 | 23 | Adjunção: mais exemplos e definições equivalentes; relações entre “liberdade” e outras noções (indução, recursão) | vídeo; slides; código; output do REPL |
| qui 23/11 | 24 | Funtores “Hom set”; 3a definição de adjunção; funtor adjunto à esquerda do produto (cópia) | vídeo; slides |
| ter 28/11 | 25 | Recap e correção do exemplo “funtor adjunto à esquerda do produto”; Haskell: Applicative (pure, “apply” <*>, lift) | vídeo; slides; código; output do REPL |
| qui 30/11 | 26 | Haskell: (mais) Applicative, Alternative, Traversable e suas leis | vídeo; código; resumo das leis |
| ter 5/12 | 27 | Haskell: “Acumulação de erros”, logs simples com Applicative; Monad (3 definições): categoria de Kleisli | vídeo; código; output do REPL; pequeno texto descrevendo Monads |
| qui 7/12 | 28 | Haskell: mais sobre Monads; (>>) “e então”; notação “do”; exemplos de uso; (a,) e (r ->) são Monads | vídeo; slides; código; output do REPL |
| ter 12/12 | - | sem aula | |
| qui 14/12 | - | sem aula | |
| ter 19/12 | - | sem aula | |
| qui 21/12 | - | sem aula |
Método de avaliação
~5 listas de exercícios, com descarte de ~1 pior(es) nota(s). Não há prova final; a nota para aprovação ao final do período é 5,0.