Intemperie

Zut.
La première est toujours valable xD

Ca marche que pour les n positifs pairs et négatifs impairs. Je pense qu'avec une couche de disjonctions de cas en plus ça doit se faire. ou pas.

kushou : Ben avec ce que j'avais griffonné, je pensais avoir trouvé, ça a duré trente secondes jusqu'à ce que je me rende compte qu'il y avait des contre-exemples =/ M'enfin une fonction informatique, mouaip, je vois pas de différence flagrante avec une fonction mathématique... En prépa on découvre assez rapidement que les fonctions genre "si x appartient à ça alors f(x)=truc, sinon f(x)=machin" sont valables en maths aussi \^\^

Rah parce que si par "fonction informatique" on sous-entend la possibilité de rajouter une variable ou utiliser des variables globales, c'est facile... Mais j'imagine que c'est pas ce qu'on cherche =/

Ou alors il peut y avoir des boucles while et des variables locales dans ladite fonction ? Parce que du coup ça ferait la différence avec une fonction mathématique et ça ouvrirait d'autres pistes de réflexion...

Si on décide d'être rigoureux, une fonction est différente d'une application. La première n'est pas forcément définie sur la totalité de son ensemble de départ, contrairement à la seconde.

Ouais, j'avais juste le doute, il y a une solution, continues de chercher :)

Alex : Mouaip, mais là c'était clairement précisé "de Z dans Z" : y'a pas d'élément exclu. Et c'est justement là le problème, j'essaie d'imaginer un axe des nombres entiers et une application géométrique qui, appliquée deux fois, donnerait pour chaque élément son opposé : ben plus je considère le problème sous un angle géométrique, et moins j'arrive à imaginer de solution =/

Donc la solution n'est possible qu'avec une fonction informatique ?? J'ai pas compris si tu disais oui ou non... ?

A ce moment-là, y'a pas une embrouille à base de pointeurs / d'adresses de variables... o_Ô ?

lun, 15/02/2010 - 23:06 — Artifère Nouveau
Si on décide d'être rigoureux, une fonction est différente d'une application. La première n'est pas forcément définie sur la totalité de son ensemble de départ, contrairement à la seconde.

D'où ma première proposition. (Mais ce n'est là qu'une astuce de vocabulaire mathématique sans intérêt.)

DeeTay : « Ou alors il peut y avoir des boucles while et des variables locales dans ladite fonction ? Parce que du coup ça ferait la différence avec une fonction mathématique et ça ouvrirait d'autres pistes de réflexion... »
→ Ah ben non, il n'y a pas de différence avec une fonction mathématique ; c'est juste plus compliqué à expliciter :)

kushou : « Ouais, j'avais juste le doute, il y a une solution, continues de chercher :) »
→ Même plusieurs :P

JJ: cf http://www.prologin.org/node/385#comment-3685

Bon, on peut toujours surcharger f...
Java :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class TrucPrologin {
    public static void main(String[] args) {
        new TrucPrologin();
    }
    TrucPrologin() {
        int n = 3;
        System.out.println(f(f(n)));
    }
    int f(long n){
        return (int)n;
    }
    long f(int n){
        return -n;
    }
}

Mais c'est un peu débile xP
(pourquoi la balise code marche pas ?)

kushou → Ben ? Dans le problème, on parle bien d'une « fonction mathématique pure » xD À moins que par « pure » vous n'entendiez : « directement exprimable en fonction de n sans disjonction de cas… »
Au fait ça marche trop mal les liens avec les ancres quand on est en page 2 ou plus…

LPTheKiller : « (pourquoi la balise code marche pas ?) »
→ Ça t'étonne ? :)

La balise code marche, mais elle laisse pas les indentations. Oui, c'est bête. Oui, tu n'as plus qu'à remplacer toute ton identation par des espaces insécables.

Toutes vos réflexions algorithmo-informatico-philosopho-mathématiques me donnent faim. Ah et sinon, j'imagine que c'est pas une priorité, mais quand est-ce qu'on aura accés aux sujets écrits sur le site ? J'avoue que je suis pas mal intéressé par celui de Lyon, du coup (j'ai jamais eu à manipuler d'arbres binaires encore).

