J'aimerais me considérer comme un programmeur assez expérimenté. Je programme depuis plus de 5 ans maintenant. Mon point faible cependant est la terminologie. Je suis autodidacte, alors que je sais programmer, je ne connais pas certains des aspects les plus formels de l'informatique. Alors, quels sont les algorithmes pratiques / structures de données que je pourrais reconnaître et connaître par leur nom?

Remarque, je ne demande pas de recommandation de livre sur la mise en œuvre d'algorithmes. Peu m'importe de les implémenter, je veux juste savoir quand un algorithme / structure de données serait une bonne solution à un problème. Je demande plus pour une liste d'algorithmes / structures de données que je devrais "reconnaître". Par exemple, je connais la solution à un problème comme celui-ci:

Vous gérez un ensemble de casiers étiquetés 0-999. Les gens viennent chez vous pour louer le casier puis reviennent pour rendre la clé du casier. Comment construirez-vous un logiciel pour savoir quels casiers sont gratuits et lesquels sont utilisés?

La solution serait une file d'attente ou une pile.

Ce que je recherche, ce sont des choses telles que "dans quelle situation faut-il utiliser un arbre B, quel algorithme de recherche doit être utilisé ici", etc. les algorithmes fonctionnent.

J'ai essayé de consulter la liste des structures de données et des algorithmes de Wikipedia, mais je pense que c'est un peu exagéré. Donc, je cherche plus quelles sont les choses essentielles que je devrais reconnaître?

Une réponse objective:

Alors que ma réponse initiale à cette question était basée sur mon expérience empirique en tant qu'étudiant en informatique qui allait bientôt obtenir son diplôme et sur mon opinion projetée sur le type de personnes avec lesquelles je voulais travailler dans le domaine de la SC. Il existe en fait une réponse objective (en ce qui concerne les opinions subjectives des sociétés informatiques ACM SIGCSE et IEEE). Tous les 10 ans, l' ACM et les organes de l' IEEE coopèrent pour une publication commune qui détaille les suggestions de cursus de premier cycle en informatique, fondées sur une connaissance professionnelle de l'état de l'industrie informatique. Plus d'informations peuvent être trouvées à cs2013.org . Le comité publie un rapport final contenant la recommandation de son programme d’études .

Cela dit, je pense toujours que ma liste est plutôt bonne.

Réponse originale ci-dessous.

Que devrais-je savoir?

Le minimum

Je pense qu'un programmeur expérimenté devrait avoir au moins une connaissance de premier cycle en informatique. Bien sûr, vous pouvez être efficace dans de nombreux emplois avec seulement un petit sous-ensemble de la science informatique en raison de la solidité de la communauté sur laquelle CS est assis et de la concentration réduite de la plupart des postes de professionnels. En outre, de nombreuses personnes se spécialiseront après leurs études de premier cycle. Cependant, je ne pense pas non plus que ce soit une excuse pour ne pas être au courant des connaissances fondamentales en matière de CS.

Pour répondre à la question du titre, voici ce qu'un étudiant de premier cycle en CS (la base d'un programmeur expérimenté) devrait savoir à la fin de ses études:

Structures de données

• Représentation des données de la machine
  • Ones, complément à deux et arithmétique associée
  • Mots, pointeurs, virgule flottante
  • Accès aux bits, décalage et manipulation
• Listes liées
• Tables de hachage (cartes ou dictionnaires)
• Tableaux
• Des arbres
• Des piles
• Les files d'attente
• Graphiques
• Bases de données

Algorithmes

