Relation entre l'orientation des objets et les algorithmes

En lisant certains manuels d'algorithmes, ils regorgent de procédures astucieuses pour certains problèmes (tri, chemin le plus court) ou quelques méthodes générales (algorithmes récursifs, diviser pour mieux régner, programmation dynamique ...). J'y ai trouvé peu de traces de programmation orientée objet; (Pourquoi sont-ils plus orientés vers la procédure?).

Alors je pensais:

• Quelle est la relation entre les algorithmes et la POO? S'agit-il de deux sujets indépendants?
• Y a-t-il des problèmes qui ne peuvent être présentés et résolus que par la POO?
• Comment la POO peut-elle aider les algorithmes? Ou dans quelle direction cela peut-il l'affecter?

Tout d'abord, définissons ce que nous entendons par POO. Par POO, je veux dire principalement:

• Encapsulation et masquage des détails en classe.
• Polymorphisme de comportement par héritage et méthodes virtuelles.

Maintenant, pour répondre à votre question:

Quelle est la relation entre les algorithmes et la POO? S'agit-il de deux sujets indépendants?

Oui.

Y a-t-il des problèmes qui ne peuvent être présentés et résolus que par la POO?

Non. OOP primaire offre la commodité et la capacité de raisonner sur le code pour le programmeur. Cela n'augmente pas votre pouvoir expressif.

Comment la POO peut aider les algorithmes? Ou dans quelle direction cela peut-il l'affecter?

Comme je l'ai dit plus haut. Les deux points que j'ai décrits OOP s'appliquent ici. Être capable de cacher les détails des algorithmes et de leurs structures de données peut aider à raisonner sur le tout. De nombreux algorithmes contiennent des détails avec lesquels vous ne voulez pas que l'utilisateur de cet algorithme s'amuse. Cacher ces détails aide beaucoup.

La capacité à avoir un comportement polymorphe est également très bonne. Listest défini comme étant capable d'ajouter / supprimer / effacer les éléments n'importe où dans la collection. Mais il peut être implémenté sous forme de tableau redimensionnable, à double ou simple lien, etc. Le fait d'avoir une seule API pour plusieurs implémentations peut aider à la réutiliser.

Pourquoi les manuels d'algorithmes sont plus orientés vers les procédures?

Comme je l'ai dit, la POO n'est pas nécessaire pour implémenter un algorithme. De plus, de nombreux algorithmes sont anciens et créés alors que la POO n'était pas encore répandue. Cela pourrait donc aussi être une chose historique.

Les algorithmes et la POO sont deux termes disparates, qui n'ont qu'un point commun, qu'ils sont des termes CS . Simplement - Un algorithme est comme une recette de cuisine : pour faire x, vous avez besoin des ingrédients suivants et faire les étapes 1,2,3,4,5,6 ... puis vous avez votre repas préparé.

Cela dit, il semble normal que les algortihms soient décrits de manière procédurale . La procédure ne signifie rien d'autre que: d' abord faire x puis faire y .

Un problème courant est: »Comment trier un ensemble de x ?«. Une solution facile à comprendre est bubble-sort:

1. Itérer sur l'ensemble du dernier élément tant que vous n'avez pas atteint le premier élément et pendant l'itération
2. Commencez une 2ème itération du début à l'élément courant de la première itération et
3. Comparer l'élément actuel de (2) avec son successeur
4. Si supérieur, permutez les positions

Telle est la description algorithmique / verbale de l' bubblesortalgorithme.

Voici une implémentation procédurale / pseudocode

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

C'était facile.

Comment cela se répercute-t-il sur la POO ? Vous pouvez utiliser cet algorithme pour traiter les collections (un objet lui-même) d' objets :

Exemple en Javascript (bien qu'il n'y ait pas d'OO-Lingo propre , mais presque sans passe-partout et facile à comprendre)

objects =[{"name":"Peter"}, {"name":"Paul"}, {"name":"Mary"}]

compareObjects=function(x,y){ return x.name>y.name };

sorted = objects.sort(compareObjects)

console.log(sorted)

Nous avons a) une collection objects, b) une méthode commune à cette collection sortqui contient / résume l'algorithme de tri et c) nos objets Peter , Paul et Mary . La spécification pour le tri se trouve ici .

Quelle est la relation entre les algorithmes et la POO? S'agit-il de deux sujets indépendants?

D'après ce qui a été dit, cela devrait être clair, la réponse devrait être: oui, ils sont indépendants.

