- Professor: Hugo Nobrega
- Turmas: 11829 (currículo novo), 15169 (currículo antigo)
- Códigos no SIGA:
- ICP035 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: Discord
- Local: Lab 1 (dentro do IC)
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 no Lab 1 do IC.
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 | 13/5 às 20:00 |
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 |
|---|---|---|---|
| ter 18/mar | 00 | Introdução e burocracias | Vídeo; Quadros |
| qui 20/mar | 01 | Definição e primeiros exemplos de categorias | Vídeo; Quadros |
| ter 25/mar | 02 | Mais exemplos de categorias | Vídeo; Quadros |
| qui 27/mar | 03 | Ainda mais exemplos de categorias; categoria livremente gerada a partir de um grafo; a noção de “preservação de estrutura” | Vídeo; Quadros |
| ter 1/abr | sem aula | Semana da Computação | - |
| qui 3/abr | sem aula | Semana da Computação | - |
| ter 8/abr | 04 | Estrutura e preservação; funtores | Vídeo; Quadros |
| qui 10/abr | 05 | Mais sobre estrutura e preservação | Vídeo; Quadros |
| ter 15/abr | 06 | “Homomorfismos” como dívidas/pagamentos; “Geração livre” e homomorfismos; exemplos de funtor | Vídeo; Quadros |
| qui 17/abr | 07 | Inversas e isomorfismos; Prova de que “imagem direta” é um funtor Set -> Set | Vídeo; Quadros |
| ter 22/abr | sem aula | Feriado enforcado (Tiradentes/São Jorge) | - |
| qui 24/abr | 08 | Introdução a Haskell: sintaxe, tipos, classes de tipos e instâncias | Vídeo; Quadros; Código |
| ter 29/abr | 09 | Mais introdução a haskell: condicionais (pattern matching, if-then-else, case, guardas); list comprehension; definições recursivas vistas como homomorfismos saindo do “livre” | Vídeo; Quadros; Código; Output do REPL |
| qui 1/mai | sem aula | Feriado (Trabalhador) | - |
| ter 6/mai | 10 | Exemplo de tipo de dados: ArvBin; classes de tipos Semigroup, Monoid |
Vídeo; Quadros; Código; Output do REPL |
| qui 8/mai | 11 | Mais sobre foldr: “para listas, com fun :: a -> b, temos que foldr fun valor é homomorfismo de (a, [a], (:), []) para (a, b, fun, valor)”; foldr para ArvBin ; folds de outras aridades; funções da biblioteca padrão para Foldable (sum, product, elem, toList, etc) |
Vídeo; Quadros; Código |
| ter 13/mai | sem aula | Aula cancelada por falta de segurança | |
| qui 15/mai | 12 | Corrigindo erro da aula 11 (“composta binária”); construtor de tipo Either; “fold” para tipo (e não construtor de tipo); soma, produto, potência, etc de naturais como “fold” de Natural | Vídeo; Código |
| ter 20/mai | sem aula | Aula cancelada por falta d’água no IC | |
| qui 22/mai | 13 | Classe de tipos Applicative (<*>, pure, liftA2): definição e exemplos |
Vídeo; Quadros; Código; Output do REPL |
| ter 27/mai | 14 | Mais sobre Applicative; Alternative |
Vídeo; Quadros; Código; Output do REPL |
| qui 29/mai | 15 | Produtos em haskell e em categorias; exemplos | Sem vídeo; Quadros |
| ter 3/jun | 16 | Produtos de estruturas de uma assinatura; coprodutos em haskell e em categorias | Vídeo; Quadros |
| qui 5/jun | 17 | Exemplos de coprodutos | Vídeo; Quadros |
| ter 10/jun | 18 | Mais exemplos de coprodutos | Vídeo; Quadros |
| qui 12/jun | 19 | Limites Colimites | Vídeo; Quadros |
| ter 17/jun | 20 | Transformações naturais | Vídeo; Quadros |
| qui 19/jun | sem aula | Feriado (Corpus Christi) | - |
| ter 24/jun | 21 | Mais exemplos de transformações naturais; “hom-sets” e “funtores hom”; equivalências de categorias; adjunções (ideia) | Vídeo; Quadros; Código |
| qui 26/jun | 22 | Adjunções: o exemplo Livre/Esquecedor | Vídeo; Quadros |
| ter 1/jul | 23 | Produto e coproduto como funtores; adjunto à esquerda do produto (funtor diagonal) | Vídeo; Quadros |
| qui 3/jul | 24 | Mais exemplos de adjunções; outra definição de adjunção | Vídeo; Quadros |
| ter 8/jul | 25 | Monads: introdução em categorias e haskell | Vídeo; Quadros |
| qui 10/jul | 26 | Mais sobre monads; Monad “Writer” (“Logador”); Monad IO; “Hello World” em haskell | Vídeo; Quadros; Código |
| ter 15/jul | |||
| qui 17/jul |
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.