L'un de nos livres Python les plus intéressants de l'année dernière a été Classic Computer Science Problems in Python par David Kopec.
Pour ceux qui n'ont pas encore eu le temps de se familiariser avec ce livre, nous vous proposons sa revue, rédigée selon l'édition originale d'octobre 2019. Vous pouvez également consulter une petite discussion sur Reddit . De plus, tout le monde peut commenter l'impression supplémentaire - pour cela, un bulletin de vote est placé à la fin de l'article.
J'ai beaucoup aimé le livre "Classical Computer Science Problems in Python" de David Kopec. Il aborde vraiment un grand nombre de problèmes divers, des informations détaillées sur lesquelles je n'ai jamais rencontré auparavant. Quelques exemples: réseaux de neurones, problèmes de satisfaction de contraintes, algorithmes génétiques, algorithme minimax. Contrairement à de nombreux autres livres sur les algorithmes et les problèmes de programmation, ce livre présente des programmes complets (mais petits) que vous pouvez facilement explorer par vous-même.
J'aime apprendre les algorithmes. J'ai travaillé sur le livre " Programmer's Career ", suivi plusieurs cours MOOC, notamment " Design and Analysis of Algorithms " du professeur Tim Rafgarden . Néanmoins, dans le livre de Kopec, il y avait aussi de tels algorithmes, dont je n'ai pas vu la mention auparavant.
CHAPITRES QUE J'AI LE PLUS AIMÉ
Réseaux de neurones . Ma section préférée du livre concerne les réseaux de neurones. L'auteur décrit la création d'un réseau de neurones à part entière. Pendant ce temps, il décrit le fonctionnement de toutes ses parties - en général et en particulier. Décrit comment les neurones et les couches sont disposés, comment la fonction d'activation fonctionne, comment la rétropropagation est utilisée pendant l'entraînement, comment les poids sont corrigés.
Enfin, le réseau neuronal est utilisé comme exemple des iris de Fisher. Il s'agit d'un ensemble de données classique, compilé dans les années 1930, avec 150 spécimens de fleurs appartenant à différents types d'iris (50 spécimens chacun). Chaque spécimen est accompagné de quatre valeurs numériques: la longueur du lobe du périanthe externe; la largeur du lobe du périanthe externe; la longueur du lobe du périanthe interne; la largeur du lobe du périanthe interne. Les valeurs sont d'abord normalisées. Ensuite, un maillage à trois couches est créé. Il y a quatre neurones dans la couche d'entrée (un pour chaque catégorie de valeurs d'entrée de l'échantillon), dans la couche cachée, il y a six neurones et dans la couche de sortie, il y a trois neurones (un pour chaque type d'iris considéré).
140 échantillons sur 150 ont été sélectionnés au hasard, qui ont ensuite été utilisés pour former le réseau. La formation est exécutée sur 140 échantillons en 50 itérations. Le réseau est ensuite utilisé pour prédire à laquelle des trois espèces d'iris appartiennent les 10 échantillons restants. Dans la plupart des cas, le réseau identifie correctement au moins 8 échantillons sur 10, et assez souvent - et tous les 10.
J'ai vraiment aimé cette expérience: programmer un réseau de neurones entier à partir de zéro sans recourir à des bibliothèques d'apprentissage automatique. J'ai expérimenté ce programme pendant un moment (tout le code du livre est posté sur GitHub). Par exemple, j'ai imprimé une impression de tous les poids dans tous les neurones une fois que le réseau a été entièrement formé. Je voulais voir s'il y aurait une similitude entre les poids entre les différentes courses. Les pondérations se sont révélées très différentes d'une série à l'autre, même si le succès prédictif dans tous les cas est resté similaire. C'est peut-être une vérité élémentaire, mais j'étais très intéressé à voir cela par moi-même.
Recherche contradictoire... Dans ce chapitre, nous sommes introduits à l'algorithme minimax. Il trouve le meilleur coup dans un jeu à somme nulle impliquant deux adversaires. L'idée est d'analyser les mouvements potentiels, en parlant au nom de l'un ou de l'autre adversaire; chaque adversaire réagit au dernier des mouvements effectués jusqu'à ce que la partie soit terminée (ou que la profondeur de récursion maximale soit atteinte). Dans le premier exemple du livre, l'IA joue au tic-tac-toe. Dans ce cas, toute la séquence de mouvements peut être entièrement analysée, car la taille du terrain de jeu n'est que de 3 cellules sur 3.
Comme dans les autres chapitres, la structure générale est d'abord développée ici, qui est ensuite discutée en relation avec des cas complexes. Après l'exemple avec tic-tac-toe, le jeu " Quatre d'affilée . " Dans ce cas, l'évaluation des coups est beaucoup plus difficile qu'en "Tic-Tac-Toe", donc ici la recherche en profondeur est limitée à trois coups. Je me suis beaucoup tourné vers ce chapitre, car je n'avais jamais vu de description de l'algorithme minimax auparavant.
Tâches de satisfaction... Un cadre général est également développé ici, qui est ensuite utilisé pour résoudre plusieurs problèmes. Au cœur de cette structure se trouve le retour en arrière récursif. Le premier problème résolu dans ce chapitre est la tâche de colorier la carte de l'Australie. Est-il possible de se débrouiller avec seulement trois couleurs et de colorier la carte de sorte que les zones adjacentes de chaque côté de toute frontière entre les régions soient de couleur différente? (Réponse: oui). La deuxième tâche est de placer huit reines sur l'échiquier, en s'assurant qu'aucune reine n'est attaquée par une autre. La troisième tâche consiste à organiser la liste de mots dans une grille pour former un carré pour la recherche de mots. Enfin, la structure est utilisée pour résoudre le puzzle crypto-arithmétique classique SEND + MORE = MONEY. Le but est de savoir à quel chiffre correspond chaque lettre afin que l'égalité arithmétique résultante soit correcte.
J'ai aimé ce chapitre parce qu'il contient beaucoup d'exemples très divers, et aussi parce que je n'ai pas utilisé auparavant cette approche pour résoudre de tels problèmes (du moins systématiquement).
Algorithmes génétiques . Avant de lire ce chapitre, je n'avais qu'une idée très générale du fonctionnement des algorithmes génétiques. Le code de ce chapitre montre une classe de chromosomes instanciée par des gènes sélectionnés au hasard. Un chromosome peut évaluer sa propre adaptabilité à l'environnement et met en œuvre des croisements (une combinaison de lui-même avec un autre chromosome du même type), et mute également (fait de petits changements complètement aléatoires en soi).
L'algorithme commence par une population aléatoire. A chaque génération de cette population, l'algorithme vérifie (à l'aide de la fonction de fitness) s'il existe une solution suffisamment bonne (la fitness est supérieure à une valeur seuil donnée). S'il n'y a pas de telle solution, alors une nouvelle génération est créée par des opérations répétées de croisement de paires d'individus (plus l'aptitude de chaque individu est élevée, plus il est probable que ces individus entreront en action). En outre, plusieurs individus sont sélectionnés pour des mutations. Maintenant, ces nouveaux individus donnent naissance à une nouvelle population et, encore une fois, leurs fonctions de forme physique sont testées. Le cycle se répète pour un nombre donné de générations.
Les tâches suivantes sont considérées comme des exemples: maximiser une expression mathématique, le casse-tête "ENVOYER + PLUS = ARGENT" mentionné ci-dessus et ordonner les éléments dans une liste pour minimiser la taille de la liste une fois compressée. La beauté de ce chapitre, comme de nombreux autres, est que tous les concepts sont présentés dans le contexte d'une solution compacte mais complète.
Chercher... Les algorithmes de ce chapitre n'étaient pas nouveaux pour moi (sauf pour A *), mais le chapitre est toujours intéressant grâce aux exemples qui y sont donnés. L'auteur démontre les principes de la première recherche en largeur et de la première recherche en profondeur en utilisant l'exemple de sortie du labyrinthe. Les labyrinthes sont des cellules de grille 9x9 ordinaires, dans lesquelles des obstacles sont placés au hasard. Affiché à l'écran en utilisant uniquement des caractères ASCII. À l'aide d'algorithmes, un chemin est trouvé à travers la grille, en diagonale, tout en évitant les obstacles. Le chemin ainsi trouvé est également tracé à travers le labyrinthe.
Vous pouvez facilement modifier ces programmes pour tester le fonctionnement des algorithmes dans différents scénarios. Après s'être familiarisé avec Breadth First Search, l'auteur parle de A *. La différence est que les chemins sont tracés à l'aide d'une heuristique (distance euclidienne), qui sert de guide et vous indique les chemins à dessiner en premier. Le dernier exemple de ce chapitre utilise une fonction de recherche pour vous aider à amener trois missionnaires et trois ogres dans un canoë sur une rivière. La limitation est que le nombre de cannibales ne peut pas dépasser le nombre de missionnaires sur le rivage ou dans le bateau, sinon les cannibales mangeront les missionnaires. Je pense que c'est une application très intelligente et intéressante de l'algorithme de recherche.
AUTRES CHAPITRES
D'autres chapitres contiennent des algorithmes que je connais déjà.
Tâches simples (premier chapitre). Le premier chapitre contient de nombreux petits exemples. Il décrit d'abord les différentes manières de calculer les nombres de Fibonacci (en particulier, récursifs, avec mémorisation, itérative, et avec un générateur Python). La section suivante traite de la manipulation des bits pour la compression et les chiffrements XOR. Enfin, nous aurons besoin de la récursivité dans ce chapitre pour résoudre le problème des tours de Hanoi.
Problèmes de graphique . Le chapitre 4 traite des algorithmes de graphes pour trouver le chemin le plus court et l'arbre couvrant minimum, en utilisant une carte des États-Unis comme exemple. L'algorithme de Dijkstra est également considéré.
Clustering K-Means... Ce chapitre vous montre comment regrouper des points de données en un nombre prédéterminé de clusters en fonction de la distance relative entre chaque point et le centre du cluster. Les exemples de ce chapitre ne m'étaient pas aussi intéressants que les exemples d'autres chapitres.
Autres tâches . Le dernier chapitre traite du problème du sac à dos, du problème du voyageur de commerce et de la mnémonique des numéros de téléphone.
QUE VOULEZ-VOUS ATTENDRE
Tous les programmes utilisent les indices de type de Python. J'ai une double attitude à l'égard de ces conseils. D'une part, les types contribuent à une meilleure compréhension du programme. Mais d'un autre côté, je n'ai pas l'habitude de les voir en Python, et parfois j'ai dû comprendre ces astuces avant de commencer à comprendre la logique du programme.
Si vous voulez vous plaindre d'une section, alors celle qui parle de programmation dynamique. À mon avis, il manque d'exhaustivité. La programmation dynamique est une chose délicate, et si vous comptez l'utiliser dans des solutions du monde réel, vous aurez besoin d'exemples supplémentaires sur ce sujet.
CONCLUSION
Les principales raisons pour lesquelles j'ai vraiment aimé ce livre sont l'étendue des algorithmes considérés, à part entière (en même temps, des solutions compactes) faciles à étudier par eux-mêmes, ainsi que des exemples intéressants sélectionnés pour illustrer les algorithmes.