Comment la POO peut aider les algorithmes? Ou dans quelle direction cela peut-il l'affecter?

La POO n'est qu'un style de programmation. Cela ne peut en aucun cas aider . Sinon, un algorithme pourrait être implémenté dans un langage OO pour faire quelque chose aux objets (comme indiqué)

Y a-t-il des problèmes qui ne peuvent être présentés et résolus que par la POO?

Je ne peux pas penser à un (mais cela ne veut pas dire que c'est impossible). Mais si vous regardez l'inverse: la POO est utile, si vous voulez modéliser certains problèmes et les résoudre avec un algorithme approprié. Disons que vous avez un enregistrement de friendsvous pourriez les modéliser comme objectsavec propertieset si vous voulez un listde friends tri de quelque façon, vous pouvez utiliser l'exemple de code ci - dessus pour faire exactement cela.

Pourquoi les manuels d'algorithmes sont plus orientés vers les procédures?

Comme dit: c'est plus naturel , puisque procédural est le caractère des algorithmes.

vous avez un problème.

Le modèle de domaine métier décrit votre problème et les concepts du domaine problématique avec lesquels vous allez vous occuper.

Les algorithmes décrivent la façon dont vous allez résoudre vos problèmes, conceptuellement; à quoi ressemblera votre implémentation; et comment gérez-vous votre problème après l'avoir traduit en termes "informatique".

Le paradigme de programmation, qu'il soit OOP, fonctionnel, logique, procédural ou même non structuré, décrit comment allez-vous structurer votre solution, quelle forme va-t-elle prendre, quels concepts de "génie logiciel" allez-vous utiliser et lesquels " Concepts de la théorie du langage de programmation que vous allez utiliser.

Pour le dire plus simplement, les algorithmes décrivent en général votre solution au problème ("C'est ce que je vais faire"). Alors que le paradigme de programmation traite de votre implémentation réelle ("C'est comme ça que je vais le faire").

Algorithmes = raconter l'histoire du « comment » (c.-à-d. Comment manipuler les données d'entrée en utilisant les structures de données à temps pour produire les résultats souhaités)

OOP = une " méthodologie " facilitée par les langages OO pour écrire des programmes (= algorithmes + structures de données) qui vous donne la sécurité de la mémoire et l'abstraction

La POO n'est qu'un paradigme d'implémentation d'algorithmes.

Bonne analogie : films

Vous pouvez enregistrer des scènes en utilisant un cascadeur ou non. Le scénario (algorithme) ne change pas. Les gens ne devraient pas voir de différence dans le résultat final.

EDIT: vous pouvez essayer un MOOC de bonne qualité: https://www.coursera.org/course/algs4partI qui entrelace les sujets discutés (en particulier l'approche POO) et donne l'essentiel de ce que vous demandez ici.

Alexander Stepanov est le créateur original de la bibliothèque de modèles standard C ++ (STL), qui est la bibliothèque d'algorithmes fondamentale pour C ++. C ++ est un langage multi-paradigme qui inclut des fonctionnalités "orientées objet", mais Alexander Stepanov a ceci à dire sur l'orientation objet:

http://www.stlport.org/resources/StepanovUSA.html

STL n'est pas orienté objet. Je pense que l'orientation objet est presque autant un canular que l'intelligence artificielle. Je n'ai pas encore vu un morceau de code intéressant qui vient de ces gens OO.

Je trouve la POO techniquement malsaine. Il tente de décomposer le monde en termes d'interfaces qui varient sur un seul type. Pour faire face aux vrais problèmes, vous avez besoin d'algèbres multisorties - des familles d'interfaces qui s'étendent sur plusieurs types. Je trouve que la POO n'est pas saine sur le plan philosophique. Il prétend que tout est un objet. Même si c'est vrai, ce n'est pas très intéressant - dire que tout est un objet ne dit rien du tout. Je trouve la POO méthodologiquement erronée. Cela commence par des cours. C'est comme si les mathématiciens commençaient par des axiomes. Vous ne commencez pas avec des axiomes - vous commencez avec des preuves. Ce n'est que lorsque vous avez trouvé un tas de preuves connexes que vous pouvez trouver des axiomes. Vous finissez avec des axiomes. La même chose est vraie en programmation: il faut commencer par des algorithmes intéressants. Seulement quand vous les comprenez bien,

