Analyse des structures de données et algorithmes en Python (2e édition)

📚 Résumé du contenu

Ce livre est un manuel classique sur les structures de données et les algorithmes utilisant Python. Il couvre le révision des bases de Python, l'analyse d'algorithmes (notation O grande), les structures de données fondamentales (pile, file, liste), la récursivité, la recherche et le tri, ainsi que les algorithmes sur les arbres et les graphes. Grâce à des listes de code pratiques, il aide les lecteurs à comprendre comment implémenter efficacement divers types abstraits de données en Python.

Seulement en maîtrisant profondément les structures de données et les algorithmes peut-on véritablement maîtriser Python.

Auteur : Bradley Miller (professeur émérite de sciences informatiques à Luther College, États-Unis) et David Ranum (ingénieur logiciel cognitif chez IBM Watson)

Remerciements : Merci à nos collègues Steve Hubbard pour ses nombreux retours sur la première édition et pour les nouveaux contenus fournis pour cette nouvelle version, ainsi qu’à tous les collègues qui ont signalé des erreurs ou donné leurs avis par courriel. Merci également aux serveurs Mary, Bob et autres du café Java John's à Decora pour avoir accepté que nous devenions "auteurs résidents" pendant nos périodes de repos. Un grand merci aussi à toute l'équipe de Franklin, Beedle & Associates (notamment Jim Leisy et Tom Sumner) pour leur collaboration agréable. Enfin, un remerciement particulier à nos deux épouses, Jane Miller et Brenda Ranum, dont l'amour et le soutien ont rendu ce livre possible.

🎯 Objectifs d'apprentissage

1. Comprendre le lien entre l'informatique, les algorithmes et la programmation, et maîtriser les concepts de type abstrait de données (TAD) et de masquage d'information.
2. Maîtriser les types de données intégrés de Python (listes, tuples, ensembles, dictionnaires) et les structures de contrôle (boucles, branches, gestion des exceptions).
3. Maîtriser les fondamentaux de la programmation orientée objet en Python : définition de classes, méthodes constructeurs, surcharge d'opérateurs (comme l'addition de fractions), application de l'algorithme d'Euclide, et distinction entre égalité profonde et égalité superficielle.
4. Comparaison de plusieurs approches algorithmiques : expliquer les quatre solutions pour détecter les anagrammes (comptage, tri, force brute, comptage) et leurs complexités temporelles respectives.
5. Évaluation quantitative des performances des conteneurs Python : maîtriser les performances en notation O grande des opérations principales sur les listes (List) et les dictionnaires (Dict), et distinguer les différences de performance entre pop() et pop(i).
6. Capacité à valider les performances : utiliser le module timeit pour concevoir des expériences et vérifier la cohérence entre la complexité théorique et les temps d'exécution réels.
7. Comprendre et distinguer les caractéristiques logiques des structures linéaires (piles, files, files doublement terminées, listes).
8. Pouvoir implémenter des piles, files et files doublement terminées personnalisées à l’aide des collections de base de Python (comme les listes).
9. Maîtriser l’utilisation des piles dans le traitement d’expressions (conversion infixe → postfixe, évaluation postfixe) et des files dans la simulation de systèmes (simulation d’imprimante).
10. Maîtriser les trois principes fondamentaux de la récursivité : identifier précisément et écrire des fonctions récursives comportant un cas de base, une évolution d’état et un appel récursif à soi-même.