Como posso melhorar minha engenhosidade algorítmica?

Question

Durante a graduação, senti que minha educação consistia principalmente na aplicação da teoria existente a problemas do mundo real (ou seja,projeto/análise de algoritmo).Já vi derivações de muitos algoritmos e provas de sua complexidade, mas muitas vezes fico incomodado com a questão de como alguém descobre um algoritmo.Parece assustador imaginar o desenvolvimento de um novo algoritmo, dada a engenhosidade envolvida na elaboração de uma abordagem eficaz.Estou me perguntando se existem maneiras de treinar essa engenhosidade.

Minha pergunta é: como posso cultivar as habilidades necessárias para desenvolver abordagens originais para problemas quantitativos?Existem recursos que se concentram nessas habilidades?

Answer 1

Parece que a programação competitiva pode ajudá-lo.Ou apenas a parte de "programação".Se você deseja aprimorar suas habilidades de resolução de problemas (e, portanto, sua capacidade de ter ideias originais), parece que resolver problemas competitivos é o caminho a percorrer, uma vez que eles visam, por design, essa habilidade.

Você precisaria de dois tipos de recursos:arquivos de problemas e materiais teóricos.

Para arquivos problemáticos, posso sugerir que você experimente

• timus.online (problemas que exigem alguns insights/observações inteligentes começam após ~270 dificuldade)
• codeforces.org (guia conjunto de problemas, variedade mais rica de problemas, mas a qualidade geral é um pouco inferior à do timus)
• juiz online.org (no uHunt existe uma tabela com problemas que cobrem uma grande variedade de problemas;um suplemento do livro Programação Competitiva 3)
• urionlinejudge.com.br (tem alguns grandes problemas)

Além disso, há atcoder.co.jp que é como codeforces, mas visa principalmente problemas relacionados à matemática.

A chave para encontrar ideias originais é saber o que as pessoas já criaram.Se você entende essas ideias e pode aplicá-las com relativa facilidade, então você a) pode ter uma ideia inteligente combinando essas ideias antigas de uma maneira inteligente eb) você pode procurar ideias fundamentalmente novas com muito mais eficiência porque sabe o que não é. uma nova ideia e qual não é a nova forma de pensar para encontrar novas ideias.

Se você concorda com o parágrafo anterior, precisará de recursos onde possa aprender novos conceitos e ideias.A chave para isso é não apenas compreender o teorema ou o algoritmo, mas também compreender a intuição e a(s) prova(s).As provas fornecem informações explícitas sobre como apresentar e como ter certeza de que a ideia funciona.Compreender os truques e algoritmos (de pensamento) usados ​​nas provas é a chave para ter suas próprias ideias.

A intuição, por outro lado, é um insight implícito, é algo que conecta problemas, suas provas (ou um subconjunto de provas) e o tema do problema em geral.Digo isso para que você não pense que a intuição é algo mágico ou que, se você não a entendesse ao ler uma prova, não a entenderia de jeito nenhum.Para adquiri-lo você deve realizar estas etapas

• Antes de ver a solução, tente pensar nela por pelo menos 30 minutos (para mim rabiscar ajuda muito a encontrar soluções intuitivas)
• Então, se você acha que algumas ideias que você acha que vão funcionar 100% estão aí, mas você não consegue alcançá-las em seu cérebro, não desista e segure-as até dormir.Se você não conseguir dormir pensando no problema, certamente terá algumas dicas ao acordar.(https://psicologia.stackexchange.com/a/13366 + minha experiência).
• Sem qualquer dependência de ter resolvido ou não o problema após tal procedimento, ao abrir a(s) prova(s), você poderá absorvê-las e analisá-las com muito mais eficiência, já que lerá para não saber as ideias, mas descobrir por que suas ideias não estavam funcionando, quão perto você estava, onde você cometeu um erro em seu pensamento, o que você perdeu, por que aquela coisa em que você se concentrou demais não era tão relevante, o que você tinha que saber para resolver de qualquer maneira, etc.etc....(é assim SQ3R o método também funciona, faz você questionar primeiro o texto e só depois permite lê-lo como forma de responder às perguntas;uma leitura ativa, em vez de uma leitura passiva).
• Se você conseguiu extrair alguma intuição orientadora das provas, parabéns!Agora esqueça esse problema e volte depois de dois ou três dias e resolva outro problema semelhante ou um pouco mais difícil sobre o mesmo assunto.Dessa forma você “imprimirá” essa intuição em seu cérebro, por assim dizer, por um tempo relativamente longo (Veja, repetição espaçada)
• Se ainda não o fez, não fique triste.Você entendeu mais ou menos como funcionam as provas.Isso significa que a única coisa que resta é uni-los de alguma forma com a intuição.Para fazer isso basta continuar resolvendo problemas sobre o mesmo tópico geral (cordas, gráficos, teoria dos números, etc.).A intuição não está ligada a algum problema concreto (se estivesse, a intuição não seria capaz de ajudar a resolver outros problemas), se você entender as intuições por trás de outros problemas, então naturalmente você entenderá a intuição por trás do problema original também !

OK, então.Com isso, você será capaz de captar as ideias antigas com eficiência, compreender a intuição e a engenhosidade por trás delas.Estes são recursos plausíveis (embora eu ache que você já possa usá-los):

1. Introdução aos Algoritmos.Cormen
2. geekforgeeks.com
3. wikipedia.com (sério, eles têm ótimos artigos sobre alguns algoritmos)
4. visualgo.net (especialmente se você for um aprendiz visual;)

Pela minha experiência neste ponto, você será capaz de ter ideias originais sozinho e naturalmente.Você será capaz de ver claramente as conexões entre as ideias e elas começarão a surgir na sua cabeça.Resolver problemas sustentará os caminhos neurais do seu cérebro e você não esquecerá a base teórica e a intuição que construiu.Resolver problemas também construirá novas conexões neurais e trará alegria ao descobrir novos insights.

Por último, quero dizer que se o seu insight não for nada que você tenha aprendido antes, então ele tem valor.Se você combinar duas ideias, mesmo que seja simples, você terá uma ideia nova e ela terá valor.Cada vez que você tem essas ideias, em qualquer caso, você cria algo valioso.Se o seu objetivo for inventar algo valioso, você sempre terá sucesso.Se o seu objetivo for chegar a um "insight original", você rapidamente ficará gravemente desmotivado, pois não importa o que faça, provavelmente irá falhar (no início, com certeza).No final, se você seguir estes passos ou algo semelhante, você não conseguirá melhorar!Certamente, em algum momento no futuro, cada décimo de suas ideias será verdadeiramente original ;)