Précisions demi-finale

Quelques questions sur la demi-finale, j'aimerai savoir ce qui est autorisé :

• Pour l'épreuve écrite : Aucun document ?

• Pour l'épreuve machine :

• Documents papier :
• Pas de document ?
• Tout document autorisé ?
• Sinon, qu'est ce qui est autorisé et qu'est ce qui ne l'est pas ?
  Par exemple, ça (imprimé) : http://blog.xebia.fr/2011/02/17/java-collection-performance/ Autorisé ou pas ?
  (Bon, ça, je le connais, mais c'est juste pour avoir une idée de ce qui pourrait être autorisé)
• Sur les clés USB :
• Clés USB interdites ?
• Sont autorisés seulement les équivalents des documents papiers autorisés ?
  (Je vous autorise à ne pas répondre à cette question si aucun document papier n'est autorisé !)
• Les logiciels de développement intégré qui signalent les erreurs de syntaxe, déjà installés ? Sinon, autorisés ou considérés comme de la triche ?!
• Je suppose qu'il n'y a pas d'autres librairies installées que les librairies standards de chaque langage, peut on amener une autre librairie ?!

Bon il y a certaines questions je me doute un peu des réponses mais je voulais essayer d'être exhaustif, on sait jamais !
Question subsidiaire 1 : Y avait il un moyen trivial de connaitre toutes ces informations ? Même en lisant l'intégralité des millions de pages du forum, j'ai l'impression que certaines questions seraient restées sans réponse !

Question subsidiaire 2 : Pour les questions du type "estimer la vitesse de votre algorithme pour telles données avec telle fréquence et telle ram", on répond en fonction du nombres d'instructions par cycle ? La ram change quelque chose au résultat ? Je suppose que toutes les opérations élémentaires (comparaisons, addition, multiplication, division ?) ont le même coût.

Question subsidiaire 3 (suite de la question subsidiaire 2) : Qu'en est il dans les faits ? Connaissez vous un ordre d'idée du temps pour effectuer une multiplication par rapport à celui pour une addition ? Du temps d'un décalage toujours par rapport à l'addition ? Même chose pour la division, la comparaison, l’assignation pour les types primitifs, assignation pour les objets.

Merci d'avance pour vos réponses !

Pour l'épreuve écrite, aucun document en effet. Mais tu ne seras pas pénalisé si tu ne connais pas le nom de certaines fonctions ou de certaines structures de données, vu que tu peux utiliser du pseudo code, ou bien déclarer "je considérerais (par exemple) dernierelement(vector v) comme étant la fonction retournant le dernier élément du vector v". Donc aucun document écrit ne t'aurait été utile, sauf ceux traitant d'algorithmique, mais là, ce serait de la triche bien entendu.
Pour l'épreuve machine, c'est pareil. Une documentation est fournie pour chaque langage.
En ce qui concerne les outils de développements autorisés, si tu cherches un peu sur le forum, tu devrais trouver des topics dans lequel il est demandé aux candidats quels sont les outils que l'on aimerait pouvoir trouver lors des demi-finales. Un nouveau topic pour l'édition 2013 devrait surement être ouvert avant les premières demi-finales.
Pas d'autres libraires que les libraires standards ne sont admises il me semble. Mais pour la finale, on peut utiliser Boost en C++.

Question subsidiaire 1: Il me semble que non, si tu entends par moyen trivial un topic qui regrouperait toutes ces informations, ou un ensemble de pages d'informations répondant à toutes ces questions.

Question subsidiaire 2: Oui. Oui. Oui.

Pour faire simple, t'as le droit a rien.

T'auras une doc pour ton langage deja presente sur la machine pour l'epreuve machine et pour l'epreuve papier tu peux faire du pseudo-code donc t'en as pas besoin.

Pour ce qui est des logiciels, en gros t'as le strict minimum pour pouvoir tester ton code. Donc globalement, oui t'as de quoi reperer les erreurs de Syntax. Apres t'as peut-etre que la ligne et pas la raison mais c'est deja ca.

Pour les libs, t'as le strict minimum aussi. Genre pour OCaml, le strict minimum, c'est ce qui s'installe avec le packet ocaml. Et j'ai demande si je pouvais avoir juste les sources d'une lib de dispo (pas trop chiant a faire) et on m'a envoyer bouler...

J'ai repondu n'importe comment a la reponse sur la RAM l'an dernier et je suis alle en finale. Les dernieres questions du genre, ca compte presque pas. Il me semble que ca compte autant que la question HS sur un anime / autre chose.

Salut,
La dernière fois que j'ai fait prologin (il y a deux ans) aucun document n'était autorisé. Pour l'épreuve écrite, on teste te connaissance algorithmique, et tes compétences en architecture, du coup, T'es pas sanctionné pour les erreurs de syntaxe (le pseudo-code est autorisé et même conseiller si il peut t'aider)

Pour les logiciels installé et libs, la question avait déjà été posée sur les forums concernant la finale, du coup, si ta demi est à EPITA, c'est la même chose. Sinon, concernant les libs, la plupart des apis standard proposent les structures de donnée fondamentales ainsi que des algos célèbres. Pour tout le reste, je te déconseille, certes, ton programme marchera bien, mais la note peut baisser si tu ne fais qu'appeler des fonctions toutes faites qui ne montrent pas tes connaissances algorithmique (du moins, c'est ce qu'on nous avait dis...)
De toute façon, l'ep machine de la demi se déroule sur le serveur, dans EXACTEMENT les même condition que l'entrainement (et le QCM)

Pour les performances de l'algo, soit il est précisé le coup d'une opération élémentaire, soit on te demande juste la complexité, et presque toujours, tu peux aller en finale sans y répondre! (mais c'est classe quelqu'un qui connait le sujet.

...Prépare-toi une petite liste de nom d'algos de tri et de graphe avec leur fonctionnement global, ça peut toujours servir... je dis ça mais je dis rien... ;)

Tu as le droit d'avoir de quoi écrire, le reste est interdit.
La RAM ne change rien au résultat.
Tu peux prendre comme référence 10\^7 instructions par seconde sur une machine cadencée à 1GHz.
Si tu dois estimer le temps d'exécution de ton algorithme, restreins-toi à trouver la complexité de celui-ci puis à calculer en fonction des contraintes données.

Exemple :

pour i = 0 à n faire
pour j = 0 à n faire
[... tout plein d'instructions qui se font en temps constant (O(1))...]
fin faire
fin faire

O(n\^2)

Avec n = 10 000, tu donneras 10s.

Pour la question 3, je te laisse faire tes propres benchmarks (parce que si c'est pour faire de l'optimisation...).

>> "estimer la vitesse de votre algorithme pour telles données avec telle fréquence et telle ram"

>> Qu'en est il dans les faits ? Connaissez vous un ordre d'idée du temps pour effectuer une multiplication par rapport à celui pour une addition ? Du temps d'un décalage toujours par rapport à l'addition ? Même chose pour la division, la comparaison, l’assignation pour les types primitifs, assignation pour les objets.

Bah, c'est de toute façon quelque chose de si aléatoire, variable et peu évident, que l'on ne peut pas répondre de façon précise. Ce qu'il faut c'est évaluer la complexité de l'algorithme, considérer qu'en gros un programme en C ou en C++ fait \~1 000 000 d'opérations lentes, lourdes et complexes avec un facteur constant non négligeable, et dans le meilleur des cas jamais plus de 10 000 000 millions d'opérations, même très simples et basiques, le tout en 1s sur un processeur à 1GHz. Après t'applique des modificateurs suivant le processeur utilisé. Et tu considères toujours que le "nombre d'opérations" effectuées par ton algorithmes est la complexité de ton algorithme avec chacune des variables valant sa valeur maximale. Par exemple s'il est de complexité O(N²), avec N valant au plus 500, ça fait 500² = 250 000 opérations. Soit grosso-modo 0,25s sur un processeur à 1GHz. Considère qu'en dessous de 1 000 000 pour 1s sur un processeur à 1GHz ça ira toujours, mais qu'après faut commencer à optimiser sérieusement ton code et que c'est plutôt aléatoire. Ce que je te dit n'est pas exhaustif, mais je procède comme ça.

>> Question subsidiaire 1 : Y avait il un moyen trivial de connaitre toutes ces informations ? Même en lisant l'intégralité des millions de pages du forum, j'ai l'impression que certaines questions seraient restées sans réponse !

Je plussoie avec toi pour le reste, et tout particulièrement à ce sujet.

Je crois que tu peux considérer tout document comme interdit.

Sauf erreur de ma part, tu viens avec un stylo et à la limite du papier vierge pour brouillon.

Pour la question subsidiaire 2, je crois qu'on demande rarement ce genre de choses. Sinon tu peux faire une analyse très grossière via la complexité que tu auras calculée au préalable.

Il paraît que les facteurs sont du genre 1, 4 et 16 pour addition, multiplication et division, mais j'imagine que ça dépend de plein de trucs. Je sais que pour les concours de type ACM-ICPC, on se limite souvent à «1 000 000 d'opérations par seconde».

Question subsidiaire 3 : dans les faits, le proc tourne à une fréquence fixée, donc même s'il parvient à faire une addition en moins de temps qu'une multiplication (s'il faut moins de portes logiques cascadées), il devra attendre le prochain top d'horloge pour continuer ses calculs, donc le temps pris sera au final le même.

Ceci vaut pour les instructions de base du microprocesseur. Il peut arriver par exemple que le proc doive émuler les opérations sur les flottants (les remplacer par une séquence de plusieurs instructions de base), auquel cas il est probable qu'une multiplication de flottants prenne plus de temps qu'une addition de flottants.

Mais je ne pense pas que la question à laquelle fait référence la question subsidiaire 2 était une question sérieuse, la complexité peut à la rigueur de donner un encadrement grossier.

7 réponses similaires qui prennent du temps à leurs auteurs à cause d'un système en carton.
Boycott ?

Thomas_94, que ferions nous sans toi ?

"Thomas_94, que ferions nous sans toi ?"

...Mais pour le coup, je rejoins son avis, j'aurais fait plus court si j'avais pu lire les autres réponses

Pour les temps pour les opérations arithmétiques, Il est impossible répondre : ça dépend de l'architecture, déjà ça:
http://en.wikipedia.org/wiki/SIMD
...Et du compilateur... bref : on ne peut tout simplement pas savoir à moins de la préciser dans le sujet

D'accord, merci pour toutes ces réponses !

7 réponses similaires qui prennent du temps à leurs auteurs à cause d'un système en carton.

J'en ai également été la victime car j'ai voulu éditer pour rendre le tout plus lisible mais ce n'était plus possible !

>> ..Mais pour le coup, je rejoins son avis, j'aurais fait plus court si j'avais pu lire les autres réponses

Oh mais ce n'était pas ironique, j'étais tout à fait sérieux.