algorithmique

Apprendre l'algorithmique

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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.

+0 -0

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

Staff

Cette réponse a aidé l'auteur du sujet

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. :-)

Édité par nohar

I was a llama before it was cool

+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

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. :)

Édité par KFC

+0 -0
Staff

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.

Édité par Algue-Rythme

+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.

Édité par KFC

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

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