J'ai passé des années à essayer de trouver une utilisation pour l'héritage et les virtuels, avant de comprendre pourquoi ce mécanisme était fondamentalement défectueux et ne devait pas être utilisé.

Stepanov a exprimé sa bibliothèque d'algorithmes non pas avec des objets, mais avec des itérateurs génériques .

Les algorithmes décrivent ce que l'ordinateur doit faire. La structure décrit comment l'algorithme est présenté [dans le code source]. La POO est un style de programmation qui exploite certaines structures "orientées objet".

Les livres d'algorithmes évitent souvent la POO car ils sont axés sur l'algorithme, pas sur la structure. Les fragments de code qui dépendent fortement de la structure ont tendance à être de mauvais exemples à mettre dans un livre d'algorithmes. De même, les livres OOP évitent souvent les algorithmes car ils encombrent l'histoire. Le point de vente de la POO est sa fluidité, et son rattachement à un algorithme le rend plus rigide. Il s'agit plus de l'objectif du livre qu'autre chose.

Dans le code réel, vous utiliserez les deux côte à côte. Vous ne pouvez pas résoudre les problèmes informatiques sans algorithmes, par définition, et vous aurez du mal à écrire de bons algorithmes sans structure (POO ou autre).

Comme exemple de flou, prenez la programmation dynamique. Dans un livre d'algorithmes, vous décririez comment prendre un ensemble de données homogène dans un tableau et utiliser la programmation dynamique pour arriver à une solution. Dans un livre OOP, vous pouvez rencontrer une structure telle que Visitor, qui est un moyen de faire des algorithmes arbitraires sur un ensemble d'objets hétérogènes. L'exemple de livre DP pourrait être considéré comme un visiteur très simple opérant sur des objets dans un ordre généralement ascendant. Le modèle des visiteurs pourrait être considéré comme le squelette d'un problème de DP, mais sans la viande et les pommes de terre. En réalité, vous constaterez que vous avez souvent besoin des deux à la fois: vous utilisez le modèle Visitor pour gérer l'hétérogénéité de votre ensemble de données (DP est mauvais à cela) et vous utilisez DP dans la structure de Visitor pour organiser votre algorithme afin de minimiser le temps d'exécution (Visitor ne fait pas

Nous voyons également des algorithmes fonctionner au-dessus des modèles de conception. Il est plus difficile d'exprimer des exemples dans un petit espace, mais une fois que vous avez une structure, vous commencez à vouloir manipuler cette structure et vous utilisez des algorithmes pour le faire.

Y a-t-il des problèmes qui ne peuvent être présentés et résolus que par la POO?

C'est une question plus difficile à répondre que vous ne le pensez. Pour la première commande, il n'y a aucune raison de calcul pour laquelle vous avez besoin de la POO pour résoudre un problème. La preuve simple est que chaque programme OOP est compilé jusqu'à l'assemblage, qui est décidément un langage non-OOP.

Cependant, dans le plus grand schéma des choses, la réponse commence à hésiter vers oui. Vous êtes rarement limité simplement par des méthodologies informatiques. La plupart du temps, il y a des choses comme les besoins de l'entreprise et les compétences des développeurs qui entrent en ligne de compte. De nombreuses demandes ne pourraient pas être écrites aujourd'hui sans POO, non pas parce que la POO est en quelque sorte fondamentale pour la tâche, mais parce que la structure fournie par la POO était essentielle pour garder le projet sur la bonne voie et dans les limites du budget.

Cela ne signifie pas que nous n'abandonnerons jamais OOP à l'avenir pour une nouvelle structure amusante. Il dit simplement que c'est l'un des outils les plus efficaces de notre boîte à outils pour une fraction étonnamment importante des tâches de programmation qui existent aujourd'hui. Les problèmes futurs peuvent nous amener à aborder le développement en utilisant différentes structures. D'une part, je m'attends à ce que les réseaux neuronaux nécessitent une approche de développement très différente, qui peut ou non se révéler «orientée objet».

Je ne vois pas la POO disparaître dans un avenir proche en raison de la façon dont les concepteurs d'algorithmes pensent. À ce jour, le schéma habituel est que quelqu'un conçoit un algorithme qui ne tire pas parti de la POO. La communauté OOP se rend compte que l'algorithme ne correspond pas vraiment à la structure OOP, et n'a vraiment pas besoin de le faire, alors ils enveloppent l'intégralité de l'algorithme dans une structure OOP et commencent à l'utiliser. Considérez boost::shared_ptr. Les algorithmes de comptage de références qui reposent à l'intérieur shared_ptrne sont pas très conviviaux pour la POO. Cependant, le modèle n'est pas devenu populaire jusqu'à ce qu'il shared_ptrcrée un wrapper OOP autour de lui qui expose les capacités des algorithmes dans un format structuré OOP. Maintenant, il est si populaire qu'il est devenu la dernière spécification pour C ++, C ++ 11.

Pourquoi est-ce si réussi? Les algorithmes sont excellents pour résoudre les problèmes, mais ils nécessitent souvent un investissement de recherche initial important pour comprendre comment les utiliser. Le développement orienté objet est très efficace pour encapsuler de tels algorithmes et fournir une interface qui nécessite moins d'investissement initial pour apprendre.

En plus des bonnes réponses, je mentionnerai un point commun conceptuel supplémentaire entre la POO et les algorithmes.

La POO et les algorithmes mettent fortement l'accent sur l'utilisation des préconditions et des postconditions pour garantir l'exactitude du code.

En général, il s'agit d'une pratique standard dans tous les domaines de l'informatique; cependant, ce principe directeur se traduit par un chemin évolutif dans la POO qui le rend mutuellement avantageux pour implémenter des algorithmes dans un environnement POO.

Dans la POO, un groupe d'objets pouvant satisfaire le même contrat (préconditions et postconditions) peut être créé pour implémenter une interface. L'utilisateur d'une telle interface n'aura pas besoin de savoir quelle implémentation est utilisée dans l'objet sous-jacent, sauf dans de rares situations (dans lesquelles une abstraction qui fuit se produit).

Un algorithme est une implémentation des étapes utilisées pour effectuer un calcul, celle qui prendra la précondition et produira la postcondition.

Par conséquent, on peut emprunter l'idée d' abstraction à la manière des préconditions et des postconditions, et l'appliquer aux algorithmes. Vous constaterez que des algorithmes parfois compliqués peuvent être décomposés en étapes plus petites, et ces étapes plus petites peuvent permettre différentes stratégies de mise en œuvre tant que les mêmes conditions préalables et postconditions sont remplies.

En implémentant des algorithmes dans la POO, on peut rendre ces petites étapes interchangeables.

Enfin, gardez à l'esprit que FP et OOP ne s'excluent pas mutuellement. Tout ce qui est décrit ci-dessus peut également s'appliquer à FP.

What is the relation between algorithms and OOP? Are they two independent topics?

Les algorithmes sont sur la façon de résoudre un problème (comment générer une sortie à partir de l'entrée donnée), la POO est sur la façon de formuler ou d'exprimer notre solution (les étapes de l'algorithme).

Un algorithme peut être décrit en langage naturel ou en langage assembleur, mais les concepts que nous avons en langage naturel nous aident à mieux l'écrire et le comprendre. Par exemple, l'algorithme de tri à bulles pourrait être:

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

Pour masquer les détails swapet les relier à la, Anous avons utilisé une syntaxe et une fonctionnalité OOP, puis OO rend l'algorithme plus proche de notre langage naturel et de notre compréhension.

Are there some problems which can only be presented and solved by OOP?

Non, si vous considérez qu'un programme (ou algorithme) sur un ordinateur sera traduit en un ensemble d'instructions exécutées sur CPU ( Turing Machine ) et si nous considérons ces instructions comme l'algorithme ultime qui résout le problème sur un ordinateur , alors OOP ne peut pas faire quelque chose de plus. Cela le rapproche simplement de la compréhension et du raisonnement humains. C'est un moyen de regrouper nos procédures et structures de données.

How OOP can help algorithms? Or in which direction it can affect it?

Cela peut aider à énoncer ou à formuler un algorithme plus facile ou plus compréhensible. Il peut masquer les détails et fournir une vue d'ensemble de la solution.

En théorie, l'algorithme est le premier et l'implémente le second . Mais en réalité, nous ne pouvons pas être sûrs que notre algorithme fonctionne comme prévu jusqu'à ce que nous le traçions ou générions la sortie attendue. Les ordinateurs nous aident à le faire, mais vous ne vous attendez pas à l'écrire en langage machine (assemblage).

À cet égard, la POO facilite l'implémentation, le test et le raffinement de notre algorithme sur les ordinateurs et l'écrit pour un ordinateur dans un langage proche de notre langage naturel.