Matemática: Finalizando com grafos, fungos e logística.
Pois é, ainda falta muito assunto para cobrir, mas por enquanto vou terminar essa mini-série que foi até que bem tranquila. (gosto de ser sarcástico e não fazer drama o tempo todo).
Para terminar, eu quero citar uma das principais formas que fazem seu mercado livre, Waze, iFood, Amazon, twitter, git... funcionarem "Grafos".
"Vocês sabem o que é um grafo?" Bem, ele é um similar ao joguinho de conecte os pontos. Pois é, na verdade, teoria dos grafos é igualmente um ramo na matemática criado para estudar relações entre objetos.
Sim, é similar ao conceito de primary-key e foreign-key no PostgreSQL, mas com muitas mais relações, incluindo relações indiretas.
Primeiramente, você sabia que a malha ferroviária japonesa foi projetada usando grafos? Curiosamente, eles não usaram algoritmos nem computadores para isso.
No caso, eles colocaram um pouco de comida em cada ponto onde precisaria ter uma estação. O fundo se dispersou em todas as direções (propagando - se) e criou uma rota mais simples que conectava o ponto inicial ao destino. "Sim, é similar ao algoritmo A*".
Outro caso famoso para uso de grafos, é em logística.
Um dos principais problemas que temos é como entregar mais mercadorias, em diferentes localidades com o menor tempo possível para entrega e o menor custo de combustível
E existem vários outros casos:
- Versionamento de código
- Recomendação
- Redes Sociais
- Biologia
- Redes
- Inteligências Artificias
- Segurança
- Computação Gráfica
- Análise de Texto e Linguística.
Por exemplo, o Git usa um Grafo DAG que significa Direct Acyclic Graph onde a modelagem do mesmo é uma lista ligada simples que nunca gera um ciclo em si.
Ou seja, com operações como merge ou rebase, o grafo continuará seguindo em frente, independentemente dos desvios ou branches criados.
Obviamente, embora árvores sejam grafos acíclicos, elas não são direcionadas, pois necessitam de desvios à esquerda e à direita para manter a ordenação.
Mas, para não parecer que estamos falando mal dos grafos cíclicos. Um dos melhores usos para grafos cíclicos são máquinas de estado, estrutura essa que é infinitamente superior a qualquer inteligência artificial pelo seu determinismo.
Os grafos são divididos em duas partes:
- Vértices: representam o objeto ou entidade
- Arestas: representa o relacionamento com outra entidade
Isso deve ser bem simples.
Comece pensando num grafo com a pessoa John que curte Rap
Nesse mesmo grafo tem uma pessoa Joseph que curte Rock
Podemos relaciona - los com seu gosto por música.
Essa ideia, baseada na homofilia, é a base de muitos sistemas de recomendação, como o algoritmo do Twitter.
Ou podemos pensar no roteamento de IP's de um computador. Usando Radix Tree (que também é um grafo como citado acima).
Mas se você quer realmente um exercício para treinar sua programação eu recomendo o Tideman (CS50 - Harvard) onde você precisa evitar construir cíclos.
Este programa em C implementa um sistema de votação e eleição usando o método de votação de pares (Tideman). O programa aceita votos de eleitores e determina o vencedor da eleição com base nas preferências dos eleitores.
Grafos são a área mais poderosa ainda em descoberta na programação. Além de ser uma das mais versáteis já que quase tudo no mundo natural pode ser representado com grafos.
E uma das mais versáteis soluções para diversos problemas.
Aqui, deixo meu chapéu ao batente da porta, e me despedindo cuidadosamente. Torço no seu progresso lendo e praticando mais sobre os assuntos que citei.
Se quiser os outros dois posts da minha mini-série