Mais on m’avait parlé d’un résultat, où il était montré qu’on ne pouvait pas écrire un lambda terme pour décider du min entre deux entiers $n$ et $m$ en $O(min(n,m))$.
Par contre pour le lambda-calcul, en représentant les entiers en binaire c’est possible de faire en $O(\min(\log n,\log m))$. L’article que j’ai donné ne parle que des fonctions primitives récursives justement. Est-ce que c’était autre chose ?
Tiens une question que je me suis posée il y a un peu près un an et à laquelle mon prof de math n’a pas pu me répondre et qui est donc pour moi sans réponse viens de ressurgir.
À quoi servent les puissances itérées et quelles situation représentent-elles ?
Ça a plein d’utilisations. C’est une opération algébrique tout aussi importante que l’addition … Difficile de donner une réponse globale.
Néanmoins la première chose qui me vient à l’esprit, c’est que $x^n$ sur $\mathbf C-\{0\}$, c’est un revêtement (trivial) à $n$ feuillets. Ce qui signifie intuitivement que ça permet de peindre $\mathbf C-\{0\}$ par $n$ couches de lui-même.
Quand j’ai cherché « puissance itérés » pour savoir de quoi il parlait, je suis arrivé sur ça. Si c’est effectivement ça le sujet, je ne vois pas de cas concrets, ni de situation usuelle d’application.
À part s’en servir comme défi personnel ; j’ai déjà placé gogol de manière pertinente dans une conversation.
Oui. Je préfère les noms communs comme pseudo, mais il m’en fallait un peu utilisé. Et il s’avère que je possède un beau métagabbro de la taille d’un poing (et un gros poing) trouvé lors d’une sortie géologie dans le lit d’une rivière à sec.
C’est prononçable dans plein de langues, c’est un truc en sciences, la plupart des gens ignorent ce que c’est, c’est libre presque tout le temps… Tout ce qu’il faut pour un bon pseudo !
Et il s’avère que je possède un beau métagabbro de la taille d’un poing (et un gros poing) trouvé lors d’une sortie géologie dans le lit d’une rivière à sec.
Je ne comprends pas la logique. Tu as un métagabbro et tu prends le pseudo gabbro. C’est comme si je m’appelais Moineau-croquant, c’est pas pareil.
Métagabbro, ça fait trop science, ça ne fait pas nom. De plus, ce n’est pas prononçable par un étranger et les accents ne passent pas sur tous les sites. Et c’est trop sujet aux jeux de mots (mets ta…).
Je persiste, gabbro, c’est mieux que métagabbro (comme pseudo).
Si vous voulez vraiment continuer cette discussion, je vous invite à le faire dans le bar ou le sujet idoine.
C’est utilisé en extremal combinatorics et par extension pour la théorie de Ramsay. Je travaille en ce moment sur ces théories appliquées aux hypergraphes, et la notation apparaît (souvent de manière implicite comme ici page 17)).
Non, ça veut dire qu’en se donnant une machine à mémoire infinie et un temps infini, PowerPoint est capable d’exécuter n’importe quel algo. C’est différent et nettement mois fort que ce qu’on veut souvent faire croire.
En plus d’être hors-sujet vis-à-vis du du message de @melepe, ce que tu dis est faux. Là où tu te trompes, c’est sur un point subtile qui est que la notion de Turing-complétude ne se fait pas sur des algorithmes mais sur des fonctions. Par exemple, tu pourrais imaginer un langage Turing-complet dans lequel il n’est pas possible d’écrire le quicksort (même si je n’en connais pas). Mais on m’avait parlé d’un résultat, où il était montré qu’on ne pouvait pas écrire un lambda terme pour décider du min entre deux entiers $n$ et $m$ en $O(min(n,m))$.
D’ailleurs la Turing-complétude ne traite, je crois, que des fonctions de $\mathbb{N} → \mathbb{N}$. À l’ordre supérieur les modèles de calcul que l’on connaît cessent d’être équivalents (des fonctions comme le « ou parallèle » ne sont pas implémentables en lambda-calcul alors qu’elles le sont avec les machines de Turing, par exemple).
Je crois que j’ai pas vu passer ça dans le thread alors bon, les enfants jouent avec des petites voitures, bah les adultes avec des encore plus petites.
Ca à l’air vraiment cool, je me suis inscrit, merci !
Bon par contre ils ouvrent aux gens de prépa mais font débuter pendant CCP et continuent pendant Centrale, ce qu’une grande majorité de prépas passent, c’est un peu dommage je trouve
À ce que j’ai compris, il faut voir aussi que le niveau est supérieur à celui des prépas. Et cette période est généralement la meilleure pour ceux en L3 ou M1.
Je crois que y a une équipe de chez nous (ENS) mais perso j’ai pas le temps pour ça …
Mais apparemment les sujets seront intéressants.
edit : je confirme par rapport au niveau :
Les mathématiciennes et mathématiciens français sont sollicités pour proposer des sujets accessibles au niveau master
J’avais vu ça aussi, mais du coup je me posais un peu des questions sur l’organisation comme des L1/L2/L3 peuvent aussi s’inscrire, ça veut dire qu’il leur manquerait des théorèmes qu’ils verraient en Master ?
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
!
