algorithmique

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.

Voici l'entraînement parfait à l'algorithmique de tout codeur qui se respecte.

Un site souvent conseillé : http://www.france-ioi.org/

Tu vas pouvoir reflechir sur des problèmes plus ou moins simples et mettre ce genre de choses en oeuvre.

Dans un style similaire mais différent tu as https://www.codingame.com/

edit : grillé

Un bon livre que tu peux trouver les entrailles d'internet : http://algs4.cs.princeton.edu/home/

Cool comme site, je sens que je vais y passer des heures

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.

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

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, …

C'est un peu réducteur pour l'algorithmique, ça. 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 !

Bien sûr, après que ça soit pour l'algo ou les graphes, dès qu'on veut s'intéresser à des problèmes intéressant, ça fait tout de suite appel à des maths plutôt difficile…

D'ailleurs : Tuto complexité Comparaison

Graphes : Algos graphe

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.

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.

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.

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.

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 »

C’est vrai que je me suis un peu emporté…

Merci de la correction

Note: vous parlez sur un sujet de mai 2016