Comment aborder la programmation compétitive et l'algorithmie à bon niveau ?

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour à tous,

Je me suis donné cet été pour objectif de participer à la Google Code Jam (et sûrement d’autres compétitions du genre organisée par Facebook ou IBM) avec l’objectif d’arriver en finale. De manière conjointe j’aimerais devenir particulièrement bon en algorithmie, domaine dans lequel j’aimerais faire de la recherche. Je viens vers vous pour savoir si mon approche est bonne et ce qui pourrait être amélioré pour compléter ces deux objectifs.

Tout d’abord, que vous sachiez où j’en suis pour me guider au mieux. Je viens de terminer une double Licence Mathématiques Informatique, que j’ai essentiellement réussi grâce à l’info sans se mentir. J’ai donc un bagage mathématiques non nul et qui commence à être suffisant pour aborder l’informatique théorique (dans ce que j’ai pu voir / lire dans différents cours). A préciser que je suis plus à l’aise en algèbre que dans le reste. Avant ceci j’avais fait un DUT Informatique à Descartes, là où j’ai appris toute l’informatique pratique que je connais. En effet, à la fac je n’ai appris des nouvelles choses que d’un point de vue théorique. Maintenant vous avez un minorant de mes connaissances.

Pour aborder mes deux objectifs j’ai décidé de procéder de la manière suivante :

  • Lire et travailler le fameux livre CLRS : Introduction to Algorithms

  • Pour chaque algorithme rencontré / découvert : le coder dans différents paradigmes : Impératif (haut niveau avec Python, bas niveau avec Rust), Fonctionnel (avec Haskell)

  • Participer à un maximum de compétitions en ligne une fois que j’ai suffisamment de bases (j’aimerais au moins apprendre la programmation dynamique avant de me lancer)

Mon approche semble correcte, j’ai cependant un doute sur mon deuxième point. Mon idée en faisant cela, c’est d’avoir un point de vue global de l’algorithme avec le haut niveau, voir comment diminuer les facteurs constants avec le bas niveau et avoir une approche différente avec le fonctionnel. Sauf que ne connaissant pas du tout le fonctionnel je ne sais pas si c’est une bonne idée. Pour le choix des langages, j’ai pris Python parce que je commence à bien connaître et qu’il s’agit du langage que je préfère, les deux autres sont totalement nouveau pour moi et m’intéressent.

Enfin, on m’a conseillé d’analyser des sources et d’essayer de les améliorer (sections critiques, changements d’algos, tests couvrants…). Sauf que je n’ai pas la moindre idée d’où je pourrais trouver des sources qui me seraient utiles (si ce n’est celles que je produirais ou que j’ai déjà produit).

+0 -0

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

Il y a un livre sur le sujet que tu peux trouver en cherchant sur github, dans la liste de livres que vhf maintenait jusqu’au début de l’été. Tous les exemples sont en java et/ou C++.

backmachine

poof https://github.com/EbookFoundation/free-programming-books


Deux remarques :

Sauf que ne connaissant pas du tout le fonctionnel je ne sais pas si c’est une bonne idée. Pour le choix des langages, j’ai pris Python parce que je commence à bien connaître et qu’il s’agit du langage que je préfère, les deux autres sont totalement nouveau pour moi et m’intéressent.

Je pense que c’est trop ambitieux d’apprendre rust et haskell en même temps tout en étudiant divers algos. C’est deux langages très très différents de python, chacun ayant une learning curve très très raide comparé à python. Peut-être te concentrer sur l’algo avec python tout en apprenant la base d’un des 2 autre plutôt qu’attaquer le tout de front ?

Aussi, l’algo c’est ton goal mais tu mentionnes pas l’étude des data structures. C’est un point qui me semble vraiment central. Passe du temps à étudier ça. Dans un problème d’algo typique, le choix de la bonne data structure pour représenter ton machin a un énorme impact en terme de complexités.

Vous aimez le frontend ? Il y a un tas de petites tâches faciles si vous voulez contribuer à ZdS : https://github.com/zestedesavoir/zds-site/issues?q=is%3Aissue+is%3Aopen+label%3AC-Front

+3 -0
Auteur du sujet

Merci pour le livre !

Quand je parle d’algorithmique j’inclue les data structures. En fait c’est même ce que je préfère donc pas de risque d’oubli mais tu fais bien de ’e signaler :)

D’accord pour n’apprendre qu’un des deux. Pour le bas niveau je peux toujours faire du C ou C++ en mode débutant (pas plus que la STL quoi). Mais j’avoue que Rust m’intrigue beaucoup donc ça m’embête de le laisser. Vous pensez que le fonctionnel va m’apporter beaucoup pour l’algo et le concours ou sans plus ? Je l’apprendrais de toute manière, au moins les bases, d’ici 1 an pour avoir les bases avancées et un point de vue la global de la programmation.

+0 -0

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

Il existe des sites comme http://codeforces.com/ qui organisent des concours assez régulièrement et il me semble qu’à la fin des concours tu peux voir des solutions. Ceci est une bonne façon de s’améliorer.