P.S : raclures, à cause de voius je me suis pris la tête plus d'une demie-heure sur votre f(f(n)) = -n. Si je manque de sommeil, ça sera de votre faute. :(

Ah ouai vazy ils t'ont donnée quoi comme question supplémentaire les orga' alors ? °°
Moi aussi j'ai fini à l'avance, mais j'ai préféré réviser mes katakanas que de demander une question supplémentaire xD

Enfin, j'avoue que le coup des BDD c'était un peu vicieux. En même temps j'ai jamais vu ça dans ma jeunesse, et c'est un truc qui s'invente pas (ou p'têt pas en 3h en tout cas xD). T'façon le pb étant NP-Complet j'avoue que je me suis bêtement contenté d'une solution par recherche exhaustive =/

TLN : Ben, regarde quelques messages avant xD

Pikrass : Franchement, il était chaud le sujet de Lyon =/ Non seulement c'est des structures qu'on a pas vraiment l'habitude de manipuler, mais en plus certaines questions étaient embêtantes à faire puisqu'on se retrouvait plus ou moins obligé de coder des algos en O(2\^n), et quand on a pas les compétences requises pour prouver que le problème était NP-complet, c'est gênant et on perd du temps à essayer de trouver mieux (pour rien)...

Ben, regarde quelques messages avant xD

Merde, j'avais zappé qu'il y avait une nouvelle page au sujet xD
Bon fuck je lirai plus tard °°

Pikrass : « P.S : raclures, à cause de voius je me suis pris la tête plus d'une demie-heure sur votre f(f(n)) = -n. Si je manque de sommeil, ça sera de votre faute. :( »
→ demi-heure*

TLN → Pour la question 3, tu avais un algorithme polynomial ou pas ?

--
Terminator Prologin

Pour continuer sur le sujet écrit , ce que je ne comprend pas c'était que lors de la correction on a dit que "Le sujet n'était pas faisable entièrement avec un AST"

Certe avec un AST c'était loin d'être optimale , mais quand même ...

Pour continuer sur le sujet écrit , ce que je ne comprend pas c'était que lors de la correction on a dit que "Le sujet n'était pas faisable entièrement avec un AST"

Certe avec un AST c'était loin d'être optimale , mais quand même ...

TLN → Pour la question 3, tu avais un algorithme polynomial ou pas ?

Si c'était le cas j'aurai publié un papier depuis, et gagné un million d'euro en montrant que P=NP ... xD

Concernant la différence AST/Arbre/Diagramme de décision, je pense que le deuxième fait référence à des "arbres de décision". En googlant vite fait je suis tombé sur ce pdf , ça fait déjà un début d'explication =D

Ah et sinon concernant la différence entre "fonction mathématique", "fonction informatique" etc., je dirai la chose suivante :
Une fonction informatique c'est d'abord une fonction calculable. On distingue toujours fonction et application, la première n'étant pas forcément définie en tout point de l'ensemble de départ.
Il existe des fonctions mathématiques qui ne sont pas calculable (par exemple, la fonction du Castor affairé, cf. Wikipédia ou Google).

Sinon pour la fonction f : Z -> Z tel que f²(n) = -n, je pense plutôt à un truc du genre :
Si n>0 :
_ f(2n+1) = 2n+2
_ f(2n) = -2n+1
Si n_ f(-2n-1) = -2n-2
_ f(-2n) = 2n-1

TLN : « TLN → Pour la question 3, tu avais un algorithme polynomial ou pas ?
Si c'était le cas j'aurai publié un papier depuis, et gagné un million d'euro en montrant que P=NP ... xD »
→ Non parce que moi, j'en cherchais un xD Et ce qui m'inquiète, c'est que je crois que j'en ai trouvé un. C'est vrai que c'est la décision qui est NP-complet, pas l'exhibition de l'assignation des variables. Il faut que je voie pourquoi mon algorithme ne marche pas xD En fait, je trouvais ça bête de demander ça à la question 3, vu que ça donnait aussi la réponse à la question 5…