algorithmique

Apprendre l'algorithmique

a marqué ce sujet comme résolu.

Salut à la communauté. J'ai appris la programmation en C sur ce site. Mais je voudrais continuer dans les sentiers joyeux de la programmation. Mais un ami m'a conseillé d'apprendre ensuite l'algorithmique. Il m'a parlé d'algorithme de tri, de structures de données et autres joyeusetés. J'ai trouvé ça passionnant. Alors je suis venu ici pour demander conseil à la communauté. Je commence déjà à lire le tuto algorithmique pour l'apprenti programmeur mais si la communauté à d'autres conseils à me donner et d'autres références, vous me voyez ravi.

Je ne sais pas vraiment si on peut parler d'apprentissage de l'algorithmique. Généralement, on découvre l'algorithmique pendant que l'on apprend un langage (ou la programmation en général). Il arrive toujours un moment où on se dit "Tiens, ça serait plus efficace comme ça" ou "Hé, pourquoi ça marche pas, là ?", et à force de chercher, on devient meilleur à trouver des algorithmes corrects et performants. :P

CodinGame, cité par mon voisin du dessus, est vraiment bourré d'excellents exercices pour ça. :D

J'approuve mon VDD.

Ça serait peut-être violent d'apprendre l'algorithmique frontalement et d'un bloc. Une bonne façon de s'y mettre est probablement de commencer par les connaissances de base (la complexité, la notation en $O(...)$), puis de découvrir le reste au fur et à mesure que l'on programme.

Souvent il s'agit de chercher la bonne structure de données pour résoudre un problème. Parfois réutiliser des algos connus pour résoudre un problème donné de façon optimale et avoir assez d'imagination pour le transposer dans un nouveau contexte (identifier les équivalences entre problèmes). Assez rarement, imaginer un nouvel algo original. Quoi qu'il en soit, tout ça demande de l'habitude, donc ça peut devenir rapidement rébarbatif de chercher à acquérir ce mind set d'un coup. :-)

+2 -0

Salut, Pour l'algo, c'est vrai que c'est intéressant au début pour apprendre à penser une fonction et t'affranchir du langage, mais après ça va vite devenir un automatisme que tu vas coder et au final, tu fera plus de la conception (UML) et l'algo des différentes méthodes viendra assez naturellement et pour faire du tri ou autre besoins assez courant, il existe de très bon algo déjà fait (Par exemple le Quick Sort pour le tri).

Après tu demandes aussi ce que tu peux voir de plus, il y a un domaine des mathématiques qui est super utilisé, même le plus utilisé, c'est la théorie des graphes. en gros c'est assez abordable pour un informaticiens (Du point de vu implémentation) et permet d'avoir des Algo très intéressant (Pour du pathfinding : Dijkstra ou Bellman Ford, Automates finis, etc…). La théorie des graphes est appliquée dans le Page Rank de Google, les RegEx, les IA, …

+0 -0

C'est un peu réducteur pour l'algorithmique, ça. :P Certes, on a vite fait le tour de l'algorithmique "de base", celle dont on se sert tous les jours quand on fait de l'info. Mais il y a beaucoup de choses à apprendre et à découvrir, d'ailleurs y'a énormément de recherches en algorithmique et en informatique théorique aujourd'hui !

Je suis plutot mitige sur l'importance que tu apportes a la theorie des graphes. Les graphes c'est aussi et surtout une structure de donnees, et un support pratique, transversale pour representer une relation entre des objets. Dans la vie de tous les jours ce n'est ni plus ni moins important que l'algo.

Rien que l'exemple du pageRank pour illustrer l'importance de la theorie des graphes est mauvais dans la mesure ou l'essentiel du pageRank c'est de l'algebre et du calcul spectral. Comme tu peux le voir ici, pas une reference a un graphe.

Pareil pour bien des algorithmes que tu donnes ou en general le graphe n'est qu'un support de visualisation.

Algorithmique et structure de donnees, c'est la vie. :)

+0 -0

En matière de graphe, faut quand même savoir coder un DFS, un BFS et un dynamique.