En ce qui concerne le CLRS, il n’est pas si bien que ça pour travailler les algorithmes car il ne proposent pas d’implémentation. Il est plus là comme référence si tu as un doute sur un algo ou bien une structure de donnée. Par contre, quasiment tout le contenu de ce bouquin est à connaître pour espérer arriver assex loin dans des concours type Google Code Jam.

En livre à travailler, même si je ne l’ai pas lu, je conseillerai plutôt Algorithms - Sedgewick. Le site est bien fait et propos des solutions écrites en Java. Le code est super bien commenté en plus.

Enfin, concernant le langage, il ne faut pas s’en préoccuper pour le moment. Pour les concours que tu vises, le langage n’a pas d’importance. Il faut juste que tu t’en tiennes à un seul langage car un facteur clé de ces concours consiste à pouvoir écrire rapidement et sans bogue les algorithmes.

Si tu continues vers cette voie, par la suite tu pourras décider de changer de langage, mais à mon avis quand on débute, il vaut mieux choisir un langage dans lequel on est à l’aise.

Ce qui peut-être assez bénéfique pour toi, c’est si tu trouves une ou deux personnes avec lesquelles tu pourrais t’entraîner, ça aiderait aussi pour la motivation que l’on peut perdre assez rapidement.

Edit: Tu trouveras ici un recensement des sites proposant des concours type algorithmique : https://github.com/EbookFoundation/free-programming-books/blob/master/problem-sets-competitive-programming.md

Édité par Saroupille

+1 -0
Auteur du sujet

Pour CLRS, ce n’est pas non plus le but du livre et c’est même un parti pris d’être général (abordé dans l’avant-propos).

L’idée d’implémenter dans différents langages c’était plutôt pour me permettre de voir les algorithmes sous différents angles. Notamment pour voir plus en détail les optimisations possibles de bas niveau. Pour la partie compétition je me contenterais de Python. Du coup est-ce toujours une mauvaise idée avec cet objectif ci ?

+0 -0

Pour CLRS, ce n’est pas non plus le but du livre et c’est même un parti pris d’être général (abordé dans l’avant-propos).

Certes, mais du coup pour commencer je ne pense pas qu’il faille que tu commences par ce livre. Il va t’encombrer la tête des détails qui au début ne sont pas forcément nécessaires.

L’idée d’implémenter dans différents langages c’était plutôt pour me permettre de voir les algorithmes sous différents angles. Notamment pour voir plus en détail les optimisations possibles de bas niveau.

Cela n’est possible que si tu as déjà une bonne connaissance des langages et des paradigmes que tu vas utiliser. Mais ceci est à mon avis indépendant de ce que tu souhaites faire. Et encore une fois, au début, cela ne devrait pas te préoccuper.

Pour la partie compétition je me contenterais de Python. Du coup est-ce toujours une mauvaise idée avec cet objectif ci ?

Ricocotam

Code, expérimente et fais des compétition en Python si tu le souhaites. Tu te poseras la question des optimisations plus tard, sinon tu ne vas jamais t’en sortir et surtout tu vas rester à des structures élémentaires.

À mon avis, il faut que tu prennes des problèmes ou bien des algorithmes et que tu les codes avant tout, au moins au début.

+0 -0
Auteur du sujet

@Saroupille J’ai l’impression que tu pense que je suis débutant alors que pas vraiment. Je "débute" dans l’approche compétitive mais ça fait 4 ans que je code et que tout mes projets ont pour coeur des algos où je passe du temps à les améliorer. Je suis encore débutant au vu de mon expérience mais j’ai quand même des bases bien solides et un niveau qui avoisine plutôt le BAC +5 que le BAC +3 (au dire d’un professeur à moi). Ce qui me manque c’est uniquement l’aspect compétitif. De plus, j’ai envie de "m’encombrer avec des détails" comme les calculs de complexité, les preuves de fonctionnements d’algorithmes etc, simplement parce que j’aime beaucoup ça (et en plus ça m’avance sur mon Master). Les algorithmes de bases sont déjà codés et je l’ai fait plus d’une fois pour tout les algos de tri par comparaison. Mais tu as quand même raison sur le fond, juste que je ne pense pas que ça me concerne pleinement.

Edit : J’ajoute que mon objectif est d’être prêt pour la Google Code Jam suivante (en Avril 2018) et que je compte m’entraîner uniquement sur les problèmes spécifiques environ 6h par semaines, sachant qu’en même temps j’aurais 10-15h de cours de complexité et d’algorithmie (avec les structures avancées mais aussi des algorithmes "nouveau"). C’est pour ça que les détails ne m’inquiètent pas mais aussi que je me pose la question du choix du langage (changer pour du C++ par exemple ?)

@A-312 Effectivement mais pas toute. C’est pour ça que le choix du Python est aussi meilleur que passer sur Rust puisque même si Google accepte tout ce n’est pas le cas des compétitions en lignes malheureusement.

Édité par Ricocotam

+0 -0

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

