Um dos nossos livros mais interessantes sobre Python no ano passado foi Classic Computer Science Problems in Python, de David Kopec.
Para quem ainda não teve tempo de se familiarizar com este livro, oferecemos sua resenha, redigida de acordo com a edição original de outubro de 2019. Você também pode conferir uma pequena discussão no Reddit . Além disso, todos podem expressar sua opinião sobre a impressão adicional - para isso, no final do artigo há uma cédula de votação.
Gostei muito do livro "Classic Computer Science Problems in Python" de David Kopec. Ele realmente aborda muitos problemas diferentes, informações detalhadas que eu não encontrei antes. Apenas alguns exemplos: redes neurais, problemas de satisfação de restrições, algoritmos genéticos, algoritmo minimax. Ao contrário de muitos outros livros sobre algoritmos e problemas de programação, este livro mostra programas completos (mas pequenos) que você pode explorar facilmente por conta própria.
Gosto de aprender algoritmos. Trabalhei no livro “ Programmer's Career ”, fiz vários cursos de MOOC, em particular, “ Design and Analysis of Algorithms ” do professor Tim Rafgarden . No entanto, no livro de Kopec também havia tais algoritmos, cuja menção eu não tinha visto antes.
CAPÍTULOS QUE EU GOSTEI MAIS
Redes neurais . Minha seção favorita do livro é sobre redes neurais. O autor descreve a criação de uma rede neural completa. Enquanto isso, ele descreve como todas as suas partes funcionam - em geral e em particular. Descreve como os neurônios e as camadas são organizados, como funciona a função de ativação, como a retropropagação é usada durante o treinamento, como os pesos são corrigidos.
Finalmente, a rede neural é usada como exemplo de íris de Fisher. Este é um conjunto de dados clássico, compilado na década de 1930, com 150 espécimes de flores pertencentes a diferentes tipos de íris (50 espécimes cada). Cada amostra é acompanhada por quatro valores numéricos: o comprimento do lobo perianto externo; a largura do lobo perianto externo; o comprimento do lobo perianto interno; a largura do lobo perianto interno. Os valores são normalizados primeiro. Em seguida, uma malha de três camadas é criada. Existem quatro neurônios na camada de entrada (um para cada categoria de valores de entrada da amostra), na camada oculta há seis neurônios e na camada de saída há três neurônios (um para cada tipo de íris considerado).
140 de 150 amostras foram selecionadas aleatoriamente, as quais foram utilizadas para treinar a rede. O treinamento é executado em 140 amostras em 50 iterações. A rede é então usada para prever a qual das três espécies de íris pertencem as 10 amostras restantes. Na maioria dos casos, a rede identifica corretamente pelo menos 8 entre 10 amostras, e com bastante frequência - e todas as 10.
Gostei muito dessa experiência: programar uma rede neural inteira do zero sem recorrer a bibliotecas de aprendizado de máquina. Eu experimentei este programa por um tempo (todo o código do livro está postado no GitHub) Por exemplo, imprimi uma impressão de todos os pesos em todos os neurônios depois que a rede foi totalmente treinada. Eu queria ver se haveria uma semelhança entre os pesos entre as diferentes execuções. Os pesos revelaram-se notavelmente diferentes de uma corrida para outra, embora o sucesso preditivo em todos os casos permanecesse semelhante. Talvez seja uma verdade elementar, mas eu estava muito interessado em ver por mim mesmo.
Pesquisa Adversarial... Neste capítulo, somos apresentados ao algoritmo minimax. Ele encontra a melhor jogada em um jogo de soma zero envolvendo dois oponentes. A ideia é analisar movimentos potenciais, falando em nome de um ou outro oponente; cada oponente reage ao último dos movimentos feitos até que o jogo seja concluído (ou a profundidade máxima de recursão seja atingida). No primeiro exemplo do livro, o AI está jogando jogo da velha. Nesse caso, toda a sequência de movimentos pode ser analisada integralmente, já que o tamanho do campo de jogo é de apenas 3 por 3 células.
Como nos outros capítulos, a estrutura geral é desenvolvida primeiro aqui, que é então considerada em relação aos casos complexos. Depois do exemplo do jogo da velha, o jogo " Quatro em uma linha . " Neste caso, a avaliação dos movimentos é muito mais difícil do que no "Tic-Tac-Toe", então aqui a busca em profundidade é limitada a três movimentos. Voltei-me muito para este capítulo, já que nunca tinha visto uma descrição do algoritmo minimax antes.
Tarefas de satisfação... Uma estrutura geral também é desenvolvida aqui, que é então usada para resolver vários problemas. No cerne dessa estrutura está o retrocesso recursivo. O primeiro problema resolvido neste capítulo é a tarefa de colorir o mapa da Austrália. É possível sobreviver com apenas três cores e colorir o mapa de modo que as áreas adjacentes de cada lado de qualquer fronteira entre as regiões tenham cores diferentes? (Resposta: sim). A segunda tarefa é colocar oito rainhas no tabuleiro de xadrez, certificando-se de que nenhuma rainha esteja sob ataque de outra. A terceira tarefa é organizar a lista de palavras em uma grade para formar um quadrado para pesquisar palavras. Finalmente, a estrutura é usada para resolver o clássico quebra-cabeça cripto-aritmético ENVIAR + MAIS = DINHEIRO. O objetivo é descobrir a qual dígito cada letra corresponde para que a igualdade aritmética resultante seja correta.
Gostei deste capítulo porque ele contém muitos exemplos muito diversos e também porque nunca usei essa abordagem para resolver tais problemas (pelo menos sistematicamente).
Algoritmos genéticos . Antes de ler este capítulo, eu só tinha uma ideia muito geral de como funcionam os algoritmos genéticos. O código deste capítulo demonstra uma classe de cromossomos instanciada por genes selecionados aleatoriamente. Um cromossomo pode avaliar sua própria adaptabilidade ao ambiente e implementar o cruzamento (uma combinação de si mesmo com outro cromossomo do mesmo tipo), e também sofrer mutação (fazer pequenas mudanças completamente aleatórias em si mesmo).
O algoritmo começa com uma população aleatória. Em cada geração dessa população, o algoritmo verifica (usando a função de adequação) se existe uma solução suficientemente boa (a adequação está acima de um determinado limite). Se não houver tal solução, então uma nova geração é criada por meio de operações repetidas de cruzamento de pares de indivíduos (quanto maior a aptidão de cada indivíduo, maior a probabilidade de esses indivíduos entrarem em ação). Além disso, vários indivíduos são selecionados para mutações. Agora, esses novos indivíduos dão origem a uma nova população e, novamente, suas funções de aptidão são testadas. O ciclo se repete por um determinado número de gerações.
As seguintes tarefas são consideradas exemplos: maximizar uma expressão matemática, o quebra-cabeça "ENVIAR + MAIS = DINHEIRO" mencionado acima, e ordenar os itens em uma lista para minimizar o tamanho da lista quando compactada. O mérito deste capítulo, como muitos outros, é que todos os conceitos são mostrados no contexto de uma solução compacta, mas completa.
Pesquisa... Os algoritmos neste capítulo não eram novos para mim (exceto para A *), mas o capítulo ainda é interessante graças aos exemplos dados nele. O autor demonstra os princípios da Primeira Pesquisa em Largura e Primeira Pesquisa em Profundidade usando o exemplo de saída do labirinto. Labirintos são células comuns de grade 9x9, nas quais os obstáculos são colocados aleatoriamente. Exibido na tela usando apenas caracteres ASCII. Com a ajuda de algoritmos, é encontrado um caminho através da grade, indo na diagonal, evitando obstáculos. O caminho encontrado dessa forma também é traçado pelo labirinto.
Você pode alterar facilmente esses programas para testar como os algoritmos funcionam em diferentes cenários. Depois de se familiarizar com Breadth First Search, o autor fala sobre A *. A diferença é que os caminhos são traçados por meio de uma heurística (distância euclidiana), que é usada como guia e informa quais caminhos devem ser traçados primeiro. O último exemplo neste capítulo usa uma função de pesquisa para ajudá-lo a colocar três missionários e três ogros em uma canoa para atravessar um rio. A limitação é que o número de canibais não pode exceder o número de missionários na costa ou no barco, caso contrário, os canibais comerão os missionários. Acho que esta é uma aplicação muito inteligente e interessante do algoritmo de busca.
OUTROS CAPÍTULOS
Outros capítulos contêm algoritmos com os quais já estou familiarizado.
Tarefas simples (primeiro capítulo). O primeiro capítulo contém muitos pequenos exemplos. Ele primeiro descreve as diferentes maneiras de calcular números de Fibonacci (em particular, recursivo, com memoização, iterativo e com um gerador Python). A próxima seção discute a manipulação de bits para compressão e cifras XOR. Finalmente, precisaremos da recursão neste capítulo para resolver o problema das Torres de Hanói.
Problemas de gráfico . O Capítulo 4 discute algoritmos de gráfico para encontrar o caminho mais curto e a árvore de abrangência mínima, usando um mapa dos Estados Unidos como exemplo. O algoritmo de Dijkstra também é considerado.
Clustering K-Means... Este capítulo mostra como agrupar pontos de dados em um número predeterminado de clusters com base na distância relativa de cada ponto ao centro do cluster. Os exemplos deste capítulo não foram tão interessantes para mim quanto os exemplos dos outros capítulos.
Outras tarefas . O último capítulo trata do problema da mochila, do problema do caixeiro-viajante e da mnemônica dos números de telefone.
O QUE VOCÊ ANEXARIA
Todos os programas usam dicas de tipo do Python. Tenho uma atitude dupla em relação a essas dicas. Por um lado, os tipos contribuem para uma melhor compreensão do programa. Mas, por outro lado, não estou acostumado a vê-los em Python e, às vezes, precisava entender essas dicas antes de começar a entender a lógica do programa.
Se você quer reclamar de uma seção, então aquela que fala sobre programação dinâmica. Na minha opinião, falta integridade. A programação dinâmica é complicada e, se você for usá-la em soluções do mundo real, precisará de exemplos adicionais neste tópico.
CONCLUSÃO
As principais razões pelas quais realmente gostei deste livro são a amplitude dos algoritmos considerados, completos (ao mesmo tempo, soluções compactas) que são fáceis de investigar por conta própria, bem como exemplos interessantes selecionados para ilustrar os algoritmos.