Quant on sait coder un DFS on a aucun mal à coder un backtrack, un min-max et pas mal d'autres fonctions de recherche récursives dans un graphe. De plus un grand nombre de problèmes peuvent être résolus avec un DFS légèrement modifié.

De manière générale, quand on code un algo qui travaille sur un graphe (même de manière implicite), c'est toujours bien de savoir que c'est un graphe, ça permet de réfléchir plus "proprement" avec plus d'outils intellectuels à sa disposition.

Pareil pour le BFS, c'est super sympa pour faire de pathfinding, et pas mal d'autres choses. Après on peut coder A* et Dijsktra sans douleur.

Et le dynamique, même si c'est pas indispensable, ça aide de savoir que ça fonctionne sur des DAG. Quand t'identifies un DAG, direct, tu penses "dynamique !".

J'aurais tendance à conseiller vivement les algo de graphe. C'est même le premier truc que je ferais apprendre après les structures de données classiques (listes, files…) et les algos de base (balayages, fenêtres glissantes, tris… ).

Même l'implémentation d'un tas ou d'un ABR je le mettrais après les graphes.

+0 -0

Rien que l'exemple du pageRank pour illustrer l'importance de la theorie des graphes est mauvais dans la mesure ou l'essentiel du pageRank c'est de l'algebre et du calcul spectral. Comme tu peux le voir ici, pas une reference a un graphe.

HS : La modélisation du problème est pourtant une marche aléatoire sur un graphe orienté. Après avec les matrices on peut très bien préférer une formalisation algébrique ou vectorielle.

Après pour revenir sur le sujet principal, je te conseille vivement de regarder l'implémentation d'un Dijkstra par exemple, c'est simple et assez marrant pour trouver le plus court chemin d'un point donné vers tout les autres.

+0 -0

Les representations en graphes de marche aleatoire c'est bon pour les cours d'introduction en processus stochastique. En pratique, ca ressemble a de l'algebre et de l'analyse fonctionnelle comme outils pour les probabilites et on utilise les graphes pour illustrer mais on fait pas de reelle theorie des graphes.
On est bien loin de problemes ou ce sont bien des outils de la theorie des graphes qui vont nous aider. Et il y a plein, juste pas PageRank.

+0 -0

Si ton but c’est d’apprendre l’algo, les sites conseillés sont clairement les plus sympa. Comme on ne sait pas ton niveau d’étude on peut pas faire vraiment mieux. Mais si tu es en études supérieur et que tu as fais des maths à un niveau de L2 Maths (voire L3) donc prépa maths 1ère année, tu peux aller jouer dans la complexité sans problème. Sinon attend un peu de mûrir dans ce domaine en explorant des problèmes.

Et sinon l’algorithmique "de base" n’est même pas si maîtrisée. On cherche encore comment multiplier des matrices et il y a pas si longtemps on a mis au point des algorithmes qui permettent de faire des multiplications de nombres. Oui oui, je parle bien de multiplication entre deux entiers. Donc pas d’inquiétude, personne n’arrêtera un jour de chercher de nouvaeux algorithmes ;)

Et sinon l’algorithmique "de base" n’est même pas si maîtrisée. On cherche encore comment multiplier des matrices et il y a pas si longtemps on a mis au point des algorithmes qui permettent de faire des multiplications de nombres. Oui oui, je parle bien de multiplication entre deux entiers. Donc pas d’inquiétude, personne n’arrêtera un jour de chercher de nouvaeux algorithmes.

On dirait un peu du journalisme : il y a bien une idée derrière, mais c’est suffisamment exagéré pour que ça devienne du sensationnalisme un peu ridicule :-°

Donc, pour compléter : on cherche comment multiplier des très grosses matrices de façon encore plus rapide. Ça fait bien longtemps qu’on sait comment multiplier des matrices, et on a aussi des algorithmes pour multiplier des nombres depuis un peu moins de 4000 ans. Ce qui est vrai, c’est qu’on cherche encore des nouveaux algorithmes pour des tâches qu’on sait déjà résoudre parce qu’on espère pouvoir les résoudre plus vite. Mais on est alors très loin de l’algorithmique « de base » :-)

+4 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte