- Material didático de matemática para estudantes de Ciência da Computação oferecido pelo MIT, cobrindo de forma sistemática conceitos matemáticos essenciais, de lógica e provas até probabilidade, recorrência e teoria dos grafos
- Composto por cinco partes — provas, estruturas, contagem, probabilidade e recorrências —, cada uma aborda em conjunto os fundamentos teóricos e as aplicações em Ciência da Computação
- Inclui tópicos indispensáveis para programação e análise de algoritmos, como fórmulas lógicas, indução matemática, máquinas de estado, grafos e variáveis aleatórias
- Mostra o uso de conceitos matemáticos por meio de casos reais e problemas aplicados, como criptografia RSA, o código de Turing e o problema de Monty Hall
- Escrito em coautoria por pesquisadores do MIT e do Google, o material é publicado sob a licença Creative Commons BY-SA 3.0, permitindo aprendizado e reutilização livremente
Visão geral do material
- Mathematics for Computer Science (MCS) é o livro-texto da disciplina de graduação em Ciência da Computação e Engenharia Elétrica do MIT (6.042), criado para desenvolver raciocínio lógico e capacidade de modelagem matemática
- Os autores são Eric Lehman (Google Inc.), F. Thomson Leighton (MIT, Akamai Technologies) e Albert R. Meyer (MIT)
- Trata-se da edição revisada de 6 de junho de 2018, distribuída sob a licença Creative Commons Attribution-ShareAlike 3.0
I. Proofs (Provas)
- Aborda os princípios básicos das provas matemáticas, como proposições, predicados, método axiomático, prova por contradição e prova por casos
- Explica a relação entre o Well Ordering Principle (princípio da boa ordenação) e a indução, com aplicação em exemplos como a fatoração em primos
- Inclui fórmulas lógicas e lógica proposicional, o problema SAT e tipos de dados matemáticos (conjuntos, funções, relações)
II. Structures (Estruturas)
- Apresenta a base matemática da Ciência da Computação com foco em teoria dos números, teoria dos grafos e estruturas de rede
- Aplicações da teoria dos números, como números primos, máximo divisor comum, aritmética modular e criptografia RSA
- Explicação de modelos estruturais como grafos direcionados, ordens parciais, roteamento em rede, grafos simples e grafos planares
- Trata do código de Turing e da relação com o problema SAT, mostrando a conexão entre teoria da computação e criptografia
III. Counting (Contagem e combinatória)
- Aborda somas, produtos, notação assintótica, regras de contagem e funções geradoras como técnicas de cálculo combinatório
- Inclui exemplos práticos como o princípio da casa dos pombos, o princípio da inclusão-exclusão e exemplos com mãos de pôquer
- Aplica funções geradoras e métodos para resolver recorrências lineares à análise de algoritmos e ao cálculo de sequências
IV. Probability (Probabilidade)
- Cobre todo o espectro da teoria das probabilidades, incluindo espaços de probabilidade, probabilidade condicional, variáveis aleatórias, variância, estimação amostral e random walk
- Inclui casos que testam a intuição, como o problema de Monty Hall, o paradoxo de Simpson e o problema do aniversário
- Fornece fundamentos para análise de dados por meio das desigualdades de Markov e Chebyshev e de amostragem aleatória
V. Recurrences (Recorrências)
- Trata de temas centrais da análise de algoritmos, como Torre de Hanói, merge sort e recorrências de divisão e conquista
- Explica estruturas eficientes de cálculo por meio de métodos para resolver recorrências lineares e de uma forma de pensar recursiva
Apêndice
- Inclui referências bibliográficas, explicação de símbolos e índice, facilitando o estudo e a consulta
- O material completo é disponibilizado gratuitamente em PDF no site do MIT CSAIL
1 comentários
Comentários do Hacker News
Menciona que Thomson Leighton é fundador da Akamai e recomenda a série de aulas dele
Foi um dos conteúdos mais impressionantes sobre internet que já viu
A estrutura de cada seção é bem padrão, mas gostou do fato de cada citação vir com referências reversas para todas as fontes
Gostaria que houvesse mais livros feitos desse jeito
Só é uma pena que a escrita tenha parado depois de 2018
Gosta muito deste livro. É difícil, mas conseguiu entender 1 a 2 páginas de cada seção
Teve o insight de que funções são listas infinitas de entradas e saídas, e também achou marcante o humor nas notações matemáticas
Quer entendê-lo completamente antes de morrer
Pergunta se é possível escolher apenas 5 livros obrigatórios de ciência da computação
Inclui Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson, Russell & Norvig, entre outros
Afirma que Python virou praticamente uma língua franca e também recomenda Python Crash Course 3rd Edition, de Matthes
Lá também há indicação de 2 livros essenciais para quem tem pouco tempo
Gostou especialmente da parte de probabilidade do livro
O problema de Monty Hall foi explicado com clareza usando o “método de 4 passos”, muito mais fácil de entender do que no filme
É boa para estudar parcialmente em formato físico
Ao ver o sumário, ficou surpreso que o capítulo 2 fosse sobre o Well-Ordering Principle
Diferentemente do teorema de Zermelo, achou estranho partir da ordem dos números naturais como premissa
Isso porque normalmente aprendeu a definir a ordem a partir dos axiomas de Peano e só depois provar o princípio
É interessante que até nos reais exista uma boa ordenação, embora não seja possível expressar concretamente essa ordem
Também cita a piada: “o axioma da escolha é obviamente verdadeiro, o princípio da boa ordenação é obviamente falso, e o lema de Zorn eu não sei”
Reexplica o princípio da casa dos pombos da seção 15.8 com a abordagem de Dijkstra
Se 500 mil pessoas em Boston tiverem entre 1 e 200 mil fios de cabelo, como a média é 2,5 pessoas por quantidade, prova-se que pelo menos 3 pessoas têm o mesmo número de fios
Achou interessante que isso se resolva com o simples fato de que a média não pode exceder o valor máximo
Diz que foi a primeira vez que viu um livro em formato de caderno de exercícios e pergunta se há respostas
Tentou resolver alguns problemas, mas não conseguiu conferir as respostas
Agradece, dizendo que é um material muito útil
Fica feliz por ter encontrado, graças ao Hacker News, o PDF que estava procurando
Pede recomendações de leitores de tela que consigam ler PDF
Diz que ele mesmo também não consegue ler a maioria dos símbolos matemáticos