Le livre "Tâches classiques en informatique en Python"

De nombreuses tâches dans le domaine de l'informatique, qui à première vue semblent nouvelles ou uniques, sont en fait ancrées dans des algorithmes classiques, des méthodes de codage et des principes de développement. Et les techniques établies sont toujours le meilleur moyen de résoudre de tels problèmes!

Le livre vous donnera l'occasion d'approfondir le langage Python, de vous tester sur des tâches, des exercices et des algorithmes éprouvés par le temps. Vous devez résoudre des dizaines de tâches de programmation: des plus simples (par exemple, rechercher des éléments de liste à l'aide du tri binaire) aux plus complexes (regrouper les données à l'aide de la méthode k-means). En vous servant d'exemples consacrés à la recherche, au regroupement, aux graphiques, etc., vous vous souviendrez de ce que vous aviez oublié et maîtriserez les techniques classiques de résolution des problèmes quotidiens.

À qui s'adresse ce livre?

Ce livre est destiné aux programmeurs de niveau moyen et élevé. Les professionnels expérimentés qui souhaitent approfondir leurs connaissances de Python trouveront ici des tâches qui leur sont familières à partir du moment où ils ont enseigné l'informatique ou la programmation. Les programmeurs de niveau intermédiaire se familiariseront avec ces tâches classiques dans leur langue choisie - Python. Pour les développeurs qui se préparent pour une interview de programmation, la publication est susceptible de devenir un précieux matériel préparatoire.

En plus des programmeurs professionnels, ce livre peut être considéré comme utile par les étudiants qui étudient pour les programmes de premier cycle en informatique et qui s'intéressent à Python. Il ne prétend pas être une introduction rigoureuse aux structures de données et aux algorithmes. Ce n'est pas un tutoriel sur les structures de données et les algorithmes. Vous ne trouverez aucune preuve de théorèmes ou l’utilisation abondante d’O grandes notations sur ses pages. Au contraire, ce livre se positionne comme un guide pratique accessible des méthodes de résolution de problèmes qui devraient devenir le produit final de l'étude de la structure des données, des algorithmes et des classes d'intelligence artificielle.

J'insiste à nouveau: on suppose que les lecteurs connaissent la syntaxe et la sémantique de Python. Il est peu probable qu'un lecteur sans expérience de programmation puisse bénéficier de ce livre, et un programmeur sans expérience en Python sera probablement difficile. En d'autres termes, «Tâches classiques en informatique en Python» est un livre pour les programmeurs Python et les étudiants en informatique.

Extrait. 1.5. Tours de Hanoi

Il y a trois hautes colonnes verticales (ci-après - tours). Nous les désignerons A, B et C. Des disques avec des trous au centre sont enfilés sur la tour A. Le disque le plus large - nous l'appellerons disque 1 - est situé en dessous. Les disques restants situés au-dessus sont indiqués par des nombres croissants et diminuent progressivement. Par exemple, si nous avions trois disques, le plus large d'entre eux, celui ci-dessous, aurait le numéro 1. Le prochain disque le plus large, au numéro 2, serait situé au-dessus du disque 1. Enfin, le disque le plus étroit, au numéro 3 se trouverait sur le disque 2.

Notre objectif est de déplacer tous les disques de la tour A vers la tour C, en tenant compte des restrictions suivantes.

• Les disques ne peuvent être déplacés qu'un par un.
• Le seul lecteur disponible pour le déplacement est celui situé en haut de n'importe quelle tour.
• Un disque plus large ne peut jamais être placé au-dessus d'un disque plus étroit.
  Schématiquement, la tâche est illustrée à la Fig. 1.7.

1.5.1. Modélisation de tour

Une pile est une structure de données modélisée selon le principe du dernier entré, premier sorti (LIFO). La dernière chose qui arrive sur la pile devient la première qui est récupérée à partir de là. Les deux opérations principales de la pile sont push (put) et pop (extract). L'opération push pousse un nouvel élément sur la pile, et pop le supprime de la pile et renvoie le dernier élément inséré. Vous pouvez facilement modéliser la pile en Python en utilisant la liste comme stockage de sauvegarde (Listing 1.20).


Listing 1.20. hanoi.py

from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container) 

La classe Stack présentée implémente la méthode __repr __ (), qui facilite l'examen du contenu de la tour. __repr __ () correspond à la sortie lorsque la fonction print () est appliquée à la pile.