• Tri:
  • Bubble Sort (pour savoir pourquoi c'est mauvais)
  • Tri par insertion
  • Tri par fusion
  • Tri rapide
  • Tris de style Radix, tri par comptage et tri par seau
  • Sorte de tas
  • Bogo et Quantum Sort (=
• Recherche:
  • Recherche linéaire
  • Recherche binaire
  • Profondeur Première Recherche
  • Largeur première recherche
• Manipulation de chaîne
• Itération
• Traversée des arbres
• Liste Traversal
• Fonctions de hachage
• Implémentation concrète d'une table de hachage, d'une arborescence, d'une liste, d'une pile, d'une file d'attente, d'un tableau et d'un ensemble ou d'une collection
• Algorithmes de planification
• Traversée et manipulation du système de fichiers (au niveau de l' inode ou d'un niveau équivalent).

Modèles de conception

• La modularisation
• Usine
• Constructeur
• Singleton
• Adaptateur
• Décorateur
• Poids mouche
• Observateur
• Itérateur
• Etat [Machine]
• Modèle Vue Contrôleur
• Filetage et modèles de programmation parallèles

Paradigmes

• Impératif
• Orienté Objet
• Fonctionnel
• Déclaratif
• Programmation statique et dynamique
• Balisage de données

Théorie de la complexité

• Espaces Complexité
• Calculabilité
• Langages complets standard, sans contexte et universels de Turing Machine
• Expressions régulières
• Comptage et combinatoire de base

Au-delà

Pour entrer dans le vif du sujet que vous posez plus tard dans votre question, si vous êtes familier avec ce qui précède, vous devriez pouvoir facilement 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 tout aussi viables. Pour cette raison, vous avez besoin de connaissances générales pour pouvoir défendre votre choix contre vos pairs.

Voici quelques conseils pour les algorithmes et les structures de données:

• La recherche binaire ne peut (et ne devrait) être utilisée que sur des données triées.
• Les tris de style Radix sont géniaux, mais seulement lorsque vous avez trié des classes finies de choses.
• Les arbres sont bons pour presque 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'une astuce mathématique pour accéder aux emplacements d'un tableau.
• Le choix de la langue peut faire la différence entre 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 beaucoup de problèmes, mais elles ne peuvent pas être utilisées pour analyser HTML .
• Parfois, la structure de données est tout aussi importante que l'algorithme.

Certains des éléments ci-dessus peuvent sembler évidents, et d'autres peuvent sembler vagues. Si vous voulez que je rentre plus en détail, je peux. Mais, mon espoir est de rencontrer une question plus concrète, telle que: "Concevoir une fonction qui compte le nombre d'occurrences de chaque caractère dans une chaîne", vous vous penchez sur le conseil concernant la table ASCII et les tableaux de 128 éléments formant un hachage implicite net. tables pour la réponse.

Sur la base de ces idées, je proposerai une réponse au problème du casier décrit dans votre question.

Répondez au problème posé dans votre question.

Ce n'est peut-être pas la meilleure réponse à votre question, mais je pense que c'est une question intéressante qui n'exige rien de trop complexe. Et il dépassera certainement la complexité temporelle liée à l'utilisation d'une file d'attente ou d'une pile, qui nécessite un temps linéaire pour déterminer si un casier est libre ou non.

Vous avez 0-999 casiers. Maintenant, comme vous avez un nombre fixe de casiers, vous pouvez facilement concevoir une fonction de hachage sans collision sur la plage de 0 à 999. Cette fonction est simplement h (x) = x mod 1000. Maintenant, [conceptuellement] construisez une table de hachage avec des clés entières et le contenu d'un tableau de 1000 éléments comme valeurs. Si un client souhaite réserver le casier 78 pour utilisation, il suffit de mettre 78 dans la fonction de hachage (en renvoyant 78), puis d'ajouter ce nombre au pointeur de base du tableau - en stockant une valeur vraie à l'emplacement indiqué par la valeur de décalage . De même, si vous devez vérifier si 78 est en cours d'utilisation, il vous suffit de lire la valeur stockée à cet emplacement et de vérifier qu'elle est vraie.

Cette solution fonctionne en temps constant pour les recherches et le stockage, par opposition à un stockage journal (n) et à une recherche dans le cas d'une file d'attente prioritaire sauvegardée par une arborescence binaire. La description est intentionnellement commentée afin que vous puissiez voir les concepts les plus élevés se résumer en un algorithme efficace.

Maintenant, vous vous demandez peut-être si je dois connaître tous les casiers disponibles, une file d'attente prioritaire ne serait-elle pas meilleure? S'il existe k casiers disponibles dans la file d'attente prioritaire, une itération sur chacun d'entre eux prendra k étapes. En outre, selon l’implémentation de votre file d’attente prioritaire, vous devrez peut-être reconstruire votre file d’attente prioritaire en l’observant dans son intégralité. Cela prendrait k * log (k): (k <1000) étapes. Dans la solution de tableau, il vous suffit d'itérer un tableau de 1000 éléments et de vérifier ceux qui sont ouverts. Vous pouvez également ajouter une liste disponible ou utilisée à l'implémentation à vérifier dans k fois seulement.

Le Manuel de conception d'algorithmes de Steven S. Skiena semble être la source que vous recherchez. La deuxième partie est une liste classifiée de problèmes avec une revue des algorithmes associés. Il existe une version Web .

Il n'y a pas de "devrait". A. Familiarisez-vous avec les classes de complexité de base (linéaire, logarithmique, etc.) B. Réalisez que vous pouvez faire à peu près n'importe quoi avec un tableau simple, comme avec une structure de données sophistiquée telle qu'un arbre B-tree. L'astuce dans le choix de la structure / algorithme appropriée réside dans l'équilibre des performances, la taille d'entrée attendue et la complexité de la mise en œuvre.

Viennent ensuite des éléments abstraits mais extrêmement utiles (bien que l’utilité ne soit pas immédiatement évidente): machines à états, théorie des graphes, théorie de la convexité (programmation linéaire, etc.).

Le MIT publie gratuitement des notes de cours, des vidéos, des travaux et du matériel d’examen pour Introduction to Algorithms . Les titres de cours énumèrent les algorithmes / structures de données couverts.

Ceci est un consensus révisé par des pairs sur ce que vous devriez savoir. C'est probablement une excellente ressource d'apprentissage, aussi.