Algorithmes et Structures de données ! Que dois-je savoir ?

Algorithmes et Structures de données ! Que dois-je savoir ?

Introduction

Un programmeur adepte devrait avoir au moins des connaissances de premier cycle en informatique. Bien sûr, vous pouvez être efficace dans de nombreux emplois avec seulement un petit sous-ensemble de connaissance informatique en raison de la communauté solide et de la concentration réduite de la plupart des postes professionnels. En outre, de nombreuses personnes se spécialiseront davantage après des études de premier cycle. Cependant, je pense que très important d’être au courant des connaissances fondamentales en science informatique.

Voici une liste de base que vous devez le savoir :

Structures de données

Une structure de données est une collection de « valeurs » de type de données qui sont stockées et organisées de manière à permettre un accès et une modification efficaces. Dans certains cas, une structure de données peut devenir l’implémentation sous-jacente d’un type de données particulier.

  • Représentation des données machine.
    • Un, complément à deux et arithmétique associée.
    • Mots, pointeurs, virgule flottante.
    • Accès, décalage et manipulation des bits
  • Listes liées.
  • Tables de hachage
  • Tableaux
  • Piles
  • Queues
  • Arbres
  • Bases de données
  • Graphiques

Algorithmes

Un algorithme est un ensemble d’instructions conçu pour effectuer une tâche spécifique. Il peut s’agir d’un processus simple, tel que la multiplication de deux nombres, ou d’une opération complexe, telle que la lecture d’un fichier vidéo compressé. Par exemple les moteurs de recherche utilisent des algorithmes propriétaires pour afficher les résultats les plus pertinents de leur index de recherche pour des requêtes spécifiques 

  • Tri
    • Tri à bulles
    • Tri par insertion
    • Tri par fusion
    • Tri rapide
    • Tri de style Radix, tri par comptage et tri par compartiment
    • Tri de tas (Heap)
    • Bogo et tri quantique
  • Recherche
    • Recherche linéaire
    • Recherche binaire
    • Première recherche en profondeur
    • Première recherche en largeur
  • Manipulation de chaînes
  • Itération
  • Traversée d’arbres
  • Traversée de liste
  • Fonctions de hachage
  • Implémentation concrète d’une
    • Table de hachage
    • Arborescence
    • Liste
    • Pile
    • File d’attente
    • Tableau
    • Ensemble ou d’une collection
  • Algorithmes de planification
  • Traversée et manipulation du système de fichiers

Modèles de conception

Les modèles de conception sont des modèles de code qui résolvent des problèmes classiques. Ce sont des solutions aux problèmes de conception de logiciels que vous pouvez trouver dans une application réelle. Un modèle de conception n’est pas un code prêt à être utilisé dans votre application, mais c’est un modèle que vous pouvez utiliser pour résoudre un problème.

  • Construction :  ils définissent comment faire l’instanciation et la configuration des classes et des objets.
    • Fabrique abstraite (Abstract Factory)
    • Monteur (Builder)
    • Fabrique (Factory Method)
    • Prototype
    • Singleton
  • Structuraux : ils définissent comment organiser les classes d’un programme dans une structure plus large (séparant l’interface de l’implémentation).
    • Adaptateur (Adapter)
    • Pont (Bridge)
    • Objet composite (Composite)
    • Décorateur (Decorator)
    • Façade (Facade)
    • Poids-mouche ou poids-plume (Flyweight)
    • Proxy (Proxy)
  • Comportementaux : ils définissent comment organiser les objets pour que ceux-ci collaborent (distribution des responsabilités) et expliquent le fonctionnement des algorithmes impliqués.
    • Chaîne de responsabilité (Chain of responsibility)
    • Commande (Command)
    • Interpréteur (Interpreter)
    • Itérateur (Iterator)
    • Médiateur (Mediator)
    • Mémento (Memento)
    • Observateur (Observer)
    • État (State)
    • Stratégie (Strategy)
    • Patron de méthode (Template Method)
    • Visiteur (Visitor)

Paradigmes

Paradigmes est une école de pensée ou un modèle qui a des caractéristiques, des cadres, des modèles et un style distincts qui vous aident à résoudre un problème particulier. Les paradigmes sont utilisés dans tous les domaines tels que la psychologie, la sociologie, l’étymologie, l’informatique, etc. Dans le domaine de l’informatique, de nouveaux langages de programmation émergent des langages existants et ajoutent, suppriment et combinent des fonctionnalités d’une manière nouvelle. Les langues peuvent suivre un paradigme particulier ou peuvent être une combinaison de nombreux paradigmes.

  • Impératif
  • Orienté objet
  • Fonctionnel
  • Déclaratif
  • Programmation statique et dynamique
  • Balisage des données

Théorie de la complexité

La théorie de la complexité est l’ensemble des connaissances concernant les principes fondamentaux du calcul. Ses débuts remontent à l’histoire jusqu’à l’utilisation de la complexité asymptotique et réductibilité par les Babyloniens. La théorie de la complexité moderne est le résultat d’activités de recherche dans de nombreux domaines différents : biologistes étudiant des modèles de réseaux de neurones ou d’évolution, ingénieurs électriciens développant la théorie de la commutation comme outil de conception de matériel, mathématiciens travaillant sur les fondements de la logique et de l’arithmétique, des linguistes enquêtant sur les grammaires des langues naturelles, des physiciens qui étudient les implications de la construction d’ordinateurs quantiques, et enfin et surtout, informaticiens à la recherche d’algorithmes efficaces pour des problèmes difficiles.

  • Espaces de complexité
  • Calculabilité
  • Langages complets de la machine de Turing régulière, sans contexte et universelle
  • Expressions régulières
  • Comptage et combinatoire de base

Conseils

  • Parfois, la structure des données est tout aussi importante que l’algorithme.
  • La recherche binaire ne peut (et devrait) être utilisée que sur des données triées.
  • Les tris de style Radix sont géniaux, mais seulement lorsque vous avez des classes finies de choses en cours de tri.
  • Les arbres sont bons pour presque tout, tout comme les tables de hachage. La fonctionnalité d’une table de hachage peut être extrapolée et utilisée pour résoudre de nombreux problèmes au détriment de l’efficacité.
  • Les tableaux peuvent être utilisés pour sauvegarder la plupart des structures de données de niveau supérieur. Parfois, une structure de données n’est rien de plus qu’un calcul intelligent pour accéder aux emplacements dans un tableau.
  • Le choix de la langue peut faire la différence entre s’arracher les cheveux ou traverser un problème.
  • La table ASCII et un tableau de 128 éléments forment une table de hachage implicite.
  • Les expressions régulières peuvent résoudre de nombreux problèmes, mais elles ne peuvent pas être utilisées pour analyser le HTML.

Conclusion

Si vous êtes familier à ce qui précède, vous devriez être facilement en mesure d’identifier le modèle, l’algorithme et la structure de données appropriés pour un scénario donné. Cependant, vous devez reconnaître qu’il n’y a souvent pas de meilleure solution. Parfois, vous devrez peut-être choisir le moindre de deux maux ou même simplement choisir entre deux solutions également viables. Pour cette raison, vous avez besoin de connaissances générales pour pouvoir défendre votre choix contre vos pairs.

Vos commentaires et critiques constructives sont toujours appréciés, Vous pouvez aussi lire l’article à-propos La programmation défensive.

Partagez !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *