Recentemente, uma pergunta foi feita em um fórum on-line: qual a demanda de matemática nas condições de um programador real, com que frequência ele a usa e quais são suas áreas? E aqui está a minha resposta.
Antes de tudo, eu, como quase todos os programadores, uso
a lógica booleana , a partir da análise de expressões lógicas para instruções condicionais e critérios de saída, para alinhar essas expressões com, por exemplo,
as leis de Morgan . A maior parte do nosso trabalho se
baseia no
cálculo de predicados de primeira ordem e outras lógicas de predicados na forma de análise de pré-condições, invariantes e muito mais (embora possa parecer que estamos realizando outras tarefas).
Além disso, muitas vezes me envolvo na análise da complexidade dos algoritmos. As dimensões dos conjuntos de dados sendo processados atualmente são enormes. Em uma conferência sobre
tecnologia de 2010
, Eric Schmidt disse que o volume de dados criado pela humanidade hoje em apenas dois dias é igual ao volume de todos os dados existentes no mundo a partir de 2003. É importante para mim ser capaz de processar grandes segmentos desses volumes e me beneficiar deles. E, nesse sentido, entender a
complexidade espaço-temporal das operações que aplicamos aos dados é a chave para determinar se certos cálculos são possíveis em princípio. Em contraste com os tipos mais tradicionais de
análise O ou
análise teta, fatores constantes nessas escalas têm um efeito significativo: o fator 2 não altera a complexidade do tempo assintótico do algoritmo, mas exige um aumento no número de processadores de 10 mil para 20 mil, e uma diferença tão grande no consumo recursos serão tangíveis. Como resultado, os cálculos se tornam mais sofisticados. Exemplos: posso fazer um cálculo linear e reduzi-lo a um logarítmico? É possível reduzir o consumo de memória em três vezes? E assim por diante
Frequentemente, preciso calcular a variante mais desfavorável do limite superior, digamos, o tamanho de alguns conjuntos de dados. Em muitos casos, esses cálculos podem não ser triviais. Ou talvez seja necessário analisar alguma
fórmula de recorrência para verificar como ela muda à medida que a profundidade da recursão aumenta. Para isso, eu, entre outras coisas, devo conhecer o
teorema básico das relações de recorrência e como entender os princípios de análise das
séries de
números . E pode parecer incrível, mas às vezes significa que preciso calcular a
integral (embora principalmente apenas as integrais de
Riemann ). Ou posso apenas resolver a relação recursiva e obter um
número finito de soluções ? Eu tenho que recorrer à
álgebra linear ? Isso leva a coisas como
gerar funções ,
números Stirling , cálculos de
matriz . Se você estiver curioso sobre o que está incluído no conjunto de conceitos matemáticos fundamentais necessários para entender a ciência da computação, consulte o primeiro volume de "A Arte da Programação", de Donald Knuth, ou "Matemática Concreta", de Knut, Ronald Graham e Oren Patashnik.
Eu faço muitos cálculos básicos em termos de agregação, combinação e transformação de dados e
combinatória (contando o número, encontrando simetrias em diferentes dimensões e muito mais) me ajuda nisso. Eu acho que os exemplos dessa área são óbvios.
Eu uso muita
matemática discreta , especialmente para pesquisar sistemas algébricos em operações em conjuntos de dados especialmente grandes. É possível exibir essa ou aquela estrutura com a ajuda do
homomorfismo como um determinado
grupo ou
anel , o que será mais claro para mim? Existe uma opção com uma conexão menos estreita? Posso aplicar a
ação de um grupo a algum conjunto para criar um modelo especulativo de transformação que simplifique o raciocínio? Posso definir alguma topologia para análise de dados? Você ficaria surpreso se soubesse quantas coisas podem ser descritas usando
topologias discretas . E ainda menos surpreendente seria a demanda por
desigualdade de triângulo .
Eu trabalho muito com a
teoria dos grafos . "Criando sites" - requer não apenas a capacidade de colocar imagens fofas de gatos na página. Esse processo também envolve a inserção de nós no gráfico global de
hiperlinks . A adição de uma única página leva a um aumento potencial no número de bordas do gráfico, e isso, por sua vez, pode ter um efeito que não é óbvio à primeira vista no desempenho, análise, classificação dos mecanismos de pesquisa e outras características. Compreender as consequências de tais alterações pode ajudar a obter informações interessantes, como o crescimento do gráfico. Acontece que essa
dinâmica é dolorosamente semelhante a uma
lei de energia : a World Wide Web é uma
rede sem escala . Qual é o
caminho mais curto entre dois nós deste gráfico? Como será essa rede se você tentar apresentá-la como um gráfico
planar ou
bipartido ? Quando é possível cumprir essas propriedades, se possível, é claro? Mas e se não considerarmos a rede mundial de computadores como um gráfico, mas toda a rede rodoviária da América do Norte, Europa ou Ásia?
Existem outras consequências desse conhecimento. Muitas vezes, as pessoas não entendem que as páginas da web modernas não são apenas documentos
HTML com links e outros recursos, mas
estruturas de dados
semelhantes a árvores conectadas umas às outras em um
gráfico . Essas árvores geralmente são rastreadas, processadas e atualizadas dinamicamente devido à interação entre o navegador da web do usuário e um servidor (graças a tecnologias como
AJAX ).
Um exemplo excelente e adequado é o
MathJax . Ou
Gmail . A compreensão de como eles funcionam envolve algum nível de conhecimento da
computação simbólica e
análise semântica dos elementos da página. Os autores do MathJax precisavam escrever um programa capaz de percorrer a árvore gerada com base no
modelo de objeto do documento , encontrando elementos matemáticos, “
armazenando-os ” e substituindo-os dinamicamente por novos elementos desenhados. Talvez alguns usuários que apenas vejam como ele funciona não sejam muito impressionantes, mas coisas bastante complicadas acontecem sob o capô. Normalmente, não preciso fazer algo semelhante (não trabalho com o front-end), mas o tempo todo faço coisas semelhantes no
Lisp . Observe que o Lisp foi originalmente aprimorado pelo processamento matemático de informações simbólicas: suas macros cobrem completamente os problemas do processamento de expressões simbólicas.
Eu trabalho muito com
séries temporais . Como o consumo de tráfego ou recursos muda? Quais tendências podem ser destacadas? Esse ou aquele salto se manifesta no atraso na resposta a solicitações ou consumo de memória
sazonalmente ? Como a
taxa de mudança de algo reage à medida que os dados de entrada variam em diferentes dimensões? Existe alguma
correlação com algum evento externo?
Eu trabalho muito com análise estatística de dados, não apenas para determinar características de desempenho, mas também para entender os dados como tais. Além de pesquisar na árvore DOM mencionada por metadados semânticos (por exemplo,
microdados e
microformatos ,
RDF , outros dados
XML com algum
esquema específico), também estou tentando compreender
dados não estruturados . Qual é a probabilidade de esse texto ser um endereço? Ou são
coordenadas gráficas ? Em que contexto ele aparece? É
spam ? Isso faz algum sentido? Parece o resultado de um gerador de texto baseado em cadeias de
Markov ? Talvez essa seja uma série de citações de alguma obra literária conhecida? Ou um fragmento de uma discussão literária? Ou talvez seja uma discussão sobre spam contendo um fragmento literário? Ainda ri toda vez que penso em um e-mail de spam anunciando drogas envoltas em um fragmento de "Master and Margarita" de Bulgakov.
Teoria das categorias .
Os tipos de linguagens de programação de computador correspondem aproximadamente a categorias, e
mônadas e
functores podem ser usados para simplificar de maneira séria e elegante algumas construções. Por exemplo, na linguagem de programação
funcional Haskell, as mônadas são usadas para
E / S e para modelagem de
estados . Ao lidar com programas simplificados, é mais fácil fazê-los funcionar. É mais fácil falar sobre eles, é mais fácil entender, mudar e assim por diante. Os tipos geralmente podem ser determinados com base no raciocínio lógico, o que leva ao aparecimento de
casos especiais (que também podem ser usados em problemas gerais de raciocínio). Pense no que acontece se você usar as
conclusões para aplicar funções lógicas, como as usadas no
prólogo , para
transformar gráficos em
sistemas distribuídos .
Os sistemas distribuídos nos remetem à teoria dos grafos. Em escala real, falhas no sistema, escavadeiras rasgam fibras, terremotos, erupções vulcânicas e arrastões de pesca danificam os cabos marítimos. Para entender as consequências de tais eventos e determinar as melhores maneiras de responder a elas, é necessário entender as características do gráfico de rede. Os algoritmos de roteamento e a análise de rede estão intimamente relacionados a coisas como
encontrar o caminho mais curto entre os nós em um gráfico. O
algoritmo Dijkstra irá ajudá-lo com isso.
E, no entanto, como você pode distribuir a carga de um grande cálculo entre data centers localizados em diferentes partes do mundo? Aqui você também precisará de algum conhecimento de física: na escala da Internet, a
velocidade da luz se transforma em um "gargalo".
Dissipação de calor ,
densidade de corrente por unidade de área e mais são exemplos do que os programadores devem considerar ao trabalhar com tarefas do mundo real. Devo hospedar um data center na Islândia? Fontes de energia geotérmica e refrigeração baratas criam condições atraentes, mas e quanto ao atraso mínimo para usuários que possam estar interessados em alugar equipamentos em um datacenter? Qual é a distância ao longo do arco de um
grande círculo entre, por exemplo, Islândia e Londres, ou Berlim e Amsterdã? Calcular tudo isso é bastante simples, mas para isso é necessário ter certo conhecimento matemático. Podemos enviar fibra da Islândia para outro centro? Qual é o atraso médio? Qual é a probabilidade de uma ruptura de cabo submarino no Mar do Norte durante 12 meses de operação? E por 48 meses?
Obviamente, a
teoria dos algoritmos , a
teoria dos autômatos , a
análise ,
a gramática formal e
as linguagens regulares são todas as áreas de conhecimento com as quais os programadores lidam constantemente. Costumo trabalhar com análise e
correspondência de padrões . Ao trabalhar com dados do mundo real, mesmo conjuntos de tamanho não muito grande podem conter elementos que podem causar
um comportamento patologicamente ruim ao usar, por exemplo,
técnicas de retorno . Usando
expressões regulares para corresponder aos dados, devo ter cuidado e garantir que essas expressões sejam
realmente regulares .
Usando uma
máquina com memória de armazenamento para analisar
a gramática livre de contexto (que, a propósito, acontece toda vez que você envia uma solicitação para um servidor
HTTP ), preciso garantir que limite a profundidade da recursão para evitar o esgotamento da
pilha de chamadas do processador, o que requer entendimento princípios subjacentes da computação e a matemática em que se baseiam.
Se eu precisar escrever meu próprio
algoritmo de descida recursiva para obter uma gramática incomum e não corresponder a
LALR (1) (portanto, não posso usar apenas
yacc ou
bison ), preciso tomar cuidado ou manter a pilha de estados separada da recursão processual. Esse entendimento também é necessário se eu contornar a árvore DOM (ou qualquer estrutura de dados definida recursivamente).
Algumas linguagens de programação consideram isso uma dificuldade no trabalho de um programador e o evitam usando
pilhas segmentadas . Obviamente, seria ótimo se eu pudesse definir minha coleção de alguns dos recursos analisados na forma de uma
função (no sentido matemático). E quão legal seria se tudo se resumisse a algum tipo de problema de
otimização de programação linear ?
Observe que nenhuma das opções acima é de conhecimento esotérico. Tudo isso é baseado na experiência com tarefas e dados do mundo real. É claro que não faço tudo isso todos os dias, mas aplico a maior parte desse conhecimento regularmente, e apenas alguns - de tempos em tempos. Provavelmente, observação, experiência e heurísticas têm mais influência no processo do que deveriam (os modelos heurísticos geralmente são incompletos e imprecisos). Tenho conhecimento matemático suficiente para calcular o
erro médio entre a realidade e meu modelo heurístico?
Essa é a essência da ciência da computação, além de como eles interagem com a programação e as realidades da computação moderna. Ser um profissional de TI não é o mesmo que ser um especialista na teoria de sistemas de computadores e, como muitos apontam corretamente, esse especialista está muito mais próximo de um matemático aplicado do que de um artesão especialista. Em nenhum caso eu quero menosprezar a importância de tais profissionais, pois eles são úteis e são universalmente respeitados, mas eu só quero observar que a ciência da computação é outra coisa.
(A propósito, eu próprio não sou especialista em ciência da computação. Estudei matemática pura e minha ocupação profissional está muito mais próxima da engenharia.)