Comme indiqué dans l'introduction, les annotations de type sont utilisées dans le livre. L'importation de Generic à partir d'un module d'entrée permet à Stack d'être une classe paramétrique pour un type spécifique dans les annotations de type. Un type arbitraire T est défini dans T = TypeVar ('T'). T peut être de tout type. Lorsque l'annotation de type est ensuite utilisée pour Stack dans la résolution du problème de la tour de Hanoi, l'invite sera Stack [int], c'est-à-dire que le type int sera utilisé à la place de T. En d'autres termes, ici la pile est une pile d'entiers. Si vous rencontrez des difficultés avec les annotations de type, consultez l'annexe B.

Les piles sont parfaites pour le défi de la tour de Hanoi. Afin de déplacer le disque vers la tour, nous pouvons utiliser l'opération push. Afin de déplacer le disque d'une tour à l'autre, nous pouvons le pousser du premier (pop) et le placer sur le second (push).

Définissez les tours en tant qu'objets de pile et remplissez la première de disques (extrait 1.21).

Listing 1.21. hanoi.py (suite)

 num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i) 

1.5.2. Résoudre le problème des tours de Hanoi

Comment puis-je résoudre le problème des tours de Hanoi? Supposons que nous essayons de déplacer un seul lecteur. Ensuite, nous saurions comment faire cela, non? En fait, le déplacement d'un disque est un cas de base pour une solution récursive à ce problème. Le déplacement de plusieurs disques est un cas récursif. Le point clé est que nous avons, en fait, deux scénarios qui doivent être encodés: déplacer un disque (cas de base) et déplacer plusieurs disques (cas récursif).

Pour comprendre le cas récursif, considérons un exemple spécifique. Supposons que nous ayons trois disques - le haut, le milieu et le bas, situés sur la tour A, et que nous voulons les déplacer vers la tour C. (Par la suite, cela aidera à décrire schématiquement le problème.) Premièrement, nous pourrions déplacer le disque supérieur vers la tour C. Ensuite - déplacer le disque du milieu vers la tour B, puis le disque supérieur de la tour C vers la tour B. Nous avons maintenant le disque inférieur toujours situé sur la tour A et les deux disques supérieurs sur la tour B. Essentiellement, nous avons déjà réussi à déplacer deux conduire d'une tour (A) à une autre (B). Le déplacement du disque inférieur de A vers C est le cas de base (déplacement d'un disque). Maintenant, nous pouvons déplacer les deux disques supérieurs de B vers C en utilisant la même procédure que de A vers B. Nous déplaçons le disque supérieur vers A, le disque du milieu vers C et enfin le disque supérieur de A vers C.

Dans les cours d'informatique, on trouve souvent de petits modèles de ces tours, construits à partir de broches et de disques en plastique. Vous pouvez créer votre propre modèle avec trois crayons et trois feuilles de papier. Cela vous aidera peut-être à visualiser la solution.

Dans l'exemple avec trois disques, il y avait un cas de base simple de déplacement d'un disque et un cas récursif de déplacement des disques restants (dans ce cas deux) en utilisant une troisième tour temporaire. Nous pouvons diviser le cas récursif en plusieurs étapes.

1. Déplacez les n - 1 lecteurs supérieurs de la tour A vers la tour B (temporaire), en utilisant C comme tour intermédiaire.
2. Déplacez le lecteur inférieur de A à C.
3. Déplacez n - 1 disques de la tour B vers la tour C, la tour A est intermédiaire.

Étonnamment, cet algorithme récursif fonctionne non seulement pour trois, mais pour n'importe quel nombre de disques. Encodez-le comme une fonction hanoi (), qui est responsable du déplacement des disques d'une tour à l'autre à l'aide d'une troisième tour temporaire (Listing 1.22).

Listing 1.22. hanoi.py (suite)

 def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1) 

Après avoir appelé hanoi (), vous devez vérifier les tours A, B et C pour vous assurer que les disques ont été déplacés avec succès (extrait 1.23).

Listing 1.23. hanoi.py (suite)

 if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c) 