@Saroupille J’ai l’impression que tu pense que je suis débutant alors que pas vraiment. Je "débute" dans l’approche compétitive mais ça fait 4 ans que je code et que tout mes projets ont pour coeur des algos où je passe du temps à les améliorer. Je suis encore débutant au vu de mon expérience mais j’ai quand même des bases bien solides et un niveau qui avoisine plutôt le BAC +5 que le BAC +3 (au dire d’un professeur à moi). Ce qui me manque c’est uniquement l’aspect compétitif. De plus, j’ai envie de "m’encombrer avec des détails" comme les calculs de complexité, les preuves de fonctionnements d’algorithmes etc, simplement parce que j’aime beaucoup ça (et en plus ça m’avance sur mon Master). Les algorithmes de bases sont déjà codés et je l’ai fait plus d’une fois pour tout les algos de tri par comparaison. Mais tu as quand même raison sur le fond, juste que je ne pense pas que ça me concerne pleinement.

Débutant ou pas débutant, je dirai la même chose. Juste pour être passé par là, ce qui m’a beaucoup manqué pour faire de la compétition était l’aisance avec le langage que j’utilisais. La seconde épreuve de Google code Jam te demande en 2h je crois de résoudre 4 problèmes. Pas seulement de trouver les algorithmes pour ces 4 problèmes, mais aussi de les implémenter. En réalité, peu de gens en font 4, et en faire 2 ou 3 assure déjà une place pour le round d’après.

Mais partons sur une base de deux problèmes. Ca veut dire en une heure, implémenter un algorithme correctement et avoir implémenter un parser pour les entrées et un printer. Alors même si en général ces deux étapes sont censées être simples, tu t’apercevras que parfois tu vas aller voir la doc car tu sais plus faire tel ou tel truc, et donc tu perds facile 5mn. Et je ne te parle pas des erreurs à déboguer…

Bref, le temps est un contrainte à ne pas négliger et seul la pratique permet de s’améliorer pour gagner du temps.

Edit : J’ajoute que mon objectif est d’être prêt pour la Google Code Jam suivante (en Avril 2018) et que je compte m’entraîner uniquement sur les problèmes spécifiques environ 6h par semaines, sachant qu’en même temps j’aurais 10-15h de cours de complexité et d’algorithmie (avec les structures avancées mais aussi des algorithmes "nouveau").

Tu peux rentrer dans les détails, mais après il faut être capable en regardant un problème de deviner la bonne structure de donnée et les algorithmes qui seront efficaces pour ce problème. Et là encore, il faut s’entraîner pour éviter de perdre du temps lors de la compétition.

Mon conseil sur mon dernier post, c’est surtout de se plonger dans la compétition dès maintenant grâce aux liens donnés plus haut. Tu engrangeras la théorie au fur et à mesure.

C’est pour ça que les détails ne m’inquiètent pas mais aussi que je me pose la question du choix du langage (changer pour du C++ par exemple ?) @A-312 Effectivement mais pas toute. C’est pour ça que le choix du Python est aussi meilleur que passer sur Rust puisque même si Google accepte tout ce n’est pas le cas des compétitions en lignes malheureusement.

Ricocotam

Si tu veux monter une équipe pour les ACM, oui il faudra se restreindre au C++. Mais ce n’est pas ce que tu mentionnes dans ton premier post. De plus, une majorité des concours en ligne autorise un grand nombre de langages tout de même. Mais encore une fois, commence à faire de la compétition avec un langage, tu verras plus tard si tu dois changer.

+2 -0

Je n’ai pas trop le temps de faire une réponse détaillée, mais en quelques mots : pose le CLRS pour le moment, va faire les 5 premiers niveaux de France-IOI pour avoir les bonnes base en algo et surtout l’expérience de chercher par toi-même (tu peux sauter les premiers niveaux si tu sais coder correctement). Dans un deuxième temps tu pourras suivre les conseils données ici (codeforces étant un bon point de départ).

Sinon y a des séances de préparation aux ACM organisées à Telecom Paris les jeudis aprem à partir de cette semaine (je peux te donner plus d’infos si t’es intéressé). Ça risque d’être un peu chaud si t’as jamais fait de concours mais ça peut se tenter.

Je n’ai pas trop le temps de faire une réponse détaillée, mais en quelques mots : pose le CLRS pour le moment, va faire les 5 premiers niveaux de France-IOI pour avoir les bonnes base en algo et surtout l’expérience de chercher par toi-même (tu peux sauter les premiers niveaux si tu sais coder correctement). Dans un deuxième temps tu pourras suivre les conseils données ici (codeforces étant un bon point de départ).

Sinon y a des séances de préparation aux ACM organisées à Telecom Paris les jeudis aprem à partir de cette semaine (je peux te donner plus d’infos si t’es intéressé). Ça risque d’être un peu chaud si t’as jamais fait de concours mais ça peut se tenter.

Lucas-84

J’en profite pour dire aussi que courant Octobre, il y aura des séances d’entrainement pour les ACM à l’ENS Cachan.

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