Vous constaterez que les disques ont bien été déplacés. Lors du codage de la solution au problème de la tour de Hanoi, il n'est pas nécessaire de comprendre toutes les étapes nécessaires pour déplacer plusieurs disques de la tour A vers la tour C. Nous sommes arrivés à comprendre l'algorithme général récursif pour déplacer n'importe quel nombre de disques et le systématiser, permettant à l'ordinateur de faire le reste. C'est le pouvoir de formuler des solutions récursives aux problèmes: on peut souvent imaginer des solutions de manière abstraite, sans gaspiller d'énergie sur la représentation mentale de chaque action individuelle.

Soit dit en passant, la fonction hanoi () sera exécutée de façon exponentielle en fonction du nombre de disques, ce qui rend la solution au problème même pour 64 disques inadaptée. Vous pouvez essayer de l'exécuter avec un nombre différent de disques en modifiant la variable num_discs. À mesure que le nombre de disques augmente, le nombre d'étapes pour terminer la tâche de la tour de Hanoi augmente de façon exponentielle; plus de détails peuvent être trouvés dans de nombreuses sources. Si vous souhaitez en savoir plus sur les mathématiques derrière la solution récursive de ce problème, voir l'explication de Karl Birch dans l'article "Sur les tours de Hanoi" .

1.6. De vraies applications

Les différentes méthodes présentées dans ce chapitre (récursivité, mémorisation, compression et manipulation au niveau du bit) sont tellement répandues dans le développement de logiciels modernes que sans elles, il est impossible d'imaginer le monde de l'informatique. Malgré le fait que les tâches peuvent être résolues sans elles, il est souvent plus logique ou plus opportun de les résoudre en utilisant ces méthodes.

En particulier, la récursivité sous-tend non seulement de nombreux algorithmes, mais même des langages de programmation entiers. Dans certains langages de programmation fonctionnels, tels que Scheme et Haskell, la récursion remplace les boucles utilisées dans les langages impératifs. Cependant, il ne faut pas oublier que tout ce qui peut être réalisé en utilisant la méthode récursive peut également être effectué de manière itérative.

La mémorisation a été utilisée avec succès pour accélérer le travail des analyseurs - programmes qui interprètent les langues. Ceci est utile dans toutes les tâches où le résultat d'un calcul récent est susceptible d'être demandé à nouveau. Un autre domaine d'action pour la mémorisation est le runtime du langage de programmation. Certains de ces environnements d'exécution, par exemple, pour la version Prolog, enregistrent automatiquement les résultats des appels de fonction (auto-mash), de sorte que la fonction n'a pas à être exécutée la prochaine fois avec le même appel. Ceci est similaire au décorateur @lru_cache () dans fib6 ().

La compression a rendu le monde d'Internet, avec sa bande passante limitée, plus supportable. La méthode des chaînes de bits discutée dans la section 1.2 est applicable aux types de données simples dans le monde réel qui ont un nombre limité de valeurs possibles, pour lesquelles même 1 octet est redondant. Cependant, la plupart des algorithmes de compression fonctionnent en recherchant des modèles ou des structures dans un ensemble de données qui éliminent les informations en double. Ils sont beaucoup plus compliqués que ceux décrits dans la section 1.2.

Les chiffres jetables ne conviennent pas aux cas de chiffrement général. Ils nécessitent que l'encodeur et le décodeur aient une des clés (données factices dans notre exemple) pour restaurer les données d'origine, ce qui est trop lourd et dans la plupart des schémas de cryptage ne permet pas d'atteindre l'objectif de garder les clés secrètes. Mais vous pourriez être intéressé de savoir que le nom «chiffrement jetable» a été inventé par des espions qui, pendant la guerre froide, ont utilisé de vrais cahiers en papier avec des données fictives enregistrées pour créer des messages cryptés.

Ces méthodes sont les éléments constitutifs des programmes; d'autres algorithmes sont basés sur eux. Dans les chapitres suivants, vous verrez à quel point ils sont appliqués.

À propos de l'auteur

David Kopec est maître de conférences en informatique et innovation au Champlain College de Burlington, au Vermont. Il est un développeur de logiciels expérimenté et auteur de Classic Computer Science Problems in Swift (Manning, 2018) et Dart for Absolute Beginners (Apress, 2014). David a obtenu un baccalauréat en économie et une maîtrise en informatique du Dartmouth College. Vous pouvez le contacter sur Twitter par @davekopec.

»Plus d'informations sur le livre sont disponibles sur le site Web de l'éditeur
» Contenu
» Extrait

25% de réduction sur les colporteurs - Python

Lors du paiement de la version papier du livre, un livre électronique est envoyé par e-mail.